Impossibility of a quantum speed-up with a faulty oracle

Oded Regev; Liron Schiff

doi:10.1007/978-3-540-70575-8_63

Impossibility of a quantum speed-up with a faulty oracle

Oded Regev, Liron Schiff

Computer Science

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 language	English (US)
Title of host publication	Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings
Pages	773-781
Number of pages	9
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-540-70575-8_63
State	Published - 2008
Event	35th International Colloquium on Automata, Languages and Programming, ICALP 2008 - Reykjavik, Iceland Duration: Jul 7 2008 → Jul 11 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	5125 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	35th International Colloquium on Automata, Languages and Programming, ICALP 2008
Country/Territory	Iceland
City	Reykjavik
Period	7/7/08 → 7/11/08

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-70575-8_63

Cite this

Regev, O., & Schiff, L. (2008). Impossibility of a quantum speed-up with a faulty oracle. In Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings (PART 1 ed., pp. 773-781). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5125 LNCS, No. PART 1). https://doi.org/10.1007/978-3-540-70575-8_63

Impossibility of a quantum speed-up with a faulty oracle. / Regev, Oded; Schiff, Liron.
Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings. PART 1. ed. 2008. p. 773-781 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5125 LNCS, No. PART 1).

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

Regev, O & Schiff, L 2008, Impossibility of a quantum speed-up with a faulty oracle. in Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 5125 LNCS, pp. 773-781, 35th International Colloquium on Automata, Languages and Programming, ICALP 2008, Reykjavik, Iceland, 7/7/08. https://doi.org/10.1007/978-3-540-70575-8_63

Regev O, Schiff L. Impossibility of a quantum speed-up with a faulty oracle. In Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings. PART 1 ed. 2008. p. 773-781. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). doi: 10.1007/978-3-540-70575-8_63

@inproceedings{ac7f908c89884268ad948f43a0c78a69,

title = "Impossibility of a quantum speed-up with a faulty oracle",

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.",

author = "Oded Regev and Liron Schiff",

year = "2008",

doi = "10.1007/978-3-540-70575-8_63",

language = "English (US)",

isbn = "3540705740",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "773--781",

booktitle = "Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings",

edition = "PART 1",

note = "35th International Colloquium on Automata, Languages and Programming, ICALP 2008 ; Conference date: 07-07-2008 Through 11-07-2008",

}

TY - GEN

T1 - Impossibility of a quantum speed-up with a faulty oracle

AU - Regev, Oded

AU - Schiff, Liron

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 -

Impossibility of a quantum speed-up with a faulty oracle

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this