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:0705.0777 · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE

Binary quantum search

V. E. Korepin, Ying Dong Xu

Published Apr 27, 2007• 7 citations
arXivHTMLPDF

Abstract

We consider a database with one target item. Partial search is designed to find a part of the database [a block] containing the target item. After a user finds the target block he/she might want to make another partial search: subdivide the target block into sub-blocks and look for a sub-block containing the target item. An example: if we need to go to a hotel, we first look at a State map [to find highways] and then at a town map [to find a local approach to the hotel]. Number of queries necessary for sequential searches is calculated in the paper. Sequential partial search can be done faster the first one.

DOI
10.1117/12.717282

Related papers

HIERARCHICAL QUANTUM SEARCH

V. E. Korepin, Ying Xu

We consider a database with one target item. Partial search is designed to find a part of a database [a block] containing the target item. After a user finds the target block he/she might want to make another partial search: subdivide the target block into sub-blocks and look for a sub-block containing the target item. An example: if we need to go to a hotel in USA in a remote location, we first look at a State map [to find highways, which lead to a town with that hotel] and then at the town map [to find a local approach to the hotel]. Minimal number of queries necessary for sequential searches is calculated in the paper. Sequential partial search can be done faster the first one.

Contemporary mathematics - American Mathematical Society•Dec 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•9 citations

Quantum Partial Searching Algorithm of a Database with Several Target Items

Zhong Pu-Cha, Wan‐Su Bao, Wei-Yun Ma

Choi and Korepin [Quantum Information Processing 6(2007)243] presented a quantum partial search algorithm of a database with several target items which can find a target block quickly when each target block contains the same number of target items. Actually, the number of target items in each target block is arbitrary. Aiming at this case, we give a condition to guarantee performance of the partial search algorithm to be performed and the number of queries to oracle of the algorithm to be minimized. In addition, by further numerical computing we come to the conclusion that the more uniform the distribution of target items, the smaller the number of queries.

Chinese Physics Letters•Feb 1, 2009•2 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•17 citations

Optimization of partial search

V. E. Korepin

A quantum Grover search 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. A partial search algorithm was recently suggested by Grover and Radhakrishnan. Here we optimize it. Efficiency of the search algorithm is measured by the number of queries to the oracle. The author suggests a new version of the Grover–Radhakrishnan algorithm which uses a minimal number of such queries. The algorithm can run on the same hardware that is used for the usual Grover algorithm.

arXiv:quant-ph/0503238•Journal of Physics A Mathematical and General•Oct 19, 2005•30 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
We consider a database with one target item. Partial search is designed to find a part of the database [a block] containing the target item. After a user finds the target block he/she might want to make another partial search: subdivide the target block into sub-blocks and look for a sub-block containing the target item. An example: if we need to go to a hotel, we first look at a State map [to find highways] and then at a town map [to find a local approach to the hotel]. Number of queries necessary for sequential searches is calculated in the paper. Sequential partial search can be done faster the first one.
We consider a database with one target item. Partial search is designed to find a part of a database [a block] containing the target item. After a user finds the target block he/she might want to make another partial search: subdivide the target block into sub-blocks and look for a sub-block containing the target item. An example: if we need to go to a hotel in USA in a remote location, we first look at a State map [to find highways, which lead to a town with that hotel] and then at the town map [to find a local approach to the hotel]. Minimal number of queries necessary for sequential searches is calculated in the paper. Sequential partial search can be done faster the first one.
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).
Choi and Korepin [Quantum Information Processing 6(2007)243] presented a quantum partial search algorithm of a database with several target items which can find a target block quickly when each target block contains the same number of target items. Actually, the number of target items in each target block is arbitrary. Aiming at this case, we give a condition to guarantee performance of the partial search algorithm to be performed and the number of queries to oracle of the algorithm to be minimized. In addition, by further numerical computing we come to the conclusion that the more uniform the distribution of target items, the smaller the number of queries.
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.
A quantum Grover search 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. A partial search algorithm was recently suggested by Grover and Radhakrishnan. Here we optimize it. Efficiency of the search algorithm is measured by the number of queries to the oracle. The author suggests a new version of the Grover–Radhakrishnan algorithm which uses a minimal number of such queries. The algorithm can run on the same hardware that is used for the usual Grover algorithm.
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.