Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy
Stephen Fenner, Frederic Green, Steven Thomas Homer, Randall J. Pruim · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · 1999
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 non–zero 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 (a quantum analogue of NP) of Adleman, Demarrais and Huang, is equal to the counting class coC=P.