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:quant-ph/0507234 · Physical Review A

Grover’s quantum search algorithm and Diophantine approximation

Shahar Dolev, Itamar Pitowsky, Boaz Tamir

Published Feb 3, 2006• 3 citations
arXivHTMLPDF

Abstract

In a fundamental paper [Phys. Rev. Lett. 78, 325 (1997)] Grover showed how a quantum computer can find a single marked object in a database of size $N$ by using only $O(\sqrt{N})$ queries of the oracle that identifies the object. His result was generalized to the case of finding one object in a subset of marked elements. We consider the following computational problem: A subset of marked elements is given whose number of elements is either $M$ or $K$, our task is to determine which is the case. We show how to solve this problem with a high probability of success using iterations of Grover's basic step only, and no other algorithm. Let $m$ be the required number of iterations; we prove that under certain restrictions on the sizes of $M$ and $K$ the estimation $m<2\sqrt{N}∕(\sqrt{K}\ensuremath{-}\sqrt{M})$ obtains. This bound reproduces previous results based on more elaborate algorithms, and is known to be optimal up to a constant factor. Our method involves simultaneous Diophantine approximations, so that Grover's algorithm is conceptualized as an orbit of an ergodic automorphism of the torus. We comment on situations where the algorithm may be slow, and note the similarity between these cases and the problem of small divisors in classical mechanics.

DOI
10.1103/physreva.73.022308

Related papers

A Grover-based quantum search of optimal order for an unknown number of marked elements

Christof Zalka

We want to find a marked element out of a black box containing N elements. When the number of marked elements is known this can be done elegantly with Grover's algorithm, a variant of which even gives a correct result with certainty. On the other hand, when the number of marked elements is not known the problem becomes more difficult. For every prescribed success probability I give an algorithm consisting of several runs of Grover's algorithm that matches a recent bound by Buhrman and de Wolf on the order of the number of queries to the black box. The improvement in the order over a previously known algorithm is small and the number of queries can clearly still be reduced by a constant factor.

arXiv:quant-ph/9902049•Feb 12, 1999•9 citations

Quantum Search Algorithm

Che‐Ming Li, Jin-Yuan Hsieh, Der-San Chuu

IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.

InTech eBooks•Apr 26, 2011•0 citations

Grover Algorithm and an Analysis of Successful Probability of Quantum Mixed State

Duolu Mao

Grover proposed how a quantum computer can find a single marked object in a database of size N by using only O(N) queries of the oracle that identifies the object with the probability of finding the marked object being not exactly 1.The Grover quantum search algorithm is generalized to deal with an arbitrary mixed initial state.The probability of finding the marked object is calculated and it is found that it depends strongly on the specific initial state.Our results contribute to analyze the influence of quantum noise on Grover algorithm based on pure state.Finally,we give few examples to show that for some extremely mixed initial states.

Acta Sinica Quantum Optica•Jan 1, 2009•0 citations

Grover's search algorithm for nnn qubits with optimal number of iterations

Simanraj Sadana

The success probability of a search of $M$ targets from a database of size $N$, using Grover's search algorithm depends critically on the number of iterations of the composite operation of the oracle followed by Grover's diffusion operation. Although the required number of iterations scales as $\mathcal{O}(\sqrt{N})$ for large $N$, the asymptote is not a good indicator of the optimal number of iterations when $\sqrt{M/N}$ is not small. A scheme for the determination of the exact number of iterations, subject to a threshold set for the success probability of the search (probability of detecting the target state(s)), is crucial for the efficacy of the algorithm. In this work, a general scheme for the construction of $n$-qubit Grover's search algorithm with $1 \leq M \leq N$ target states is presented, along with the procedure to find the optimal number of iterations for a successful search. It is also shown that for given $N$ and $M$, there is an upper-bound on the success probability of the algorithm.

arXiv:2011.04051•Nov 8, 2020•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 $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

Analysis of Grover’s quantum search algorithm on a classical computer: Identifying opportunities for improvement

Necati Çeli̇k

In this paper, Grover's quantum search algorithm is analyzed using a classical computer by calculating the amplitudes and the probabilities of finding a single marked state for n=5, 10, 15, 20, 25, and 27 qubit states.The calculations show that the marked state can be found in 𝒪(√𝑁) iterations, where 𝑁 = 2 ( is the number of items.The possibility of improving Grover's search algorithm to find a single item in N search elements is discussed by calculating the amplitudes and hence the probabilities of finding a single marked state for n=5, 10, 15, 20, 25, 30, 35, 40, 45, and 50 qubit states.The calculations showed that the marked state could be found with sufficiently high probability in 𝒪(ln (𝑁)) iterations.This is quite a remarkable speed-up that can be achieved to find a single marked element in an unsorted N search element.

Sigma Journal of Engineering and Natural Sciences – Sigma Mühendislik ve Fen Bilimleri Dergisi•Jun 20, 2023•5 citations
In a fundamental paper [Phys. Rev. Lett. 78, 325 (1997)] Grover showed how a quantum computer can find a single marked object in a database of size NNN by using only O(N)O(\sqrt{N})O(N​) queries of the oracle that identifies the object. His result was generalized to the case of finding one object in a subset of marked elements. We consider the following computational problem: A subset of marked elements is given whose number of elements is either MMM or KKK, our task is to determine which is the case. We show how to solve this problem with a high probability of success using iterations of Grover's basic step only, and no other algorithm. Let mmm be the required number of iterations; we prove that under certain restrictions on the sizes of MMM and KKK the estimation m<2N∕(K\ensuremath−M)m<2\sqrt{N}∕(\sqrt{K}\ensuremath{-}\sqrt{M})m<2N​∕(K​\ensuremath−M​) obtains. This bound reproduces previous results based on more elaborate algorithms, and is known to be optimal up to a constant factor. Our method involves simultaneous Diophantine approximations, so that Grover's algorithm is conceptualized as an orbit of an ergodic automorphism of the torus. We comment on situations where the algorithm may be slow, and note the similarity between these cases and the problem of small divisors in classical mechanics.
We want to find a marked element out of a black box containing N elements. When the number of marked elements is known this can be done elegantly with Grover's algorithm, a variant of which even gives a correct result with certainty. On the other hand, when the number of marked elements is not known the problem becomes more difficult. For every prescribed success probability I give an algorithm consisting of several runs of Grover's algorithm that matches a recent bound by Buhrman and de Wolf on the order of the number of queries to the black box. The improvement in the order over a previously known algorithm is small and the number of queries can clearly still be reduced by a constant factor.
IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.
Grover proposed how a quantum computer can find a single marked object in a database of size N by using only O(N) queries of the oracle that identifies the object with the probability of finding the marked object being not exactly 1.The Grover quantum search algorithm is generalized to deal with an arbitrary mixed initial state.The probability of finding the marked object is calculated and it is found that it depends strongly on the specific initial state.Our results contribute to analyze the influence of quantum noise on Grover algorithm based on pure state.Finally,we give few examples to show that for some extremely mixed initial states.
The success probability of a search of MMM targets from a database of size NNN, using Grover's search algorithm depends critically on the number of iterations of the composite operation of the oracle followed by Grover's diffusion operation. Although the required number of iterations scales as O(N)\mathcal{O}(\sqrt{N})O(N​) for large NNN, the asymptote is not a good indicator of the optimal number of iterations when M/N\sqrt{M/N}M/N​ is not small. A scheme for the determination of the exact number of iterations, subject to a threshold set for the success probability of the search (probability of detecting the target state(s)), is crucial for the efficacy of the algorithm. In this work, a general scheme for the construction of nnn-qubit Grover's search algorithm with 1≤M≤N1 \leq M \leq N1≤M≤N target states is presented, along with the procedure to find the optimal number of iterations for a successful search. It is also shown that for given NNN and MMM, there is an upper-bound on the success probability of the algorithm.
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​.
In this paper, Grover's quantum search algorithm is analyzed using a classical computer by calculating the amplitudes and the probabilities of finding a single marked state for n=5, 10, 15, 20, 25, and 27 qubit states.The calculations show that the marked state can be found in 𝒪(√𝑁) iterations, where 𝑁 = 2 ( is the number of items.The possibility of improving Grover's search algorithm to find a single item in N search elements is discussed by calculating the amplitudes and hence the probabilities of finding a single marked state for n=5, 10, 15, 20, 25, 30, 35, 40, 45, and 50 qubit states.The calculations showed that the marked state could be found with sufficiently high probability in 𝒪(ln (𝑁)) iterations.This is quite a remarkable speed-up that can be achieved to find a single marked element in an unsorted N search element.