Quantum Computing, Postselection, and Probabilistic Polynomial-Time
| dc.creator | Aaronson, Scott | |
| dc.date | 2004-12-23 | |
| dc.date.accessioned | 2026-07-07T06:11:51Z | |
| dc.date.available | 2026-07-07T06:11:51Z | |
| dc.description | 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. | |
| dc.description | 8 pages, 1 figure. Supersedes the computational results in quant-ph/0401062 | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0412187 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0412187 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/92610 | |
| dc.subject | Quantum Physics | |
| dc.subject | Computational Complexity | |
| dc.title | Quantum Computing, Postselection, and Probabilistic Polynomial-Time | |
| dc.type | text |