Simple Algorithm for Partial Quantum Search

Abstract

Quite often in database search, we only need to extract portion of the information about the satisfying item. Recently Radhakrishnan & Grover [RG] considered this problem in the following form: the database of $N$ items was divided into $K$ equally sized blocks. The algorithm has just to find the block containing the item of interest. The queries are exactly the same as in the standard database search problem. [RG] invented a quantum algorithm for this problem of partial search that took about $0.33\sqrt{N/K}$ fewer iterations than the quantum search algorithm. They also proved that the best any quantum algorithm could do would be to save $0.78\sqrt{(}N/K)$ iterations. The main limitation of the algorithm was that it involved complicated analysis as a result of which it has been inaccessible to most of the community. This paper gives a simple analysis of the algorithm. This analysis is based on three elementary observations about quantum search, does not require a single equation and takes less than 2 pages.

3 pages, 3 figures

References in corpus (3)

• Quantum Mechanics helps in searching for a needle in a haystack
• Grover's quantum searching algorithm is optimal
• Finding Matches between Two Databases on a Quantum Computer

Cited by in corpus (15)

• 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
• Quest for Fast Partial Search Algorithm
• Group Theoretical Formulation of Quantum Partial Search Algorithm
• Tree Search and Quantum Computation
• Hardware Efficient Quantum Search Algorithm
• Optimization of probabilistic quantum search algorithm with a priori information
• Application of a Quantum Search Algorithm to High- Energy Physics Data at the Large Hadron Collider
• Near-deterministic quantum search algorithm without phase design
• A Quantum Production Model
• Asymptotic bounds on quantum partial search algorithm and its applications to parallel search
• Asymptotic optimality of Grover-Radhakrishnan-Korepin algorithm
• Quantum search followed by classical search versus quantum search alone