pith. sign in

arxiv: quant-ph/9812032 · v3 · submitted 1998-12-14 · 🪐 quant-ph · cs.CC

NQP_(C) = co-C₌P

classification 🪐 quant-ph cs.CC
keywords amplitudeswhenco-cnumbersarbitraryadlemanalgebraicanalogue
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.