Quantum Search with Prior Knowledge
arXiv:2009.08721
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.
arXiv comment16 pages, 6 figures
References in corpus (10)
- Quantum Mechanics helps in searching for a needle in a haystack
- Strengths and Weaknesses of Quantum Computing
- Quantum computers can search rapidly by using almost any transformation
- Complete 3-Qubit Grover Search on a Programmable Quantum Computer
- Fixed-point quantum search with an optimal number of queries
- A different kind of quantum search
- Implementation of Grover's Quantum Search Algorithm in a Scalable System
- Coherence depletion in the Grover quantum search algorithm
- Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
- Critically damped quantum search