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:2111.14907 · Communications in Mathematical Physics

Random Quantum Circuits Transform Local Noise into Global White Noise

Alexander M. Dalzell, Nicholas Hunter-Jones, Fernando G. S. L. Brandão

Published Mar 1, 2024• 126 citations
arXivHTMLPDF

Abstract

Abstract We study the distribution over measurement outcomes of noisy random quantum circuits in the regime of low fidelity, which corresponds to the setting where the computation experiences at least one gate-level error with probability close to one. We model noise by adding a pair of weak, unital, single-qubit noise channels after each two-qubit gate, and we show that for typical random circuit instances, correlations between the noisy output distribution $$p_{\text {noisy}}$$ p noisy and the corresponding noiseless output distribution $$p_{\text {ideal}}$$ p ideal shrink exponentially with the expected number of gate-level errors. Specifically, the linear cross-entropy benchmark F that measures this correlation behaves as $$F=\text {exp}(-2s\epsilon \pm O(s\epsilon ^2))$$ F = exp ( - 2 s ϵ ± O ( s ϵ 2 ) ) , where $$\epsilon $$ ϵ is the probability of error per circuit location and s is the number of two-qubit gates. Furthermore, if the noise is incoherent—for example, depolarizing or dephasing noise—the total variation distance between the noisy output distribution $$p_{\text {noisy}}$$ p noisy and the uniform distribution $$p_{\text {unif}}$$ p unif decays at precisely the same rate. Consequently, the noisy output distribution can be approximated as $$p_{\text {noisy}}\approx Fp_{\text {ideal}}+ (1-F)p_{\text {unif}}$$ p noisy ≈ F p ideal + ( 1 - F ) p unif . In other words, although at least one local error occurs with probability $$1-F$$ 1 - F , the errors are scrambled by the random quantum circuit and can be treated as global white noise, contributing completely uniform output. Importantly, we upper bound the average total variation error in this approximation by $$O(F\epsilon \sqrt{s})$$ O ( F ϵ s ) . Thus, the “white-noise approximation” is meaningful when $$\epsilon \sqrt{s} \ll 1$$ ϵ s ≪ 1 , a quadratically weaker condition than the $$\epsilon s\ll 1$$ ϵ s ≪ 1

DOI
10.1007/s00220-024-04958-z

Related papers

Error accumulation in dissipative quantum circuits

Nadir Samos-Sáenz de Buruaga, Rodrigo M. C. Pereira, Karol Życzkowski +2 more

Present-day quantum processors are open systems in which dissipation and decoherence degrade the information carried by a quantum state as it propagates through a circuit. We study this degradation in dissipative random quantum circuits, modeling each two-qubit gate as a diluted unitary that interpolates between the intended unitary operation and a random dissipative quantum channel. Using the fidelity between the ideal and noisy output states as a diagnostic, we show that sufficiently random unitary gates or dissipative Kraus operators lead to a universal decay of the average fidelity. This decay is determined only by the dissipation strength, system size, and circuit depth, while microscopic details of the gates and noise, including the Kraus rank, appear only in subleading corrections to higher moments. We derive a closed-form expression for the average fidelity in terms of three physically meaningful error parameters, dissipation strength, coherent two-qubit gate-error strength, and connectivity-error probability. Finally, we identify the cases when dissipative effects can be reproduced by an unitary-noise model and when dissipation-induced decoherence remains distinguishable from coherent noise at the level of the average fidelity.

quant-pharXiv:2609.01848•Sep 3, 2026•0 citations

The Impact of Markovian Errors on Random Circuits

Anthony M. Polloreno, Timothy Proctor, Robin Blume-Kohout

Randomized benchmarking (RB) returns a single decay parameter or gate error rate, but when the noise is gate-dependent that parameter is notoriously difficult to interpret. We study RB and related random-circuit benchmarks under small gate-local Markovian noise by factorizing each noisy gate into its ideal action followed by the exponential of a small error generator and then perturbing the RB $\mathscr{L}$ matrix, which models the RB decay. For any low-error gate set that satisfies the requirements of RB (it is a sequence-asymptotic unitary 2-design), we show that Pauli-stochastic error rates contribute linearly to the RB decay parameter, while Hamiltonian error rates contribute through a gauge-invariant quadratic form. Pauli-correlation and active generators are absent from the linear term and enter only at higher order. For the single-qubit native gate set $\{X_{π/2},Y_{π/2}\}$ we derive this quadratic form explicitly in terms of three first-order gauge-invariant (FOGI) coordinates: the two intrinsic over-rotations and one relational axis-tilt error. The resulting formula explains the dependence of DRB on the sampling distribution and the compilation dependence of CRB. These results turn RB decay rates into interpretable functions of experimentally meaningful elementary error rates.

quant-pharXiv:2610.31500•Oct 23, 2026•0 citations

Metrological Benchmarking of Random Quantum Circuits

Simone Cavazzoni, Changhun Oh

Random circuit sampling is a leading approach to demonstrating quantum computational advantage, but benchmarking noisy implementations through linear cross-entropy requires costly calculations of ideal output probabilities. We propose a metrological benchmark based on the response to controlled perturbations, characterized by quantum Fisher information (QFI). A relation between QFI and out-of-time-order correlators enables protocols with local or global control. For Haar-random circuits, the average QFI approaches its maximal value in the local protocol and grows linearly with the number of qubits under collective control. In contrast, Clifford circuits yield zero QFI despite extensive operator spreading, showing that the response probes dynamical properties beyond spreading alone. A butterfly protocol further uses system size to enhance sensitivity, yielding a mean inverse sensitivity proportional to the number of qubits with single-qubit readout. Its fluctuations distinguish the Haar and Clifford ensembles despite their identical mean responses. For noisy implementations, we derive an exact relation between the noisy and ideal QFI within a global white-noise model, providing a quantitative reference for the degradation of the benchmark. These protocols enable metrological benchmarking of noisy random quantum circuits without computing ideal output probabilities.

quant-pharXiv:2609.39226•Oct 1, 2026•0 citations

Random Quantum Circuits Beyond Moment Matching

Shih-Han Hung

Random quantum circuits aim to efficiently reproduce the statistical properties of ideal random quantum evolution. One approach is to construct approximate unitary designs, which match the moments of Haar-random unitaries up to a prescribed order with controlled error. We establish quantitative guarantees for how accurately these designs reproduce the distribution of each output probability. We show that, for every strong $\varepsilon$-approximate unitary $k$-design on $n$ qubits, the distribution of each output probability is within $O(k^{-1/2}(1+k/2^n)^{-1/2}+\varepsilon)$ in Kolmogorov distance of the Porter-Thomas distribution, a beta distribution with parameters $1$ and $2^n-1$. This bound is optimal up to constant factors, implying that a substantially better uniform bound requires additional structure. We then show that a mild form of local invariance suffices. We prove that any such design that is invariant under unitary translations acting on a single qubit approximates Porter-Thomas to total variation distance $O(k^{-1/2}+\varepsilon)$. Every strong $\varepsilon$-approximate unitary $k$-design invariant on $\log k+O(1)$ qubits achieves error $2^{-Ω(k)}+O(\varepsilon)$ in Kolmogorov distance and $2^{-Ω(k)}+O(\varepsilon\log(2/\varepsilon))$ in total variation distance. These results identify the distributional accuracy guaranteed by moment matching and the structure that improves it. As an application, we show that the Shannon entropy of the output distribution of a strong $\varepsilon$-approximate $k$-design is concentrated around its Haar value $n-Θ(1)$: its mean differs from the Haar mean by $O(k^{-1/4}+\varepsilon^{1/2})$ and its standard deviation is $O(2^{-n/2}+k^{-1/8}+\varepsilon^{1/4})$. Consequently, a trusted device sampling such circuits generates $n-O(1)$ bits of entropy per sample, which makes them useful for random number generation.

quant-pharXiv:2610.02135•Oct 2, 2026•0 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

Sampling of globally depolarized random quantum circuit

Tomoyuki Morimae, Yuki Takeuchi, Seiichiro Tani

The recent paper [F. Arute et al. Nature {\bf 574}, 505 (2019)] considered exact classical sampling of the output probability distribution of the globally depolarized random quantum circuit. In this paper, we show three results. First, we consider the case when the fidelity $F$ is constant. We show that if the distribution is classically sampled in polynomial time within a constant multiplicative error, then ${\rm BQP}\subseteq{\rm SBP}$, which means that BQP is in the second level of the polynomial-time hierarchy. We next show that for any $F\le1/2$, the distribution is classically trivially sampled by the uniform distribution within the multiplicative error $F2^{n+2}$, where $n$ is the number of qubits. We finally show that for any $F$, the distribution is classically trivially sampled by the uniform distribution within the additive error $2F$. These last two results show that if we consider realistic cases, both $F\sim2^{-m}$ and $m\gg n$, or at least $F\sim2^{-m}$, where $m$ is the number of gates, quantum supremacy does not exist for approximate sampling even with the exponentially-small errors. We also argue that if $F\sim2^{-m}$ and $m\gg n$, the standard approach will not work to show quantum supremacy even for exact sampling.

arXiv:1911.02220•Nov 6, 2019•3 citations
Abstract We study the distribution over measurement outcomes of noisy random quantum circuits in the regime of low fidelity, which corresponds to the setting where the computation experiences at least one gate-level error with probability close to one. We model noise by adding a pair of weak, unital, single-qubit noise channels after each two-qubit gate, and we show that for typical random circuit instances, correlations between the noisy output distribution pnoisyp_{\text {noisy}}pnoisy​ p noisy and the corresponding noiseless output distribution pidealp_{\text {ideal}}pideal​ p ideal shrink exponentially with the expected number of gate-level errors. Specifically, the linear cross-entropy benchmark F that measures this correlation behaves as F=exp(−2sϵ±O(sϵ2))F=\text {exp}(-2s\epsilon \pm O(s\epsilon ^2))F=exp(−2sϵ±O(sϵ2)) F = exp ( - 2 s ϵ ± O ( s ϵ 2 ) ) , where ϵ\epsilon ϵ ϵ is the probability of error per circuit location and s is the number of two-qubit gates. Furthermore, if the noise is incoherent—for example, depolarizing or dephasing noise—the total variation distance between the noisy output distribution pnoisyp_{\text {noisy}}pnoisy​ p noisy and the uniform distribution punifp_{\text {unif}}punif​ p unif decays at precisely the same rate. Consequently, the noisy output distribution can be approximated as pnoisy≈Fpideal+(1−F)punifp_{\text {noisy}}\approx Fp_{\text {ideal}}+ (1-F)p_{\text {unif}}pnoisy​≈Fpideal​+(1−F)punif​ p noisy ≈ F p ideal + ( 1 - F ) p unif . In other words, although at least one local error occurs with probability 1−F1-F1−F 1 - F , the errors are scrambled by the random quantum circuit and can be treated as global white noise, contributing completely uniform output. Importantly, we upper bound the average total variation error in this approximation by O(Fϵs)O(F\epsilon \sqrt{s})O(Fϵs​) O ( F ϵ s ) . Thus, the “white-noise approximation” is meaningful when ϵs≪1\epsilon \sqrt{s} \ll 1ϵs​≪1 ϵ s ≪ 1 , a quadratically weaker condition than the ϵs≪1\epsilon s\ll 1ϵs≪1 ϵ s ≪ 1
Present-day quantum processors are open systems in which dissipation and decoherence degrade the information carried by a quantum state as it propagates through a circuit. We study this degradation in dissipative random quantum circuits, modeling each two-qubit gate as a diluted unitary that interpolates between the intended unitary operation and a random dissipative quantum channel. Using the fidelity between the ideal and noisy output states as a diagnostic, we show that sufficiently random unitary gates or dissipative Kraus operators lead to a universal decay of the average fidelity. This decay is determined only by the dissipation strength, system size, and circuit depth, while microscopic details of the gates and noise, including the Kraus rank, appear only in subleading corrections to higher moments. We derive a closed-form expression for the average fidelity in terms of three physically meaningful error parameters, dissipation strength, coherent two-qubit gate-error strength, and connectivity-error probability. Finally, we identify the cases when dissipative effects can be reproduced by an unitary-noise model and when dissipation-induced decoherence remains distinguishable from coherent noise at the level of the average fidelity.
Randomized benchmarking (RB) returns a single decay parameter or gate error rate, but when the noise is gate-dependent that parameter is notoriously difficult to interpret. We study RB and related random-circuit benchmarks under small gate-local Markovian noise by factorizing each noisy gate into its ideal action followed by the exponential of a small error generator and then perturbing the RB L\mathscr{L}L matrix, which models the RB decay. For any low-error gate set that satisfies the requirements of RB (it is a sequence-asymptotic unitary 2-design), we show that Pauli-stochastic error rates contribute linearly to the RB decay parameter, while Hamiltonian error rates contribute through a gauge-invariant quadratic form. Pauli-correlation and active generators are absent from the linear term and enter only at higher order. For the single-qubit native gate set {Xπ/2,Yπ/2}\{X_{π/2},Y_{π/2}\}{Xπ/2​,Yπ/2​} we derive this quadratic form explicitly in terms of three first-order gauge-invariant (FOGI) coordinates: the two intrinsic over-rotations and one relational axis-tilt error. The resulting formula explains the dependence of DRB on the sampling distribution and the compilation dependence of CRB. These results turn RB decay rates into interpretable functions of experimentally meaningful elementary error rates.
Random circuit sampling is a leading approach to demonstrating quantum computational advantage, but benchmarking noisy implementations through linear cross-entropy requires costly calculations of ideal output probabilities. We propose a metrological benchmark based on the response to controlled perturbations, characterized by quantum Fisher information (QFI). A relation between QFI and out-of-time-order correlators enables protocols with local or global control. For Haar-random circuits, the average QFI approaches its maximal value in the local protocol and grows linearly with the number of qubits under collective control. In contrast, Clifford circuits yield zero QFI despite extensive operator spreading, showing that the response probes dynamical properties beyond spreading alone. A butterfly protocol further uses system size to enhance sensitivity, yielding a mean inverse sensitivity proportional to the number of qubits with single-qubit readout. Its fluctuations distinguish the Haar and Clifford ensembles despite their identical mean responses. For noisy implementations, we derive an exact relation between the noisy and ideal QFI within a global white-noise model, providing a quantitative reference for the degradation of the benchmark. These protocols enable metrological benchmarking of noisy random quantum circuits without computing ideal output probabilities.
Random quantum circuits aim to efficiently reproduce the statistical properties of ideal random quantum evolution. One approach is to construct approximate unitary designs, which match the moments of Haar-random unitaries up to a prescribed order with controlled error. We establish quantitative guarantees for how accurately these designs reproduce the distribution of each output probability. We show that, for every strong ε\varepsilonε-approximate unitary kkk-design on nnn qubits, the distribution of each output probability is within O(k−1/2(1+k/2n)−1/2+ε)O(k^{-1/2}(1+k/2^n)^{-1/2}+\varepsilon)O(k−1/2(1+k/2n)−1/2+ε) in Kolmogorov distance of the Porter-Thomas distribution, a beta distribution with parameters 111 and 2n−12^n-12n−1. This bound is optimal up to constant factors, implying that a substantially better uniform bound requires additional structure. We then show that a mild form of local invariance suffices. We prove that any such design that is invariant under unitary translations acting on a single qubit approximates Porter-Thomas to total variation distance O(k−1/2+ε)O(k^{-1/2}+\varepsilon)O(k−1/2+ε). Every strong ε\varepsilonε-approximate unitary kkk-design invariant on log⁡k+O(1)\log k+O(1)logk+O(1) qubits achieves error 2−Ω(k)+O(ε)2^{-Ω(k)}+O(\varepsilon)2−Ω(k)+O(ε) in Kolmogorov distance and 2−Ω(k)+O(εlog⁡(2/ε))2^{-Ω(k)}+O(\varepsilon\log(2/\varepsilon))2−Ω(k)+O(εlog(2/ε)) in total variation distance. These results identify the distributional accuracy guaranteed by moment matching and the structure that improves it. As an application, we show that the Shannon entropy of the output distribution of a strong ε\varepsilonε-approximate kkk-design is concentrated around its Haar value n−Θ(1)n-Θ(1)n−Θ(1): its mean differs from the Haar mean by O(k−1/4+ε1/2)O(k^{-1/4}+\varepsilon^{1/2})O(k−1/4+ε1/2) and its standard deviation is O(2−n/2+k−1/8+ε1/4)O(2^{-n/2}+k^{-1/8}+\varepsilon^{1/4})O(2−n/2+k−1/8+ε1/4). Consequently, a trusted device sampling such circuits generates n−O(1)n-O(1)n−O(1) bits of entropy per sample, which makes them useful for random number generation.
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.
The recent paper [F. Arute et al. Nature {\bf 574}, 505 (2019)] considered exact classical sampling of the output probability distribution of the globally depolarized random quantum circuit. In this paper, we show three results. First, we consider the case when the fidelity FFF is constant. We show that if the distribution is classically sampled in polynomial time within a constant multiplicative error, then BQP⊆SBP{\rm BQP}\subseteq{\rm SBP}BQP⊆SBP, which means that BQP is in the second level of the polynomial-time hierarchy. We next show that for any F≤1/2F\le1/2F≤1/2, the distribution is classically trivially sampled by the uniform distribution within the multiplicative error F2n+2F2^{n+2}F2n+2, where nnn is the number of qubits. We finally show that for any FFF, the distribution is classically trivially sampled by the uniform distribution within the additive error 2F2F2F. These last two results show that if we consider realistic cases, both F∼2−mF\sim2^{-m}F∼2−m and m≫nm\gg nm≫n, or at least F∼2−mF\sim2^{-m}F∼2−m, where mmm is the number of gates, quantum supremacy does not exist for approximate sampling even with the exponentially-small errors. We also argue that if F∼2−mF\sim2^{-m}F∼2−m and m≫nm\gg nm≫n, the standard approach will not work to show quantum supremacy even for exact sampling.