ECCC-Report TR99-003https://eccc.weizmann.ac.il/report/1999/003Comments and Revisions published for TR99-003en-usThu, 11 Feb 1999 18:04:28 +0200
Paper TR99-003
| Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy |
Stephen A. Fenner,
Frederic Green,
Steven Homer,
Randall Pruim
https://eccc.weizmann.ac.il/report/1999/003It 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.
Thu, 11 Feb 1999 18:04:28 +0200https://eccc.weizmann.ac.il/report/1999/003