Relativized separation of EQP from P-NP

Authors
Green, F Pruim, R
Citation
F. Green et R. Pruim, Relativized separation of EQP from P-NP, INF PROCESS, 80(5), 2001, pp. 257-260
Citations number
8
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190 → ACNP
Volume
80
Issue
5
Year of publication
2001
Pages
257 - 260
Database
ISI
SICI code
0020-0190(200112)80:5<257:RSOEFP>2.0.ZU;2-#
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 th at EQp(A) not subset of or equal to PNPA. This generalizes and simplifies p revious 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 al gorithm for database search, in order to show that the test language is in EQP(A). (C) 2001 Elsevier Science B.V. All rights reserved.