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

Complex Quantum Queries

Lov K. Grover

Published Jun 3, 1997• 0 citations
OpenAlex

Abstract

A quantum mechanical computer can search a database consisting of N items in O(sqrt(N)) elementary quantum queries (a query is defined as any question to the database to which a binary (YES/NO) answer is required; an elementary query is a query pertaining to only one of the N possible states). A classical computer would take at least O(N) elementary queries. This paper shows that a quantum mechanical algorithm that can query information relating to multiple states, can search the database in a single query. A classical algorithm will be limited to the information theoretic bound of at least O(log N)queries (which it would achieve by using a binary search). A similar result was recently independently obtained by Terhal & Smolin by a different method.

Related papers

Quantum Computers Can Search Arbitrarily Large Databases by a Single Query

Lov K. Grover

This paper shows that a quantum mechanical algorithm that can query information relating to multiple items of the database can search a database for a unique item satisfying a given condition, in a single query [a query is defined as any question to the database to which the database has to return a (yes/no answer]. A classical algorithm will be limited to the information theoretic bound of at least ${log}_{2}N$ queries, which it would achieve by using a binary search.

arXiv:quant-ph/9706005•Physical Review Letters•Dec 8, 1997•432 citations

Single quantum querying of a database

Barbara M. Terhal, John A. Smolin

We present a class of fast quantum algorithms, based on Bernstein and Vazirani's parity problem, that retrieves the entire contents of a quantum database $Y$ in a single query. The class includes binary search problems and coin-weighing problems. We compare the efficiency of these quantum algorithms with the classical algorithms that are bounded by the classical information-theoretic bound. We show the connection between classical algorithms based on several compression codes and our quantum-mechanical method.

arXiv:quant-ph/9705041•Physical Review A•Sep 1, 1998•56 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

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

Quantum Search in Hilbert Space

Michail A. Zak

A proposed quantum-computing algorithm would perform a search for an item of information in a database stored in a Hilbert-space memory structure. The algorithm is intended to make it possible to search relatively quickly through a large database under conditions in which available computing resources would otherwise be considered inadequate to perform such a task. The algorithm would apply, more specifically, to a relational database in which information would be stored in a set of N complex orthonormal vectors, each of N dimensions (where N can be exponentially large). Each vector would constitute one row of a unitary matrix, from which one would derive the Hamiltonian operator (and hence the evolutionary operator) of a quantum system. In other words, all the stored information would be mapped onto a unitary operator acting on a quantum state that would represent the item of information to be retrieved. Then one could exploit quantum parallelism: one could pose all search queries simultaneously by performing a quantum measurement on the system. In so doing, one would effectively solve the search problem in one computational step. One could exploit the direct- and inner-product decomposability of the unitary matrix to make the dimensionality of the memory space exponentially large by use of only linear resources. However, inasmuch as the necessary preprocessing (the mapping of the stored information into a Hilbert space) could be exponentially expensive, the proposed algorithm would likely be most beneficial in applications in which the resources available for preprocessing were much greater than those available for searching.

•Jan 1, 2003•0 citations

An efficient quantum search engine on unsorted database

Heping Hu, Yingyu Zhang, Zhengding Lu

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.

arXiv:0904.3060•Apr 20, 2009•0 citations
A quantum mechanical computer can search a database consisting of N items in O(sqrt(N)) elementary quantum queries (a query is defined as any question to the database to which a binary (YES/NO) answer is required; an elementary query is a query pertaining to only one of the N possible states). A classical computer would take at least O(N) elementary queries. This paper shows that a quantum mechanical algorithm that can query information relating to multiple states, can search the database in a single query. A classical algorithm will be limited to the information theoretic bound of at least O(log N)queries (which it would achieve by using a binary search). A similar result was recently independently obtained by Terhal & Smolin by a different method.
This paper shows that a quantum mechanical algorithm that can query information relating to multiple items of the database can search a database for a unique item satisfying a given condition, in a single query [a query is defined as any question to the database to which the database has to return a (yes/no answer]. A classical algorithm will be limited to the information theoretic bound of at least log2N{log}_{2}Nlog2​N queries, which it would achieve by using a binary search.
We present a class of fast quantum algorithms, based on Bernstein and Vazirani's parity problem, that retrieves the entire contents of a quantum database YYY in a single query. The class includes binary search problems and coin-weighing problems. We compare the efficiency of these quantum algorithms with the classical algorithms that are bounded by the classical information-theoretic bound. We show the connection between classical algorithms based on several compression codes and our quantum-mechanical method.
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.
A proposed quantum-computing algorithm would perform a search for an item of information in a database stored in a Hilbert-space memory structure. The algorithm is intended to make it possible to search relatively quickly through a large database under conditions in which available computing resources would otherwise be considered inadequate to perform such a task. The algorithm would apply, more specifically, to a relational database in which information would be stored in a set of N complex orthonormal vectors, each of N dimensions (where N can be exponentially large). Each vector would constitute one row of a unitary matrix, from which one would derive the Hamiltonian operator (and hence the evolutionary operator) of a quantum system. In other words, all the stored information would be mapped onto a unitary operator acting on a quantum state that would represent the item of information to be retrieved. Then one could exploit quantum parallelism: one could pose all search queries simultaneously by performing a quantum measurement on the system. In so doing, one would effectively solve the search problem in one computational step. One could exploit the direct- and inner-product decomposability of the unitary matrix to make the dimensionality of the memory space exponentially large by use of only linear resources. However, inasmuch as the necessary preprocessing (the mapping of the stored information into a Hilbert space) could be exponentially expensive, the proposed algorithm would likely be most beneficial in applications in which the resources available for preprocessing were much greater than those available for searching.
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.