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.
| Original language | English |
|---|---|
| Pages (from-to) | 63-69 |
| Number of pages | 7 |
| Journal | Information Processing Letters |
| Volume | 71 |
| Issue number | 2 |
| DOIs | |
| State | Published - 30 Jul 1999 |
Keywords
- Computational complexity
- Theory of computation
Fingerprint
Dive into the research topics of 'NQPℂ = co-C=P'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver