TR99-003 Authors: Stephen A. Fenner, Frederic Green, Steven Homer, Randall Pruim

Publication: 11th February 1999 18:04

Downloads: 2070

Keywords:

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.