2006/09/27 by V. E. Korepin, Vladimir E. Korepin, Brenno C. Vallilo +1 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #cs.DS #math.GR #quant-ph
paper · pdf · doi:10.1143/ptp.116.783
published as Prog. Theor. Phys. Vol. 116, No. 5 (2006), p. 783 · 12 pages
arxiv created 2006/09/27 · openalex publication_date 2006/11/01 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Searching and sorting are 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 a partial search. For example, an 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, a partial search considers the problem in which a database is separated into several blocks and we want to find a block with the target item, not the target item itself. In this paper, we reformulate a quantum partial search algorithm in terms of group theory.