Computer Science
Relativized separation of EQP from PNP
Document Type
Article
Abstract
An oracle is constructed relative to which quantum polynomial time (EQP) is not polynomial-time Turing reducible to NP. That is, there is an A such that EQPA ⊈ PNPA. This generalizes and simplifies previous separations of EQP from NP and ZPP, due to Berthiaume and Brassard. A key element of the proof is the use of a special property of Grover's algorithm for database search, in order to show that the test language is in EQPA. © 2001 Elsevier Science B.V. All rights reserved.
Publication Title
Information Processing Letters
Publication Date
2001
Volume
80
Issue
5
First Page
257
Last Page
260
ISSN
0020-0190
DOI
10.1016/S0020-0190(01)00176-4
Keywords
computational complexity, quantum computation, theory of computation
Repository Citation
Green, Frederic and Pruim, Randall, "Relativized separation of EQP from PNP" (2001). Computer Science. 63.
https://commons.clarku.edu/faculty_computer_sciences/63
APA Citation
Green, F., & Pruim, R. (2001). Relativized separation of EQP from PNP. Information Processing Letters, 80(5), 257-260.