PostBQP

In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, PostBQP is a <a href="/facts/Complexity_class/IIKrcTbP">complexity class</a> consisting of all of the <a href="/facts/Computational_problem/jQ7bYUVh">computational problems</a> solvable in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a> on a <a href="/facts/Quantum_Turing_machine/tTJ8P43B">quantum Turing machine</a> with <a href="/facts/Postselection/cQLt0MMC">postselection</a> and bounded error (in the sense that the algorithm is correct at least 2/3 of the time on all inputs).
Postselection is not considered to be a feature that a realistic computer (even a quantum one) would possess, but nevertheless postselecting machines are interesting from a theoretical perspective.
Removing either one of the two main features (quantumness, postselection) from PostBQP gives the following two complexity classes, both of which are subsets of PostBQP:

<ul><li><a href="/facts/BQP/whjD9eyf">BQP</a> is the same as PostBQP except without postselection</li>
<li>BPPpath is the same as PostBQP except that instead of quantum, the algorithm is a classical randomized algorithm (with postselection)</li></ul>
The addition of <a href="/facts/Postselection/cQLt0MMC">postselection</a> seems to make quantum Turing machines much more powerful: <a href="/facts/Scott_Aaronson/htGK5zuz">Scott Aaronson</a> proved PostBQP is equal to <a href="/facts/PP_(complexity)/WCLqxQF8">PP</a>, a class which is believed to be relatively powerful, whereas <a href="/facts/BQP/whjD9eyf">BQP</a> is not known even to contain the seemingly smaller class <a href="/facts/NP_(complexity_class)/6muUfVMI">NP</a>. Using similar techniques, Aaronson also proved that small changes to the laws of quantum computing would have significant effects. As specific examples, under either of the two following changes, the "new" version of BQP would equal <a href="/facts/PP_(complexity)/WCLqxQF8">PP</a>:

<ul><li>if we broadened the definition of 'quantum gate' to include not just unitary operations but linear operations, or</li>
<li>if the probability of measuring a basis state 
 
 
 
 
 |
 
 x
 ⟩
 
 
 {\displaystyle |x\rangle }
 
 was proportional to 
 
 
 
 
 |
 
 
 α
 
 x
 
 
 
 
 |
 
 
 p
 
 
 
 
 {\displaystyle |\alpha _{x}|^{p}}
 
 instead of 
 
 
 
 
 |
 
 
 α
 
 x
 
 
 
 
 |
 
 
 2
 
 
 
 
 {\displaystyle |\alpha _{x}|^{2}}
 
 for any even integer p > 2.</li></ul>

PostBQP open-in-new

PostBQP