[2024-07-05 Xingjian Zhang]

Quantum theory promises computational speed-ups than classical means. 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 our recent work (arXiv: 2402.12246), we demonstrate the first unconditional magic advantage: a separation between the power of generic constant-depth quantum circuits and magic-free counterparts. For this purpose, we link the computational problem 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 to generate such correlated statistics in a specific nonlocal game inspired by the linear binary constraint system. Then, we translate generating quantum pseudo-telepathy correlations into a relation problem, where magic is necessary for a constant-depth circuit to solve it perfectly. In my talk, I plan to explain the connection between constant-depth (namely “shallow”) circuit computation and quantum nonlocality and discuss how quantum “magic” defines “fine structures” within the two notions. On the technical part, I plan to present an efficient algorithm to solve a general linear binary constraint system over the Pauli group --- a tool to exclude magic-free nonlocality. I hope our results will enlighten the final establishment of the unconditional advantage of universal quantum computation.