aiqbench analysis
This paper establishes an unconditional separation between constant-depth quantum circuits and bounded fan-in classical circuits specifically for input-independent sampling tasks, resolving a key question posed by Bravyi, Gosset, and Koenig. The authors demonstrate that even with access to random inputs, shallow quantum architectures can generate distributions inaccessible to equivalent classical depth constraints without requiring exponential resources or unproven complexity assumptions. This theoretical advance strengthens the foundational argument for practical advantages in near-term sampling applications within constant-depth regimes.
Unconditional Quantum Advantage for Sampling with Shallow Circuits
arXiv:2301.00995v5 Announce Type: replace Abstract: Recent work by Bravyi, Gosset, and Koenig showed that there exists a search problem that a constant-depth quantum circuit can solve, but that any constant-depth classical circuit with bounded fan-in cannot. They also pose the question: Can we achieve a similar proof of separation for an input-independent sampling task? In this paper, we show that the answer to this question is yes when the number of random input bits given to the classical circuit is bounded. We introduce a distribution $D_{n}$ over $\{0,1\}^n$ and construct a constant-depth uniform quantum circuit family $\{C_n\}_n$ such that $C_n$ samples from a distribution close to $D_{n}$ in total variation distance. For any $\delta < 1$ we also prove, unconditionally, that any classical circuit with bounded fan-in gates that takes as input $kn + n^\delta$ i.i.d. Bernouli random variables with entropy $1/k$ and produces output close to $D_{n}$ in total variation distance has depth $\Omega(\log \log n)$. This gives an unconditional proof that constant-depth quantum circuits can sample from distributions that can't be reproduced by constant-depth bounded fan-in classical circuits, even up to additive error. We also show a similar separation between constant-depth quantum circuits with advice and classical circuits with bounded fan-in and fan-out, but access to an unbounded number of i.i.d random inputs. The distribution $D_n$ and classical circuit lower bounds are inspired by work of Viola, in which he shows a different (but related) distribution cannot be sampled from approximately by constant-depth bounded fan-in classical circuits.
Abstract:Recent work by Bravyi, Gosset, and Koenig showed that there exists a search problem that a constant-depth quantum circuit can solve, but that any constant-depth classical circuit with bounded fan-in cannot. They also pose the question: Can we achieve a similar proof of separation for an input-independent sampling task? In this paper, we show that the answer to this question is yes when the number of random input bits given to the classical circuit is bounded. We introduce a distribution $D_{n}$ over $\{0,1\}^n$ and construct a constant-depth uniform quantum circuit family $\{C_n\}_n$ such that $C_n$ samples from a distribution close to $D_{n}$ in total variation distance. For any $\delta < 1$ we also prove, unconditionally, that any classical circuit with bounded fan-in gates that takes as input $kn + n^\delta$ i.i.d. Bernouli random variables with entropy $1/k$ and produces output close to $D_{n}$ in total variation distance has depth $\Omega(\log \log n)$. This gives an unconditional proof that constant-depth quantum circuits can sample from distributions that can't be reproduced by constant-depth bounded fan-in classical circuits, even up to additive error. We also show a similar separation between constant-depth quantum circuits with advice and classical circuits with bounded fan-in and fan-out, but access to an unbounded number of i.i.d random inputs. The distribution $D_n$ and classical circuit lower bounds are inspired by work of Viola, in which he shows a different (but related) distribution cannot be sampled from approximately by constant-depth bounded fan-in classical circuits.
54 pages, 12 figures. The new version improves the result with proofs in the appendices, and includes a new proof overview in the introduction, accepted to Quantum journal December 2025, published 2026
Quantum Physics (quant-ph); Computational Complexity (cs.CC)
arXiv:2301.00995 [quant-ph]
(or arXiv:2301.00995v5 [quant-ph] for this version)
Full text under the publisher's open licence · 290 words
Related coverage
Unconditional Quantum Advantage for Sampling with Shallow Circuits
Quantum Journal · Aug 12, 2026
New proof shows quantum advantage with shallow circuits
Quantum Zeitgeist · Aug 31, 2026
Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D
arXiv · Oct 1, 2026
Quantum Machine-Learning Design Targets Training And Scaling Barriers
The Quantum Insider · Jul 28, 2026