Experimentally Testable Quantum Advantage in Shallow Circuits

arXiv:2609.38775v1 Announce Type: new Abstract: Experimental tests of shallow-circuit quantum advantage require explicit classical bounds at finite circuit sizes. We refine the finite-size classical soundness bound of Aasnaess's graph-distributed construction to depend linearly on the number of players. Combined with standard disjoint-player repetition, this gives a two-round test on a single processor for any finite nonlocal game with a finite-dimensional perfect quantum strategy and classical winning probability $\gamma<1$, with arbitrarily small classical success. The method is based on playing $m$ copies with disjoint players and teleporting each player's register to a uniformly random one of $N$ sites before the questions are revealed. Each answer bit of a depth-$D$, fan-in-$K$ classical response with fixed wiring depends on at most $K^D$ question wires, making cross-player dependencies unlikely when $N$ is large. The quantum implementation has constant depth per round and wins with certainty. A classical device wins with probability at most $\gamma^m+O(mK^D/N)$, which vanishes as $O(\log N/N)$ for $m=\lceil\log_{1/\gamma}N\rceil$ at fixed $D$ and $K$. We present an explicit proposal for an experimentally testable quantum advantage with 99 qubits.

Abstract:Experimental tests of shallow-circuit quantum advantage require explicit classical bounds at finite circuit sizes. We refine the finite-size classical soundness bound of Aasnaess's graph-distributed construction to depend linearly on the number of players. Combined with standard disjoint-player repetition, this gives a two-round test on a single processor for any finite nonlocal game with a finite-dimensional perfect quantum strategy and classical winning probability $\gamma<1$, with arbitrarily small classical success. The method is based on playing $m$ copies with disjoint players and teleporting each player's register to a uniformly random one of $N$ sites before the questions are revealed. Each answer bit of a depth-$D$, fan-in-$K$ classical response with fixed wiring depends on at most $K^D$ question wires, making cross-player dependencies unlikely when $N$ is large. The quantum implementation has constant depth per round and wins with certainty. A classical device wins with probability at most $\gamma^m+O(mK^D/N)$, which vanishes as $O(\log N/N)$ for $m=\lceil\log_{1/\gamma}N\rceil$ at fixed $D$ and $K$. We present an explicit proposal for an experimentally testable quantum advantage with 99 qubits.

Quantum Physics (quant-ph); Computational Complexity (cs.CC)

arXiv:2609.38775 [quant-ph]

(or arXiv:2609.38775v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2609.38775 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

analiza aiqbench

Experimentally Testable Quantum Advantage in Shallow Circuits

Subiecte conexe