Unconditional quantum MAGIC advantage in shallow circuit computation

• DOI: 10.48550/arxiv.2402.12246
• Publication Date: 2024-02-19
• Authors: Xingjian Zhang; Zhaokai Pan; Guoding Liu
• Keywords: Quantum Physics; Science; Q; FOS: Physical sciences; Quantum Physics (quant-ph); Article

Quantum theory promises computation speed-ups than classical means. The full power is believed to reside in "magic" states, or equivalently non-Clifford operations -- the secret sauce establish universal quantum computing. Despite celebrated Gottesman-Knill Theorem stating that magic-free can be efficiently simulated by a computer, it still questionable whether really magical. Indeed, all existing results its supremacy for efficient upon unproven complexity assumptions queries black-box oracles. In this work, we show magic advantage unconditionally established, at least shallow circuit with constant depth. For purpose, first construct specific nonlocal game inspired linear binary constraint system, which requires resource generate desired statistics "pseudo telepathy." relation problem targeting generating such correlations between arbitrary sites, bounded fan-in gates takes strategy pseudo telepathy as sub-routine solve certainty. contrast, counterparts inevitably require logarithmic depth input size, and separation proven optimal. As by-products, prove has non-unique perfect winning strategies, answering an open self-testing. We also provide algorithm aid search potential magic-requiring games similar current one. anticipate our enlighten ultimate establishment of unconditional computation.