TY - GEN
T1 - Impossibility of a quantum speed-up with a faulty oracle
AU - Regev, Oded
AU - Schiff, Liron
N1 - Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.
PY - 2008
Y1 - 2008
N2 - We consider Grover's unstructured search problem in the setting where each oracle call has some small probability of failing. We show that no quantum speed-up is possible in this case.
AB - We consider Grover's unstructured search problem in the setting where each oracle call has some small probability of failing. We show that no quantum speed-up is possible in this case.
UR - http://www.scopus.com/inward/record.url?scp=49049102737&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=49049102737&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-70575-8_63
DO - 10.1007/978-3-540-70575-8_63
M3 - Conference contribution
AN - SCOPUS:49049102737
SN - 3540705740
SN - 9783540705741
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 773
EP - 781
BT - Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings
T2 - 35th International Colloquium on Automata, Languages and Programming, ICALP 2008
Y2 - 7 July 2008 through 11 July 2008
ER -