2005/04/21 by V. E. Korepin, Vladimir E. Korepin, Lov K. Grover · 3 citations
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Block (permutation group theory) #Combinatorics #Computer science #Database search engine #Information retrieval #Mathematics #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum algorithm #Quantum computer #Quantum error correction #Quantum information #Quantum mechanics #Quantum phase estimation algorithm #Search algorithm #Search engine #Simple (philosophy) #Theoretical computer science #quant-ph
paper · pdf · doi:10.1007/s11128-005-0004-z
published as Quantum Information Processing, vol. 5, number 1, page 5-10, 2006 · 3 pages, 3 figures
arxiv created 2005/04/21 · openalex publication_date 2006/02/01 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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√(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 √(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.