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:2306.16659

Effect of Nonunital Noise on Random-Circuit Sampling

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

Published Jun 29, 2023• 0 citations
arXivHTMLPDF

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 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.

DOI
10.48550/arxiv.2306.16659

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 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

PRX Quantum•Jul 26, 2024•20 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

Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D

Robert Koenig, Marco Tomamichel

We consider quantum circuits consisting of $d$ layers of nearest-neighbor two-qubit gates acting on $n$ qubits arranged on a line, where every qubit is independently depolarized with a constant probability before each layer. We describe a randomized parallel algorithm which samples from the output distribution of any such circuit to within total variation error $δ$, with parallel runtime $2^{O(d)}\log\log(n/δ)$ and $n 2^{O(d)}$ elementary real-arithmetic operations. Without noise, the same approach gives an exact sampler with parallel runtime $O(\log n)$. For constant depth, we further show that the input/output behavior of the noisy quantum circuit is reproduced up to a constant error by a randomized $\mathsf{AC}^0$-circuit, that is, a Boolean circuit of polynomial size and constant depth with unbounded fan-in AND and OR gates and NOT gates. Consequently, every relation problem solved by a noisy constant-depth quantum circuit in one dimension is also solved, with essentially the same success probability, by a randomized $\mathsf{AC}^0$-circuit. This rules out, for noisy circuits in one dimension, the unconditional quantum advantage established for noisy shallow circuits in two and three dimensions, where polynomial-size classical circuits over the same gate set require depth $Ω(\log n/\log\log n)$. Our algorithm exploits the fact that depolarizing noise cuts a one-dimensional circuit into independent pieces of logarithmic width, each of which can be sampled exactly in parallel.

quant-pharXiv:2609.39448•Oct 1, 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 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 \unicodex2014\unicode{x2014}\unicodex2014 meaning it is never too "flat" \unicodex2014\unicode{x2014}\unicodex2014 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.
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
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.
We consider quantum circuits consisting of ddd layers of nearest-neighbor two-qubit gates acting on nnn qubits arranged on a line, where every qubit is independently depolarized with a constant probability before each layer. We describe a randomized parallel algorithm which samples from the output distribution of any such circuit to within total variation error δδδ, with parallel runtime 2O(d)log⁡log⁡(n/δ)2^{O(d)}\log\log(n/δ)2O(d)loglog(n/δ) and n2O(d)n 2^{O(d)}n2O(d) elementary real-arithmetic operations. Without noise, the same approach gives an exact sampler with parallel runtime O(log⁡n)O(\log n)O(logn). For constant depth, we further show that the input/output behavior of the noisy quantum circuit is reproduced up to a constant error by a randomized AC0\mathsf{AC}^0AC0-circuit, that is, a Boolean circuit of polynomial size and constant depth with unbounded fan-in AND and OR gates and NOT gates. Consequently, every relation problem solved by a noisy constant-depth quantum circuit in one dimension is also solved, with essentially the same success probability, by a randomized AC0\mathsf{AC}^0AC0-circuit. This rules out, for noisy circuits in one dimension, the unconditional quantum advantage established for noisy shallow circuits in two and three dimensions, where polynomial-size classical circuits over the same gate set require depth Ω(log⁡n/log⁡log⁡n)Ω(\log n/\log\log n)Ω(logn/loglogn). Our algorithm exploits the fact that depolarizing noise cuts a one-dimensional circuit into independent pieces of logarithmic width, each of which can be sampled exactly in parallel.
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.