Unconditional quantum magic advantage in shallow circuit computation.

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 p

SUBMITTER: Zhang X 

PROVIDER: S-EPMC11615043 | biostudies-literature | 2024 Dec

REPOSITORIES: biostudies-literature