TY - JOUR
T1 - NQPℂ = co-C=P
AU - Yamakami, Tomoyuki
AU - Yao, Andrew C.
PY - 1999/7/30
Y1 - 1999/7/30
N2 - 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.
AB - 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.
KW - Computational complexity
KW - Theory of computation
UR - https://www.scopus.com/pages/publications/33644825593
U2 - 10.1016/s0020-0190(99)00084-8
DO - 10.1016/s0020-0190(99)00084-8
M3 - 文章
AN - SCOPUS:33644825593
SN - 0020-0190
VL - 71
SP - 63
EP - 69
JO - Information Processing Letters
JF - Information Processing Letters
IS - 2
ER -