Title: Determining Acceptance Possibility for a Quantum Computation is Hard for PH
Author: Stephen Fenner, University of Southern Maine
Frederic Green, Clark University
Steven Homer, Boston University
Randall Pruim, Boston University
Date: April 2, 1998
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.