Quest for Fast Partial Search Algorithm

Abstract

Quantum algorithm can find target item in a database faster than any classical. 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. One can think of partial search in following terms: an exact address of the target item is given by a sequence of many bites, but we want to find only several first bites of the address. We consider different partial search algorithms consisting of a sequence of global and local searches and suggest the optimal one. Global search consists of the standard Grover iterations for the whole database. Local search consists of Grover iterations in each individual block made simultaneously in all blocks. Efficiency of an algorithm is measured by number of queries to the oracle.

11 pages 4 figures

References in corpus (2)

• Simple Algorithm for Partial Quantum Search
• Optimization of Partial Search

Cited by in corpus (9)

• Depth optimization of quantum search algorithms beyond Grover's algorithm
• Implementation of efficient quantum search algorithms on NISQ computers
• Sure success partial search
• Quantum search on noisy intermediate-scale quantum devices
• Group Theoretical Formulation of Quantum Partial Search Algorithm
• Hardware Efficient Quantum Search Algorithm
• Optimization of probabilistic quantum search algorithm with a priori information
• Asymptotic bounds on quantum partial search algorithm and its applications to parallel search
• Asymptotic optimality of Grover-Radhakrishnan-Korepin algorithm