期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1999
卷号：1999
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
