Impossibility of a quantum speed-up with a faulty oracle

Oded Regev, Liron Schiff

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings
Pages773-781
Number of pages9
EditionPART 1
DOIs
StatePublished - 2008
Event35th International Colloquium on Automata, Languages and Programming, ICALP 2008 - Reykjavik, Iceland
Duration: Jul 7 2008 → Jul 11 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume5125 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other35th International Colloquium on Automata, Languages and Programming, ICALP 2008
CountryIceland
CityReykjavik
Period7/7/08 → 7/11/08

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Access to Document

Other files and links

Fingerprint Dive into the research topics of 'Impossibility of a quantum speed-up with a faulty oracle'. Together they form a unique fingerprint.

Cite this