Quantum advantage through the magic pentagram problem

Abstract

Through the two specific problems, the 2D hidden linear function problem and the 1D magic square problem, Bravyi et al. have recently shown that there exists a separation between $\mathbf{QN}{\mathbf{C}}^0$ and $\mathbf{N}{\mathbf{C}}^0$, where $\mathbf{QN}{\mathbf{C}}^0$ and $\mathbf{N}{\mathbf{C}}^0$ are the classes of polynomial-size and constant-depth quantum and classical circuits with bounded fan-in gates, respectively. In this paper, we present another problem with the same property, the magic pentagram problem based on the magic pentagram game, which is a nonlocal game. In other words, we show that the problem can be solved with certainty by a $\mathbf{QN}{\mathbf{C}}^0$ circuit but not by any $\mathbf{N}{\mathbf{C}}^0$ circuits.

arXiv comment10 pages, 5 figures

References in corpus (7)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Hidden Variables and the Two Theorems of John Bell
• Quantum advantage with shallow circuits
• Quantum Pseudo-Telepathy
• Quantum advantage with noisy shallow circuits in 3D
• Device-independent parallel self-testing of two singlets
• Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits