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/0201049 · Physical Review A

Family of sure-success quantum algorithms for solving a generalized Grover search problem

Chia-Ren Hu

Published Oct 1, 2002• 9 citations
arXivHTMLPDF

Abstract

This work considers a generalization of Grover's search problem, viz., to find any one element in a set of acceptable choices which constitute a fraction f of the total number of choices in an unsorted database. An infinite family of sure-success quantum algorithms are introduced here to solve this problem, each member for a different range of f. The nth member of this family involves n queries of the database, and so the lowest few members of this family should be very convenient algorithms within their ranges of validity. The even member ${\mathcal{A}}_{2n}$ of the family covers an ever larger range of f for larger n, which is expected to become the full range $0<~f<~1$ in the limit $\stackrel{\ensuremath{\rightarrow}}{n}\ensuremath{\infty}.$ These algorithms are particularly useful when the cost of failure of a search is very high, and for multistage searches with a different search criterion for each stage.

DOI
10.1103/physreva.66.042301

Related papers

FORMULATION OF A FAMILY OF SURE-SUCCESS QUANTUM SEARCH ALGORITHMS

Jin-Yuan Hsieh, Che‐Ming Li, Jenn-Sen Lin +1 more

In this work, we consider a family of sure-success quantum algorithms, which is grouped into even and odd members for solving a generalized Grover search problem. We prove the matching conditions for both groups and give the corresponding formulae for evaluating the iterations or oracle calls required in the search computation. We also present how to adjust the phase angles in the generalized Grover operator to ensure the sure-success if minimal oracle calls are demanded in the search.

arXiv:quant-ph/0210201•International Journal of Quantum Information•Aug 30, 2004•2 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

Family of Grover’s quantum-searching algorithms

Alberto Galindo, Miguel Angel Martin-Delgado

We introduce the concepts of Grover operators and Grover kernels to systematically analyze Grover's searching algorithms. Then we investigate a one-parameter family of quantum searching algorithms of Grover type and we show that the standard Grover algorithm is a distinguished member of this family. We show that all the algorithms of this class solve the searching problem with an efficiency of order $O(\sqrt{N}),$ with a coefficient which is class-dependent. The analysis of this dependence is a test of the stability and robustness of the algorithms. We show the stability of this constructions under perturbations of the initial conditions and extend them to a very general class of Grover operators.

arXiv:quant-ph/0009086•Physical Review A•Nov 8, 2000•50 citations

Quantum Searching amidst large uncertainties

D. Li, Xiao-Ming Li, Hongtao Huang +1 more

The quantum search algorithm is a way for finding an item with desired properties in an unsorted database of size N in only$\\sqrt{N}$ steps by means of a sequence of selective inversion and quantum diffusion operations. However, like most quantum algorithms, this requires the algorithm to execute the precise sequence of operations, any further probing into the database only worsens the result. Grover recently showed that by replacing the selective inversion by selective phase shifts of $\\pi /3$, the algorithm converges to the desired item monotonically. This paper builds on that result and considers the problem of retrieving a marked item from a database containing an unknown fraction of marked items, say $\\epsilon $. We derive optimal algorithms for different ranges of $\\epsilon .$ These are similar to Grover's recent algorithm but the phase shift turns out to vary with $\\epsilon $ - this is generally quite different from $\\pi /3$.

•Jan 1, 2006•0 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

Robust Quantum Search with Uncertain Number of Target States

Yuanyue Zhu, Zeguo Wang, Bao Yan +1 more

The quantum search algorithm is one of the milestones of quantum algorithms. Compared with classical algorithms, it shows quadratic speed-up when searching marked states in an unsorted database. However, the success rates of quantum search algorithms are sensitive to the number of marked states. In this paper, we study the relation between the success rate and the number of iterations in a quantum search algorithm of given λ=M/N, where M is the number of marked state and N is the number of items in the dataset. We develop a robust quantum search algorithm based on Grover–Long algorithm with some uncertainty in the number of marked states. The proposed algorithm has the same query complexity ON as the Grover’s algorithm, and shows high tolerance of the uncertainty in the ratio M/N. In particular, for a database with an uncertainty in the ratio M±MN, our algorithm will find the target states with a success rate no less than 96%.

Entropy•Dec 8, 2021•5 citations
This work considers a generalization of Grover's search problem, viz., to find any one element in a set of acceptable choices which constitute a fraction f of the total number of choices in an unsorted database. An infinite family of sure-success quantum algorithms are introduced here to solve this problem, each member for a different range of f. The nth member of this family involves n queries of the database, and so the lowest few members of this family should be very convenient algorithms within their ranges of validity. The even member A2n{\mathcal{A}}_{2n}A2n​ of the family covers an ever larger range of f for larger n, which is expected to become the full range 0< f< 10<~f<~10< f< 1 in the limit n\ensuremath→\ensuremath∞.\stackrel{\ensuremath{\rightarrow}}{n}\ensuremath{\infty}.n\ensuremath→\ensuremath∞. These algorithms are particularly useful when the cost of failure of a search is very high, and for multistage searches with a different search criterion for each stage.
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.
We introduce the concepts of Grover operators and Grover kernels to systematically analyze Grover's searching algorithms. Then we investigate a one-parameter family of quantum searching algorithms of Grover type and we show that the standard Grover algorithm is a distinguished member of this family. We show that all the algorithms of this class solve the searching problem with an efficiency of order O(N),O(\sqrt{N}),O(N​), with a coefficient which is class-dependent. The analysis of this dependence is a test of the stability and robustness of the algorithms. We show the stability of this constructions under perturbations of the initial conditions and extend them to a very general class of Grover operators.
The quantum search algorithm is a way for finding an item with desired properties in an unsorted database of size N in onlysqrtN\\sqrt{N}sqrtN steps by means of a sequence of selective inversion and quantum diffusion operations. However, like most quantum algorithms, this requires the algorithm to execute the precise sequence of operations, any further probing into the database only worsens the result. Grover recently showed that by replacing the selective inversion by selective phase shifts of pi/3\\pi /3pi/3, the algorithm converges to the desired item monotonically. This paper builds on that result and considers the problem of retrieving a marked item from a database containing an unknown fraction of marked items, say $\\epsilon $. We derive optimal algorithms for different ranges of epsilon.\\epsilon .epsilon. These are similar to Grover's recent algorithm but the phase shift turns out to vary with $\\epsilon $ - this is generally quite different from pi/3\\pi /3pi/3.
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.
The quantum search algorithm is one of the milestones of quantum algorithms. Compared with classical algorithms, it shows quadratic speed-up when searching marked states in an unsorted database. However, the success rates of quantum search algorithms are sensitive to the number of marked states. In this paper, we study the relation between the success rate and the number of iterations in a quantum search algorithm of given λ=M/N, where M is the number of marked state and N is the number of items in the dataset. We develop a robust quantum search algorithm based on Grover–Long algorithm with some uncertainty in the number of marked states. The proposed algorithm has the same query complexity ON as the Grover’s algorithm, and shows high tolerance of the uncertainty in the ratio M/N. In particular, for a database with an uncertainty in the ratio M±MN, our algorithm will find the target states with a success rate no less than 96%.