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 · Electronic colloquium on computational complexity

Quantum Computing, Postselection, and Probabilistic Polynomial-Time

Scott Aaronson

Published Dec 23, 2004• 9 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.48550/arxiv.quant-ph/0412187

Related papers

Quantum computing, postselection, and probabilistic polynomial-time

Scott Aaronson

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.

Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Sep 5, 2005•315 citations

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•2 citations

The Power of Lorentz Quantum Computer

Qi Zhang, Biao Wu

We demonstrate the superior capabilities of the recently proposed Lorentz quantum computer (LQC) compared to conventional quantum computers. We introduce an associated computational complexity class termed bounded-error Lorentz quantum polynomial-time (BLQP), demonstrating its equivalence to the complexity class ${\text P}^{\sharp \text{P}}$. We present LQC algorithms that efficiently solve the problem of maximum independent set, PP (probabilistic polynomial-time), and consequently ${\text P}^{\sharp \text{P}}$, all within polynomial time. Additionally, we show that the quantum computing with postselection proposed by Aaronson can be efficiently simulated by LQC, but not vice versa.

arXiv:2403.04170•Mar 7, 2024•0 citations

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•3 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
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.
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 demonstrate the superior capabilities of the recently proposed Lorentz quantum computer (LQC) compared to conventional quantum computers. We introduce an associated computational complexity class termed bounded-error Lorentz quantum polynomial-time (BLQP), demonstrating its equivalence to the complexity class P♯P{\text P}^{\sharp \text{P}}P♯P. We present LQC algorithms that efficiently solve the problem of maximum independent set, PP (probabilistic polynomial-time), and consequently P♯P{\text P}^{\sharp \text{P}}P♯P, all within polynomial time. Additionally, we show that the quantum computing with postselection proposed by Aaronson can be efficiently simulated by LQC, but not vice versa.
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.