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

arXiv:2607.20804

Hardness and Complexity Transition of Noisy Random Circuit Sampling

Byeongseon Go, Changhun Oh, Hyunseok Jeong

quant-phSubmitted Jul 23, 2026• Announced Jul 24, 2026• 0 citations
arXivHTMLPDF

Abstract

Random circuit sampling (RCS) is a leading candidate for demonstrating quantum advantage, supported by strong complexity-theoretic evidence of hardness in the ideal setting and by rapid experimental progress to date. In practice, however, noise is unavoidable, and a central problem is to identify the noise-strength boundary between classically simulable and classically hard regimes. In this work, we establish an architecture-general hardness bound for this boundary for the standard local depolarizing noise of strength $γ$. Assuming the standard average-case #P-hardness conjecture for ideal RCS, we show that, for any circuit architecture satisfying this conjecture, noisy RCS on the same architecture remains hard to simulate classically within any inverse-polynomial total variation distance whenever $γ=O(\log n/(nd))$ for $n$-qubit circuits of depth $d$, unless the polynomial hierarchy collapses. Crucially, noisy-RCS hardness follows without any additional conjectural or architecture-specific assumption beyond those already entering the ideal-RCS hardness framework. Our proof combines a low-degree polynomial extrapolation with a monotonicity reduction showing that efficient classical simulation at one depolarizing noise strength implies efficient simulation at every larger strength. Together, these ingredients transfer the standard ideal-RCS hardness conjecture to sampling hardness at a prespecified noise strength. Finally, combining the convergence-to-uniformity result of Dalzell et al. [Commun. Math. Phys. 405, 78 (2024)] with our monotonicity reduction yields efficient classical simulation for $γ=ω(\log n/(nd))$ on layered, regularly connected architectures. Thus, wherever the two architectural settings overlap, this identifies $γ=Θ(\log n/(nd))$ as the asymptotic complexity-transition scale.

Comments
21 pages, 3 figures

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

Limitations of Noisy Geometrically Local Quantum Circuits

Jon Nelson, Joel Rajakumar, Michael J. Gullans

Quantum circuits with a constant rate of depolarizing noise per qubit per time step are known to converge to the uniform distribution at depth $ω(p^{-1}\log n)$, and hence become trivially classically simulable by uniform sampling. We show that under the physically natural constraint of geometric locality, noisy circuits become classically simulable at shallower depths by substantially more structured classical algorithms. We consider arbitrary geometrically local quantum circuits on $n$ qubits, initialized in an arbitrary product state, with nearest-neighbor gates in $O(1)$ spatial dimensions and interspersed depolarizing noise of any constant strength $p$. Our first result is that when the depth exceeds a threshold $d^*=Θ(p^{-1}\log n)$, the output distribution can be approximately sampled in quasipolynomial time. This gives a worst-case simulability result for noisy geometrically local circuits, and matches in its $n$-dependence the best previously known results for noisy random circuits. The proof is based on new information-theoretic bounds showing that in geometrically local noisy circuits, local regions lose correlations and independently converge to maximally mixed strictly before the entire system converges to the uniform distribution. We further prove structural results suggesting a sharper transition at depth $\tildeΘ(p^{-1})$: after coarse-graining the lattice, Pauli weight supported on long connected paths can be truncated with exponentially small error. These results provide evidence for a percolation-like mechanism behind classical simulability at constant depth, and motivate our conjecture that all noisy geometrically local circuits admit quasipolynomial-time approximate sampling once circuit depth exceeds $\tildeΘ(p^{-1})$.

arXiv:2510.06346•Oct 7, 2025•0 citations

Exponential improvements to the average-case hardness of BosonSampling

Adam Bouland, Ishaun Datta, Bill Fefferman +1 more

BosonSampling and Random Circuit Sampling are important both as a theoretical tool for separating quantum and classical computation, and as an experimental means of demonstrating quantum speedups. Prior works have shown that average-case hardness of sampling follows from certain unproven conjectures about the hardness of computing output probabilities, such as the Permanent-of-Gaussians Conjecture (PGC), which states that $e^{-n \log n-n-O(\log n)}$ additive-error estimates to the output probability of most random BosonSampling experiments are #P-hard. Prior works have only shown weaker average-case hardness results that do not imply sampling hardness. Proving these conjectures has become a central question in quantum complexity. In this work, we show that $e^{-n \log n-n-O\left(n^{\delta}\right)}$ additive-error estimates to output probabilities of most random BosonSampling experiments are #P-hard for any $\delta\gt 0$, exponentially improving on prior work. In the process, we circumvent all known barrier results for proving PGC. The remaining hurdle to prove PGC is now “merely” to show that the $O\left(n^{\delta}\right)$ in the exponent can be improved to $O(\log n)$. We also obtain an analogous result for Random Circuit Sampling. We then show, for the first time, a hardness of average-case classical sampling result for BosonSampling, under an anticoncentration conjecture. Specifically, we prove the impossibility of multiplicative-error sampling from random BosonSampling experiments with probability $1-2^{-\tilde{O}\left(N^{1 / 3}\right)}$ for input size N, unless the Polynomial Hierarchy collapses. This exponentially improves upon the state-of-the-art. To do this, we introduce new proof techniques which tolerate exponential loss in the worst-to-average-case reduction. This opens the possibility to show the hardness of average-case sampling without ever proving PGC.

Annual Symposium on Foundations of Computer Science•Dec 14, 2025•1 citation

A polynomial-time classical sampler for noisy quantum circuits from statistical mechanics

Jon Nelson, Joel Rajakumar, Chao Yin +2 more

Developing classical simulation algorithms for noisy quantum circuits is essential to delineating the limits of quantum advantage. Existing classical sampling approaches for general circuits require circuit depths to grow logarithmically with system size, so that noise drives the global output state close to a trivial state. Here we show that local accumulation of noise at a depth independent of system size is already sufficient. Specifically, we prove that any geometrically local circuit composed of unital operations and interspersed with single-qubit depolarizing noise of strength $p$ after $Θ(p^{-1} \log p^{-1})$ depth can be approximately sampled from a polynomial-time classical computer. This generalizes existing results that impose anticoncentration assumptions or non-universal gate sets in order to obtain a classical sampler at such shallow depths. Our proof maps the output state of the circuit to a polymer model in statistical mechanics, and combines a convergent cluster expansion with hypercontractivity of the depolarizing channel.

quant-pharXiv:2610.00548•Oct 2, 2026•0 citations

Improved robustness of quantum supremacy for random circuit sampling

Y. Kondo, Ryuhei Mori, Ramis Movassagh

Motivated by the recent experimental demonstrations of quantum supremacy, proving the hardness of the output of random quantum circuits is an imperative near term goal. We prove under the complexity theoretical assumption of the non-collapse of the polynomial hierarchy that approximating the output probabilities of random quantum circuits to within $\exp(-\Omega(m\log m))$ additive error is hard for any classical computer, where $m$ is the number of gates in the quantum computation. More precisely, we show that the above problem is $\#\mathsf{P}$-hard under $\mathsf{BPP}^{\mathsf{NP}}$ reduction. In the recent experiments, the quantum circuit has $n$-qubits and the architecture is a two-dimensional grid of size $\sqrt{n}\times\sqrt{n}$. Indeed for constant depth circuits approximating the output probabilities to within $2^{-\Omega(n\log{n})}$ is hard. For circuits of depth $\log{n}$ or $\sqrt{n}$ for which the anti-concentration property holds, approximating the output probabilities to within $2^{-\Omega(n\log^2{n})}$ and $2^{-\Omega(n^{3/2}\log n)}$ is hard respectively. We made an effort to find the best proofs and proved these results from first principles, which do not use the standard techniques such as the Berlekamp--Welch algorithm, the usual Paturi's lemma, and Rakhmanov's result.

•Feb 3, 2021•5 citations

The Energy-Advantage Frontier of Random Circuit Sampling Across the Simulability Transition

Hikaru Wakaura, Taiki Tanimae

We introduce the energy-advantage frontier of random circuit sampling (RCS)—the locus in the noise-rate/size plane where the classical and quantum energy-to-solution are equal—and locate it relative to the noise-induced classical-simulability transition. Our firm, model-free result is that the classical sampling-energy floor collapses sharply across the transition, exhibiting a finite-size scaling collapse over exact systems n≤12 (with a collapse exponent of order unity). Built on it, the energy-advantage frontier is distinct from the computational (wall-clock) frontier: in the exascale-classical, few-femtojoule regime, the energy frontier is the more noise-robust, so an energy advantage can persist where a time advantage does not—a projection, not a deployment claim, whose direction reverses outside that regime. We give a conditional Landauer lower bound for sampling, RE≡Ecl/Eq≳2(1.0±0.2)n/n under standard RCS hardness, package RE as a single figure of merit computed by a released open tool (exs), and map an energy-normalized cross-entropy witness within a cost model. A run on a 156-qubit IBM Heron processor tests the fidelity model (no energy is measured on hardware) and shows real noise exceeds the depolarizing idealization, so quoted frontier locations are upper bounds.

Mathematics•Jun 30, 2026•0 citations
Random circuit sampling (RCS) is a leading candidate for demonstrating quantum advantage, supported by strong complexity-theoretic evidence of hardness in the ideal setting and by rapid experimental progress to date. In practice, however, noise is unavoidable, and a central problem is to identify the noise-strength boundary between classically simulable and classically hard regimes. In this work, we establish an architecture-general hardness bound for this boundary for the standard local depolarizing noise of strength γγγ. Assuming the standard average-case #P-hardness conjecture for ideal RCS, we show that, for any circuit architecture satisfying this conjecture, noisy RCS on the same architecture remains hard to simulate classically within any inverse-polynomial total variation distance whenever γ=O(log⁡n/(nd))γ=O(\log n/(nd))γ=O(logn/(nd)) for nnn-qubit circuits of depth ddd, unless the polynomial hierarchy collapses. Crucially, noisy-RCS hardness follows without any additional conjectural or architecture-specific assumption beyond those already entering the ideal-RCS hardness framework. Our proof combines a low-degree polynomial extrapolation with a monotonicity reduction showing that efficient classical simulation at one depolarizing noise strength implies efficient simulation at every larger strength. Together, these ingredients transfer the standard ideal-RCS hardness conjecture to sampling hardness at a prespecified noise strength. Finally, combining the convergence-to-uniformity result of Dalzell et al. [Commun. Math. Phys. 405, 78 (2024)] with our monotonicity reduction yields efficient classical simulation for γ=ω(log⁡n/(nd))γ=ω(\log n/(nd))γ=ω(logn/(nd)) on layered, regularly connected architectures. Thus, wherever the two architectural settings overlap, this identifies γ=Θ(log⁡n/(nd))γ=Θ(\log n/(nd))γ=Θ(logn/(nd)) as the asymptotic complexity-transition scale.
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.
Quantum circuits with a constant rate of depolarizing noise per qubit per time step are known to converge to the uniform distribution at depth ω(p−1log⁡n)ω(p^{-1}\log n)ω(p−1logn), and hence become trivially classically simulable by uniform sampling. We show that under the physically natural constraint of geometric locality, noisy circuits become classically simulable at shallower depths by substantially more structured classical algorithms. We consider arbitrary geometrically local quantum circuits on nnn qubits, initialized in an arbitrary product state, with nearest-neighbor gates in O(1)O(1)O(1) spatial dimensions and interspersed depolarizing noise of any constant strength ppp. Our first result is that when the depth exceeds a threshold d∗=Θ(p−1log⁡n)d^*=Θ(p^{-1}\log n)d∗=Θ(p−1logn), the output distribution can be approximately sampled in quasipolynomial time. This gives a worst-case simulability result for noisy geometrically local circuits, and matches in its nnn-dependence the best previously known results for noisy random circuits. The proof is based on new information-theoretic bounds showing that in geometrically local noisy circuits, local regions lose correlations and independently converge to maximally mixed strictly before the entire system converges to the uniform distribution. We further prove structural results suggesting a sharper transition at depth Θ~(p−1)\tildeΘ(p^{-1})Θ~(p−1): after coarse-graining the lattice, Pauli weight supported on long connected paths can be truncated with exponentially small error. These results provide evidence for a percolation-like mechanism behind classical simulability at constant depth, and motivate our conjecture that all noisy geometrically local circuits admit quasipolynomial-time approximate sampling once circuit depth exceeds Θ~(p−1)\tildeΘ(p^{-1})Θ~(p−1).
BosonSampling and Random Circuit Sampling are important both as a theoretical tool for separating quantum and classical computation, and as an experimental means of demonstrating quantum speedups. Prior works have shown that average-case hardness of sampling follows from certain unproven conjectures about the hardness of computing output probabilities, such as the Permanent-of-Gaussians Conjecture (PGC), which states that e−nlog⁡n−n−O(log⁡n)e^{-n \log n-n-O(\log n)}e−nlogn−n−O(logn) additive-error estimates to the output probability of most random BosonSampling experiments are #P-hard. Prior works have only shown weaker average-case hardness results that do not imply sampling hardness. Proving these conjectures has become a central question in quantum complexity. In this work, we show that e−nlog⁡n−n−O(nδ)e^{-n \log n-n-O\left(n^{\delta}\right)}e−nlogn−n−O(nδ) additive-error estimates to output probabilities of most random BosonSampling experiments are #P-hard for any δ>0\delta\gt 0δ>0, exponentially improving on prior work. In the process, we circumvent all known barrier results for proving PGC. The remaining hurdle to prove PGC is now “merely” to show that the O(nδ)O\left(n^{\delta}\right)O(nδ) in the exponent can be improved to O(log⁡n)O(\log n)O(logn). We also obtain an analogous result for Random Circuit Sampling. We then show, for the first time, a hardness of average-case classical sampling result for BosonSampling, under an anticoncentration conjecture. Specifically, we prove the impossibility of multiplicative-error sampling from random BosonSampling experiments with probability 1−2−O~(N1/3)1-2^{-\tilde{O}\left(N^{1 / 3}\right)}1−2−O~(N1/3) for input size N, unless the Polynomial Hierarchy collapses. This exponentially improves upon the state-of-the-art. To do this, we introduce new proof techniques which tolerate exponential loss in the worst-to-average-case reduction. This opens the possibility to show the hardness of average-case sampling without ever proving PGC.
Developing classical simulation algorithms for noisy quantum circuits is essential to delineating the limits of quantum advantage. Existing classical sampling approaches for general circuits require circuit depths to grow logarithmically with system size, so that noise drives the global output state close to a trivial state. Here we show that local accumulation of noise at a depth independent of system size is already sufficient. Specifically, we prove that any geometrically local circuit composed of unital operations and interspersed with single-qubit depolarizing noise of strength ppp after Θ(p−1log⁡p−1)Θ(p^{-1} \log p^{-1})Θ(p−1logp−1) depth can be approximately sampled from a polynomial-time classical computer. This generalizes existing results that impose anticoncentration assumptions or non-universal gate sets in order to obtain a classical sampler at such shallow depths. Our proof maps the output state of the circuit to a polymer model in statistical mechanics, and combines a convergent cluster expansion with hypercontractivity of the depolarizing channel.
Motivated by the recent experimental demonstrations of quantum supremacy, proving the hardness of the output of random quantum circuits is an imperative near term goal. We prove under the complexity theoretical assumption of the non-collapse of the polynomial hierarchy that approximating the output probabilities of random quantum circuits to within exp⁡(−Ω(mlog⁡m))\exp(-\Omega(m\log m))exp(−Ω(mlogm)) additive error is hard for any classical computer, where mmm is the number of gates in the quantum computation. More precisely, we show that the above problem is #P\#\mathsf{P}#P-hard under BPPNP\mathsf{BPP}^{\mathsf{NP}}BPPNP reduction. In the recent experiments, the quantum circuit has nnn-qubits and the architecture is a two-dimensional grid of size n×n\sqrt{n}\times\sqrt{n}n​×n​. Indeed for constant depth circuits approximating the output probabilities to within 2−Ω(nlog⁡n)2^{-\Omega(n\log{n})}2−Ω(nlogn) is hard. For circuits of depth log⁡n\log{n}logn or n\sqrt{n}n​ for which the anti-concentration property holds, approximating the output probabilities to within 2−Ω(nlog⁡2n)2^{-\Omega(n\log^2{n})}2−Ω(nlog2n) and 2−Ω(n3/2log⁡n)2^{-\Omega(n^{3/2}\log n)}2−Ω(n3/2logn) is hard respectively. We made an effort to find the best proofs and proved these results from first principles, which do not use the standard techniques such as the Berlekamp--Welch algorithm, the usual Paturi's lemma, and Rakhmanov's result.
We introduce the energy-advantage frontier of random circuit sampling (RCS)—the locus in the noise-rate/size plane where the classical and quantum energy-to-solution are equal—and locate it relative to the noise-induced classical-simulability transition. Our firm, model-free result is that the classical sampling-energy floor collapses sharply across the transition, exhibiting a finite-size scaling collapse over exact systems n≤12 (with a collapse exponent of order unity). Built on it, the energy-advantage frontier is distinct from the computational (wall-clock) frontier: in the exascale-classical, few-femtojoule regime, the energy frontier is the more noise-robust, so an energy advantage can persist where a time advantage does not—a projection, not a deployment claim, whose direction reverses outside that regime. We give a conditional Landauer lower bound for sampling, RE≡Ecl/Eq≳2(1.0±0.2)n/n under standard RCS hardness, package RE as a single figure of merit computed by a released open tool (exs), and map an energy-normalized cross-entropy witness within a cost model. A run on a 156-qubit IBM Heron processor tests the fidelity model (no energy is measured on hardware) and shows real noise exceeds the depolarizing idealization, so quoted frontier locations are upper bounds.