Opening book details…
Can I read NQPC= co-C=P on EtoBox?
NQPC= co-C=P by Tomoyuki Yamakami; Andrew C. Yao is a Computer Science article available to read on EtoBox.
What is NQPC= co-C=P about?
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.
Who reads NQPC= co-C=P?
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- Tomoyuki Yamakami; Andrew C. Yao
- Publisher
- Elsevier Science; Elsevier ; Elsevier BV (ISSN 0020-0190)
- Published
- 1999
- Language
- EN
- Field
- Computer Science (Physical Sciences)