In computational complexity theory, PostBQP is a complexity class consisting of all of the computational problems solvable in polynomial time on a quantum Turing machine with postselection 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:
BQP is the same as PostBQP except without postselection
BPPpath is the same as PostBQP except that instead of quantum, the algorithm is a classical randomized algorithm (with postselection)[1]
The addition of postselection seems to make quantum Turing machines much more powerful: Scott Aaronson proved[2][3]PostBQP is equal to PP, a class which is believed to be relatively powerful, whereas BQP is not known even to contain the seemingly smaller class NP. 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 PP:
if we broadened the definition of 'quantum gate' to include not just unitary operations but linear operations, or
if the probability of measuring a basis state was proportional to instead of for any even integer p > 2.
^Y. Han and Hemaspaandra, L. and Thierauf, T. (1997). "Threshold computation and cryptographic security". SIAM Journal on Computing. 26: 59–78. CiteSeerX 10.1.1.23.510. doi:10.1137/S0097539792240467.{{cite journal}}: CS1 maint: multiple names: authors list (link)
^Aaronson, Scott (2005). "Quantum computing, postselection, and probabilistic polynomial-time". Proceedings of the Royal Society A. 461 (2063): 3473–3482. arXiv:quant-ph/0412187. Bibcode:2005RSPSA.461.3473A. doi:10.1098/rspa.2005.1546. S2CID 1770389.. Preprint available at [1]
^Aaronson, Scott (2004-01-11). "Complexity Class of the Week: PP". Computational Complexity Weblog. Retrieved 2008-05-02.
postselection) from PostBQP gives the following two complexity classes, both of which are subsets of PostBQP: BQP is the same as PostBQP except without postselection...
computing. Adding postselection to BQP results in the complexity class PostBQP which is equal to PP. Promise-BQP is the class of promise problems that...
appearing to give super-polynomial speedups and are BQP-complete. Because these problems are BQP-complete, an equally fast classical algorithm for them...
Aaronson, who showed that the class of polynomial time on such a machine (PostBQP) is equal to the classical complexity class PP. Quantum simulator § Solving...
universal for the class BQP. It also relies on the following facts: Linear optics with postselected measurements is universal for PostBQP, i.e. quantum polynomial-time...
are much more powerful: Scott Aaronson proved PostBQP is equal to PP. Some quantum experiments use post-selection after the experiment as a replacement...
A problem is BQP-complete if it is in BQP and any problem in BQP can be reduced to it in polynomial time. Informally, the class of BQP-complete problems...
non-quantum) complexity classes. Two important quantum complexity classes are BQP and QMA. A complexity class is a collection of computational problems that...
increased investment in quantum computing research and the development of post-quantum cryptography to prepare for the fault-tolerant quantum computing...
electronics industry trade show. Some organizations have recommended using "post-quantum cryptography (or quantum-resistant cryptography)" as an alternative...
Global Information
