Unconditional quantum magic advantage in shallow circuit computation
arXiv:2402.12246 · doi:10.1038/s41467-024-54864-0
Abstract
Quantum theory promises computational speed-ups over classical approaches. The celebrated Gottesman-Knill Theorem implies that the full power of quantum computation resides in the specific resource of "magic" states -- the secret sauce to establish universal quantum computation. However, it is still questionable whether magic indeed brings the believed quantum advantage, ridding unproven complexity assumptions or black-box oracles. In this work, we demonstrate the first unconditional magic advantage: a separation between the power of generic constant-depth or shallow quantum circuits and magic-free counterparts. For this purpose, we link the shallow circuit computation with the strongest form of quantum nonlocality -- quantum pseudo-telepathy, where distant non-communicating observers generate perfectly synchronous statistics. We prove quantum magic is indispensable for such correlated statistics in a specific nonlocal game inspired by the linear binary constraint system. Then, we translate generating quantum pseudo-telepathy into computational tasks, where magic is necessary for a shallow circuit to meet the target. As a by-product, we provide an efficient algorithm to solve a general linear binary constraint system over the Pauli group, in contrast to the broad undecidability in constraint systems. We anticipate our results will enlighten the final establishment of the unconditional advantage of universal quantum computation.
35 pages, 7 figures, 3 tables. In version 1, there was a bug in the analysis of the lower bound on the Clifford circuit depth; this version provides alternative constructions that bypass the issue
References in corpus (30)
- Quantum entanglement
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Experimental loophole-free violation of a Bell inequality using entangled electron spins separated by 1.3 km
- Bell nonlocality
- Measurement-based quantum computation with cluster states
- Improved Simulation of Stabilizer Circuits
- Universal Quantum Computation with ideal Clifford gates and noisy ancillas
- Strong quantum computational advantage using a superconducting quantum processor
- Logical quantum processor based on reconfigurable atom arrays
- The Resource Theory of Stabilizer Computation
- Real-time quantum error correction beyond break-even
- Quantum advantage with shallow circuits
- Application of a resource theory for magic states to fault-tolerant quantum computing
- Self-testing of quantum systems: a review
- Simulation of quantum circuits by low-rank stabilizer decompositions
- Beating the break-even point with a discrete-variable-encoded logical qubit
- Quantum Pseudo-Telepathy
- Quantum advantage with noisy shallow circuits in 3D
- Classicality in discrete Wigner functions
- Quantifying the magic of quantum channels
- Quantifying quantum speedups: improved classical simulation from tighter magic monotones
- Quantifying magic for multi-qubit operations
- Quantum Circuits with Unbounded Fan-out
- Tsirelson's problem and an embedding theorem for groups arising from non-local games
- Perfect Commuting-Operator Strategies for Linear System Games
- Modeling Pauli measurements on graph states with nearest-neighbor classical communication
- A weak form of self-testing
- Magic of quantum hypergraph states
- Irreducible magic sets for -qubit systems
- An operator-algebraic formulation of self-testing