NQP_{C} = co-C_{=}P

Simple item page
dc.creatorYamakami, Tomoyuki
dc.creatorYao, Andrew C.
dc.date1998-12-14
dc.date1999-07-26
dc.date.accessioned2026-07-07T06:15:55Z
dc.date.available2026-07-07T06:15:55Z
dc.descriptionAdleman, 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.
dc.description9 pages. Accepted for Information Processing Letters, June, 1999
dc.identifierhttps://arxiv.org/abs/quant-ph/9812032
dc.identifierhttp://arxiv.org/abs/quant-ph/9812032
dc.identifierInform.Proc.Lett. 71 (1999) 63-69
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/93907
dc.subjectQuantum Physics
dc.subjectComputational Complexity
dc.titleNQP_{C} = co-C_{=}P
dc.typetext

Files

Collections

arXiv