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:0904.3060

An efficient quantum search engine on unsorted database

Heping Hu, Yingyu Zhang, Zhengding Lu

Published Apr 20, 2009• 0 citations
arXivHTMLPDF

Abstract

We consider the problem of finding one or more desired items out of an unsorted database. Patel has shown that if the database permits quantum queries, then mere digitization is sufficient for efficient search for one desired item. The algorithm, called factorized quantum search algorithm, presented by him can locate the desired item in an unsorted database using $O(log_{4}N)$ queries to factorized oracles. But the algorithm requires that all the property values must be distinct from each other. In this paper, we discuss how to make a database satisfy the requirements, and present a quantum search engine based on the algorithm. Our goal is achieved by introducing auxiliary files for the property values that are not distinct, and converting every complex query request into a sequence of calls to factorized quantum search algorithm. The query complexity of our algorithm is $O(P*Q*M*log_{4}N)$, where P is the number of the potential simple query requests in the complex query request, Q is the maximum number of calls to the factorized quantum search algorithm of the simple queries, M is the number of the auxiliary files for the property on which our algorithm are searching for desired items. This implies that to manage an unsorted database on an actual quantum computer is possible and efficient.

DOI
10.48550/arxiv.0904.3060

Related papers

Quantum database search can do without sorting

Apoorva D. Patel

Sorting is a fundamental computational process that facilitates subsequent searching of a database. It can be thought of as factorization of the search process. The location of a desired item in a sorted database can be found by classical queries that inspect one letter of the label at a time. For an unsorted database, no such classical quick search algorithm is available. If the database permits quantum queries, however, then mere digitization is sufficient for efficient search. Sorting becomes redundant with the quantum superposition of states. A quantum algorithm is written down that locates the desired item in an unsorted database a factor of two faster than the best classical algorithm can in a sorted database. This algorithm has close resemblance to the assembly process in DNA replication.

arXiv:quant-ph/0012149•Physical Review A•Aug 15, 2001•16 citations

Quantum search for multiple items using parallel queries

Lov K. Grover, Jaikumar Radhakrishnan

In the quantum database search problem we are required to search for an item in a database. In this paper, we consider a generalization of this problem, where we are provided d identical copes of a database each with N items which we can query in parallel. Then, given k items, we are required to determine the locations where these items are stored. We show that any quantum algorithm for this task must perform Omega(sqrt{Nk/d min{d,k}}) parallel queries. We also design an algorithm whose performance comes within a factor O(log d) of this lower bound.

arXiv:quant-ph/0407217•Jul 27, 2004•9 citations

Hardware Efficient Quantum Search Algorithm

Ji Liu, Huiyang Zhou

Quantum computing has noteworthy speedup over classical computing by taking advantage of quantum parallelism, i.e., the superposition of states. In particular, quantum search is widely used in various computationally hard problems. Grover's search algorithm finds the target element in an unsorted database with quadratic speedup than classical search and has been proved to be optimal in terms of the number of queries to the database. The challenge, however, is that Grover's search algorithm leads to high numbers of quantum gates, which make it infeasible for the Noise-Intermediate-Scale-Quantum (NISQ) computers. In this paper, we propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. Our analysis shows that our algorithm has similar oracle complexity to the original Grover's search algorithm while significantly reduces the circuit depth and gate count. The circuit cost reduction leads to a remarkable improvement in the system success rates, paving the way for quantum search on NISQ machines.

arXiv:2103.14196•Mar 26, 2021•6 citations

VERIFIER-BASED ALGORITHM FOR UNSORTED DATABASE SEARCH PROBLEM

Xiao Wu, GUI LU LONG

Unsorted database search problem is an important science and engineering problem. We proposed quantum algorithm to solve the problem by dividing the database binarily and then use a probabilistic verifier algorithm to determine if the item is within one part of the divided database. We analyzed the computational complexity of this algorithm, and found that in general, the number of steps is proportional to that in the standard Grover algorithm. However in some cases, it is less than that of the Grover algorithm.

International Journal of Quantum Information•Aug 1, 2007•7 citations

A fast quantum mechanical algorithm for database search

Lov K. Grover

An unsorted database contains N records, of which just one satisfies a particular property.The problem is to identify that one record.Any classical algorithm, deterministic or probabilistic, will clearly take O (N) steps since on the average it will have to examine a large fraction of the N records.Quantum mechanical systems can do several operations simultaneously due to their wave like properties.This paper gives an O ( JN) step quantum mechanical algorithm for identifying that record.It is within a constant factor of the fastest possible quantum mechanical algorithm.

ACM Symposium on Theory of Computing (STOC)•Jan 1, 1996•8,830 citations

How fast can a quantum computer search?

Lov K. Grover

This paper gives a simple proof of why a quantum computer, despite being in all possible states simultaneously, needs at least 0.707 sqrt(N) queries to retrieve a desired item from an unsorted list of items. The proof is refined to show that a quantum computer would need at least 0.785 sqrt(N) queries. The quantum search algorithm needs precisely this many queries.

arXiv:quant-ph/9809029•Sep 10, 1998•21 citations
We consider the problem of finding one or more desired items out of an unsorted database. Patel has shown that if the database permits quantum queries, then mere digitization is sufficient for efficient search for one desired item. The algorithm, called factorized quantum search algorithm, presented by him can locate the desired item in an unsorted database using O(log4N)O(log_{4}N)O(log4​N) queries to factorized oracles. But the algorithm requires that all the property values must be distinct from each other. In this paper, we discuss how to make a database satisfy the requirements, and present a quantum search engine based on the algorithm. Our goal is achieved by introducing auxiliary files for the property values that are not distinct, and converting every complex query request into a sequence of calls to factorized quantum search algorithm. The query complexity of our algorithm is O(P∗Q∗M∗log4N)O(P*Q*M*log_{4}N)O(P∗Q∗M∗log4​N), where P is the number of the potential simple query requests in the complex query request, Q is the maximum number of calls to the factorized quantum search algorithm of the simple queries, M is the number of the auxiliary files for the property on which our algorithm are searching for desired items. This implies that to manage an unsorted database on an actual quantum computer is possible and efficient.
Sorting is a fundamental computational process that facilitates subsequent searching of a database. It can be thought of as factorization of the search process. The location of a desired item in a sorted database can be found by classical queries that inspect one letter of the label at a time. For an unsorted database, no such classical quick search algorithm is available. If the database permits quantum queries, however, then mere digitization is sufficient for efficient search. Sorting becomes redundant with the quantum superposition of states. A quantum algorithm is written down that locates the desired item in an unsorted database a factor of two faster than the best classical algorithm can in a sorted database. This algorithm has close resemblance to the assembly process in DNA replication.
In the quantum database search problem we are required to search for an item in a database. In this paper, we consider a generalization of this problem, where we are provided d identical copes of a database each with N items which we can query in parallel. Then, given k items, we are required to determine the locations where these items are stored. We show that any quantum algorithm for this task must perform Omega(sqrt{Nk/d min{d,k}}) parallel queries. We also design an algorithm whose performance comes within a factor O(log d) of this lower bound.
Quantum computing has noteworthy speedup over classical computing by taking advantage of quantum parallelism, i.e., the superposition of states. In particular, quantum search is widely used in various computationally hard problems. Grover's search algorithm finds the target element in an unsorted database with quadratic speedup than classical search and has been proved to be optimal in terms of the number of queries to the database. The challenge, however, is that Grover's search algorithm leads to high numbers of quantum gates, which make it infeasible for the Noise-Intermediate-Scale-Quantum (NISQ) computers. In this paper, we propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. Our analysis shows that our algorithm has similar oracle complexity to the original Grover's search algorithm while significantly reduces the circuit depth and gate count. The circuit cost reduction leads to a remarkable improvement in the system success rates, paving the way for quantum search on NISQ machines.
Unsorted database search problem is an important science and engineering problem. We proposed quantum algorithm to solve the problem by dividing the database binarily and then use a probabilistic verifier algorithm to determine if the item is within one part of the divided database. We analyzed the computational complexity of this algorithm, and found that in general, the number of steps is proportional to that in the standard Grover algorithm. However in some cases, it is less than that of the Grover algorithm.
An unsorted database contains N records, of which just one satisfies a particular property.The problem is to identify that one record.Any classical algorithm, deterministic or probabilistic, will clearly take O (N) steps since on the average it will have to examine a large fraction of the N records.Quantum mechanical systems can do several operations simultaneously due to their wave like properties.This paper gives an O ( JN) step quantum mechanical algorithm for identifying that record.It is within a constant factor of the fastest possible quantum mechanical algorithm.