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:2410.20935 · Leibniz international proceedings in informatics

Improved Separation Between Quantum and Classical Computers for Sampling and Functional Tasks

Marshall, Simon C., Scott Aaronson, Vedran Dunjko

Published Oct 28, 2024• 14 citations
arXivHTMLPDF

Abstract

This paper furthers existing evidence that quantum computers are capable of computations beyond classical computers. Specifically, we strengthen the collapse of the polynomial hierarchy to the second level if: (i) Quantum computers with postselection are as powerful as classical computers with postselection ($\mathsf{PostBQP=PostBPP}$), (ii) any one of several quantum sampling experiments ($\mathsf{BosonSampling}$, $\mathsf{IQP}$, $\mathsf{DQC1}$) can be approximately performed by a classical computer (contingent on existing assumptions). This last result implies that if any of these experiment's hardness conjectures hold, then quantum computers can implement functions classical computers cannot ($\mathsf{FBQP\neq FBPP}$) unless the polynomial hierarchy collapses to its 2nd level. These results are an improvement over previous work which either achieved a collapse to the third level or were concerned with exact sampling, a physically impractical case. The workhorse of these results is a new technical complexity-theoretic result which we believe could have value beyond quantum computation. In particular, we prove that if there exists an equivalence between problems solvable with an exact counting oracle and problems solvable with an approximate counting oracle, then the polynomial hierarchy collapses to its second level, indeed to $\mathsf{ZPP^{NP}}$.

DOI
10.4230/lipics.ccc.2025.5

Related papers

Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy

Michael J. Bremner, Richard Jozsa, Dan J. Shepherd

We consider quantum computations comprising only commuting gates, known as IQP computations, and provide compelling evidence that the task of sampling their output probability distributions is unlikely to be achievable by any efficient classical means. More specifically, we introduce the class post-IQP of languages decided with bounded error by uniform families of IQP circuits with post-selection, and prove first that post-IQP equals the classical class PP. Using this result we show that if the output distributions of uniform IQP circuit families could be classically efficiently sampled, either exactly in total variation distance or even approximately up to 41 per cent multiplicative error in the probabilities, then the infinite tower of classical complexity classes known as the polynomial hierarchy would collapse to its third level. We mention some further results on the classical simulation properties of IQP circuit families, in particular showing that if the output distribution results from measurements on only lines then it may, in fact, be classically efficiently sampled.

arXiv:1005.1407•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Aug 11, 2010•465 citations

The Power of Quantum Fourier Sampling

Bill Fefferman, Christopher Umans

How powerful are Quantum Computers? Despite the prevailing belief that Quantum Computers are more powerful than their classical counterparts, this remains a conjecture backed by little formal evidence. Shor's famous factoring algorithm [Shor97] gives an example of a problem that can be solved efficiently on a quantum computer with no known efficient classical algorithm. Factoring, however, is unlikely to be NP-Hard, meaning that few unexpected formal consequences would arise, should such a classical algorithm be discovered. Could it then be the case that any quantum algorithm can be simulated efficiently classically? Likewise, could it be the case that Quantum Computers can quickly solve problems much harder than factoring? If so, where does this power come from, and what classical computational resources do we need to solve the hardest problems for which there exist efficient quantum algorithms? We make progress toward understanding these questions through studying the relationship between classical nondeterminism and quantum computing. In particular, is there a problem that can be solved efficiently on a Quantum Computer that cannot be efficiently solved using nondeterminism? In this thesis we address this problem from the perspective of sampling problems. Namely, we give evidence that approximately sampling the Quantum Fourier Transform of an efficiently computable function, while easy quantumly, is hard for any classical machine in the Polynomial Time Hierarchy. In particular, we prove the existence of a class of distributions that can be sampled efficiently by a Quantum Computer, that likely cannot be approximately sampled in randomized polynomial time with an oracle for the Polynomial Time Hierarchy. Our work complements and generalizes the evidence given in Aaronson and Arkhipov's work [AA2013] where a different distribution with the same computational properties was given. Our result is more general than theirs, but requires a more powerful quantum sampler.

Conference on Theory of Quantum Computation, Communication and Cryptography•Jan 1, 2016•8 citations

Complexity-Theoretic Foundations of Quantum Supremacy Experiments

Scott Aaronson, Lijie Chen

Depending on time, I'll discuss some subset of the following results. (1) There exists an oracle relative to which classical and quantum computers can solve the same approximate sampling problems in polynomial time, and yet the polynomial hierarchy is infinite. This means that any "BosonSampling-type theorem" will need to be non-relativizing. (2) Can P be separated from BQP by an efficiently-computable oracle (one in P/poly)? Yes if quantum-resistant one-way functions exist; no if P=PSPACE. The latter builds on recent results in quantum query complexity by myself and Shalev Ben-David. (3) How hard is it to approximately sample the output distribution of a random quantum circuit? One can do it (and even calculate the probabilities) in polynomial space and m^O(n) time, where m is the number of gates and n is the number of qubits. But if that's essentially optimal for estimating probabilities, then approximate sampling also requires exponential time. Joint work with Lijie Chen (Tsinghua University)

arXiv:1612.05903•Leibniz international proceedings in informatics•Dec 18, 2016•400 citations

Classical Verification of Quantum Computation Beyond the Polynomial Hierarchy

Atul Mantri

It is not known whether a classical polynomial-time verifier can verify arbitrary polynomial-time quantum computations with an efficient quantum honest prover without computational assumptions. We show that, relative to a classical oracle, such verification is possible for a language beyond the polynomial hierarchy that is decided exactly in quantum polynomial time. The protocol is public-coin, with perfect completeness and soundness error at most 1/4. To our knowledge, no language with such a proof system was previously proved to lie outside AM relative to an oracle. For every unbounded polynomial-time computable function, the oracle can be chosen so that the message count and the oracle query counts of the quantum algorithm, verifier, and honest prover are bounded by this function of the input length. The message count is optimal up to a constant factor, since for a suitable oracle every interactive proof system for the language uses at least a constant fraction of the messages of our protocol on infinitely many lengths, with a constant depending on its verifier. The language is a variant of recursive Fourier sampling in which code tables encode secrets that address data tables. The tables are evaluated recursively, and the oracle stores only the leaves. The quantum algorithm recovers every secret exactly, and the verifier checks the prover's secrets recursively against random code entries. The recursion restricts the input in a correlated way, as the same secret fixes the code bits and chooses the free coordinate, so Håstad's switching lemma does not apply. We prove a switching theorem for these restrictions, which may be of independent interest. For instances of sufficient height, no constant-depth circuit of size $2^{\mathrm{poly}(n)}$ changes its output with probability above $2^{-Ω(n)}$ when the answer of a random instance is flipped by changing a single leaf.

quant-pharXiv:2610.37635•Oct 28, 2026•2 citations

Quantum supremacy and high-dimensional integration

Juan Miguel Arrazola, Patrick Rebentrost, Christian Weedbrook

We establish a connection between continuous-variable quantum computing and high-dimensional integration by showing that the outcome probabilities of continuous-variable instantaneous quantum polynomial (CV-IQP) circuits are given by integrals of oscillating functions in large dimensions. We prove two results related to the classical hardness of evaluating these integrals: (i) we show that there exist circuits such that these integrals are approximations of a weighted sum of #P-hard problems and (ii) we prove that calculating these integrals is as hard as calculating integrals of arbitrary bounded functions. We then leverage these results to show that, given a plausible conjecture about the hardness of computing the integrals, approximate sampling from CV-IQP circuits cannot be done in polynomial time on a classical computer unless the polynomial hierarchy collapses to the third level. Our results hold even in the presence of finite squeezing and limited measurement precision, without an explicit need for fault-tolerance.

arXiv:1712.07288•Dec 20, 2017•15 citations

Improved robustness of quantum supremacy for random circuit sampling

Y. 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 $\#\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.

•Feb 3, 2021•6 citations
This paper furthers existing evidence that quantum computers are capable of computations beyond classical computers. Specifically, we strengthen the collapse of the polynomial hierarchy to the second level if: (i) Quantum computers with postselection are as powerful as classical computers with postselection (PostBQP=PostBPP\mathsf{PostBQP=PostBPP}PostBQP=PostBPP), (ii) any one of several quantum sampling experiments (BosonSampling\mathsf{BosonSampling}BosonSampling, IQP\mathsf{IQP}IQP, DQC1\mathsf{DQC1}DQC1) can be approximately performed by a classical computer (contingent on existing assumptions). This last result implies that if any of these experiment's hardness conjectures hold, then quantum computers can implement functions classical computers cannot (FBQP≠FBPP\mathsf{FBQP\neq FBPP}FBQP=FBPP) unless the polynomial hierarchy collapses to its 2nd level. These results are an improvement over previous work which either achieved a collapse to the third level or were concerned with exact sampling, a physically impractical case. The workhorse of these results is a new technical complexity-theoretic result which we believe could have value beyond quantum computation. In particular, we prove that if there exists an equivalence between problems solvable with an exact counting oracle and problems solvable with an approximate counting oracle, then the polynomial hierarchy collapses to its second level, indeed to ZPPNP\mathsf{ZPP^{NP}}ZPPNP.
We consider quantum computations comprising only commuting gates, known as IQP computations, and provide compelling evidence that the task of sampling their output probability distributions is unlikely to be achievable by any efficient classical means. More specifically, we introduce the class post-IQP of languages decided with bounded error by uniform families of IQP circuits with post-selection, and prove first that post-IQP equals the classical class PP. Using this result we show that if the output distributions of uniform IQP circuit families could be classically efficiently sampled, either exactly in total variation distance or even approximately up to 41 per cent multiplicative error in the probabilities, then the infinite tower of classical complexity classes known as the polynomial hierarchy would collapse to its third level. We mention some further results on the classical simulation properties of IQP circuit families, in particular showing that if the output distribution results from measurements on only lines then it may, in fact, be classically efficiently sampled.
How powerful are Quantum Computers? Despite the prevailing belief that Quantum Computers are more powerful than their classical counterparts, this remains a conjecture backed by little formal evidence. Shor's famous factoring algorithm [Shor97] gives an example of a problem that can be solved efficiently on a quantum computer with no known efficient classical algorithm. Factoring, however, is unlikely to be NP-Hard, meaning that few unexpected formal consequences would arise, should such a classical algorithm be discovered. Could it then be the case that any quantum algorithm can be simulated efficiently classically? Likewise, could it be the case that Quantum Computers can quickly solve problems much harder than factoring? If so, where does this power come from, and what classical computational resources do we need to solve the hardest problems for which there exist efficient quantum algorithms? We make progress toward understanding these questions through studying the relationship between classical nondeterminism and quantum computing. In particular, is there a problem that can be solved efficiently on a Quantum Computer that cannot be efficiently solved using nondeterminism? In this thesis we address this problem from the perspective of sampling problems. Namely, we give evidence that approximately sampling the Quantum Fourier Transform of an efficiently computable function, while easy quantumly, is hard for any classical machine in the Polynomial Time Hierarchy. In particular, we prove the existence of a class of distributions that can be sampled efficiently by a Quantum Computer, that likely cannot be approximately sampled in randomized polynomial time with an oracle for the Polynomial Time Hierarchy. Our work complements and generalizes the evidence given in Aaronson and Arkhipov's work [AA2013] where a different distribution with the same computational properties was given. Our result is more general than theirs, but requires a more powerful quantum sampler.
Depending on time, I'll discuss some subset of the following results. (1) There exists an oracle relative to which classical and quantum computers can solve the same approximate sampling problems in polynomial time, and yet the polynomial hierarchy is infinite. This means that any "BosonSampling-type theorem" will need to be non-relativizing. (2) Can P be separated from BQP by an efficiently-computable oracle (one in P/poly)? Yes if quantum-resistant one-way functions exist; no if P=PSPACE. The latter builds on recent results in quantum query complexity by myself and Shalev Ben-David. (3) How hard is it to approximately sample the output distribution of a random quantum circuit? One can do it (and even calculate the probabilities) in polynomial space and m^O(n) time, where m is the number of gates and n is the number of qubits. But if that's essentially optimal for estimating probabilities, then approximate sampling also requires exponential time. Joint work with Lijie Chen (Tsinghua University)
It is not known whether a classical polynomial-time verifier can verify arbitrary polynomial-time quantum computations with an efficient quantum honest prover without computational assumptions. We show that, relative to a classical oracle, such verification is possible for a language beyond the polynomial hierarchy that is decided exactly in quantum polynomial time. The protocol is public-coin, with perfect completeness and soundness error at most 1/4. To our knowledge, no language with such a proof system was previously proved to lie outside AM relative to an oracle. For every unbounded polynomial-time computable function, the oracle can be chosen so that the message count and the oracle query counts of the quantum algorithm, verifier, and honest prover are bounded by this function of the input length. The message count is optimal up to a constant factor, since for a suitable oracle every interactive proof system for the language uses at least a constant fraction of the messages of our protocol on infinitely many lengths, with a constant depending on its verifier. The language is a variant of recursive Fourier sampling in which code tables encode secrets that address data tables. The tables are evaluated recursively, and the oracle stores only the leaves. The quantum algorithm recovers every secret exactly, and the verifier checks the prover's secrets recursively against random code entries. The recursion restricts the input in a correlated way, as the same secret fixes the code bits and chooses the free coordinate, so Håstad's switching lemma does not apply. We prove a switching theorem for these restrictions, which may be of independent interest. For instances of sufficient height, no constant-depth circuit of size 2poly(n)2^{\mathrm{poly}(n)}2poly(n) changes its output with probability above 2−Ω(n)2^{-Ω(n)}2−Ω(n) when the answer of a random instance is flipped by changing a single leaf.
We establish a connection between continuous-variable quantum computing and high-dimensional integration by showing that the outcome probabilities of continuous-variable instantaneous quantum polynomial (CV-IQP) circuits are given by integrals of oscillating functions in large dimensions. We prove two results related to the classical hardness of evaluating these integrals: (i) we show that there exist circuits such that these integrals are approximations of a weighted sum of #P-hard problems and (ii) we prove that calculating these integrals is as hard as calculating integrals of arbitrary bounded functions. We then leverage these results to show that, given a plausible conjecture about the hardness of computing the integrals, approximate sampling from CV-IQP circuits cannot be done in polynomial time on a classical computer unless the polynomial hierarchy collapses to the third level. Our results hold even in the presence of finite squeezing and limited measurement precision, without an explicit need for fault-tolerance.
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.