Unconditional Quantum Advantage for Sampling with Shallow Circuits
1Institute for Quantum Computing, University of Waterloo, Canada
2Department of Computer Science, Columbia University
3Perimeter Institute for Theoretical Physics, Canada
| Published: | 2026-08-12, volume 10, page 2188 |
| Editor: | Alexander Dalzell |
| Eprint: | arXiv:2301.00995v5 |
| Doi: | https://doi.org/10.22331/q-2026-08-12-2188 |
| Citation: | Quantum 10, 2188 (2026). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
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 \lt 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.
Popular summary
► BibTeX data
► References
[1] Peter W Shor. ``Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer''. SIAM review 41, 303–332 (1999).
https://doi.org/10.1137/S0036144598347011
[2] Iulia Georgescu. ``How the Bell tests changed quantum physics''. Nature Reviews Physics 3, 674–676 (2021).
https://doi.org/10.1038/s42254-021-00365-8
[3] John Watrous. ``Quantum computational complexity''. Pages 7174–7201. Springer New York. New York, NY (2009).
https://doi.org/10.1007/978-0-387-30440-3_428
[4] Scott Aaronson. ``Quantum computing, postselection, and probabilistic polynomial-time''. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 461, 3473–3482 (2005).
https://doi.org/10.1098/rspa.2005.1546
[5] Barbara M. Terhal and David P. DiVincenzo. ``Adaptive quantum computation, constant depth quantum circuits and arthur-merlin games''. Quantum Information and Computation 4, 134–145 (2004). arXiv:quant-ph/0205133.
https://doi.org/10.26421/QIC4.2-5
arXiv:quant-ph/0205133
[6] Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. ``On the complexity and verification of quantum random circuit sampling''. Nature Physics 15, 159–163 (2019).
https://doi.org/10.1038/s41567-018-0318-2
[7] Scott Aaronson and Lijie Chen. ``Complexity-theoretic foundations of quantum supremacy experiments''. In 32nd Computational Complexity Conference (CCC 2017). Volume 79 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1–22:67. Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2017).
https://doi.org/10.4230/LIPIcs.CCC.2017.22
[8] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis, and Hartmut Neven. ``Characterizing quantum supremacy in near-term devices''. Nature Physics 14, 595–600 (2018).
https://doi.org/10.1038/s41567-018-0124-x
[9] Aram W Harrow and Ashley Montanaro. ``Quantum computational supremacy''. Nature 549, 203–209 (2017).
https://doi.org/10.1038/nature23458
[10] John Preskill. ``Quantum computing in the NISQ era and beyond''. Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79
[11] Sergey Bravyi, David Gosset, and Robert König. ``Quantum advantage with shallow circuits''. Science 362, 308–311 (2018).
https://doi.org/10.1126/science.aar3106
[12] Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal. ``Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits''. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Pages 515–526. (2019).
https://doi.org/10.1145/3313276.3316404
[13] Daniel Grier and Luke Schaeffer. ``Interactive shallow Clifford circuits: Quantum advantage against NC$^1$ and beyond''. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Pages 875–888. (2020).
https://doi.org/10.1145/3357713.3384332
[14] Sergey Bravyi, David Gosset, Robert Koenig, and Marco Tomamichel. ``Quantum advantage with noisy shallow circuits''. Nature Physics 16, 1040–1045 (2020).
https://doi.org/10.1038/s41567-020-0948-z
[15] Scott Aaronson. ``The complexity of quantum states and transformations: From quantum money to black holes'' (2016). arXiv:1607.05256.
arXiv:1607.05256
[16] Anurag Anshu, Nikolas Breuckmann, and Chinmay Nirkhe. ``NLTS hamiltonians from good quantum codes''. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing. Pages 1090–1096. Association for Computing Machinery (2023).
https://doi.org/10.1145/3564246.3585114
[17] Dorit Aharonov and Tomer Naveh. ``Quantum NP-a survey'' (2002).
[18] Johan Torkel Håstad. ``Computational limitations for small-depth circuits''. MIT press. (1987). url: https://mitpress.mit.edu/9780262081672/computational-limitations-for-small-depth-circuits/.
https://mitpress.mit.edu/9780262081672/computational-limitations-for-small-depth-circuits/
[19] Alexander A Razborov. ``Lower bounds on the size of bounded depth circuits over a complete basis with logical addition''. Mathematical Notes of the Academy of Sciences of the USSR 41, 333–338 (1987).
https://doi.org/10.1007/BF01137685
[20] Roman Smolensky. ``Algebraic methods in the theory of lower bounds for boolean circuit complexity''. In Proceedings of the nineteenth annual ACM symposium on Theory of computing. Pages 77–82. (1987).
https://doi.org/10.1145/28395.28404
[21] Emanuele Viola. ``The complexity of distributions''. SIAM Journal on Computing 41, 191–218 (2012).
https://doi.org/10.1137/100814998
[22] Emanuele Viola. ``Extractors for circuit sources''. SIAM Journal on Computing 43, 655–672 (2014).
https://doi.org/10.1137/11085983X
[23] Daniel M Kane, Anthony Ostuni, and Kewen Wu. ``Locality bounds for sampling hamming slices''. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing. Pages 1279–1286. Association for Computing Machinery (2024).
https://doi.org/10.1145/3618260.3649670
[24] Richard Cleve and John Watrous. ``Fast parallel circuits for the quantum Fourier transform''. In Proceedings 41st Annual Symposium on Foundations of Computer Science. Pages 526–536. IEEE (2000).
https://doi.org/10.1109/SFCS.2000.892140
[25] Peter Høyer and Robert Špalek. ``Quantum fan-out is powerful''. Theory of computing 1, 81–103 (2005).
https://doi.org/10.4086/toc.2005.v001a005
[26] Dan Browne, Elham Kashefi, and Simon Perdrix. ``Computational depth complexity of measurement-based quantum computation''. In Conference on Quantum Computation, Communication, and Cryptography. Pages 35–46. Springer (2010).
https://doi.org/10.1007/978-3-642-18073-6_4
[27] Frederic Green, Steven Homer, Cristopher Moore, and Christopher Pollett. ``Counting, fanout, and the complexity of quantum ACC''. Quantum Information and Computation 2, 35–65 (2002).
https://doi.org/10.26421/QIC2.1-3
[28] Michael Reck, Anton Zeilinger, Herbert J Bernstein, and Philip Bertani. ``Experimental realization of any discrete unitary operator''. Physical review letters 73, 58 (1994).
https://doi.org/10.1103/PhysRevLett.73.58
[29] Adriano Barenco, Charles H Bennett, Richard Cleve, David P DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A Smolin, and Harald Weinfurter. ``Elementary gates for quantum computation''. Physical review A 52, 3457 (1995).
https://doi.org/10.1103/PhysRevA.52.3457
[30] Andrej Bogdanov and Emanuele Viola. ``Pseudorandom bits for polynomials''. SIAM Journal on Computing 39, 2464–2486 (2010).
https://doi.org/10.1137/070712109
[31] Shachar Lovett, Omer Reingold, Luca Trevisan, and Salil Vadhan. ``Pseudorandom bit generators that fool modular sums''. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings. Pages 615–630. Springer (2009).
https://doi.org/10.1007/978-3-642-03685-9_46
Cited by
[1] Michael de Oliveira, Sathyawageeswar Subramanian, Leandro Mendes, and Min-Hsiu Hsieh, "Unconditional advantage of noisy qudit quantum circuits over biased threshold circuits in constant depth", Nature Communications 16 1, 3559 (2025).
[2] Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag Anshu, Zeph Landau, and Jarrod R. McClean, "Learning shallow quantum circuits", arXiv:2401.10095, (2024).
[3] Alex Bredariol Grilo, Elham Kashefi, Damian Markham, and Michael de Oliveira, "The Power of Shallow-depth Toffoli and Qudit Quantum Circuits", arXiv:2404.18104, (2024).
[4] Jonathan Allcock, Jinge Bao, Joao F. Doriguello, Alessandro Luongo, and Miklos Santha, "Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates", Quantum 8, 1530 (2024).
[5] Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, and Li-Yang Tan, "The power of quantum circuits in sampling", arXiv:2510.03645, (2025).
[6] Qisheng Wang and Zhicheng Zhang, "Tight quantum depth lower bound for solving systems of linear equations", Physical Review A 110 1, 012422 (2024).
[7] Libor Caha, Xavier Coiteux-Roy, and Robert Koenig, "Single-qubit gate teleportation provides a quantum advantage", Quantum 8, 1548 (2024).
[8] Daniel M. Kane, Anthony Ostuni, and Kewen Wu, "Locally Sampleable Uniform Symmetric Distributions", arXiv:2411.08183, (2024).
[9] Zhihan Zhang, Weiyuan Gong, Weikang Li, and Dong-Ling Deng, "Quantum-classical separations in shallow-circuit-based learning with and without noises", Communications Physics 7 1, 290 (2024).
[10] Francisca Vasconcelos and Hsin-Yuan Huang, "Learning shallow quantum circuits with many-qubit gates", arXiv:2410.16693, (2024).
[11] Niels M. P. Neumann, "Adaptive Quantum Computers: decoding and state preparation", arXiv:2509.08718, (2025).
[12] N. Pirnay, S. Jerbi, J.-P. Seifert, and J. Eisert, "An unconditional distribution learning advantage with shallow quantum circuits", arXiv:2411.15548, (2024).
[13] Joseph Carolan, Amin Shiraz Gilani, and Mahathi Vempati, "Quantum advantage and lower bounds in parallel query complexity", arXiv:2410.02665, (2024).
[14] Sabee Grewal and Vinayak M. Kumar, "Improved Circuit Lower Bounds and Quantum-Classical Separations", arXiv:2408.16406, (2024).
[15] Adam Wills and Sergii Strelchuk, "Generalised Coupling and An Elementary Algorithm for the Quantum Schur Transform", arXiv:2305.04069, (2023).
[16] Joseph Slote, "Parity vs. AC0 with simple quantum preprocessing", arXiv:2311.13679, (2023).
[17] Daniel M. Kane, Anthony Ostuni, and Kewen Wu, "Locality Bounds for Sampling Hamming Slices", arXiv:2402.14278, (2024).
[18] Yangjing Dong, Fengning Ou, and Penghui Yao, "Linear-Size QAC0 Channels: Learning, Testing and Hardness", arXiv:2510.00593, (2025).
[19] Jop Briët, Harry Buhrman, Davi Castro-Silva, and Niels M. P. Neumann, "Noisy decoding by shallow circuits with parities: classical and quantum", arXiv:2302.02870, (2023).
[20] Daniel Grier, Jackson Morris, and Kewen Wu, "$\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)", arXiv:2601.03243, (2026).
[21] Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, Artur Riazanov, and Dmitry Sokolov, "Sampling Permutations with Cell Probes is Hard", arXiv:2512.02724, (2025).
[22] Daniel M. Kane, Anthony Ostuni, and Kewen Wu, "Symmetric Distributions from Shallow Circuits", arXiv:2511.14127, (2025).
The above citations are from SAO/NASA ADS (last updated successfully 2026-09-07 13:11:29). The list may be incomplete as not all publishers provide suitable and complete citation data.
On Crossref's cited-by service no data on citing works was found (last attempt 2026-09-07 13:11:28).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.