Quantum advantage test proven for shallow circuits with 99 qubits
Experimentally Testable Quantum Advantage in Shallow Circuits
Computational Complexity
Summary
Showing that quantum computers can outperform classical ones in practical tests is hard because classical methods can still sometimes do well. This paper improves how to set up tests with many players so that classical machines almost never win, even with limited resources. The authors describe a way to test quantum advantage using quick, shallow quantum circuits on about 99 qubits, making experiments more feasible. Their approach cleverly randomizes how classical answers depend on questions to limit classical strategies, while quantum strategies can win every time.
What this means in practice
- •For quantum hardware engineers: Design and verify shallow quantum circuits with around 99 qubits demonstrating clear quantum advantage experimentally.
- •For quantum software developers: Develop quantum algorithms and tests that use randomized teleportation to limit classical simulation success in shallow circuits.
Authors
Kishor Bharti, Adán Cabello
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 $γ<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 $γ^m+O(mK^D/N)$, which vanishes as $O(\log N/N)$ for $m=\lceil\log_{1/γ}N\rceil$ at fixed $D$ and $K$. We present an explicit proposal for an experimentally testable quantum advantage with 99 qubits.