Optimization of Partial Search

Abstract

Quantum Grover search algorithm can find a target item in a database faster than any classical algorithm. One can trade accuracy for speed and find a part of the database (a block) containing the target item even faster, this is partial search. A partial search algorithm was recently suggested by Grover and Radhakrishnan. Here we optimize it. Efficiency of the search algorithm is measured by number of queries to the oracle. The author suggests new version of Grover-Radhakrishnan algorithm which uses minimal number of queries to the oracle. The algorithm can run on the same hardware which is used for the usual Grover algorithm.

5 pages

Cited by in corpus (9)

• A Review on Quantum Search Algorithms
• Depth optimization of quantum search algorithms beyond Grover's algorithm
• Implementation of efficient quantum search algorithms on NISQ computers
• Sure success partial search
• Quest for Fast Partial Search Algorithm
• Optimization of probabilistic quantum search algorithm with a priori information
• Near-deterministic quantum search algorithm without phase design
• Asymptotic bounds on quantum partial search algorithm and its applications to parallel search
• Asymptotic optimality of Grover-Radhakrishnan-Korepin algorithm