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

Fourier analysis of sampling from noisy chaotic quantum circuits

Sergio Boixo, Vadim Smelyanskiy, Hartmut Neven

Published Aug 6, 2017• 28 citations
arXivHTMLPDF

Abstract

Sampling from the output distribution of chaotic quantum evolutions, and of pseudo-random universal quantum circuits in particular, has been proposed as a prominent milestone for near-term quantum supremacy. The same paper notes that chaotic distributions are very sensitive to noise, and under quite general noise models converge to the uniform distribution over bit-strings exponentially in the number of gates. On the one hand, for increasing number of gates, it suffices to choose bit-strings at random to approximate the noisy distribution with fixed statistical distance. On the other hand, cross-entropy benchmarking can be used to gauge the fidelity of an experiment, and the distance to the uniform distribution. We estimate that state-of-the-art classical supercomputers would fail to simulate high-fidelity chaotic quantum circuits with approximately fifty qubits and depth forty. A recent interesting paper proposed a different approximation algorithm to a noisy distribution, extending previous results on the Fourier analysis of commuting quantum circuits. Using the statistical properties of the Porter-Thomas distribution, we show that this new approximation algorithm does not improve random guessing, in polynomial time. Therefore, it confirms previous results and does not represent an additional challenge to the suggested failure stated above.

DOI
10.48550/arxiv.1708.01875

Related papers

Local random quantum circuits converge to the Porter-Thomas distribution in polynomial depth

Aniruddha Sen, Nicholas Hunter-Jones

Porter-Thomas statistics are a characteristic feature of the output distribution of random quantum states and, more broadly, chaotic quantum many-body systems. Convergence to Porter-Thomas plays a central role in random circuit sampling and experimental demonstrations of quantum advantage, where the output statistics of low-depth random quantum circuits are expected to be approximately Porter-Thomas, despite the absence of a rigorous proof of convergence. We show that the output distribution of polynomial-depth brickwork random circuits converges inverse-polynomially in total variation distance to the Porter-Thomas distribution. Specifically, consider the output probability distribution over a fixed bitstring of a local random quantum circuit, constructed from nearest-neighbor Haar random gates. Then, for any $m \geq 0$, the distribution corresponding to circuits of depth $O(n^{2m+1}\log(n))$ is at most $O(1/n^m)$ far in total variation distance from the Porter-Thomas distribution. Our proof uses moment bounds from approximate designs, analytic estimates for characteristic functions, and a local anticoncentration property for inverse moments.

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

Can Chaotic Quantum Circuits Maintain Quantum Supremacy under Noise?

Man‐Hong Yung, Xun Gao

Although the emergence of a fully-functional quantum computer may still be far away from today, in the near future, it is possible to have medium-size, special-purpose, quantum devices that can perform computational tasks not efficiently simulable with any classical computer. This status is known as quantum supremacy (or quantum advantage), where one of the promising approaches is through the sampling of chaotic quantum circuits. Sampling of ideal chaotic quantum circuits has been argued to require an exponential time for classical devices. A major question is whether quantum supremacy can be maintained under noise without error correction, as the implementation of fault-tolerance would cost lots of extra qubits and quantum gates. Here we show that, for a family of chaotic quantum circuits subject to Pauli errors, there exists an non-exponential classical algorithm capable of simulating the noisy chaotic quantum circuits with bounded errors. This result represents a serious challenge to a previous result in the literature suggesting the failure of classical devices in simulating noisy chaotic circuits with about 48 qubits and depth 25. Moreover, even though our model does not cover all types of experimental errors, from a practical point view, our result describes a well-defined setting where quantum supremacy can be tested against the challenges of classical rivals, in the context of chaotic quantum circuits.

arXiv:1706.08913•Jun 27, 2017•20 citations

Statistical analysis on random quantum circuit sampling by Sycamore and Zuchongzhi quantum processors

Sangchul Oh, Sabre Kais

Random quantum circuit sampling, a task to sample bit strings from a random quantum circuit, is considered a suitable benchmark task to demonstrate the outperformance of quantum computers even with noisy qubits. Recently, random quantum circuit sampling was performed on the Sycamore quantum processor with 53 qubits [Nature (London) 574, 505 (2019)] and on the Zuchongzhi quantum processor with 56 qubits [Phys. Rev. Lett. 127, 180501 (2021)]. Here, we analyze and compare the statistical properties of the outputs of the random quantum circuit sampling by the Sycamore and Zuchongzhi processors. Using the Marchenko-Pastur law of random matrices of bit strings and the Wasssertein distances between bit strings, we find that the statistical properties of Sycamore bit strings are quite different from those of Zuchongzhi bit strings, while both processors score similar values of linear cross-entropy fidelity for random circuit sampling. Some bit strings sampled by the Zuchongzhi processor pass the NIST random number tests while both Sycamore and Zuchongzhi processors show similar patterns in the heat maps of bit strings. Zuchongzhi bit strings are much closer to classical uniform random bits than those of Sycamore. It is shown that the statistical properties of bit strings of both random quantum circuits change little as the depth of the random quantum circuits increases. Our findings raise a question about the computational reliability of noisy quantum processors because two quantum processors with similar noise levels and similar qubit structures produced statistically different outputs for the same random quantum circuit sampling.

arXiv:2204.05875•Physical Review A•Sep 28, 2022•4 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

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

Sampling (noisy) quantum circuits through randomized rounding

Victor Martinez, Omar Fawzi, Daniel Stilck França

The present era of quantum processors with hundreds to thousands of noisy qubits has sparked interest in understanding the computational power of these devices and how to leverage it to solve practically relevant problems. For applications that require estimating expectation values of observables the community developed a good understanding of how to simulate them classically and denoise them. Certain applications, like combinatorial optimization, however demand more than expectation values: the bit-strings themselves encode the candidate solutions. While recent impossibility and threshold results indicate that noisy samples alone rarely beat classical heuristics, we still lack classical methods to replicate those noisy samples beyond the setting of random quantum circuits.Focusing on problems whose objective depends only on two-body correlations such as Max-Cut, we show that Gaussian randomized rounding in the spirit of Goemans-Williamson applied to the circuit's two-qubit marginals produces a distribution whose expected cost is provably close to that of the noisy quantum device. For instance, for Max-Cut problems we show that for any depth-D circuit affected by local depolarizing noise p, our sampler achieves a recovery ratio 1 − O [ ( 1 − p ) D ] , giving ways to efficiently sample from a distribution that behaves similarly to the noisy circuit for the problem at hand. Beyond theory we run large-scale simulations and experiments on IBMQ hardware, confirming that the rounded samples faithfully reproduce the full energy distribution, and we show similar behaviour under other various noise models. Our results supply a simple classical surrogate for sampling noisy optimization circuits, clarify the realistic power of near-term hardware for combinatorial tasks, and provide a quantitative benchmark for future error-mitigated or fault-tolerant demonstrations of quantum advantage.

arXiv:2507.21883•Quantum•Apr 15, 2026•1 citation
Sampling from the output distribution of chaotic quantum evolutions, and of pseudo-random universal quantum circuits in particular, has been proposed as a prominent milestone for near-term quantum supremacy. The same paper notes that chaotic distributions are very sensitive to noise, and under quite general noise models converge to the uniform distribution over bit-strings exponentially in the number of gates. On the one hand, for increasing number of gates, it suffices to choose bit-strings at random to approximate the noisy distribution with fixed statistical distance. On the other hand, cross-entropy benchmarking can be used to gauge the fidelity of an experiment, and the distance to the uniform distribution. We estimate that state-of-the-art classical supercomputers would fail to simulate high-fidelity chaotic quantum circuits with approximately fifty qubits and depth forty. A recent interesting paper proposed a different approximation algorithm to a noisy distribution, extending previous results on the Fourier analysis of commuting quantum circuits. Using the statistical properties of the Porter-Thomas distribution, we show that this new approximation algorithm does not improve random guessing, in polynomial time. Therefore, it confirms previous results and does not represent an additional challenge to the suggested failure stated above.
Porter-Thomas statistics are a characteristic feature of the output distribution of random quantum states and, more broadly, chaotic quantum many-body systems. Convergence to Porter-Thomas plays a central role in random circuit sampling and experimental demonstrations of quantum advantage, where the output statistics of low-depth random quantum circuits are expected to be approximately Porter-Thomas, despite the absence of a rigorous proof of convergence. We show that the output distribution of polynomial-depth brickwork random circuits converges inverse-polynomially in total variation distance to the Porter-Thomas distribution. Specifically, consider the output probability distribution over a fixed bitstring of a local random quantum circuit, constructed from nearest-neighbor Haar random gates. Then, for any m≥0m \geq 0m≥0, the distribution corresponding to circuits of depth O(n2m+1log⁡(n))O(n^{2m+1}\log(n))O(n2m+1log(n)) is at most O(1/nm)O(1/n^m)O(1/nm) far in total variation distance from the Porter-Thomas distribution. Our proof uses moment bounds from approximate designs, analytic estimates for characteristic functions, and a local anticoncentration property for inverse moments.
Although the emergence of a fully-functional quantum computer may still be far away from today, in the near future, it is possible to have medium-size, special-purpose, quantum devices that can perform computational tasks not efficiently simulable with any classical computer. This status is known as quantum supremacy (or quantum advantage), where one of the promising approaches is through the sampling of chaotic quantum circuits. Sampling of ideal chaotic quantum circuits has been argued to require an exponential time for classical devices. A major question is whether quantum supremacy can be maintained under noise without error correction, as the implementation of fault-tolerance would cost lots of extra qubits and quantum gates. Here we show that, for a family of chaotic quantum circuits subject to Pauli errors, there exists an non-exponential classical algorithm capable of simulating the noisy chaotic quantum circuits with bounded errors. This result represents a serious challenge to a previous result in the literature suggesting the failure of classical devices in simulating noisy chaotic circuits with about 48 qubits and depth 25. Moreover, even though our model does not cover all types of experimental errors, from a practical point view, our result describes a well-defined setting where quantum supremacy can be tested against the challenges of classical rivals, in the context of chaotic quantum circuits.
Random quantum circuit sampling, a task to sample bit strings from a random quantum circuit, is considered a suitable benchmark task to demonstrate the outperformance of quantum computers even with noisy qubits. Recently, random quantum circuit sampling was performed on the Sycamore quantum processor with 53 qubits [Nature (London) 574, 505 (2019)] and on the Zuchongzhi quantum processor with 56 qubits [Phys. Rev. Lett. 127, 180501 (2021)]. Here, we analyze and compare the statistical properties of the outputs of the random quantum circuit sampling by the Sycamore and Zuchongzhi processors. Using the Marchenko-Pastur law of random matrices of bit strings and the Wasssertein distances between bit strings, we find that the statistical properties of Sycamore bit strings are quite different from those of Zuchongzhi bit strings, while both processors score similar values of linear cross-entropy fidelity for random circuit sampling. Some bit strings sampled by the Zuchongzhi processor pass the NIST random number tests while both Sycamore and Zuchongzhi processors show similar patterns in the heat maps of bit strings. Zuchongzhi bit strings are much closer to classical uniform random bits than those of Sycamore. It is shown that the statistical properties of bit strings of both random quantum circuits change little as the depth of the random quantum circuits increases. Our findings raise a question about the computational reliability of noisy quantum processors because two quantum processors with similar noise levels and similar qubit structures produced statistically different outputs for the same random quantum circuit sampling.
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.
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.
The present era of quantum processors with hundreds to thousands of noisy qubits has sparked interest in understanding the computational power of these devices and how to leverage it to solve practically relevant problems. For applications that require estimating expectation values of observables the community developed a good understanding of how to simulate them classically and denoise them. Certain applications, like combinatorial optimization, however demand more than expectation values: the bit-strings themselves encode the candidate solutions. While recent impossibility and threshold results indicate that noisy samples alone rarely beat classical heuristics, we still lack classical methods to replicate those noisy samples beyond the setting of random quantum circuits.Focusing on problems whose objective depends only on two-body correlations such as Max-Cut, we show that Gaussian randomized rounding in the spirit of Goemans-Williamson applied to the circuit's two-qubit marginals produces a distribution whose expected cost is provably close to that of the noisy quantum device. For instance, for Max-Cut problems we show that for any depth-D circuit affected by local depolarizing noise p, our sampler achieves a recovery ratio 1 − O [ ( 1 − p ) D ] , giving ways to efficiently sample from a distribution that behaves similarly to the noisy circuit for the problem at hand. Beyond theory we run large-scale simulations and experiments on IBMQ hardware, confirming that the rounded samples faithfully reproduce the full energy distribution, and we show similar behaviour under other various noise models. Our results supply a simple classical surrogate for sampling noisy optimization circuits, clarify the realistic power of near-term hardware for combinatorial tasks, and provide a quantitative benchmark for future error-mitigated or fault-tolerant demonstrations of quantum advantage.