Quantum Computing, Postselection, and Probabilistic Polynomial-Time
<|reference_start|>Quantum Computing, Postselection, and Probabilistic Polynomial-Time: 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.<|reference_end|>
@article{aaronson2004quantum,
    title={Quantum Computing, Postselection, and Probabilistic Polynomial-Time},
    author={Scott Aaronson},
    journal={arXiv preprint arXiv:quant-ph/0412187},
    year={2004},
    archivePrefix={arXiv},
    eprint={quant-ph/0412187},
    primaryClass={quant-ph cs.CC}
}