Simple algorithm for partial quantum search

DOI10.1007/S11128-005-0004-ZMaRDI QIDQ2491384zbMATH OpenOpenAlexFDO

Authors Lov K. Grover, Vladimir E. Korepin

Publication date 29 May 2006

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/0504157

zbMATH Keywords

quantum algorithmsQuantum computationsearch algorithms

Mathematics Subject Classification ID

Searching and sorting (68P10) Database theory (68P15) Quantum computation (81P68)

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.33sqrtN/K$ fewer iterations than the quantum search algorithm. They also proved that the best any quantum algorithm could do would be to save $0.78sqrt(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.

Recommendations

• Quantum partial search of a database with several target items
• Quest for fast partial search algorithm
• Optimization of partial search
• Hierarchical quantum search
• HIERARCHICAL QUANTUM SEARCH

Cited in

(22)

• Searching a database under decoherence
• Fast quantum search algorithm for databases of arbitrary size and its implementation in a cavity QED system
• Quantum partial search for uneven distribution of multiple target items
• Quantum partial search algorithm with smaller oracles for multiple target items
• Non-local quantum functions and the distributed Deutsch-Jozsa algorithm
• Quantum partial search of a database with several target items
• Wavelet quantum search algorithm with partial information
• Implementation of efficient quantum search algorithms on NISQ computers
• Workflow of the Grover algorithm simulation incorporating CUDA and GPGPU
• HIERARCHICAL QUANTUM SEARCH
• Optimality proofs of quantum weight decision algorithms
• scientific article; zbMATH DE number 2143771 (Why is no real title available?)
• Multiparty controlled quantum secure direct communication based on quantum search algorithm
• scientific article; zbMATH DE number 1406120 (Why is no real title available?)
• Group Theoretical Formulation of a Quantum Partial Search Algorithm
• Quantum search algorithms
• Quantum algorithm for the asymmetric weight decision problem and its generalization to multiple weights
• Performance analysis of the hardware-efficient quantum search algorithm
• Tree search and quantum computation
• Deterministic quantum partial search for target states with proportion 1/16
• Asymptotic optimality of Grover-Radhakrishnan-Korepin algorithm
• Quest for fast partial search algorithm

This page was built for publication: Simple algorithm for partial quantum search

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2491384)