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•24 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•1 citation

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•4 citations

Quantum Search Algorithm

The quantum search algorithm was discovered by L. K. Grover in 1997, and is called Grover’s algorithm after his name. Let us consider how to find elements marked by a certain symbol out of a database consisting of N elements (say, multi-million elements). This problem is similar to how to find the name of the person from a telephone book knowing only his/her telephone number. This search takes by far more time than finding the phone number from the name of the person. The difference comes from the structure of the telephone book. In the telephone book, the names are arranged in the alphabetical order and constitute the structured database, while phone numbers do not form any structure in the telephone book. In classical computers, when we search one target element from the database with N elements, we need N/ 2 trials on average. Grover showed using the quantum search algorithm that N trials will be enough on average to find the target element from the database with N elements. Shor’s quantum computation algorithm was an epoch-making algorithm which made possible to solve the factorization problem in polynomial time, while the classical computers need exponentially increasing time to solve it. In comparison, Grover’s algorithm makes the data search possible by O ( N ) computation time, while it takes O ( N ) computation time by the classical computers. Concerning the reduction of computing time, Grover’s algorithm may look less powerful than Shor’s algorithm. However, it has good potentiality of application in the wide area such as NP-complete problems and structured databases.

WORLD SCIENTIFIC eBooks•Sep 24, 2020•0 citations

Optimal quantum searching to find a common element of two sets

Avatar Tulsi

Given two sets A and B and two oracles O(A) and O(B) that can identify the elements of these sets respectively, the goal is to find an element common to both sets using minimum number of oracle queries. Each application of either O(A) or O(B) is taken as a single oracle query. This is basically a search problem and a straightforward application of Grover algorithm can solve this problem but its performance is slow compared to the optimal one by a constant factor of 1.57. Here we present a variant of Grover algorithm which achieves the optimal performance in not too restrictive cases.

arXiv:1210.4648•Oct 17, 2012•2 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.
The quantum search algorithm was discovered by L. K. Grover in 1997, and is called Grover’s algorithm after his name. Let us consider how to find elements marked by a certain symbol out of a database consisting of N elements (say, multi-million elements). This problem is similar to how to find the name of the person from a telephone book knowing only his/her telephone number. This search takes by far more time than finding the phone number from the name of the person. The difference comes from the structure of the telephone book. In the telephone book, the names are arranged in the alphabetical order and constitute the structured database, while phone numbers do not form any structure in the telephone book. In classical computers, when we search one target element from the database with N elements, we need N/ 2 trials on average. Grover showed using the quantum search algorithm that N trials will be enough on average to find the target element from the database with N elements. Shor’s quantum computation algorithm was an epoch-making algorithm which made possible to solve the factorization problem in polynomial time, while the classical computers need exponentially increasing time to solve it. In comparison, Grover’s algorithm makes the data search possible by O ( N ) computation time, while it takes O ( N ) computation time by the classical computers. Concerning the reduction of computing time, Grover’s algorithm may look less powerful than Shor’s algorithm. However, it has good potentiality of application in the wide area such as NP-complete problems and structured databases.
Given two sets A and B and two oracles O(A) and O(B) that can identify the elements of these sets respectively, the goal is to find an element common to both sets using minimum number of oracle queries. Each application of either O(A) or O(B) is taken as a single oracle query. This is basically a search problem and a straightforward application of Grover algorithm can solve this problem but its performance is slow compared to the optimal one by a constant factor of 1.57. Here we present a variant of Grover algorithm which achieves the optimal performance in not too restrictive cases.