Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0608106 · Quantum Information Processing

Quantum Partial Search of a Database with Several Target Items

Byung-Soo Choi, V. E. Korepin

Published Aug 1, 2007• 18 citations
arXivHTMLPDF
DOI
10.1007/s11128-007-0056-3

Related papers

Quantum partial search for uneven distribution of multiple target items

Kun Zhang, V. E. Korepin

arXiv:1709.08230•Quantum Information Processing•Apr 28, 2018•12 citations

Quantum partial search algorithm with smaller oracles for multiple target items

Dan Li, Ling Qian, Yuqian Zhou +1 more

Quantum Information Processing•Apr 27, 2022•3 citations

Quantum Algorithm for Partial Search

V. E. Korepin

Bulletin of the American Physical Society•Mar 8, 2007•0 citations

Group Theoretical Formulation of a Quantum Partial Search Algorithm

V. E. Korepin, Brenno Carlini Vallilo

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.

arXiv:quant-ph/0609205•Progress of Theoretical Physics•Nov 1, 2006•14 citations

Quantum Partial Search of a Database with Several Target Items——All the target itemsare asymmetrically divided into two target block

Guo Guang-Can

By quantum Grover search algorithm,people can find a target item in a database faster than any classical algorithm.In this search algorithm the initial state is the equally weighted superposition of all basis states,which is operated by the unitary operator repeatedly.Consequently,non-target states transfer their amplitude to the target state,so we can find the target item with larger probability.However,sometimes we just want to know partial information,so we only need to find the subdatabase(a block) containing the target item,which is partial search.A partial search algorithm was suggested by Grover and Radhakrishnan,which is denoted as Grover-Radhakrishnan Algorithm of Partial Search(GRK),in which they considered the database contains one target item.In our paper,we study the database which contains several target items,and they are randomly distributed in two target blocks.Our algorithm is based on GRK.We minimize the number of queries to the oracle for blocks of large size,and compare this case with the one that each target block contains the same number of target items.

Acta Sinica Quantum Optica•Jan 1, 2008•0 citations

HIERARCHICAL QUANTUM SEARCH

V. E. Korepin, YING XU

Database search has wide applications and is used as a subroutine in many important algorithms. In this paper, we will consider a database with a single target item. Quantum algorithm (Grover) locates the target item faster than any classical algorithm. In addition to a full (Grover) search, it frequently occurs that one is looking for a group of items (a block) containing the target item, rather than the target item itself. This problem is known as partial search. As a generalization of the full search, partial search is of particular importance in practice. Partial search trades accuracy for speed, i.e., it works faster than a full search. There exists different versions of partial search. We will study the optimized version of the algorithm discovered by Grover and Radhakrishnan and call it GRK. GRK can be applied successively (in a sequence). First, the database is partitioned into blocks and GRK is applied to find the target block. This target block is then partitioned into subblocks and GRK is used again to find the target subblock. This procedure can be repeated if the database is large enough. (This sequence of GRK's is called a hierarchy.) Another possibility is to partition the database into subblocks directly and use GRK to find the target subblock once. In this paper, we will prove that the latter is faster (makes less queries to the Oracle).

International Journal of Modern Physics B•Dec 20, 2007•10 citations
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.
By quantum Grover search algorithm,people can find a target item in a database faster than any classical algorithm.In this search algorithm the initial state is the equally weighted superposition of all basis states,which is operated by the unitary operator repeatedly.Consequently,non-target states transfer their amplitude to the target state,so we can find the target item with larger probability.However,sometimes we just want to know partial information,so we only need to find the subdatabase(a block) containing the target item,which is partial search.A partial search algorithm was suggested by Grover and Radhakrishnan,which is denoted as Grover-Radhakrishnan Algorithm of Partial Search(GRK),in which they considered the database contains one target item.In our paper,we study the database which contains several target items,and they are randomly distributed in two target blocks.Our algorithm is based on GRK.We minimize the number of queries to the oracle for blocks of large size,and compare this case with the one that each target block contains the same number of target items.
Database search has wide applications and is used as a subroutine in many important algorithms. In this paper, we will consider a database with a single target item. Quantum algorithm (Grover) locates the target item faster than any classical algorithm. In addition to a full (Grover) search, it frequently occurs that one is looking for a group of items (a block) containing the target item, rather than the target item itself. This problem is known as partial search. As a generalization of the full search, partial search is of particular importance in practice. Partial search trades accuracy for speed, i.e., it works faster than a full search. There exists different versions of partial search. We will study the optimized version of the algorithm discovered by Grover and Radhakrishnan and call it GRK. GRK can be applied successively (in a sequence). First, the database is partitioned into blocks and GRK is applied to find the target block. This target block is then partitioned into subblocks and GRK is used again to find the target subblock. This procedure can be repeated if the database is large enough. (This sequence of GRK's is called a hierarchy.) Another possibility is to partition the database into subblocks directly and use GRK to find the target subblock once. In this paper, we will prove that the latter is faster (makes less queries to the Oracle).