1998/12/31 by Tomoyuki Yamakami, Andrew C. Yao
Physics and Astronomy · Computer Science · #quant-ph #cs.CC
published as Inform.Proc.Lett. 71 (1999) 63-69 · 9 pages. Accepted for Information Processing Letters, June, 1999
arxiv created 1999/07/26 · arxiv updated 2009/12/01
Adleman, DeMarrais, and Huang introduced the nondeterministic quantum polynomial-time complexity class NQP as an analogue of NP. Fortnow and Rogers implicitly showed that, when the amplitudes are rational numbers, NQP is contained in the complement of C=P. Fenner, Green, Homer, and Pruim improved this result by showing that, when the amplitudes are arbitrary algebraic numbers, NQP coincides with co-C=P. In this paper we prove that, even when the amplitudes are arbitrary complex numbers, NQP still remains identical to co-C=P. As an immediate corollary, BQP differs from NQP when the amplitudes are unrestricted.