ECCC-Report TR05-003https://eccc.weizmann.ac.il/report/2005/003Comments and Revisions published for TR05-003en-usSun, 09 Jan 2005 21:51:38 +0200
Paper TR05-003
| Quantum Computing, Postselection, and Probabilistic Polynomial-Time |
Scott Aaronson
https://eccc.weizmann.ac.il/report/2005/003I 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.
Sun, 09 Jan 2005 21:51:38 +0200https://eccc.weizmann.ac.il/report/2005/003