nLab PostBQP

Idea

In quantum complexity theory, “PostBQP” stands (in variation of BQP) for postselected bounded-error quantum polynomial time, denoting a fundamental complexity class of quantum computation.

Properties

PostBQP is closed under unions and intersections of problems in PostBQP. PostBQP is equivalent to the complexity class PP?, and includes BQP and QMA? as subclasses.

Related concepts

• postselection

• BQP

• QMA?

References

The notion is due to:

• Scott Aaronson: Quantum computing, postselection, and probabilistic polynomial-time, Proceedings of the Royal Society A 461 2063 (2005) 3473–3482 [doi:10.1098/rspa.2005.1546, arXiv:quant-ph/0412187]

See also:

• Wikipedia, PostBQP