© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:quant-ph/0011019 · Zeitschrift für Naturforschung A

Quantum Multi-object Search Algorithm with the Availability of Partial Information

Goong Chen, Zijian Diao

Published Dec 1, 2001• 0 citations

Abstract

Abstract Consider the unstructured search of an unknown number I of items in a large unsorted database of size N. The multi-object quantum search algorithm consists of two parts. The first part of the algorithm is to generalize Grover's single-object search algorithm to the multi-object case, and the second part is to solve a counting problem to determine l. In this paper we study the multi-object quantum search algorithm (in continuous time), but in a more structured way by taking into account the availability of partial information. The modeling of available partial information is done simply by the combination of several prescribed, possibly overlapping, information sets with varying weights to signify the reliability of each set. The associated statistics is estimated and the algorithm efficiency and complexity are analyzed. Our analysis shows that the search described here may not be more efficient than the unstructured (generalized) multi-object Grover search if there is "misplaced confidence". However, if the information sets have a "basic confidence" property in the sense that each information set contains at least one search item, then a quadratic speedup holds on a much smaller data space, which further expedites the quantum search for the first item.

DOI: 10.1515/zna-2001-1215

Related papers

Generalization of Grover's Algorithm to Multiobject Search in Quantum Computing, Part I: Continuous Time and Discrete Time

Goong Chen, S. A. Fulling, Jeesen Chen

L. K. Grover's search algorithm in quantum computing gives an optimal, quadratic speedup in the search for a single object in a large unsorted database. In this paper, we generalize Grover's algorithm in a Hilbert-space framework for both continuous and discrete time cases that isolates its geometrical essence to the case where more than one object satisfies the search criterion.

arXiv:quant-ph/0007123•Jul 31, 2000•0 citations

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

Generalization of Grover’s algorithm to multiobject search in quantum computing, Part I: continuous time and dis- crete time

Goong Chen, S. A. Fulling, Jeesen Chen

Abstract L. K. Grover’s search algorithm in quantum computing gives an optimal, quadratic speedup in the search for a single object in a large unsorted database. In this paper, we generalize Grover’s algorithm in a Hilbert-space framework for both continuous and discrete time cases that isolates its geometrical essence to the case where more than one object satisﬁes the search criterion.

Chapman & Hall/CRC eBooks•Feb 14, 2002•15 citations

Improved quantum multi-object search algorithm

Wei-Yun Ma

Grover’s quantum mechanical search algorithm solves the unsorted database search with quadratic speed-up over the classical algorithms.But Grover’s algorithm will be inefficient when the number of matching is close to 2n/2.This paper presents a quantum algorithm which can get a target item with certainty by a single query when the number of the target items is more than a quarter.

Computer Engineering and Applications Journal•Jan 1, 2009•0 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

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

Abstract Consider the unstructured search of an unknown number I of items in a large unsorted database of size N. The multi-object quantum search algorithm consists of two parts. The first part of the algorithm is to generalize Grover's single-object search algorithm to the multi-object case, and the second part is to solve a counting problem to determine l. In this paper we study the multi-object quantum search algorithm (in continuous time), but in a more structured way by taking into account the availability of partial information. The modeling of available partial information is done simply by the combination of several prescribed, possibly overlapping, information sets with varying weights to signify the reliability of each set. The associated statistics is estimated and the algorithm efficiency and complexity are analyzed. Our analysis shows that the search described here may not be more efficient than the unstructured (generalized) multi-object Grover search if there is "misplaced confidence". However, if the information sets have a "basic confidence" property in the sense that each information set contains at least one search item, then a quadratic speedup holds on a much smaller data space, which further expedites the quantum search for the first item.

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.

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.