dorsal/arxiv
View SchemaDetermining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy
| Authors | Stephen Fenner, Frederic Green, Steven Homer, Randall Pruim |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9812056 |
| URL | https://arxiv.org/abs/quant-ph/9812056 |
Abstract
It is shown that determining whether a quantum computation has a non-zero probability of accepting is at least as hard as the polynomial time hierarchy. This hardness result also applies to determining in general whether a given quantum basis state appears with nonzero amplitude in a superposition, or whether a given quantum bit has positive expectation value at the end of a quantum computation. This result is achieved by showing that the complexity class NQP of Adleman, Demarrais, and Huang, a quantum analog of NP, is equal to the counting class coC$_=$P.
{
"annotation_id": "a47e8471-33b0-4ac2-97ca-e992f4a4db87",
"date_created": "2026-03-02T18:02:44.965000Z",
"date_modified": "2026-03-02T18:02:44.965000Z",
"file_hash": "3819c2a1885398ea29ee542322bc9433e21efefcabba1ac2342309a418539f11",
"private": false,
"record": {
"abstract": "It is shown that determining whether a quantum computation has a non-zero\nprobability of accepting is at least as hard as the polynomial time hierarchy.\nThis hardness result also applies to determining in general whether a given\nquantum basis state appears with nonzero amplitude in a superposition, or\nwhether a given quantum bit has positive expectation value at the end of a\nquantum computation. This result is achieved by showing that the complexity\nclass NQP of Adleman, Demarrais, and Huang, a quantum analog of NP, is equal to\nthe counting class coC$_=$P.",
"arxiv_id": "quant-ph/9812056",
"authors": [
"Stephen Fenner",
"Frederic Green",
"Steven Homer",
"Randall Pruim"
],
"categories": [
"quant-ph"
],
"title": "Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy",
"url": "https://arxiv.org/abs/quant-ph/9812056"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "611de6ff-4689-4dfe-b69b-cc595402e106",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}