Correlations decide a shallow-circuit advantage
Abstract
Quantum computers are claimed to produce samples ordinary classical computers cannot reproduce. The sharpest such claim known pits constant-depth quantum circuits, given one entangled state per run, against shallow classical circuits of few-input gates and limited randomness. No efficient test was known that certifies such a claim from classical samples alone. Here we show that what such a test must read is decided by the classical class's pattern of single-bit and pair correlations, not by a distance. The test rests on one inequality: any machine producing the samples sits no further from the target than the fraction it mislabels plus the deviation of its string half, the bits beyond the label, from uniform. A collapse theorem, machine-checked in the Lean~4 proof assistant, confines that second term, one setting of the sampler's random input bits at a time. Four natural checks provably fail; a fifth, reading those same correlations, catches a far-from-target construction they cannot reach, and is exact on the class of few-input gates. The label test is proven and sample-optimal in its own tolerance up to a logarithmic factor; the fifth check is sound, not only effective, on the bounded pinned-residue class, pairwise-uniform samplers whose residue, the string's weight modulo the prime, is pinned by few seeds and whose seed sharing is bounded. What binds an experiment is the $43$-qubit entangled resource state at fidelity near $0.99$, not the readout. What remains are two named open problems; a positive answer to the first would extend the guarantee to the full class.
Related
- Experimentally Testable Quantum Advantage in Shallow Circuits
- Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D
- Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation
- On-chip reconfigurable two-mode Gaussian correlations in a Si₃N₄photonic circuit
- A Single Fixed Shallow Circuit for Classical Shadows of Arbitrary n-Qubit States
BibTeX
@misc{gong2026correlations,
title = {{Correlations decide a shallow-circuit advantage}},
author = {Zijian Gong and Zhaobin Lyu and Jingjing Hu and Dengfeng Li and Shuoming An},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04666},
eprint = {2610.04666},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04666},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Correlations decide a shallow-circuit advantage
AU - Zijian Gong
AU - Zhaobin Lyu
AU - Jingjing Hu
AU - Dengfeng Li
AU - Shuoming An
PY - 2026
DA - 2026/10/03
PB - arXiv
DO - 10.48550/arxiv.2610.04666
UR - https://arxiv.org/abs/2610.04666
AB - Quantum computers are claimed to produce samples ordinary classical computers cannot reproduce. The sharpest such claim known pits constant-depth quantum circuits, given one entangled state per run, against shallow classical circuits of few-input gates and limited randomness. No efficient test was known that certifies such a claim from classical samples alone. Here we show that what such a test must read is decided by the classical class's pattern of single-bit and pair correlations, not by a distance. The test rests on one inequality: any machine producing the samples sits no further from the target than the fraction it mislabels plus the deviation of its string half, the bits beyond the label, from uniform. A collapse theorem, machine-checked in the Lean~4 proof assistant, confines that second term, one setting of the sampler's random input bits at a time. Four natural checks provably fail; a fifth, reading those same correlations, catches a far-from-target construction they cannot reach, and is exact on the class of few-input gates. The label test is proven and sample-optimal in its own tolerance up to a logarithmic factor; the fifth check is sound, not only effective, on the bounded pinned-residue class, pairwise-uniform samplers whose residue, the string's weight modulo the prime, is pinned by few seeds and whose seed sharing is bounded. What binds an experiment is the $43$-qubit entangled resource state at fidelity near $0.99$, not the readout. What remains are two named open problems; a positive answer to the first would extend the guarantee to the full class.
ER -