Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Nature Physics

On the complexity and verification of quantum random circuit sampling

Adam Bouland, Bill Fefferman, Chinmay Nirkhe, Umesh V. Vazirani

Published Oct 16, 2018• 287 citations
Publisher
DOI
10.1038/s41567-018-0318-2

Related papers

"Quantum Supremacy" and the Complexity of Random Circuit Sampling

Adam Bouland, Bill Fefferman, Chinmay Nirkhe +1 more

A critical milestone on the path to useful quantum computers is quantum supremacy - a demonstration of a quantum computation that is prohibitively hard for classical computers. A leading near-term candidate, put forth by the Google/UCSB team, is sampling from the probability distributions of randomly chosen quantum circuits, which we call Random Circuit Sampling (RCS). In this paper we study both the hardness and verification of RCS. While RCS was defined with experimental realization in mind, we show complexity theoretic evidence of hardness that is on par with the strongest theoretical proposals for supremacy. Specifically, we show that RCS satisfies an average-case hardness condition - computing output probabilities of typical quantum circuits is as hard as computing them in the worst-case, and therefore #P-hard. Our reduction exploits the polynomial structure in the output amplitudes of random quantum circuits, enabled by the Feynman path integral. In addition, it follows from known results that RCS satisfies an anti-concentration property, making it the first supremacy proposal with both average-case hardness and anti-concentration.

arXiv:1803.04402•Leibniz international proceedings in informatics•Mar 12, 2018•63 citations

Notes on Interrogating Random Quantum Circuits

Luís T. A. N. Brandão, René Peralta

•Jan 1, 2020•3 citations

The hardness of random quantum circuits

Ramis Movassagh

Nature Physics•Jul 27, 2023•27 citations

On Certified Randomness from Fourier Sampling or Random Circuit Sampling

Roozbeh Bassirian, Adam Bouland, Bill Fefferman +2 more

Certified randomness has a long history in quantum information, with many potential applications. Recently Aaronson and Hung proposed a novel public certified randomness protocol based on existing random circuit sampling (RCS) experiments. The security of their protocol, however, relies on non-standard complexity-theoretic conjectures which were not previously studied in the literature. Inspired by this work, we study certified randomness in the quantum random oracle model (QROM). We show that quantum Fourier Sampling can be used to define a publicly verifiable certified randomness protocol with black-box security without any computational assumptions. In addition to giving a certified randomness protocol in the QROM, our work can also be seen as supporting Aaronson and Hung's conjectures for RCS-based randomness generation, as our protocol is in some sense the "black-box version" of Aaronson and Hung's protocol. In further support of Aaronson and Hung's proposal, we prove a Fourier Sampling version of Aaronson and Hung's conjecture by extending Raz and Tal's separation of BQP vs PH. Our work complements the subsequent certified randomness protocol of Yamakawa and Zhandry (2022) in the QROM. Whereas the security of that protocol relied on the Aaronson-Ambainis conjecture, ours does not rely on any computational assumption – at the expense of requiring exponential-time classical verification. Our protocol also has a simple heuristic implementation.

arXiv:2111.14846•Quantum•Feb 10, 2026•3 citations

Sample-efficient benchmarking of shallow all-to-all random quantum circuits

Gregory Bentsen, Bill Fefferman, Soumik Ghosh +2 more

Random circuit sampling (RCS) remains one of the most competitive frameworks for demonstrating quantum advantage in near-term noisy intermediate-scale quantum (NISQ) hardware. Unfortunately, absent error-correction, existing benchmarks to characterize these experiments, like linear cross-entropy, have been classically spoofed due to noise. Because of this, there are interesting regimes, like shallow-depth random quantum circuits, where sampling is plausibly classically intractable, but no existing benchmark can distinguish between a noisy quantum computer and an adversarial classical spoofer. In this paper, we demonstrate that the nonlinear cross-entropy provides a sample-efficient benchmark for shallow-depth all-to-all random quantum circuits whose score cleanly separates noisy quantum computers from state-of-the-art classical spoofers, even in the presence of depolarizing noise. Further, we develop a binary classifier based on the notion of heavy output generation that features logarithmic sample complexity at short depth. Our evidence comes from exact analytic expressions for all-to-all Brownian circuit ensembles derived using replica tricks, and numerical simulations that corroborate these results for discrete Haar-random unitary circuits.

quant-pharXiv:2605.22909•May 25, 2026•0 citations

On the Verification of Quantum Circuits (Research Challenges and Opportunities)

Parosh Aziz Abdulla, Y. C. Chen, Yu‐Fang Chen +6 more

Lecture notes in computer science•Aug 30, 2025•0 citations
A critical milestone on the path to useful quantum computers is quantum supremacy - a demonstration of a quantum computation that is prohibitively hard for classical computers. A leading near-term candidate, put forth by the Google/UCSB team, is sampling from the probability distributions of randomly chosen quantum circuits, which we call Random Circuit Sampling (RCS). In this paper we study both the hardness and verification of RCS. While RCS was defined with experimental realization in mind, we show complexity theoretic evidence of hardness that is on par with the strongest theoretical proposals for supremacy. Specifically, we show that RCS satisfies an average-case hardness condition - computing output probabilities of typical quantum circuits is as hard as computing them in the worst-case, and therefore #P-hard. Our reduction exploits the polynomial structure in the output amplitudes of random quantum circuits, enabled by the Feynman path integral. In addition, it follows from known results that RCS satisfies an anti-concentration property, making it the first supremacy proposal with both average-case hardness and anti-concentration.
Certified randomness has a long history in quantum information, with many potential applications. Recently Aaronson and Hung proposed a novel public certified randomness protocol based on existing random circuit sampling (RCS) experiments. The security of their protocol, however, relies on non-standard complexity-theoretic conjectures which were not previously studied in the literature. Inspired by this work, we study certified randomness in the quantum random oracle model (QROM). We show that quantum Fourier Sampling can be used to define a publicly verifiable certified randomness protocol with black-box security without any computational assumptions. In addition to giving a certified randomness protocol in the QROM, our work can also be seen as supporting Aaronson and Hung's conjectures for RCS-based randomness generation, as our protocol is in some sense the "black-box version" of Aaronson and Hung's protocol. In further support of Aaronson and Hung's proposal, we prove a Fourier Sampling version of Aaronson and Hung's conjecture by extending Raz and Tal's separation of BQP vs PH. Our work complements the subsequent certified randomness protocol of Yamakawa and Zhandry (2022) in the QROM. Whereas the security of that protocol relied on the Aaronson-Ambainis conjecture, ours does not rely on any computational assumption – at the expense of requiring exponential-time classical verification. Our protocol also has a simple heuristic implementation.
Random circuit sampling (RCS) remains one of the most competitive frameworks for demonstrating quantum advantage in near-term noisy intermediate-scale quantum (NISQ) hardware. Unfortunately, absent error-correction, existing benchmarks to characterize these experiments, like linear cross-entropy, have been classically spoofed due to noise. Because of this, there are interesting regimes, like shallow-depth random quantum circuits, where sampling is plausibly classically intractable, but no existing benchmark can distinguish between a noisy quantum computer and an adversarial classical spoofer. In this paper, we demonstrate that the nonlinear cross-entropy provides a sample-efficient benchmark for shallow-depth all-to-all random quantum circuits whose score cleanly separates noisy quantum computers from state-of-the-art classical spoofers, even in the presence of depolarizing noise. Further, we develop a binary classifier based on the notion of heavy output generation that features logarithmic sample complexity at short depth. Our evidence comes from exact analytic expressions for all-to-all Brownian circuit ensembles derived using replica tricks, and numerical simulations that corroborate these results for discrete Haar-random unitary circuits.