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:quant-ph/0412187 · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences

Quantum computing, postselection, and probabilistic polynomial-time

Scott Aaronson

Published Sep 5, 2005• 360 citations
arXivHTMLPDF

Abstract

I study the class of problems efficiently solvable by a quantum computer, given the ability to ‘postselect’ on the outcomes of measurements. I prove that this class coincides with a classical complexity class called PP, or probabilistic polynomial-time. Using this result, I show that several simple changes to the axioms of quantum mechanics would let us solve PP-complete problems efficiently. The result also implies, as an easy corollary, a celebrated theorem of Beigel, Reingold and Spielman that PP is closed under intersection, as well as a generalization of that theorem due to Fortnow and Reingold. This illustrates that quantum computing can yield new and simpler proofs of major results about classical computation.

DOI
10.1098/rspa.2005.1546

Related papers

Revisiting a limit on efficient quantum computation

Tarsem S. Purewal

In this paper, we offer an exposition of a theorem originally due to Adleman, Demarrais and Huang that shows that the quantum complexity class BQP (Bounded-error Quantum Polynomial time) is contained in the classical counting class PP (Probabilistic Polynomial time). Our proof follows the one given by Fortnow and Rogers that relates quantum computing to counting complexity classes by way of GapP functions. The contribution of this paper is an exposition of an important result that assumes a minimal background in computational complexity theory and no knowledge of quantum mechanics.

ACM Southeast Regional Conference (ACMSE)•Mar 10, 2006•1 citation

Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection

Ryo Hiromasa, Akihiro Mizutani, Yuki Takeuchi +1 more

Abstract We define rewinding operators that invert quantum measurements. Then, we define complexity classes $$\textsf{RwBQP}$$ RwBQP , $$\textsf{CBQP}$$ CBQP , and $$\textsf{AdPostBQP}$$ AdPostBQP as sets of decision problems solvable by polynomial-size quantum circuits with a polynomial number of rewinding operators, cloning operators, and adaptive postselections, respectively. Our main result is that $$\textsf{BPP}^\textsf{PP}\subseteq \textsf{RwBQP}=\textsf{CBQP}=\textsf{AdPostBQP}\subseteq \textsf{PSPACE}$$ BPP PP ⊆ RwBQP = CBQP = AdPostBQP ⊆ PSPACE . As a byproduct of this result, we show that any problem in $$\textsf{PostBQP}$$ PostBQP can be solved with only postselections of events that occur with probabilities polynomially close to one. Under the strongly believed assumption that $$\textsf{BQP}\nsupseteq \textsf{SZK}$$ BQP ⊉ SZK , or the shortest independent vectors problem cannot be efficiently solved with quantum computers, we also show that a single rewinding operator is sufficient to achieve tasks that are intractable for quantum computation. Finally, we show that rewindable Clifford circuits remain classically simulatable, but rewindable instantaneous quantum polynomial time circuits can solve any problem in $$\textsf{PP}$$ PP .

arXiv:2206.05434•Theory of Computing Systems•Jan 17, 2025•5 citations

Power of quantum computing with restricted postselections.

Tomoyuki Morimae, Harumichi Nishimura

We consider restricted versions of ${\rm postBQP}$ where postselection probabilities can be efficiently calculated by classical or quantum computers. We show that such restricted ${\rm postBQP}$ classes are in ${\rm AWPP}(\subseteq{\rm PP}={\rm postBQP})$. This result suggests that postselecting an event with an exponentially small probability does not necessarily boost ${\rm BQP}$ to PP. The best upperbound of ${\rm BQP}$ is ${\rm AWPP}$, and therefore restricted ${\rm postBQP}$ classes are other examples of complexity classes slightly above ${\rm BQP}$. In [C. M. Lee and J. Barrett, arXiv:1412.8671], it was shown that the computational capacity of a general probabilistic theory which satisfies the tomographic locality is in ${\rm AWPP}$. Our result therefore implies that quantum physics with restricted postselections is an example of a super quantum theory which seems to be outside of their general probabilistic theory but its computational capacity is also in ${\rm AWPP}$. Although it is physically natural to expect that such restricted ${\rm postBQP}$ classes are not equivalent to BQP, we show that ${\rm UP}\cap{\rm coUP}$, which is unlikely to be in BQP, is contained in the restricted ${\rm postBQP}$ classes. Finally, we also consider another restricted class of ${\rm postBQP}$, where the postselected probability depends only on the size of inputs. We show that this restricted version is contained in ${\rm APP}$, where ${\rm AWPP}\subseteq{\rm APP}\subseteq{\rm PP}={\rm postBQP}$.

•Jan 31, 2015•1 citation

Quantum computational advantage implies contextuality

Farid Shähandeh

We show that a separation between the class of all problems that can efficiently be solved on a quantum computer and those solvable using probabilistic classical algorithms in polynomial time implies the generalized contextuality of quantum algorithms. Our result subsumes versions of Gottesman-Knill theorem as special cases.

arXiv:2112.00024•Nov 30, 2021•30 citations

Quantum Complexity Theory

Ethan Bernstein, Umesh V. Vazirani

In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing machine in Deutsch's model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97--117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specified. We prove that $O(\log T)$ bits of precision suffice to support a T step computation. This justifies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the first formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class $\BPP$. The class $\BQP$ of languages that are efficiently decidable (with small error-probability) on a quantum Turing machine satisfies $\BPP \subseteq \BQP \subseteq \Ptime^{\SP}$. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.

SIAM Journal on Computing•Oct 1, 1997•1,635 citations

BQP is not in NP

J.T. Librande

Quantum computers are widely believed have an advantage over classical computers, and some have even published some empirical evidence that this is the case. However, these publications do not include a rigorous proof of this advantage, which would have to minimally state that the class of problems decidable by a quantum computer in polynomial time, BQP, contains problems that are not in the class of problems decidable by a classical computer with similar time bounds, P. Here, I provide the proof of a stronger result that implies this result: BQP contains problems that lie beyond the much larger classical computing class NP. This proves that quantum computation is able to efficiently solve problems which are far beyond the capabilities of classical computers.

arXiv:2209.10398•Sep 19, 2022•0 citations
I study the class of problems efficiently solvable by a quantum computer, given the ability to ‘postselect’ on the outcomes of measurements. I prove that this class coincides with a classical complexity class called PP, or probabilistic polynomial-time. Using this result, I show that several simple changes to the axioms of quantum mechanics would let us solve PP-complete problems efficiently. The result also implies, as an easy corollary, a celebrated theorem of Beigel, Reingold and Spielman that PP is closed under intersection, as well as a generalization of that theorem due to Fortnow and Reingold. This illustrates that quantum computing can yield new and simpler proofs of major results about classical computation.
In this paper, we offer an exposition of a theorem originally due to Adleman, Demarrais and Huang that shows that the quantum complexity class BQP (Bounded-error Quantum Polynomial time) is contained in the classical counting class PP (Probabilistic Polynomial time). Our proof follows the one given by Fortnow and Rogers that relates quantum computing to counting complexity classes by way of GapP functions. The contribution of this paper is an exposition of an important result that assumes a minimal background in computational complexity theory and no knowledge of quantum mechanics.
Abstract We define rewinding operators that invert quantum measurements. Then, we define complexity classes RwBQP\textsf{RwBQP}RwBQP RwBQP , CBQP\textsf{CBQP}CBQP CBQP , and AdPostBQP\textsf{AdPostBQP}AdPostBQP AdPostBQP as sets of decision problems solvable by polynomial-size quantum circuits with a polynomial number of rewinding operators, cloning operators, and adaptive postselections, respectively. Our main result is that BPPPP⊆RwBQP=CBQP=AdPostBQP⊆PSPACE\textsf{BPP}^\textsf{PP}\subseteq \textsf{RwBQP}=\textsf{CBQP}=\textsf{AdPostBQP}\subseteq \textsf{PSPACE}BPPPP⊆RwBQP=CBQP=AdPostBQP⊆PSPACE BPP PP ⊆ RwBQP = CBQP = AdPostBQP ⊆ PSPACE . As a byproduct of this result, we show that any problem in PostBQP\textsf{PostBQP}PostBQP PostBQP can be solved with only postselections of events that occur with probabilities polynomially close to one. Under the strongly believed assumption that BQP⊉SZK\textsf{BQP}\nsupseteq \textsf{SZK}BQP⊉SZK BQP ⊉ SZK , or the shortest independent vectors problem cannot be efficiently solved with quantum computers, we also show that a single rewinding operator is sufficient to achieve tasks that are intractable for quantum computation. Finally, we show that rewindable Clifford circuits remain classically simulatable, but rewindable instantaneous quantum polynomial time circuits can solve any problem in PP\textsf{PP}PP PP .
We consider restricted versions of postBQP{\rm postBQP}postBQP where postselection probabilities can be efficiently calculated by classical or quantum computers. We show that such restricted postBQP{\rm postBQP}postBQP classes are in AWPP(⊆PP=postBQP){\rm AWPP}(\subseteq{\rm PP}={\rm postBQP})AWPP(⊆PP=postBQP). This result suggests that postselecting an event with an exponentially small probability does not necessarily boost BQP{\rm BQP}BQP to PP. The best upperbound of BQP{\rm BQP}BQP is AWPP{\rm AWPP}AWPP, and therefore restricted postBQP{\rm postBQP}postBQP classes are other examples of complexity classes slightly above BQP{\rm BQP}BQP. In [C. M. Lee and J. Barrett, arXiv:1412.8671], it was shown that the computational capacity of a general probabilistic theory which satisfies the tomographic locality is in AWPP{\rm AWPP}AWPP. Our result therefore implies that quantum physics with restricted postselections is an example of a super quantum theory which seems to be outside of their general probabilistic theory but its computational capacity is also in AWPP{\rm AWPP}AWPP. Although it is physically natural to expect that such restricted postBQP{\rm postBQP}postBQP classes are not equivalent to BQP, we show that UP∩coUP{\rm UP}\cap{\rm coUP}UP∩coUP, which is unlikely to be in BQP, is contained in the restricted postBQP{\rm postBQP}postBQP classes. Finally, we also consider another restricted class of postBQP{\rm postBQP}postBQP, where the postselected probability depends only on the size of inputs. We show that this restricted version is contained in APP{\rm APP}APP, where AWPP⊆APP⊆PP=postBQP{\rm AWPP}\subseteq{\rm APP}\subseteq{\rm PP}={\rm postBQP}AWPP⊆APP⊆PP=postBQP.
In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing machine in Deutsch's model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97--117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specified. We prove that O(log⁡T)O(\log T)O(logT) bits of precision suffice to support a T step computation. This justifies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the first formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church--Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class $\BPP$. The class $\BQP$ of languages that are efficiently decidable (with small error-probability) on a quantum Turing machine satisfies $\BPP \subseteq \BQP \subseteq \Ptime^{\SP}$. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.
Quantum computers are widely believed have an advantage over classical computers, and some have even published some empirical evidence that this is the case. However, these publications do not include a rigorous proof of this advantage, which would have to minimally state that the class of problems decidable by a quantum computer in polynomial time, BQP, contains problems that are not in the class of problems decidable by a classical computer with similar time bounds, P. Here, I provide the proof of a stronger result that implies this result: BQP contains problems that lie beyond the much larger classical computing class NP. This proves that quantum computation is able to efficiently solve problems which are far beyond the capabilities of classical computers.