quantum-computing

Unconditional Quantum Advantage for Sampling with Shallow Circuits

Adam Bene Watts and Natalie Parham

18 min read

0 likes

⚡ Quantum Brief

AI Audio Summary

0:00 / 0:00

Click to play

Quantum News · Media Library

Understand this faster with AI

Ask ChatGPT

Research with Perplexity

Explain with Claude

Discuss on Grok

AbstractRecent 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 summaryIn this work, we show that constant-depth quantum circuits can sample from certain probability distributions that comparable constant-depth classical circuits cannot reproduce, even approximately. Here, constant depth means that the number of computational steps remains fixed, even as the size of the system grows. We prove this separation unconditionally, without relying on unproven assumptions about the power of classical computation. Earlier work by Bravyi, Gosset, and Koenig showed that constant-depth quantum circuits outperform constant-depth classical circuits on a task with an externally supplied input. They asked whether a quantum advantage could also exist for a task with no external input, where the goal is simply to generate samples from a specified distribution. We answer this question affirmatively, under a restriction on the amount of randomness available to the classical circuit.► BibTeX data@article{BeneWatts2026unconditional, doi = {10.22331/q-2026-08-12-2188}, url = {https://doi.org/10.22331/q-2026-08-12-2188}, title = {Unconditional {Q}uantum {A}dvantage for {S}ampling with {S}hallow {C}ircuits}, author = {Bene Watts, Adam and Parham, Natalie}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2188}, month = aug, year = {2026} }► 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_46Cited by[1] 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). [2] 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). [3] 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). [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] Qisheng Wang and Zhicheng Zhang, "Tight quantum depth lower bound for solving systems of linear equations", Physical Review A 110 1, 012422 (2024). [6] Adam Wills and Sergii Strelchuk, "Generalised Coupling and An Elementary Algorithm for the Quantum Schur Transform", arXiv:2305.04069, (2023). [7] N. Pirnay, S. Jerbi, J.-P. Seifert, and J. Eisert, "An unconditional distribution learning advantage with shallow quantum circuits", arXiv:2411.15548, (2024). [8] Libor Caha, Xavier Coiteux-Roy, and Robert Koenig, "Single-qubit gate teleportation provides a quantum advantage", Quantum 8, 1548 (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] Daniel M. Kane, Anthony Ostuni, and Kewen Wu, "Locality Bounds for Sampling Hamming Slices", arXiv:2402.14278, (2024). [11] Daniel M. Kane, Anthony Ostuni, and Kewen Wu, "Locally Sampleable Uniform Symmetric Distributions", arXiv:2411.08183, (2024). [12] Francisca Vasconcelos and Hsin-Yuan Huang, "Learning shallow quantum circuits with many-qubit gates", arXiv:2410.16693, (2024). [13] Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, and Li-Yang Tan, "The power of quantum circuits in sampling", arXiv:2510.03645, (2025). [14] 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). [15] Joseph Slote, "Parity vs. AC0 with simple quantum preprocessing", arXiv:2311.13679, (2023). [16] Joseph Carolan, Amin Shiraz Gilani, and Mahathi Vempati, "Quantum advantage and lower bounds in parallel query complexity", arXiv:2410.02665, (2024). [17] Sabee Grewal and Vinayak M. Kumar, "Improved Circuit Lower Bounds and Quantum-Classical Separations", arXiv:2408.16406, (2024). [18] Niels M. P. Neumann, "Adaptive Quantum Computers: decoding and state preparation", arXiv:2509.08718, (2025). [19] Yangjing Dong, Fengning Ou, and Penghui Yao, "Linear-Size QAC0 Channels: Learning, Testing and Hardness", arXiv:2510.00593, (2025). [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] Daniel M. Kane, Anthony Ostuni, and Kewen Wu, "Symmetric Distributions from Shallow Circuits", arXiv:2511.14127, (2025). [22] Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov, Artur Riazanov, and Dmitry Sokolov, "Sampling Permutations with Cell Probes is Hard", arXiv:2512.02724, (2025). The above citations are from SAO/NASA ADS (last updated successfully 2026-08-12 12:27:02). The list may be incomplete as not all publishers provide suitable and complete citation data.Could not fetch Crossref cited-by data during last attempt 2026-08-12 12:26:58: Could not fetch cited-by data for 10.22331/q-2026-08-12-2188 from Crossref. This is normal if the DOI was registered recently.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. AbstractRecent 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 summaryIn this work, we show that constant-depth quantum circuits can sample from certain probability distributions that comparable constant-depth classical circuits cannot reproduce, even approximately. Here, constant depth means that the number of computational steps remains fixed, even as the size of the system grows. We prove this separation unconditionally, without relying on unproven assumptions about the power of classical computation. Earlier work by Bravyi, Gosset, and Koenig showed that constant-depth quantum circuits outperform constant-depth classical circuits on a task with an externally supplied input. They asked whether a quantum advantage could also exist for a task with no external input, where the goal is simply to generate samples from a specified distribution. We answer this question affirmatively, under a restriction on the amount of randomness available to the classical circuit.► BibTeX data@article{BeneWatts2026unconditional, doi = {10.22331/q-2026-08-12-2188}, url = {https://doi.org/10.22331/q-2026-08-12-2188}, title = {Unconditional {Q}uantum {A}dvantage for {S}ampling with {S}hallow {C}ircuits}, author = {Bene Watts, Adam and Parham, Natalie}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2188}, month = aug, year = {2026} }► 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.

Read Original

Source Information

Source: Quantum Journal

Website: https://quantum-journal.org/feed/

Discussion

0 professional contributions

Be the first to add a constructive contribution.

Unconditional Quantum Advantage for Sampling with Shallow Circuits

Tags

Source Information