检索结果-内蒙古大学图书馆

arXiv 2025年

作者： Bravyi, Sergey Gosset, David Havlicek, Vojtech Schatzki, Louis IBM Quantum IBM T.J. Watson Research Center Yorktown HeightsNY10598 United States Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo Canada Perimeter Institute for Theoretical Physics Canada University of Illinois Urbana Champaign UrbanaIL61801 United States

Characters of irreducible representations are ubiquitous in group theory. However, computing characters of some groups such as the symmetric group Sn is a challenging problem known to be #P-hard in the worst case. Here we describe a Matrix Product State (MPS) algorithm for characters of Sn. The algorithm computes an MPS encoding all irreducible characters of a given permutation. It relies on a mapping from characters of Sn to quantum spin chains proposed by Crichigno and Prakash. We also provide a simpler derivation of this mapping. We complement this result by presenting a poly(n) size quantum circuit that prepares the corresponding MPS obtaining an efficient quantum algorithm for certain sampling problems based on characters of Sn. To assess classical hardness of these problems we present a general reduction from strong simulation (computing a given probability) to weak simulation (sampling with a small error). This reduction applies to any sampling problem with a certain granularity structure and may be of independent interest. © 2025, CC BY.

关键词： Group theory

来源：评论

学校读者我要写书评

暂无评论

Generating graph states with a single quantum emitter and the minimum number of fusions

引用

Physical Review A 2025年第5期111卷 052604-052604页

作者： Matthias C. Löbl Love A. Pettersson Andrew Jena Luca Dellantonio Stefano Paesani Anders S. Sørensen Department of Combinatorics and Optimization University of Waterloo and Institute for Quantum Computing University of Waterloo Ontario Canada Department of Physics and Astronomy University of Exeter Stocker Road Exeter EX4 4QL United Kingdom NNF Quantum Computing Programme Niels Bohr Institute University of Copenhagen Blegdamsvej 17 DK-2100 Copenhagen Ø Denmark

Graph states are the key resources for measurement- and fusion-based quantum computing with photons, yet their creation is experimentally challenging. We optimize a hybrid graph-state generation scheme using a single quantum emitter and linear optics Bell-state measurements called fusions. We first generate a restricted class of states from a single quantum emitter and then apply fusions to create a target graph state, where we use a dynamic programming approach to find the construction that requires the lowest possible number of fusions. Our analysis yields a lookup table for constructing ≈2.8×107 nonisomorphic graph states with the minimum number of fusions. The lookup table covers all graph states with up to eight qubits and several other ones with up to 14 qubits. We present construction protocols of selected graph states and provide the lookup table. For large graph states that are not in the lookup table, we derive bounds for the required number of fusions using graph-theoretic properties. Finally, we use the lookup table to search for the best graph codes for loss-tolerant encodings, given a fixed number of fusions for their construction.

关键词： Qubits

来源：评论

学校读者我要写书评

暂无评论

Fault-tolerant Preparation of Distant Logical Bell Pair - with application in the magic square game

arXiv

引用

arXiv 2025年

作者： Liu, Andy Zeyi Leung, Debbie Institute for Quantum Computing University of Waterloo ONN2L 3G1 Canada Department of Combinatorics and Optimization University of Waterloo Canada Perimeter Institute of Theoretical Physics ONN2L 2Y5 Canada Yale Quantum Institute Yale University New HavenCT06511 United States Department of Applied Physics Yale University New HavenCT06511 United States

Measures of quantum nonlocal properties are traditionally defined assuming perfect and unlimited local computational ability of each remote party. In real experiments, each computational primitive will be imperfect. Fault-tolerant techniques, developed to enable simulation of arbitrarily accurate quantum computation using noisy primitives, applies only to problems with classical input and output. and need not preserve optimized measures of nonlocality. In this paper, we examine the impact of very low noise in measures of quantum nonlocality in the context of nonlocal games. We observe that, as a nonlocal game has classical inputs and outputs, fault-tolerant techniques can approximate the game value, yet, even arbitrarily small imperfection can disproportionately affect the amount of entanglement required for approximating the game value. Focusing on the fault-tolerant magic square game, we seek to optimize the tradeoff between noisy entanglement consumption and the deficit in the game value. We introduce a novel approach leveraging an interface circuit and entanglement purification protocol (EPP) to translate states between physical and logical qubits and purify noisy logical ebits. This method significantly reduces the number of initial ebits needed compared to conventional strategies. Our analytical and numerical analyses, particularly for the [[7k, 1, 3k]] concatenated Steane code, demonstrate substantial(actually, exponential) ebit savings and higher noise threshold. Analytical lower bounds for local noise threshold of 4.70 × 10−4 and initial ebit infidelity threshold of 18.3% are obtained. Our framework is adaptable to various quantum error-correcting codes (QECCs) and experimental platforms. Our protocol will not only enhance understanding of fault-tolerant nonlocal games, but also inspire further exploration of interfacing between different QECCs, promoting the development of modular quantum architectures and advancing quantum internet. © 2025, CC BY.

关键词： Concatenated codes

来源：评论

学校读者我要写书评

暂无评论

quantum Advantage from Measurement-Induced Entanglement in Random Shallow Circuits

引用

PRX quantum 2025年第1期6卷 010356-010356页

作者： Adam Bene Watts David Gosset Yinchen Liu Mehdi Soleimanifar Department of Pure Mathematics University of Waterloo Waterloo Ontario Canada N2L 3G1 Institute for Quantum Computing University of Waterloo Waterloo Ontario Canada N2L 3G1 Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario Canada N2L 3G1 Perimeter Institute for Theoretical Physics Waterloo Ontario Canada N2L 2Y5 California Institute of Technology Pasadena California 91125 USA

We study random constant-depth quantum circuits in a two-dimensional (2D) architecture. While these circuits only produce entanglement between nearby qubits on the lattice, long-range entanglement can be generated by measuring a subset of the qubits of the output state. It is conjectured that this long-range measurement-induced entanglement (MIE) proliferates when the circuit depth is at least a constant critical value d∗. For circuits composed of Haar-random two-qubit gates, it is also believed that this coincides with a quantum advantage phase transition in the classical hardness of sampling from the output distribution. Here, we provide evidence for a quantum advantage phase transition in the setting of random Clifford circuits. Our work extends the scope of recent separations between the computational power of constant-depth quantum and classical circuits, demonstrating that this kind of advantage is present in canonical random circuit sampling tasks. In particular, we show that in any architecture of random shallow Clifford circuits, the presence of long-range MIE gives rise to an unconditional quantum advantage. In contrast, any depth-d 2D quantum circuit that satisfies a short-range MIE property can be classically simulated efficiently and with depth O(d). Finally, we introduce a 2D depth-2 “coarse-grained” circuit architecture, composed of random Clifford gates acting on O(log (n)) qubits, for which we prove the existence of long-range MIE and establish an unconditional quantum advantage.

关键词： Qubits

来源：评论

学校读者我要写书评

暂无评论

A new quantum lower bound method, with applications to direct product theorems and time-space tradeoffs

A new quantum lower bound method, with applications to direc...

引用

38th Annual ACM Symposium on Theory of computing, STOC'06

作者： Ambainis, Andris Špalek, Robert De Wolf, Ronald University of Waterloo CWI Amsterdam Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo

ISBN: (纸本)1595931341

We give a new version of the adversary method for proving lower bounds on quantum query algorithms. The new method is based on analyzing the eigenspace structure of the problem at hand. We use it to prove a new and optimal strong direct product theorem for 2-sided error quantum algorithms computing k independent instances of a symmetric Boolean function: if the algorithm uses significantly less than k times the number of queries needed for one instance of the function, then its success probability is exponentially small in k. We also use the polynomial method to prove a direct product theorem for 1-sided error algorithms for k threshold functions with a stronger bound on the success probability. Finally, we present a quantum algorithm for evaluating solutions to systems of linear inequalities, and use our direct product theorems to show that the time-space tradeoff of this algorithm is close to optimal. Copyright 2006 ACM.

关键词： quantum theory

来源：评论

学校读者我要写书评

暂无评论

Theory of quantum Computation, Communication, and Cryptography 1

引用

丛书名： Lecture Notes in Computer Science

1000年

作者： Andrew Childs Michele Mosca

ISBN: (数字)9783642106989

ISBN: (纸本)9783642106972

This book constitutes the thoroughly refereed post-workshop proceedings of the 4th Workshop on Theory of quantum Computation, Communication, and Cryptography, TQC 2009, held in Waterloo, Canada, in May 2009. The 10 revised papers presented were carefully selected during two rounds of reviewing and improvement. The papers present current original research and focus on theoretical aspects of quantum computation, quantum communication, and quantum cryptography, which are part of a larger interdisciplinary field embedding information science in a quantum mechanical framework. Topics addressed are such as quantum algorithms, models of quantum computation, quantum complexity theory, simulation of quantum systems, quantum cryptography, quantum communication, quantum estimation and measurement, quantum noise, quantum coding theory, fault-tolerant quantum computing, and entanglement theory.

关键词： User Interfaces and Human Computer Interaction Programming Techniques Coding and Information Theory Theory of Computation Algorithm Analysis and Problem Complexity Computation by Abstract Devices

来源：评论

学校读者我要写书评

暂无评论

Making existential-unforgeable signatures strongly unforgeable in the quantum random-oracle model 10

Making existential-unforgeable signatures strongly unforgeab...

引用

10th Conference on the Theory of quantum Computation, Communication and Cryptography, TQC 2015

作者： Eaton, Edward Song, Fang Department of Combinatorics and Optimization University of Waterloo Waterloo Canada Institute for Quantum Computing University of Waterloo Waterloo Canada

ISBN: (纸本)9783939897965

Strongly unforgeable signature schemes provide a more stringent security guarantee than the standard existential unforgeability. It requires that not only forging a signature on a new message is hard, it is infeasible as well to produce a new signature on a message for which the adversary has seen valid signatures before. Strongly unforgeable signatures are useful both in practice and as a building block in many cryptographic constructions. This work investigates a generic transformation that compiles any existential-unforgeable scheme into a strongly unforgeable one, which was proposed by Teranishi et al. [30] and was proven in the classical random-oracle model. Our main contribution is showing that the transformation also works against quantum adversaries in the quantum random-oracle model. We develop proof techniques such as adaptively programming a quantum random-oracle in a new setting, which could be of independent interest. Applying the transformation to an existential-unforgeable signature scheme due to Cash et al. [10], which can be shown to be quantum-secure assuming certain lattice problems are hard for quantum computers, we get an efficient quantum-secure strongly unforgeable signature scheme in the quantum random-oracle model. © Edward Eaton and Fang Song.

关键词： quantum computers

来源：评论

学校读者我要写书评

暂无评论

On the Limitations of Graph Invariants Inspired by quantum Walks

引用

Electronic Notes in Discrete Mathematics 2011年 38卷 795-801页

作者： Smith, Jamie Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo Waterloo N2L 3G1 Canada

We consider two graph invariants inspired by quantum walks-one in continuous time [John King Gamble, Mark Friesen, Dong Zhou, Robert Joynt, and S. N. Coppersmith. Two-particle quantum walks applied to the graph isomorphism problem. Phys. Rev. A, (81), May 2010] and one in discrete time [David Emms, Edwin R Hancock, Simone Severini, and Richard C Wilson. A matrix representation of graphs and its spectrum as a graph invariant. arXiv:quant-ph/0505026v2, May 2005, Chris Godsil and Krystal Guo. quantum walks on regular graphs and eigenvalues. arXiv:***/1011.5460v1, Nov 2010]. We will associate a matrix algebra called a cellular algebra with every graph. We show that, if the cellular algebras of two graphs have a similar structure, then they are not distinguished by either of the proposed invariants. This has implications for the strength of these proposed invariants in relation to other known invariants, and gives rise to several interesting open problems. © 2011 Elsevier B.V.

关键词： Cellular algebras Graph isomorphism problem quantum walks

来源：评论

学校读者我要写书评

暂无评论

An efficient post-quantum one-time signature scheme 22nd

引用

22nd International Conference on Selected Areas in Cryptography, SAC 2015

作者： Kalach, Kassem Safavi-Naini, Reihaneh Department of Combinatorics and Optimization and Institute for Quantum Computing University of Waterloo WaterlooON Canada Department of Computer Science University of Calgary Calgary Canada

ISBN: (纸本)9783319313009

One-time signature (OTS) schemes are important cryptographic primitives that can be constructed using one-way functions, and provide post-quantum security. They have found diverse applications including forward security and broadcast authentication. OTS schemes are time-efficient, but their space complexity is high: the sizes of signatures and keys are linear in the message size. Regular schemes (e.g., based on discrete logarithm or factoring problems, and their variants), however, have very low space complexity but are not time-efficient. Therefore, in particular, they are not suitable for resource-constraint devices. Many widely used signature schemes are not post-quantum. In this paper, we give a signature scheme that has the advantages of the previous two approaches. It provides constant-size short signatures, and is much more time-efficient than schemes in the second approach. We prove that our scheme is post-quantum secure as long as the SVP in ideal lattices is hard in the presence of a quantum computer. We use SWIFFT: a family of provable collision-resistant functions, which have efficient implementations, comparable with that of SHA-256, hence our proposed scheme could be used on resource-constrained devices. © Springer International Publishing Switzerland 2016.

关键词： quantum computers

来源：评论

学校读者我要写书评

暂无评论

Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields 27

Efficient quantum algorithms for computing class groups and ...

引用

27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016

作者： Biasse, Jean-François Song, Fang Department of Mathematics and Statistics University of South Florida United States Department of Combinatorics Optimization and Institute for Quantum Computing University of Waterloo Canada

ISBN: (纸本)9781510819672

This paper gives polynomial time quantum algorithms for computing the ideal class group (CGP) under the Generalized Riemann Hypothesis and solving the principal ideal problem (PIP) in number fields of arbitrary degree. These are are fundamental problems in number theory and they are connected to many unproven conjectures in both analytic and algebraic number theory. Previously the best known algorithms by Hallgren [20] only allowed to solve these problems in quantum polynomial time for number fields of constant degree. In a recent breakthrough, Eisentrager et al. [11] showed how to compute the unit group in arbitrary fields, thus opening the way to the resolution of CGP and PIP in the general case. For example, Biasse and Song [3] pointed out how to directly apply this result to solve PIP in classes of cyclotomic fields of arbitrary degree. The methods we introduce in this paper run in quantum polynomial time in arbitrary classes of number fields. They can be applied to solve other problems in computational number theory as well including computing the ray class group and solving relative norm equations. They are also useful for ongoing cryptanalysis of cryptographic schemes based on ideal lattices [5, 10]. Our algorithms generalize the quantum algorithm for computing the (ordinary) unit group [11]. We first show that CGP and PIP reduce naturally to the computation of S-unit groups, which is another fundamental problem in number theory. Then we show an efficient quantum reduction from computing 5-units to the continuous hidden subgroup problem introduced in [11]. This step is our main technical contribution, which involves careful analysis of the metrical properties of lattices to prove the correctness of the reduction. In addition, we show how to convert the output into an exact compact representation, which is convenient for further algebraic manipulations.

关键词： Number theory

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：