Skip to main navigation Skip to search Skip to main content

NQPℂ = co-C=P

  • Tomoyuki Yamakami
  • , Andrew C. Yao
  • Princeton University

Research output: Contribution to journal › Article › peer-review

28 Scopus citations

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 languageEnglish
Pages (from-to)63-69
Number of pages7
JournalInformation Processing Letters
Volume71
Issue number2
DOIs
StatePublished - 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