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

Quantum search with advice

Ashley Montanaro

Published Aug 21, 2009• 2 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.0908.3066

Related papers

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

Quantum Search with Prior Knowledge

Xiaoyu He, Jialin Zhang, Xiaoming Sun

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.

arXiv:2009.08721•Sep 18, 2020•1 citation

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

Super-exponential query complexity reduction via noise-resistant quantum search

Daniel Z. Zanger

In the SEARCH WITH ADVICE problem, a single entry of interest within a database of N entries is to be found assuming that an ordering of the entries, from that with the highest probability of being the entry of interest (as determined by a so-called advice distribution) to that with the lowest, is provided. We present a quantum algorithm that, in the presence of significant levels of quantum noise, solves SEARCH WITH ADVICE for a power law advice distribution with average-case query complexity O(1) as N tends to infinity. Since as we also show the best classical algorithms for this problem exhibit average-case query complexity of order no better than log(N), our quantum algorithm provides a super-exponential reduction in query complexity.

arXiv:1710.10790•Oct 30, 2017•0 citations

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 [Formula: see text] using [Formula: see text] queries. It provides a significant speed-up over any classical algorithm [3]. The running time of the algorithm, however, is very sensitive to errors in queries. Multiple authors have analysed the algorithm using different models of query errors and showed the loss of quantum speed-up [2, 6]. 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 marked elements in [Formula: see text] queries. We also analyze the limiting behavior of the algorithm for a large number of steps and show the existence and the structure of a limiting state [Formula: see text].

International Journal of Foundations of Computer Science•Jun 1, 2018•3 citations

Introducing structure to expedite quantum searching

Marcin Briański, Jan Gwinner, Vladyslav Hlembotskyi +3 more

We present a quantum algorithm for solving the unstructured search problem with one marked element. Our algorithm allows generating quantum circuits that use asymptotically fewer additional quantum gates than the famous Grover's algorithm and may be successfully executed on noisy intermediate-scale quantum devices. We prove that our algorithm is optimal in the total number of elementary gates up to a multiplicative constant. As many NP-hard problems are, in fact, not unstructured, we also describe the partial uncompute technique which exploits the oracle structure and allows a significant reduction in the number of elementary gates required to find the solution. Combining these results allows us to use an asymptotically smaller number of elementary gates than Grover's algorithm in various applications, keeping the number of queries to the oracle essentially the same. We show how the results can be applied to solve hard combinatorial problems, for example, Unique $k$-SAT. Additionally, we show how to asymptotically reduce the number of elementary gates required to solve the unstructured search problem with multiple marked elements.

arXiv:2006.05828•Physical Review A•Jun 28, 2021•13 citations
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 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​.
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.
In the SEARCH WITH ADVICE problem, a single entry of interest within a database of N entries is to be found assuming that an ordering of the entries, from that with the highest probability of being the entry of interest (as determined by a so-called advice distribution) to that with the lowest, is provided. We present a quantum algorithm that, in the presence of significant levels of quantum noise, solves SEARCH WITH ADVICE for a power law advice distribution with average-case query complexity O(1) as N tends to infinity. Since as we also show the best classical algorithms for this problem exhibit average-case query complexity of order no better than log(N), our quantum algorithm provides a super-exponential reduction in query complexity.
Grover’s algorithm is a quantum query algorithm solving the unstructured search problem of size [Formula: see text] using [Formula: see text] queries. It provides a significant speed-up over any classical algorithm [3]. The running time of the algorithm, however, is very sensitive to errors in queries. Multiple authors have analysed the algorithm using different models of query errors and showed the loss of quantum speed-up [2, 6]. 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 marked elements in [Formula: see text] queries. We also analyze the limiting behavior of the algorithm for a large number of steps and show the existence and the structure of a limiting state [Formula: see text].
We present a quantum algorithm for solving the unstructured search problem with one marked element. Our algorithm allows generating quantum circuits that use asymptotically fewer additional quantum gates than the famous Grover's algorithm and may be successfully executed on noisy intermediate-scale quantum devices. We prove that our algorithm is optimal in the total number of elementary gates up to a multiplicative constant. As many NP-hard problems are, in fact, not unstructured, we also describe the partial uncompute technique which exploits the oracle structure and allows a significant reduction in the number of elementary gates required to find the solution. Combining these results allows us to use an asymptotically smaller number of elementary gates than Grover's algorithm in various applications, keeping the number of queries to the oracle essentially the same. We show how the results can be applied to solve hard combinatorial problems, for example, Unique kkk-SAT. Additionally, we show how to asymptotically reduce the number of elementary gates required to solve the unstructured search problem with multiple marked elements.