Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1202.1027

Impossibility of a Quantum Speed-up with a Faulty Oracle

Oded Regev, Liron Schiff

Published Feb 6, 2012• 2 citations
arXivHTMLPDF

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.
DOI
10.48550/arxiv.1202.1027

Related papers

On fault-tolerance of Grover's algorithm

Nikolajs Nahimovs, Alexander Rivosh, Dmitry Kravchenko

Grover’s algorithm is a quantum search algorithm solving the unstructured search problem of size N in O( √ N ) queries, while any classical algorithm needs O(N ) queries [1]. However, if the query transformation might fail (with probability independent of the number of steps of the algorithm), then quantum speed-up disappears: no quantum algorithm can be faster than a classical exhaustive search by more than a constant factor [6]. In this paper we study the effect of a small number of failed queries. We show that k failed queries with a very high probability change the number of actually executed steps of Grover’s algorithm from l to O � l √ k

•Jan 1, 2012•0 citations

Quantum Search with Noisy Oracle

Ansis Rosmanis

We consider quantum search algorithms that have access to a noisy oracle that, for every oracle call, with probability $p>0$ completely depolarizes the query registers, while otherwise working properly. Previous results had not ruled out quantum $\mathrm{O}(\sqrt{n})$-query algorithms in this setting, even for constant $p$. We show that, for all $p\le 0.99$, the quantum noisy-query complexity of the unstructured search is $\tildeΘ(\max\{np,\sqrt{n}\})$. The lower bound $Ω(\max\{np,\sqrt n\})$ holds also for the dephasing noise and even when, for every oracle call, the algorithm is provided with a flag indicating whether the error has occurred.

arXiv:2309.14944•Sep 26, 2023•1 citation

Exponential speed-up for quantum search of real databases

Bogusław Broda

A simple circuit implementation of the oracle for Grover's quantum search of a real unstructured classical database is proposed. The oracle contains a kind of quantumly accessible classical memory, which stores the database.

•Feb 17, 2015•0 citations

Grover's search with faults on some marked elements

Dmitry Kravchenko, Nikolajs Nahimovs, Alexander Rivosh

Grover's algorithm is a quantum query algorithm solving the unstructured search problem of size $N$ using $O(\sqrt{N})$ queries. It provides a significant speed-up over any classical algorithm \cite{Gro96}. The running time of the algorithm, however, is very sensitive to errors in queries. It is known that if query may fail (report all marked elements as unmarked) the algorithm needs $Ω(N)$ queries to find a marked element \cite{RS08}. \cite{AB+13} have proved the same result for the model where each marked element has its own probability to be reported as unmarked. We study the behavior of Grover's algorithm in the model where the search space contains both faulty and non-faulty marked elements. We show that in this setting it is indeed possible to find one of non-faulty marked items in $O(\sqrt{N})$ queries. We also analyze the limiting behavior of the algorithm for a large number of steps and show the existence and the structure of limiting state $ρ_{lim}$.

arXiv:1508.05108•Aug 20, 2015•0 citations

An information-theoretic analysis of Grover's algorithm

Erdal Arıkan

Grover discovered a quantum algorithm for identifying a target element in an unstructured search universe of N items in approximately square-root of N queries to a quantum oracle, thus achieving a square-root speed-up over classical algorithms. We present an information-theoretic analysis of Grover's algorithm and show that the square-root speed-up is the best attainable result using Grover's oracle.

arXiv:quant-ph/0210068•Oct 10, 2002•1 citation

Grover’s Search with Faults on Some Marked Elements

Dmitry Kravchenko, Nikolajs Nahimovs, Alexander Rivosh

Grover’s algorithm is a quantum query algorithm solving the unstructured search problem of size [Formula: see text] using [Formula: see text] queries. It provides a significant speed-up over any classical algorithm [3]. The running time of the algorithm, however, is very sensitive to errors in queries. Multiple authors have analysed the algorithm using different models of query errors and showed the loss of quantum speed-up [2, 6]. We study the behavior of Grover’s algorithm in the model where the search space contains both faulty and non-faulty marked elements. We show that in this setting it is indeed possible to find one of marked elements in [Formula: see text] queries. We also analyze the limiting behavior of the algorithm for a large number of steps and show the existence and the structure of a limiting state [Formula: see text].

International Journal of Foundations of Computer Science•Jun 1, 2018•3 citations
Grover’s algorithm is a quantum search algorithm solving the unstructured search problem of size N in O( √ N ) queries, while any classical algorithm needs O(N ) queries [1]. However, if the query transformation might fail (with probability independent of the number of steps of the algorithm), then quantum speed-up disappears: no quantum algorithm can be faster than a classical exhaustive search by more than a constant factor [6]. In this paper we study the effect of a small number of failed queries. We show that k failed queries with a very high probability change the number of actually executed steps of Grover’s algorithm from l to O � l √ k
We consider quantum search algorithms that have access to a noisy oracle that, for every oracle call, with probability p>0p>0p>0 completely depolarizes the query registers, while otherwise working properly. Previous results had not ruled out quantum O(n)\mathrm{O}(\sqrt{n})O(n​)-query algorithms in this setting, even for constant ppp. We show that, for all p≤0.99p\le 0.99p≤0.99, the quantum noisy-query complexity of the unstructured search is Θ~(max⁡{np,n})\tildeΘ(\max\{np,\sqrt{n}\})Θ~(max{np,n​}). The lower bound Ω(max⁡{np,n})Ω(\max\{np,\sqrt n\})Ω(max{np,n​}) holds also for the dephasing noise and even when, for every oracle call, the algorithm is provided with a flag indicating whether the error has occurred.
Grover's algorithm is a quantum query algorithm solving the unstructured search problem of size NNN using O(N)O(\sqrt{N})O(N​) queries. It provides a significant speed-up over any classical algorithm \cite{Gro96}. The running time of the algorithm, however, is very sensitive to errors in queries. It is known that if query may fail (report all marked elements as unmarked) the algorithm needs Ω(N)Ω(N)Ω(N) queries to find a marked element \cite{RS08}. \cite{AB+13} have proved the same result for the model where each marked element has its own probability to be reported as unmarked. We study the behavior of Grover's algorithm in the model where the search space contains both faulty and non-faulty marked elements. We show that in this setting it is indeed possible to find one of non-faulty marked items in O(N)O(\sqrt{N})O(N​) queries. We also analyze the limiting behavior of the algorithm for a large number of steps and show the existence and the structure of limiting state ρlimρ_{lim}ρlim​.
Grover’s algorithm is a quantum query algorithm solving the unstructured search problem of size [Formula: see text] using [Formula: see text] queries. It provides a significant speed-up over any classical algorithm [3]. The running time of the algorithm, however, is very sensitive to errors in queries. Multiple authors have analysed the algorithm using different models of query errors and showed the loss of quantum speed-up [2, 6]. We study the behavior of Grover’s algorithm in the model where the search space contains both faulty and non-faulty marked elements. We show that in this setting it is indeed possible to find one of marked elements in [Formula: see text] queries. We also analyze the limiting behavior of the algorithm for a large number of steps and show the existence and the structure of a limiting state [Formula: see text].