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:2009.08721

Quantum Search with Prior Knowledge

Xiaoyu He, Jialin Zhang, Xiaoming Sun

Published Sep 18, 2020• 1 citation
arXivHTMLPDF

Abstract

Search-base algorithms have widespread applications in different scenarios. Grover's quantum search algorithms and its generalization, amplitude amplification, provide a quadratic speedup over classical search algorithms for unstructured search. We consider the problem of searching with prior knowledge. More preciously, search for the solution among N items with a prior probability distribution. This letter proposes a new generalization of Grover's search algorithm which performs better than the standard Grover algorithm in average under this setting. We prove that our new algorithm achieves the optimal expected success probability of finding the solution if the number of queries is fixed.

DOI
10.48550/arxiv.2009.08721

Related papers

Adaptive complete quantum search with unknown number of solutions

Raj Alexandru Guţoiu, Bogdan-Călin Ciobanu, Pantelimon George Popescu

Unstructured database search is a fundamental problem that requires finding one or more elements satisfying a specific property within a set of candidates. While Grover's algorithm provides a quadratic speedup for finding a marked element when the number of solutions is known, finding all solutions when their number is unknown presents additional challenges. In this paper, we thoroughly analyze this problem by considering all the different regimes of combinations of classical, Grover and generalized fixed-point quantum search instances. We unify these into an adaptive Bayesian approach that maximizes the expected success probability per unit execution time at each searching instance. For a problem with a known number of solutions, much lower than the database size, we prove that our proposed approach is asymptotically optimal within the considered search model. Furthermore, we prove that for any probability distribution characterizing the likely number of solutions, in regimes where the classical verification time is at most 25% of the quantum amplitude amplification time, hybrid classical and Grover approaches are preferred to generalized fixed-point. Outside of this regime, we derive an upper bound on the maximal improvement achievable by fixed-point search compared to the best Grover-based score. Additionally, we determine the optimal transition point between classical sampling and quantum searching using an integral approximation of the probability distribution of the number of solutions. The analytical results are also supported by numerical simulations of the proposed algorithm and by comparisons between the generalized fixed-point and Grover-based search policies.

quant-pharXiv:2610.06364•Oct 6, 2026•0 citations

Fixed-Point Quantum Search with an Optimal Number of Queries

Theodore J. Yoder, Guang Hao Low, Isaac L. Chuang

Grover's quantum search and its generalization, quantum amplitude amplification, provide a quadratic advantage over classical algorithms for a diverse set of tasks but are tricky to use without knowing beforehand what fraction λ of the initial state is comprised of the target states. In contrast, fixed-point search algorithms need only a reliable lower bound on this fraction but, as a consequence, lose the very quadratic advantage that makes Grover's algorithm so appealing. Here we provide the first version of amplitude amplification that achieves fixed-point behavior without sacrificing the quantum speedup. Our result incorporates an adjustable bound on the failure probability and, for a given number of oracle queries, guarantees that this bound is satisfied over the broadest possible range of λ.

arXiv:1409.3305•Physical Review Letters•Nov 18, 2014•223 citations

Quantum search with advice

Ashley Montanaro

We consider the problem of search of an unstructured list for a marked element, when one is given advice as to where this element might be located, in the form of a probability distribution. The goal is to minimise the expected number of queries to the list made to find the marked element, with respect to this distribution. We present a quantum algorithm which solves this problem using an optimal number of queries, up to a constant factor. For some distributions on the input, such as certain power law distributions, the algorithm can achieve exponential speed-ups over the best possible classical algorithm. We also give an efficient quantum algorithm for a variant of this task where the distribution is not known in advance, but must be queried at an additional cost. The algorithms are based on the use of Grover's quantum search algorithm and amplitude amplification as subroutines.

arXiv:0908.3066•Aug 21, 2009•2 citations

Optimal fixed-point quantum amplitude amplification using Chebyshev polynomials

Theodore J. Yoder, Guang Hao Low, Isaac L. Chuang

Grover's quantum search and its generalization, quantum amplitude amplification, provide quadratic advantage over classical algorithms for a diverse set of tasks, but are tricky to use without knowing beforehand what fraction $\lambda$ of the initial state is comprised of the target states. In contrast, fixed-point search algorithms need only a reliable lower bound on this fraction, but, as a consequence, lose the very quadratic advantage that makes Grover's algorithm so appealing. Here we provide the first version of amplitude amplification that achieves fixed-point behavior without sacrificing the quantum speedup. Our result incorporates an adjustable bound on the failure probability, and, for a given number of oracle queries, guarantees that this bound is satisfied over the broadest possible range of $\lambda$.

•Sep 11, 2014•1 citation

Applications and limits of the Grover Quantum Algorithm

David R.C. Hill, Benjamin A. Antunes

The Grover algorithm is a fundamental quantum algorithm that achieves a quadratic speedup for unstructured search problems, requiring O(√N) queries instead of O(N) classically. It works by repeatedly applying an oracle and a diffusion operator to amplify the probability of marked states. This advantage makes it relevant to cryptography, optimization, constraint satisfaction, and as a general primitive via amplitude amplification in areas like quantum machine learning and simulation. However, practical implementations are severely constrained by current Noisy Intermediate Scale Qualtum machines with limited coherence, deep oracle circuits and lack of scalable QRAM, restricting demonstrations to small-scale experiments with reproducibility challenges.

•Jan 23, 2026•0 citations

Deterministic Grover search with a restricted oracle

Tanay Roy, Liang Jiang, David Schuster

Grover's quantum search algorithm provides a quadratic quantum advantage over classical algorithms across a broad class of unstructured search problems.The original protocol is probabilistic, returning the desired result with significant probability on each query but, in general, requiring several iterations of the algorithm.We present a modified version to return the correct result with certainty without having user control over the quantum search oracle.Our deterministic, two-parameter "D2p" protocol utilizes generalized phase rotations replacing the phase inversions after a standard oracle query.The D2p protocol achieves a 100% success rate in no more than one additional iteration compared to the optimal number of steps as in the original Grover's search enabling the same quadratic speedup.We also provide a visualization using the Bloch sphere for enhanced geometric intuition.

arXiv:2201.00091•Physical Review Research•Apr 21, 2022•60 citations
Search-base algorithms have widespread applications in different scenarios. Grover's quantum search algorithms and its generalization, amplitude amplification, provide a quadratic speedup over classical search algorithms for unstructured search. We consider the problem of searching with prior knowledge. More preciously, search for the solution among N items with a prior probability distribution. This letter proposes a new generalization of Grover's search algorithm which performs better than the standard Grover algorithm in average under this setting. We prove that our new algorithm achieves the optimal expected success probability of finding the solution if the number of queries is fixed.
Unstructured database search is a fundamental problem that requires finding one or more elements satisfying a specific property within a set of candidates. While Grover's algorithm provides a quadratic speedup for finding a marked element when the number of solutions is known, finding all solutions when their number is unknown presents additional challenges. In this paper, we thoroughly analyze this problem by considering all the different regimes of combinations of classical, Grover and generalized fixed-point quantum search instances. We unify these into an adaptive Bayesian approach that maximizes the expected success probability per unit execution time at each searching instance. For a problem with a known number of solutions, much lower than the database size, we prove that our proposed approach is asymptotically optimal within the considered search model. Furthermore, we prove that for any probability distribution characterizing the likely number of solutions, in regimes where the classical verification time is at most 25% of the quantum amplitude amplification time, hybrid classical and Grover approaches are preferred to generalized fixed-point. Outside of this regime, we derive an upper bound on the maximal improvement achievable by fixed-point search compared to the best Grover-based score. Additionally, we determine the optimal transition point between classical sampling and quantum searching using an integral approximation of the probability distribution of the number of solutions. The analytical results are also supported by numerical simulations of the proposed algorithm and by comparisons between the generalized fixed-point and Grover-based search policies.
Grover's quantum search and its generalization, quantum amplitude amplification, provide a quadratic advantage over classical algorithms for a diverse set of tasks but are tricky to use without knowing beforehand what fraction λ of the initial state is comprised of the target states. In contrast, fixed-point search algorithms need only a reliable lower bound on this fraction but, as a consequence, lose the very quadratic advantage that makes Grover's algorithm so appealing. Here we provide the first version of amplitude amplification that achieves fixed-point behavior without sacrificing the quantum speedup. Our result incorporates an adjustable bound on the failure probability and, for a given number of oracle queries, guarantees that this bound is satisfied over the broadest possible range of λ.
We consider the problem of search of an unstructured list for a marked element, when one is given advice as to where this element might be located, in the form of a probability distribution. The goal is to minimise the expected number of queries to the list made to find the marked element, with respect to this distribution. We present a quantum algorithm which solves this problem using an optimal number of queries, up to a constant factor. For some distributions on the input, such as certain power law distributions, the algorithm can achieve exponential speed-ups over the best possible classical algorithm. We also give an efficient quantum algorithm for a variant of this task where the distribution is not known in advance, but must be queried at an additional cost. The algorithms are based on the use of Grover's quantum search algorithm and amplitude amplification as subroutines.
Grover's quantum search and its generalization, quantum amplitude amplification, provide quadratic advantage over classical algorithms for a diverse set of tasks, but are tricky to use without knowing beforehand what fraction λ\lambdaλ of the initial state is comprised of the target states. In contrast, fixed-point search algorithms need only a reliable lower bound on this fraction, but, as a consequence, lose the very quadratic advantage that makes Grover's algorithm so appealing. Here we provide the first version of amplitude amplification that achieves fixed-point behavior without sacrificing the quantum speedup. Our result incorporates an adjustable bound on the failure probability, and, for a given number of oracle queries, guarantees that this bound is satisfied over the broadest possible range of λ\lambdaλ.
The Grover algorithm is a fundamental quantum algorithm that achieves a quadratic speedup for unstructured search problems, requiring O(√N) queries instead of O(N) classically. It works by repeatedly applying an oracle and a diffusion operator to amplify the probability of marked states. This advantage makes it relevant to cryptography, optimization, constraint satisfaction, and as a general primitive via amplitude amplification in areas like quantum machine learning and simulation. However, practical implementations are severely constrained by current Noisy Intermediate Scale Qualtum machines with limited coherence, deep oracle circuits and lack of scalable QRAM, restricting demonstrations to small-scale experiments with reproducibility challenges.
Grover's quantum search algorithm provides a quadratic quantum advantage over classical algorithms across a broad class of unstructured search problems.The original protocol is probabilistic, returning the desired result with significant probability on each query but, in general, requiring several iterations of the algorithm.We present a modified version to return the correct result with certainty without having user control over the quantum search oracle.Our deterministic, two-parameter "D2p" protocol utilizes generalized phase rotations replacing the phase inversions after a standard oracle query.The D2p protocol achieves a 100% success rate in no more than one additional iteration compared to the optimal number of steps as in the original Grover's search enabling the same quadratic speedup.We also provide a visualization using the Bloch sphere for enhanced geometric intuition.