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

Improved robustness of quantum supremacy for random circuit sampling

Y. Kondo, Ryuhei Mori, Ramis Movassagh

Published Feb 3, 2021• 5 citations
OpenAlex

Abstract

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.

Related papers

Fine-grained analysis and improved robustness of quantum supremacy for random circuit sampling

Y. Kondo, Ryuhei Mori, Ramis Movassagh

We prove under the complexity theoretical assumption of the non-collapse of the polynomial hierarchy that estimating 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 estimating the output probabilities to within $2^{-\Omega(n\log{n})}$ is hard, and for circuits of depth $\sqrt{n}$, for which the anti-concentration property holds, estimating the output probabilities to within $2^{-\Omega(n^{3/2}\log n)}$ is hard. We prove these results from first principles and 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

Quantum supremacy and hardness of estimating output probabilities of quantum circuits

Yasuhiro 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 #P-hard under BPPNPreduction. 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}$[1]. 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 then show that the hardness results extend to any open neighborhood of an arbitrary (fixed) circuit including the trivial circuit with identity gates. 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.

arXiv:2102.01960•Annual Symposium on Foundations of Computer Science•Feb 1, 2022•15 citations

Quantum supremacy and random circuits

Ramis Movassagh

As Moore's law reaches its limits, quantum computers are emerging with the promise of dramatically outperforming classical computers. We have witnessed the advent of quantum processors with over $50$ quantum bits (qubits), which are expected to be beyond the reach of classical simulation. Quantum supremacy is the event at which the old Extended Church-Turing Thesis is overturned: A quantum computer performs a task that is practically impossible for any classical (super)computer. The demonstration requires both a solid theoretical guarantee and an experimental realization. The lead candidate is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of random quantum circuits. Google recently announced a $53-$qubit experimental demonstration of RCS. Soon after, classical algorithms appeared that challenge the supremacy of random circuits by estimating their outputs. How hard is it to classically simulate the output of random quantum circuits? We prove that estimating the output probabilities of random quantum circuits is formidably hard ($\#P$-Hard) for any classical computer. This makes RCS the strongest candidate for demonstrating quantum supremacy relative to all other proposals. The robustness to the estimation error that we prove may serve as a new hardness criterion for the performance of classical algorithms. To achieve this, we introduce the Cayley path interpolation between any two gates of a quantum computation and convolve recent advances in quantum complexity and information with probability and random matrices. Furthermore, we apply algebraic geometry to generalize the well-known Berlekamp-Welch algorithm that is widely used in coding theory and cryptography. Our results imply that there is an exponential hardness barrier for the classical simulation of most quantum circuits.

arXiv:1909.06210•Sep 11, 2019•23 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

Average-case hardness of estimating probabilities of random quantum circuits with a linear scaling in the error exponent

Hari Krovi

We consider the hardness of computing additive approximations to output probabilities of random quantum circuits. We consider three random circuit families, namely, Haar random, $p=1$ QAOA, and random IQP circuits. Our results are as follows. For Haar random circuits with $m$ gates, we improve on prior results by showing $\mathsf{coC_=P}$ hardness of average-case additive approximations to an imprecision of $2^{-O(m)}$. Efficient classical simulation of such problems would imply the collapse of the polynomial hierarchy. For constant depth circuits i.e., when $m=O(n)$, this linear scaling in the exponent is within a constant of the scaling required to show hardness of sampling. Prior to our work, such a result was shown only for Boson Sampling in Bouland et al (2021). We also use recent results in polynomial interpolation to show $\mathsf{coC_=P}$ hardness under $\mathsf{BPP}$ reductions rather than $\mathsf{BPP}^{\mathsf{NP}}$ reductions. This improves the results of prior work for Haar random circuits both in terms of the error scaling and the power of reductions. Next, we consider random $p=1$ QAOA and IQP circuits and show that in the average-case, it is $\mathsf{coC_=P}$ hard to approximate the output probability to within an additive error of $2^{-O(n)}$. For $p=1$ QAOA circuits, this work constitutes the first average-case hardness result for the problem of approximating output probabilities for random QAOA circuits, which include Sherrington-Kirkpatrick and Erdös-Renyi graphs. For IQP circuits, a consequence of our results is that approximating the Ising partition function with imaginary couplings to an additive error of $2^{-O(n)}$ is hard even in the average-case, which extends prior work on worst-case hardness of multiplicative approximation to Ising partition functions.

arXiv:2206.05642•Jun 12, 2022•2 citations

Efficient unitary paths and quantum computational supremacy: A proof of average-case hardness of Random Circuit Sampling

Ramis Movassagh

One-parameter interpolations between any two unitary matrices (e.g., quantum gates) $U_1$ and $U_2$ along efficient paths contained in the unitary group are constructed. Motivated by applications, we propose the continuous unitary path $U(θ)$ obtained from the QR-factorization \[ U(θ)R(θ)=(1-θ)A+θB, \] where $U_1 R_1=A$ and $U_2 R_2=B$ are the QR-factorizations of $A$ and $B$, and $U(θ)$ is a unitary for all $θ$ with $U(0)=U_1$ and $U(1)=U_2$. The QR-algorithm is modified to, instead of $U(θ)$, output a matrix whose columns are proportional to the corresponding columns of $U(θ)$ and whose entries are polynomial or rational functions of $θ$. By an extension of the Berlekamp-Welch algorithm we show that rational functions can be efficiently and exactly interpolated with respect to $θ$. We then construct probability distributions over unitaries that are arbitrarily close to the Haar measure. Demonstration of computational advantages of NISQ over classical computers is an imperative near-term goal, especially with the exuberant experimental frontier in academia and industry (e.g., IBM and Google). A candidate for quantum computational supremacy is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of a random circuit. The aforementioned mathematical results provide a new way of scrambling quantum circuits and are applied to prove that exact RCS is $\#P$-Hard on average, which is a simpler alternative to Bouland et al's. (Dis)Proving the quantum supremacy conjecture requires "approximate" average case hardness; this remains an open problem for all quantum supremacy proposals.

arXiv:1810.04681•Oct 10, 2018•13 citations
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 prove under the complexity theoretical assumption of the non-collapse of the polynomial hierarchy that estimating 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 n−n-n−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 estimating the output probabilities to within 2−Ω(nlog⁡n)2^{-\Omega(n\log{n})}2−Ω(nlogn) is hard, and for circuits of depth n\sqrt{n}n​, for which the anti-concentration property holds, estimating the output probabilities to within 2−Ω(n3/2log⁡n)2^{-\Omega(n^{3/2}\log n)}2−Ω(n3/2logn) is hard. We prove these results from first principles and do not use the standard techniques such as the Berlekamp--Welch algorithm, the usual Paturi's lemma, and Rakhmanov's result.
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 withinexp⁡(−Ω(mlog⁡m))\exp(-\Omega(m\log m))exp(−Ω(mlogm))additive error is hard for any classical computer, wheremmmis the number of gates in the quantum computation. More precisely, we show that the above problem is #P-hard under BPPNPreduction. In the recent experiments, the quantum circuit has n-qubits and the architecture is a two-dimensional grid of sizen×n\sqrt{n}\times\sqrt{n}n​×n​[1]. Indeed for constant depth circuits approximating the output probabilities to within2−Ω(nlog⁡n)2^{-\Omega(n\log n)}2−Ω(nlogn)is hard. For circuits of depthlog⁡n\log nlognorn\sqrt{n}n​for which the anti-concentration property holds, approximating the output probabilities to within2−Ω(nlog⁡2n)2^{-\Omega(n\log^{2}n)}2−Ω(nlog2n)and2−Ω(n3/2log⁡n)2^{-\Omega(n^{3/2}\log n)}2−Ω(n3/2logn)is hard respectively. We then show that the hardness results extend to any open neighborhood of an arbitrary (fixed) circuit including the trivial circuit with identity gates. 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.
As Moore's law reaches its limits, quantum computers are emerging with the promise of dramatically outperforming classical computers. We have witnessed the advent of quantum processors with over 505050 quantum bits (qubits), which are expected to be beyond the reach of classical simulation. Quantum supremacy is the event at which the old Extended Church-Turing Thesis is overturned: A quantum computer performs a task that is practically impossible for any classical (super)computer. The demonstration requires both a solid theoretical guarantee and an experimental realization. The lead candidate is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of random quantum circuits. Google recently announced a 53−53-53−qubit experimental demonstration of RCS. Soon after, classical algorithms appeared that challenge the supremacy of random circuits by estimating their outputs. How hard is it to classically simulate the output of random quantum circuits? We prove that estimating the output probabilities of random quantum circuits is formidably hard (#P\#P#P-Hard) for any classical computer. This makes RCS the strongest candidate for demonstrating quantum supremacy relative to all other proposals. The robustness to the estimation error that we prove may serve as a new hardness criterion for the performance of classical algorithms. To achieve this, we introduce the Cayley path interpolation between any two gates of a quantum computation and convolve recent advances in quantum complexity and information with probability and random matrices. Furthermore, we apply algebraic geometry to generalize the well-known Berlekamp-Welch algorithm that is widely used in coding theory and cryptography. Our results imply that there is an exponential hardness barrier for the classical simulation of most quantum circuits.
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.
We consider the hardness of computing additive approximations to output probabilities of random quantum circuits. We consider three random circuit families, namely, Haar random, p=1p=1p=1 QAOA, and random IQP circuits. Our results are as follows. For Haar random circuits with mmm gates, we improve on prior results by showing coC=P\mathsf{coC_=P}coC=​P hardness of average-case additive approximations to an imprecision of 2−O(m)2^{-O(m)}2−O(m). Efficient classical simulation of such problems would imply the collapse of the polynomial hierarchy. For constant depth circuits i.e., when m=O(n)m=O(n)m=O(n), this linear scaling in the exponent is within a constant of the scaling required to show hardness of sampling. Prior to our work, such a result was shown only for Boson Sampling in Bouland et al (2021). We also use recent results in polynomial interpolation to show coC=P\mathsf{coC_=P}coC=​P hardness under BPP\mathsf{BPP}BPP reductions rather than BPPNP\mathsf{BPP}^{\mathsf{NP}}BPPNP reductions. This improves the results of prior work for Haar random circuits both in terms of the error scaling and the power of reductions. Next, we consider random p=1p=1p=1 QAOA and IQP circuits and show that in the average-case, it is coC=P\mathsf{coC_=P}coC=​P hard to approximate the output probability to within an additive error of 2−O(n)2^{-O(n)}2−O(n). For p=1p=1p=1 QAOA circuits, this work constitutes the first average-case hardness result for the problem of approximating output probabilities for random QAOA circuits, which include Sherrington-Kirkpatrick and Erdös-Renyi graphs. For IQP circuits, a consequence of our results is that approximating the Ising partition function with imaginary couplings to an additive error of 2−O(n)2^{-O(n)}2−O(n) is hard even in the average-case, which extends prior work on worst-case hardness of multiplicative approximation to Ising partition functions.
One-parameter interpolations between any two unitary matrices (e.g., quantum gates) U1U_1U1​ and U2U_2U2​ along efficient paths contained in the unitary group are constructed. Motivated by applications, we propose the continuous unitary path U(θ)U(θ)U(θ) obtained from the QR-factorization U(θ)R(θ)=(1−θ)A+θB, U(θ)R(θ)=(1-θ)A+θB, U(θ)R(θ)=(1−θ)A+θB, where U1R1=AU_1 R_1=AU1​R1​=A and U2R2=BU_2 R_2=BU2​R2​=B are the QR-factorizations of AAA and BBB, and U(θ)U(θ)U(θ) is a unitary for all θθθ with U(0)=U1U(0)=U_1U(0)=U1​ and U(1)=U2U(1)=U_2U(1)=U2​. The QR-algorithm is modified to, instead of U(θ)U(θ)U(θ), output a matrix whose columns are proportional to the corresponding columns of U(θ)U(θ)U(θ) and whose entries are polynomial or rational functions of θθθ. By an extension of the Berlekamp-Welch algorithm we show that rational functions can be efficiently and exactly interpolated with respect to θθθ. We then construct probability distributions over unitaries that are arbitrarily close to the Haar measure. Demonstration of computational advantages of NISQ over classical computers is an imperative near-term goal, especially with the exuberant experimental frontier in academia and industry (e.g., IBM and Google). A candidate for quantum computational supremacy is Random Circuit Sampling (RCS), which is the task of sampling from the output distribution of a random circuit. The aforementioned mathematical results provide a new way of scrambling quantum circuits and are applied to prove that exact RCS is #P\#P#P-Hard on average, which is a simpler alternative to Bouland et al's. (Dis)Proving the quantum supremacy conjecture requires "approximate" average case hardness; this remains an open problem for all quantum supremacy proposals.