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

Authors: Fenner, Stephen; Green, Frederic; Homer, Steven and Pruim, Randall

Date: Jan 20, 2000

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 $co-C equals P$.