Group Theoretical Formulation of Quantum Partial Search Algorithm

Abstract

Searching and sorting used as a subroutine in many important algorithms. Quantum 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. An example is the following: exact address of the target item is given by a sequence of many bits, but we need to know only some of them. More generally partial search considers the following problem: a database is separated into several blocks. We want to find a block with the target item, not the target item itself. In this paper we reformulate quantum partial search algorithm in terms of group theory.

12 pages

References in corpus (6)

• Strengths and Weaknesses of Quantum Computing
• Quantum Amplitude Amplification and Estimation
• Tight bounds on quantum searching
• Grover's quantum searching algorithm is optimal
• Simple Algorithm for Partial Quantum Search
• Quest for Fast Partial Search Algorithm

Cited by in corpus (8)

• 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
• Quantum search on noisy intermediate-scale quantum devices
• 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
• Quantum partial search for uneven distribution of multiple target items