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

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

作者： Robbie King David Gosset Robin Kothari Ryan Babbush Google Quantum AI Venice California USA California Institute of Technology Pasadena California USA IQC and Department of Combinatorics and Optimization University of Waterloo Canada Perimeter Institute for Theoretical Physics Waterloo Canada

We investigate the problem of efficiently estimating expectation values of large sets of observables from copies of an unknown many-body quantum state. This task, known as shadow tomography, is crucial for quantum simulation and quantum chemistry, where the relevant observables often include k-body fermionic or k-local Pauli operators. A key goal is to achieve sample efficiency, computational efficiency, and few-copy measurements. We introduce the notion of triply efficient shadow tomography to formalize these requirements. Prior work has shown that single-copy measurements suffice for k-local Pauli operators with constant k. However, we prove that for k-body fermionic observables and the full set of n-qubit Pauli operators, single-copy protocols fail to achieve sample-efficient tomography. We then present new protocols based on measuring two copies of the state at a time that overcome these lower bounds, providing a triply efficient protocol.

关键词： Tomography

来源：评论

学校读者我要写书评

暂无评论

PCP-free APX-Hardness of Nearest Codeword and Minimum Distance

arXiv

引用

arXiv 2025年

作者： Bhattiprolu, Vijay Guruswami, Venkatesan Ren, Xuandi Department of Combinatorics & Optimization University of Waterloo Canada Simons Institute for the Theory of Computing Departments of EECS and Mathematics UC Berkeley United States Department of EECS UC Berkeley United States

We give simple deterministic reductions demonstrating the NP-hardness of approximating the nearest codeword problem and minimum distance problem within arbitrary constant factors (and almost-polynomial factors assuming NP cannot be solved in quasipolynomial time). The starting point is a simple NP-hardness result without a gap, and is thus "PCP-free." Our approach is inspired by that of Bhattiprolu and Lee [BL24] who give a PCP-free randomized reduction for similar problems over the integers and the reals. We leverage the existence of Ε-balanced codes to derandomize and further simplify their reduction for the case of finite fields. © 2025, CC BY.

关键词： NP-hard

来源：评论

学校读者我要写书评

暂无评论

Classical and quantum algorithms for characters of the symmetric group

arXiv

引用

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：