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/0609205 · Progress of Theoretical Physics

Group Theoretical Formulation of a Quantum Partial Search Algorithm

V. E. Korepin, Brenno Carlini Vallilo

Published Nov 1, 2006• 14 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1143/ptp.116.783

Related papers

QUANTUM SEARCH ALGORITHMS

V. E. Korepin, YING XU

This article reviews recent progress in quantum database search algorithms. The subject is presented in a self-contained and pedagogical way. The problem of searching a large database (a Hilbert space) for a target item is performed by the famous Grover algorithm which locates the target item with high probability and a quadratic speed-up compared with the corresponding classical algorithm. If the database is partitioned into blocks and one is searching for the block containing the target item instead of the target item itself, then the problem is referred to as partial search. Partial search trades accuracy for speed and the most efficient version is the Grover–Radhakrishnan–Korepin (GRK) algorithm. The target block can be further partitioned into sub-blocks so that GRK's can be performed in a sequence called a hierarchy. We study the Grover search and GRK partial search in detail and prove that a GRK hierarchy is less efficient than a direct GRK partial search. Both the Grover search and the GRK partial search can be generalized to the case with several target items (or target blocks for a GRK). The GRK partial search algorithm can also be represented in terms of group theory.

International Journal of Modern Physics B•Dec 20, 2009•7 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

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•1 citation

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

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•27 citations

Binary quantum search

V. E. Korepin, Ying Dong Xu

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.

arXiv:0705.0777•Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Apr 27, 2007•7 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.
This article reviews recent progress in quantum database search algorithms. The subject is presented in a self-contained and pedagogical way. The problem of searching a large database (a Hilbert space) for a target item is performed by the famous Grover algorithm which locates the target item with high probability and a quadratic speed-up compared with the corresponding classical algorithm. If the database is partitioned into blocks and one is searching for the block containing the target item instead of the target item itself, then the problem is referred to as partial search. Partial search trades accuracy for speed and the most efficient version is the Grover–Radhakrishnan–Korepin (GRK) algorithm. The target block can be further partitioned into sub-blocks so that GRK's can be performed in a sequence called a hierarchy. We study the Grover search and GRK partial search in detail and prove that a GRK hierarchy is less efficient than a direct GRK partial search. Both the Grover search and the GRK partial search can be generalized to the case with several target items (or target blocks for a GRK). The GRK partial search algorithm can also be represented in terms of group theory.
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.
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.
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.
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.