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/0407122 · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)

Is partial quantum search of a database any easier?

Lov K. Grover, Jaikumar Radhakrishnan

Published Jul 18, 2005• 48 citations
arXivHTMLPDF

Abstract

We consider the partial database search problem where given a quantum database f : {0,1}n→{0,1} such that f(x) =1 for a unique x ∈ {0,1}n, we are required to determine only the first k bits of the address x. We present an algorithm and derive a lower bound for this problem. Let q(k,n) be the minimum number of queries needed to find the first k bits of the required address x with certainty (or with very high probability, say 1--O(N--¼)). We show that there exist constants ck (corresponding to the algorithm) and dk (corresponding to the lower bound) such that πover4 (1--dkover√K) √N ≤ q(k,n) ≤ πover4 (1--ckover√K) √N, where K=2k and N=2n. Our algorithm returns the correct answer with probability 1--O(N--½), and can be easily modified to give the correct answer with certainty. The lower bound for algorithms that return the correct answer with certainty is proved by reducing the usual database search problem to this partial search problem, and invoking Zalka's lower bound showing that Grovers algorithm is optimal for the usual database search problem. We then derive a lower bound that is applicable for database search algorithms that err with small probability, and use it to show that our lower bound also applies to partial search algorithms that return the correct answer with probability at least 1--O(N--¼).

DOI
10.1145/1073970.1073997

Related papers

Tight Bounds on Quantum Searching

Michel Boyer, Gilles Brassard A, Peter Høyer +1 more

We provide a tight analysis of Grover's algorithm for quantum database searching. We give a simple closed-form formula for the probability of success after any given number of iterations of the algorithm. This allows us to determine the number of iterations necessary to achieve almost certainty of finding the answer. Furthermore, we analyse the behaviour of the algorithm when the element to be found appears more than once in the table and we provide a new algorithm to find such an element even when the number of solutions is not known ahead of time. Finally, we provide a lower bound on the efficiency of any possible quantum database searching algorithm and we show that Grover's algorithm comes within 2.62% of being optimal.

arXiv:quant-ph/9605034•Fortschritte der Physik•Jun 1, 1998•756 citations

Tight Bounds on Quantum Searching

Michel Boyer, Gilles Brassard A, Peter Høyer +1 more

We provide a tight analysis of Grover's algorithm for quantum database searching. We give a simple closed-form formula for the probability of success after any given number of iterations of the algorithm. This allows us to determine the number of iterations necessary to achieve almost certainty of finding the answer. Furthermore, we analyse the behaviour of the algorithm when the element to be found appears more than once in the table and we provide a new algorithm to find such an element even when the number of solutions is not known ahead of time. Finally, we provide a lower bound on the efficiency of any possible quantum database searching algorithm and we show that Grover's algorithm comes within 2.62% of being optimal. Keywords: Quantum computation. Searching. Lower bound. This research was presented at the Fourth Workshop on Physics and Computation, Boston, 23 November 1996. y D'epartement IRO, Universit'e de Montr'eal, C.P. 6128, succursale centre-ville, Montr'eal (Qu'ebec...

•Jan 1, 1996•823 citations

Asymptotic bounds on quantum partial search algorithm and its applications to parallel search

Yan-Bo Jiang, Xiao-Hui Wang, Kun Zhang +1 more

Grover's algorithm provides a quadratic speedup over classical algorithms for searching an unstructured database and is known to be strictly optimal in oracle query complexity, with tight bounds on its success probability. Although the standard Grover search cannot be further accelerated in the full-search setting, a trade-off between accuracy and query complexity gives rise to the partial search problem. The Grover-Radhakrishnan-Korepin (GRK) algorithm is the standard and most extensively studied protocol for this task. In this work, we provide systematic numerical evidence that the GRK operator sequence gives the highest success probability in all examined cases, supporting it as the optimal ansatz among admissible compositions of global and local Grover operators. Guided by this numerically supported GRK ansatz, we derive an asymptotically tight upper bound on the maximal success probability within the GRK family and establish the corresponding lower bound on the minimal expected number of oracle queries. Furthermore, we investigate parallel quantum search within the partial-search framework. While a direct GRK-based parallelization does not outperform established parallel Grover schemes, we demonstrate that a hybrid strategy combining partial and full search protocols yields a strict, though subleading, improvement over the outer parallel Grover scheme. Our results clarify the fundamental limits of quantum partial search and its role in optimizing parallel quantum search algorithms.

quant-pharXiv:2603.01462•Physical Review A•Mar 3, 2026•1 citation

Optimizing the number of gates in quantum search

Srinivasan Arunachalam, Ronald de Wolf

In its usual form, Grover’s quantum search algorithm uses O( √ N) queries and O( √ N log N) other elementary gates to find a solution in an N-bit database. Grover in 2002 showed how to reduce the number of other gates to O( √ N log log N) for the special case where the database has a unique solution, without significantly increasing the number of queries. We show how to reduce this further to O( √ N log(r) N) gates for every constant r, and sufficiently large N. This means that, on average, the circuits between two queries barely touch more than a constant number of the log N qubits on which the algorithm acts. For a very large N that is a power of 2, we can choose r such that the algorithm uses essentially the minimal number π 4 √ N of queries, and only O( √ N log(log? N)) other gates.

arXiv:1512.07550•Quantum Information and Computation•Mar 1, 2017•7 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

Quantum Computers Can Search Arbitrarily Large Databases by a Single Query

Lov K. Grover

This paper shows that a quantum mechanical algorithm that can query information relating to multiple items of the database can search a database for a unique item satisfying a given condition, in a single query [a query is defined as any question to the database to which the database has to return a (yes/no answer]. A classical algorithm will be limited to the information theoretic bound of at least ${log}_{2}N$ queries, which it would achieve by using a binary search.

arXiv:quant-ph/9706005•Physical Review Letters•Dec 8, 1997•432 citations
We consider the partial database search problem where given a quantum database f : {0,1}n→{0,1} such that f(x) =1 for a unique x ∈ {0,1}n, we are required to determine only the first k bits of the address x. We present an algorithm and derive a lower bound for this problem. Let q(k,n) be the minimum number of queries needed to find the first k bits of the required address x with certainty (or with very high probability, say 1--O(N--¼)). We show that there exist constants ck (corresponding to the algorithm) and dk (corresponding to the lower bound) such that πover4 (1--dkover√K) √N ≤ q(k,n) ≤ πover4 (1--ckover√K) √N, where K=2k and N=2n. Our algorithm returns the correct answer with probability 1--O(N--½), and can be easily modified to give the correct answer with certainty. The lower bound for algorithms that return the correct answer with certainty is proved by reducing the usual database search problem to this partial search problem, and invoking Zalka's lower bound showing that Grovers algorithm is optimal for the usual database search problem. We then derive a lower bound that is applicable for database search algorithms that err with small probability, and use it to show that our lower bound also applies to partial search algorithms that return the correct answer with probability at least 1--O(N--¼).
We provide a tight analysis of Grover's algorithm for quantum database searching. We give a simple closed-form formula for the probability of success after any given number of iterations of the algorithm. This allows us to determine the number of iterations necessary to achieve almost certainty of finding the answer. Furthermore, we analyse the behaviour of the algorithm when the element to be found appears more than once in the table and we provide a new algorithm to find such an element even when the number of solutions is not known ahead of time. Finally, we provide a lower bound on the efficiency of any possible quantum database searching algorithm and we show that Grover's algorithm comes within 2.62% of being optimal.
We provide a tight analysis of Grover's algorithm for quantum database searching. We give a simple closed-form formula for the probability of success after any given number of iterations of the algorithm. This allows us to determine the number of iterations necessary to achieve almost certainty of finding the answer. Furthermore, we analyse the behaviour of the algorithm when the element to be found appears more than once in the table and we provide a new algorithm to find such an element even when the number of solutions is not known ahead of time. Finally, we provide a lower bound on the efficiency of any possible quantum database searching algorithm and we show that Grover's algorithm comes within 2.62% of being optimal. Keywords: Quantum computation. Searching. Lower bound. This research was presented at the Fourth Workshop on Physics and Computation, Boston, 23 November 1996. y D'epartement IRO, Universit'e de Montr'eal, C.P. 6128, succursale centre-ville, Montr'eal (Qu'ebec...
Grover's algorithm provides a quadratic speedup over classical algorithms for searching an unstructured database and is known to be strictly optimal in oracle query complexity, with tight bounds on its success probability. Although the standard Grover search cannot be further accelerated in the full-search setting, a trade-off between accuracy and query complexity gives rise to the partial search problem. The Grover-Radhakrishnan-Korepin (GRK) algorithm is the standard and most extensively studied protocol for this task. In this work, we provide systematic numerical evidence that the GRK operator sequence gives the highest success probability in all examined cases, supporting it as the optimal ansatz among admissible compositions of global and local Grover operators. Guided by this numerically supported GRK ansatz, we derive an asymptotically tight upper bound on the maximal success probability within the GRK family and establish the corresponding lower bound on the minimal expected number of oracle queries. Furthermore, we investigate parallel quantum search within the partial-search framework. While a direct GRK-based parallelization does not outperform established parallel Grover schemes, we demonstrate that a hybrid strategy combining partial and full search protocols yields a strict, though subleading, improvement over the outer parallel Grover scheme. Our results clarify the fundamental limits of quantum partial search and its role in optimizing parallel quantum search algorithms.
In its usual form, Grover’s quantum search algorithm uses O( √ N) queries and O( √ N log N) other elementary gates to find a solution in an N-bit database. Grover in 2002 showed how to reduce the number of other gates to O( √ N log log N) for the special case where the database has a unique solution, without significantly increasing the number of queries. We show how to reduce this further to O( √ N log(r) N) gates for every constant r, and sufficiently large N. This means that, on average, the circuits between two queries barely touch more than a constant number of the log N qubits on which the algorithm acts. For a very large N that is a power of 2, we can choose r such that the algorithm uses essentially the minimal number π 4 √ N of queries, and only O( √ N log(log? N)) other gates.
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.
This paper shows that a quantum mechanical algorithm that can query information relating to multiple items of the database can search a database for a unique item satisfying a given condition, in a single query [a query is defined as any question to the database to which the database has to return a (yes/no answer]. A classical algorithm will be limited to the information theoretic bound of at least log2N{log}_{2}Nlog2​N queries, which it would achieve by using a binary search.