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

PRX Quantum

Effect of Nonunital Noise on Random-Circuit Sampling

Bill Fefferman, Soumik Ghosh, Michael J. Gullans, Kohdai Kuroiwa, Kunal Sharma

Published Jul 26, 2024• 20 citations
Publisher

Abstract

In this work, drawing inspiration from the type of noise present in real hardware, we study the output distribution of random quantum circuits under practical nonunital noise sources with constant noise rates. We show that even in the presence of unital sources such as the depolarizing channel, the distribution, under the combined noise channel, never resembles a maximally entropic distribution at any depth. To show this, we prove that the output distribution of such circuits never anticoncentrates—meaning that it is never too “flat”—regardless of the depth of the circuit. This is in stark contrast to the behavior of noiseless random quantum circuits or those with only unital noise, both of which anticoncentrate at sufficiently large depths. As a consequence, our results shows that the complexity of random-circuit sampling under realistic noise is still an open question, since anticoncentration is a critical property exploited by both state-of-the-art classical hardness and easiness results. Published by the American Physical Society 2024

DOI
10.1103/prxquantum.5.030317

Related papers

Effect of Nonunital Noise on Random-Circuit Sampling

Bill Fefferman, Soumik Ghosh, Michael J. Gullans +2 more

In this work, drawing inspiration from the type of noise present in real hardware, we study the output distribution of random quantum circuits under practical non-unital noise sources with constant noise rates. We show that even in the presence of unital sources like the depolarizing channel, the distribution, under the combined noise channel, never resembles a maximally entropic distribution at any depth. To show this, we prove that the output distribution of such circuits never anticoncentrates $\unicode{x2014}$ meaning it is never too "flat" $\unicode{x2014}$ regardless of the depth of the circuit. This is in stark contrast to the behavior of noiseless random quantum circuits or those with only unital noise, both of which anticoncentrate at sufficiently large depths. As consequences, our results have interesting algorithmic implications on both the hardness and easiness of noisy random circuit sampling, since anticoncentration is a critical property exploited by both state-of-the-art classical hardness and easiness results.

arXiv:2306.16659•Jun 29, 2023•0 citations

Tight bounds on the convergence of noisy random circuits to uniform.

Abhinav Deshpande, Bill Fefferman, Alexey Vyacheslavovich Gorshkov +3 more

We study the properties of output distributions of noisy, random circuits. We obtain upper and lower bounds on the expected distance of the output distribution from the uniform distribution. These bounds are tight with respect to the dependence on circuit depth. Our proof techniques also allow us to make statements about the presence or absence of anticoncentration for both noisy and noiseless circuits. We uncover a number of interesting consequences for hardness proofs of sampling schemes that aim to show a quantum computational advantage over classical computation. Specifically, we discuss recent barrier results for depth-agnostic and/or noise-agnostic proof techniques. We show that in certain depth regimes, noise-agnostic proof techniques might still work in order to prove an often-conjectured claim in the literature on quantum computational advantage, contrary to what was thought prior to this work.

•Dec 1, 2021•3 citations

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

Tight Bounds on the Convergence of Noisy Random Circuits to the Uniform Distribution

Abhinav Deshpande, Pradeep Niroula, Oles Shtanko +3 more

We study the properties of output distributions of noisy random circuits.We obtain upper and lower bounds on the expected distance of the output distribution from the "useless" uniform distribution.These bounds are tight with respect to the dependence on circuit depth.Our proof techniques also allow us to make statements about the presence or absence of anticoncentration for both noisy and noiseless circuits.We uncover a number of interesting consequences for hardness proofs of sampling schemes that aim to show a quantum computational advantage over classical computation.Specifically, we discuss recent barrier results for depth-agnostic and/or noise-agnostic proof techniques.We show that in certain depth regimes, noise-agnostic proof techniques might still work in order to prove an often-conjectured claim in the literature on quantum computational advantage, contrary to what has been thought prior to this work.

arXiv:2112.00716•PRX Quantum•Dec 16, 2022•48 citations

Hardness and Complexity Transition of Noisy Random Circuit Sampling

Byeongseon Go, Changhun Oh, Hyunseok Jeong

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.

quant-pharXiv:2607.20804•Jul 24, 2026•0 citations

Complexity of Local Quantum Circuits under Nonunital Noise

Oles Shtanko, Kunal Sharma

It is widely accepted that noisy quantum devices are limited to logarithmic depth circuits unless midcircuit measurements and error correction are employed. However, this conclusion holds only for unital error channels, such as depolarizing noise. Building on the idea of the “quantum refrigerator” Ben-Or [Quantum refrigerator, arXiv1301.1995 (2013)], we improve upon previous results and show that geometrically local circuits in the presence of nonunital noise, in any dimension d ≥ 1 , can correct errors without midcircuit measurements and extend computation to any depth, with only polylogarithmic overhead in the depth and the number of qubits. This implies that local quantum dynamics subjected to sufficiently weak nonunital noise are computationally universal and nearly as hard to simulate as noiseless dynamics. Additionally, we quantify the contraction property of local random circuits in the presence of nonunital noise.

arXiv:2411.04819•PRX Quantum•Jul 16, 2025•2 citations
In this work, drawing inspiration from the type of noise present in real hardware, we study the output distribution of random quantum circuits under practical nonunital noise sources with constant noise rates. We show that even in the presence of unital sources such as the depolarizing channel, the distribution, under the combined noise channel, never resembles a maximally entropic distribution at any depth. To show this, we prove that the output distribution of such circuits never anticoncentrates—meaning that it is never too “flat”—regardless of the depth of the circuit. This is in stark contrast to the behavior of noiseless random quantum circuits or those with only unital noise, both of which anticoncentrate at sufficiently large depths. As a consequence, our results shows that the complexity of random-circuit sampling under realistic noise is still an open question, since anticoncentration is a critical property exploited by both state-of-the-art classical hardness and easiness results. Published by the American Physical Society 2024
In this work, drawing inspiration from the type of noise present in real hardware, we study the output distribution of random quantum circuits under practical non-unital noise sources with constant noise rates. We show that even in the presence of unital sources like the depolarizing channel, the distribution, under the combined noise channel, never resembles a maximally entropic distribution at any depth. To show this, we prove that the output distribution of such circuits never anticoncentrates $\unicode{x2014}$ meaning it is never too "flat" $\unicode{x2014}$ regardless of the depth of the circuit. This is in stark contrast to the behavior of noiseless random quantum circuits or those with only unital noise, both of which anticoncentrate at sufficiently large depths. As consequences, our results have interesting algorithmic implications on both the hardness and easiness of noisy random circuit sampling, since anticoncentration is a critical property exploited by both state-of-the-art classical hardness and easiness results.
We study the properties of output distributions of noisy, random circuits. We obtain upper and lower bounds on the expected distance of the output distribution from the uniform distribution. These bounds are tight with respect to the dependence on circuit depth. Our proof techniques also allow us to make statements about the presence or absence of anticoncentration for both noisy and noiseless circuits. We uncover a number of interesting consequences for hardness proofs of sampling schemes that aim to show a quantum computational advantage over classical computation. Specifically, we discuss recent barrier results for depth-agnostic and/or noise-agnostic proof techniques. We show that in certain depth regimes, noise-agnostic proof techniques might still work in order to prove an often-conjectured claim in the literature on quantum computational advantage, contrary to what was thought prior to this work.
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.
We study the properties of output distributions of noisy random circuits.We obtain upper and lower bounds on the expected distance of the output distribution from the "useless" uniform distribution.These bounds are tight with respect to the dependence on circuit depth.Our proof techniques also allow us to make statements about the presence or absence of anticoncentration for both noisy and noiseless circuits.We uncover a number of interesting consequences for hardness proofs of sampling schemes that aim to show a quantum computational advantage over classical computation.Specifically, we discuss recent barrier results for depth-agnostic and/or noise-agnostic proof techniques.We show that in certain depth regimes, noise-agnostic proof techniques might still work in order to prove an often-conjectured claim in the literature on quantum computational advantage, contrary to what has been thought prior to this work.
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.
It is widely accepted that noisy quantum devices are limited to logarithmic depth circuits unless midcircuit measurements and error correction are employed. However, this conclusion holds only for unital error channels, such as depolarizing noise. Building on the idea of the “quantum refrigerator” Ben-Or [Quantum refrigerator, arXiv1301.1995 (2013)], we improve upon previous results and show that geometrically local circuits in the presence of nonunital noise, in any dimension d ≥ 1 , can correct errors without midcircuit measurements and extend computation to any depth, with only polylogarithmic overhead in the depth and the number of qubits. This implies that local quantum dynamics subjected to sufficiently weak nonunital noise are computationally universal and nearly as hard to simulate as noiseless dynamics. Additionally, we quantify the contraction property of local random circuits in the presence of nonunital noise.