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

Stephen Fenner, Frederic Green, Steven Homer +1

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 a…