dorsal/arxiv
View SchemaQuantum Computing, Postselection, and Probabilistic Polynomial-Time
| Authors | Scott Aaronson |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0412187 |
| URL | https://arxiv.org/abs/quant-ph/0412187 |
Abstract
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.
{
"annotation_id": "5c0f8b8e-1545-44e8-92b8-769b57b11c6f",
"date_created": "2026-03-02T18:02:13.639000Z",
"date_modified": "2026-03-02T18:02:13.639000Z",
"file_hash": "9c1725b52b416f04f2e234e1b4b789d8f9e59222a504fa68ab8c816caa4f350b",
"private": false,
"record": {
"abstract": "I study the class of problems efficiently solvable by a quantum computer,\ngiven the ability to \"postselect\" on the outcomes of measurements. I prove that\nthis class coincides with a classical complexity class called PP, or\nProbabilistic Polynomial-Time. Using this result, I show that several simple\nchanges to the axioms of quantum mechanics would let us solve PP-complete\nproblems efficiently. The result also implies, as an easy corollary, a\ncelebrated theorem of Beigel, Reingold, and Spielman that PP is closed under\nintersection, as well as a generalization of that theorem due to Fortnow and\nReingold. This illustrates that quantum computing can yield new and simpler\nproofs of major results about classical computation.",
"arxiv_id": "quant-ph/0412187",
"authors": [
"Scott Aaronson"
],
"categories": [
"quant-ph",
"cs.CC"
],
"title": "Quantum Computing, Postselection, and Probabilistic Polynomial-Time",
"url": "https://arxiv.org/abs/quant-ph/0412187"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "6fbc3f1b-3ad9-4a07-a5c6-606f4a250823",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}