Impossibility of a Quantum Speed-Up with a Faulty Oracle

DOI10.1007/978-3-540-70575-8_63MaRDI QIDQ3521965zbMATH OpenOpenAlexFDO

Authors Liron Schiff, Oded Regev

Publication date 28 August 2008

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.1027

Mathematics Subject Classification ID

Searching and sorting (68P10) Quantum computation (81P68)

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.

Recommendations

• Grover's search with faults on some marked elements
• Grover's search with faults on some marked elements
• Grover's algorithm with errors
• Fault-ignorant quantum search
• An upper bound on the rate of information transfer by Grover's oracle

Cited in

(15)

• Parametric quantum search algorithm as quantum walk: a quantum simulation
• Characterizing error propagation in quantum circuits: the isotropic index
• Impact of the malicious input data modification on the efficiency of quantum spatial search
• Grover's search with local and total depolarizing channel errors: complexity analysis
• Fault-ignorant quantum search
• On the robustness of bucket brigade quantum RAM
• A Not So Impossible Machine Based on the GHZ Paradox
• Grover's algorithm with errors
• Grover's search with faults on some marked elements
• Grover's search with faults on some marked elements
• The NISQ complexity of collision finding
• The computational advantage of MIP* vanishes in the presence of noise
• The computational advantage of MIP* vanishes in the presence of noise
• Using quantum switches to mitigate noise in Grover's search algorithm
• Quantum search with in-place queries

This page was built for publication: Impossibility of a Quantum Speed-Up with a Faulty Oracle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3521965)