Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR98-073 | 26th July 1999 00:00

NQP_{C}=co-C_{=}P Revision of: TR98-073

RSS-Feed




Revision #2
Authors: Tomoyuki Yamakami, Andrew Chi-Chih Yao
Accepted on: 26th July 1999 00:00
Downloads: 3031
Keywords: 


Abstract:

Adleman, DeMarrais, and Huang introduced the
nondeterministic quantum polynomial-time complexity class NQP as an
analogue of NQP. 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.


Revision #1 to TR98-073 | 23rd March 1999 00:00

NQP_{C} = co-C_{=}P Revision of: TR98-073





Revision #1
Authors: Tomoyuki Yamakami, Andrew Chi-Chih Yao
Accepted on: 23rd March 1999 00:00
Downloads: 3059
Keywords: 


Abstract:

Adleman, DeMarrais, and Huang introduced the
nondeterministic quantum polynomial-time complexity class NQP as an
analogue of NP. Fortnow and Rogers 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.


Paper:

TR98-073 | 14th December 1998 00:00

NQP = co-C_{=}P





TR98-073
Authors: Tomoyuki Yamakami, Andrew Chi-Chih Yao
Publication: 15th December 1998 09:09
Downloads: 3647
Keywords: 


Abstract:

Adleman, DeMarrais, and Huang introduced the
nondeterministic quantum polynomial-time complexity class NQP as an
analogue of NP. It is known that, with restricted amplitudes, NQP is
characterized in terms of the classical counting complexity class
C_{=}P. In this paper we prove that, with unrestricted amplitudes,
NQP indeed coincides with the complement of C_{=}P. As an immediate
corollary, with unrestricted amplitudes BQP differs from NQP.



ISSN 1433-8092 | Imprint