Quantum computing, postselection, and probabilistic polynomial-time

By Scott Aaronson. Proceedings of the Royal Society A, 2004

374 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/dba68b472d9931dcfa8ae5d82446ee6fbaa7ad63

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Quantum Algorithm for Linear Differential Equations with Exponentially Improved Dependence on Precision (2017, background): “The latter dependence is necessary since producing a normalized version of a subnormalized solution vector is equivalent to postselection, which is computationally intractable [1], as discussed further in Sect.”
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy (2010, methodology): “For quantum computation, the class post-BQP was introduced and studied by Aaronson (2005), who showed that post-BQP equals the classical class PP.”
The computational complexity of linear optics (2010, background): “Later, Aaronson [1] defined the class PostBQP, or quantum polynomial-time with postselection on possibly exponentiallyunlikely measurement outcomes.”
Shadow tomography of quantum states (2017, methodology): “This tool was introduced by Aaronson [1] in 2004 to prove the complexity class containment BQP/qpoly ⊆ PostBQP/poly, where BQP/qpolymeans BQP augmented with polynomial-size quantum advice, and PostBQP means BQP augmented with postselected measurements, a class that equals PP by another result of Aar”
Quantum Supremacy through the Quantum Approximate Optimization Algorithm (2016, background): “There is a result due to Aaronson [1] that says that the ability to do post-selected quantum computing allows one to solve problems in # P , that is, to perform exact counting.”