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:0709.3627 · Physical Review A

Exact quantum search by parallel unitary discrimination schemes

Xiaodi Wu, Runyao Duan

Published Jul 2, 2008• 15 citations
arXivHTMLPDF

Abstract

We study the unsorted database search problem with items $N$ from the viewpoint of unitary discrimination. Instead of considering the famous $O(\sqrt{N})$ Grover bounded-error algorithm for the original problem, we seek the results for the exact algorithms, i.e., those that succeed with certainty. Under the standard oracle model ${\ensuremath{\sum}}_{j}{(\ensuremath{-}1)}^{{\ensuremath{\delta}}_{\ensuremath{\tau}j}}|j⟩⟨j|$, we demonstrate a tight lower bound $\frac{2}{3}N+o(N)$ of the number of queries for any parallel scheme with unentangled input states. With the assistance of entanglement, we obtain a general lower bound $\frac{1}{2}(N\ensuremath{-}\sqrt{N})$. We provide concrete examples to illustrate our results. In particular, we show that the case of $N=6$ can be solved exactly with only two queries by using a bipartite entangled input state. Our results indicate that in the standard oracle model the complexity of the exact quantum search with one unique solution can be strictly less than that of the calculation of the OR function.

DOI
10.1103/physreva.78.012303

Related papers

Quantum Query Complexity for Searching Multiple Marked States from an Unsorted Database

Shang Bin

An important and usual sort of search problems is to find all marked states from an unsorted database with a large number of states. Grover's original quantum search algorithm is for finding single marked state with uncertainty, and it has been generalized to the case of multiple marked states, as well as been modified to find single marked state with certainty. However, the query complexity for finding all multiple marked states has not been addressed. We use a generalized Long's algorithm with high precision to solve such a problem. We calculate the approximate query complexity, which increases with the number of marked states and with the precision that we demand. In the end we introduce an algorithm for the problem on a ``duality computer'' and show its advantage over other algorithms.

arXiv:quant-ph/0604059•Communications in Theoretical Physics•Aug 1, 2007•3 citations

Asymptotic bounds on quantum partial search algorithm and its applications to parallel search

Yan-Bo Jiang, Xiao-Hui Wang, Kun Zhang +1 more

Grover's algorithm provides a quadratic speedup over classical algorithms for searching an unstructured database and is known to be strictly optimal in oracle query complexity, with tight bounds on its success probability. Although the standard Grover search cannot be further accelerated in the full-search setting, a trade-off between accuracy and query complexity gives rise to the partial search problem. The Grover-Radhakrishnan-Korepin (GRK) algorithm is the standard and most extensively studied protocol for this task. In this work, we provide systematic numerical evidence that the GRK operator sequence gives the highest success probability in all examined cases, supporting it as the optimal ansatz among admissible compositions of global and local Grover operators. Guided by this numerically supported GRK ansatz, we derive an asymptotically tight upper bound on the maximal success probability within the GRK family and establish the corresponding lower bound on the minimal expected number of oracle queries. Furthermore, we investigate parallel quantum search within the partial-search framework. While a direct GRK-based parallelization does not outperform established parallel Grover schemes, we demonstrate that a hybrid strategy combining partial and full search protocols yields a strict, though subleading, improvement over the outer parallel Grover scheme. Our results clarify the fundamental limits of quantum partial search and its role in optimizing parallel quantum search algorithms.

quant-pharXiv:2603.01462•Physical Review A•Mar 3, 2026•1 citation

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

Structured search algorithm: A quantum leap

Yash Prabhat, Thakur, Snigdha, Ankur Raina

We introduce a structured quantum search algorithm that leverages entanglement maps and a fixed-point method to minimize oracle query complexity in unsorted datasets. By partitioning qubits into rows based on their entanglement order, the algorithm enables parallel subspace searches, achieving solution identification with at most two oracle calls per row. Experimental results on IBM Kyiv hardware demonstrate successful searches in datasets with up to 5 TB of unsorted data. Our findings indicate that with optimal encoding, the quantum search complexity becomes $\mathcal{O}(1)$, that is, independent of the dataset size $N$, surpassing both classical $\mathcal{O}(N)$ and Grover's $\mathcal{O}(\sqrt{N})$ scaling. Furthermore, the letter hypothesizes a scalable simulation of the said algorithm using classical means.

arXiv:2504.03426•Apr 4, 2025•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

Is partial quantum search of a database any easier?

Lov K. Grover, Jaikumar Radhakrishnan

We consider the partial database search problem where given a quantum database f : {0,1}n→{0,1} such that f(x) =1 for a unique x ∈ {0,1}n, we are required to determine only the first k bits of the address x. We present an algorithm and derive a lower bound for this problem. Let q(k,n) be the minimum number of queries needed to find the first k bits of the required address x with certainty (or with very high probability, say 1--O(N--¼)). We show that there exist constants ck (corresponding to the algorithm) and dk (corresponding to the lower bound) such that πover4 (1--dkover√K) √N ≤ q(k,n) ≤ πover4 (1--ckover√K) √N, where K=2k and N=2n. Our algorithm returns the correct answer with probability 1--O(N--½), and can be easily modified to give the correct answer with certainty. The lower bound for algorithms that return the correct answer with certainty is proved by reducing the usual database search problem to this partial search problem, and invoking Zalka's lower bound showing that Grovers algorithm is optimal for the usual database search problem. We then derive a lower bound that is applicable for database search algorithms that err with small probability, and use it to show that our lower bound also applies to partial search algorithms that return the correct answer with probability at least 1--O(N--¼).

arXiv:quant-ph/0407122•ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)•Jul 18, 2005•48 citations
We study the unsorted database search problem with items NNN from the viewpoint of unitary discrimination. Instead of considering the famous O(N)O(\sqrt{N})O(N​) Grover bounded-error algorithm for the original problem, we seek the results for the exact algorithms, i.e., those that succeed with certainty. Under the standard oracle model \ensuremath∑j(\ensuremath−1)\ensuremathδ\ensuremathτj∣j⟩⟨j∣{\ensuremath{\sum}}_{j}{(\ensuremath{-}1)}^{{\ensuremath{\delta}}_{\ensuremath{\tau}j}}|j⟩⟨j|\ensuremath∑j​(\ensuremath−1)\ensuremathδ\ensuremathτj​∣j⟩⟨j∣, we demonstrate a tight lower bound 23N+o(N)\frac{2}{3}N+o(N)32​N+o(N) of the number of queries for any parallel scheme with unentangled input states. With the assistance of entanglement, we obtain a general lower bound 12(N\ensuremath−N)\frac{1}{2}(N\ensuremath{-}\sqrt{N})21​(N\ensuremath−N​). We provide concrete examples to illustrate our results. In particular, we show that the case of N=6N=6N=6 can be solved exactly with only two queries by using a bipartite entangled input state. Our results indicate that in the standard oracle model the complexity of the exact quantum search with one unique solution can be strictly less than that of the calculation of the OR function.
An important and usual sort of search problems is to find all marked states from an unsorted database with a large number of states. Grover's original quantum search algorithm is for finding single marked state with uncertainty, and it has been generalized to the case of multiple marked states, as well as been modified to find single marked state with certainty. However, the query complexity for finding all multiple marked states has not been addressed. We use a generalized Long's algorithm with high precision to solve such a problem. We calculate the approximate query complexity, which increases with the number of marked states and with the precision that we demand. In the end we introduce an algorithm for the problem on a ``duality computer'' and show its advantage over other algorithms.
Grover's algorithm provides a quadratic speedup over classical algorithms for searching an unstructured database and is known to be strictly optimal in oracle query complexity, with tight bounds on its success probability. Although the standard Grover search cannot be further accelerated in the full-search setting, a trade-off between accuracy and query complexity gives rise to the partial search problem. The Grover-Radhakrishnan-Korepin (GRK) algorithm is the standard and most extensively studied protocol for this task. In this work, we provide systematic numerical evidence that the GRK operator sequence gives the highest success probability in all examined cases, supporting it as the optimal ansatz among admissible compositions of global and local Grover operators. Guided by this numerically supported GRK ansatz, we derive an asymptotically tight upper bound on the maximal success probability within the GRK family and establish the corresponding lower bound on the minimal expected number of oracle queries. Furthermore, we investigate parallel quantum search within the partial-search framework. While a direct GRK-based parallelization does not outperform established parallel Grover schemes, we demonstrate that a hybrid strategy combining partial and full search protocols yields a strict, though subleading, improvement over the outer parallel Grover scheme. Our results clarify the fundamental limits of quantum partial search and its role in optimizing parallel quantum search algorithms.
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.
We introduce a structured quantum search algorithm that leverages entanglement maps and a fixed-point method to minimize oracle query complexity in unsorted datasets. By partitioning qubits into rows based on their entanglement order, the algorithm enables parallel subspace searches, achieving solution identification with at most two oracle calls per row. Experimental results on IBM Kyiv hardware demonstrate successful searches in datasets with up to 5 TB of unsorted data. Our findings indicate that with optimal encoding, the quantum search complexity becomes O(1)\mathcal{O}(1)O(1), that is, independent of the dataset size NNN, surpassing both classical O(N)\mathcal{O}(N)O(N) and Grover's O(N)\mathcal{O}(\sqrt{N})O(N​) scaling. Furthermore, the letter hypothesizes a scalable simulation of the said algorithm using classical means.
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.
We consider the partial database search problem where given a quantum database f : {0,1}n→{0,1} such that f(x) =1 for a unique x ∈ {0,1}n, we are required to determine only the first k bits of the address x. We present an algorithm and derive a lower bound for this problem. Let q(k,n) be the minimum number of queries needed to find the first k bits of the required address x with certainty (or with very high probability, say 1--O(N--¼)). We show that there exist constants ck (corresponding to the algorithm) and dk (corresponding to the lower bound) such that πover4 (1--dkover√K) √N ≤ q(k,n) ≤ πover4 (1--ckover√K) √N, where K=2k and N=2n. Our algorithm returns the correct answer with probability 1--O(N--½), and can be easily modified to give the correct answer with certainty. The lower bound for algorithms that return the correct answer with certainty is proved by reducing the usual database search problem to this partial search problem, and invoking Zalka's lower bound showing that Grovers algorithm is optimal for the usual database search problem. We then derive a lower bound that is applicable for database search algorithms that err with small probability, and use it to show that our lower bound also applies to partial search algorithms that return the correct answer with probability at least 1--O(N--¼).