Experimentally Testable Quantum Advantage in Shallow Circuits
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 KD 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(mKD/N), which vanishes as O(log N/N) for m=⌈log1/γN⌉ at fixed D and K. We present an explicit proposal for an experimentally testable quantum advantage with 99 qubits.
Related
- Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D
- Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits
- Classical Pre-Training of Large Shallow Parametrized Quantum Circuits through Pauli Propagation and deployment on Quantum Hardware
- Shadow Quantum Singular Value Transformation with Shallow Quantum Circuits
- Distilling Datasets into Shallow Circuits for Quantum Machine Learning
BibTeX
@misc{bharti2026experimentally,
title = {{Experimentally Testable Quantum Advantage in Shallow Circuits}},
author = {Kishor Bharti and Adán Cabello},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.38775},
eprint = {2609.38775},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38775},
}
RIS
TY - UNPB
TI - Experimentally Testable Quantum Advantage in Shallow Circuits
AU - Kishor Bharti
AU - Adán Cabello
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.38775
UR - https://arxiv.org/abs/2609.38775
AB - 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=⌈log_1/γN⌉ at fixed D and K. We present an explicit proposal for an experimentally testable quantum advantage with 99 qubits.
ER -