Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR99-003 | 18th December 1998 00:00

Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy

RSS-Feed




TR99-003
Authors: Stephen A. Fenner, Frederic Green, Steven Homer, Randall Pruim
Publication: 11th February 1999 18:04
Downloads: 1000
Keywords: 


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.



ISSN 1433-8092 | Imprint