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

Random Grover Search

Dekuan Dong, Yingzhou Li, Jiaxin Ma

quant-phSubmitted Jun 10, 2026• Announced Jun 11, 2026• 0 citations• Revised Jul 2, 2026 (v2)
v1 · Jun 10, 2026v2 · Jul 2, 2026
arXivHTMLPDF

Abstract

Grover's algorithm achieves a quadratic speedup for unstructured search given a global oracle for the target set. In many applications, however, the target set is specified as the intersection of multiple constraint sets. Constructing a global oracle for the intersection can be costly, whereas the individual constraint oracles are often much simpler to implement. We study a randomized Grover search algorithm that directly uses these constraint oracles. At each iteration, one of the corresponding Grover operators is selected at random. For the two-operator case with uniform sampling, we prove that the success probability approaches one after \[ Θ\left(\frac\pi4\sqrt{\frac{N}{r}}\right) \] iterations, where \(r\) is the size of the intersection. Thus, the algorithm achieves the same asymptotic query complexity as standard Grover search but without requiring a global oracle. We then generalize the analysis to arbitrary sampling distributions and an arbitrary number of Grover operators through an auxiliary operator that approximates the expected Grover evolution, while retaining the same asymptotic complexity. We further show that highly biased sampling distributions can still achieve near-unit success probability, enabling cheaper Grover operators to be used more frequently. Finally, we prove asymptotic optimality and support the theoretical results with numerical simulations.

Comments
23 pages, 5 figures

Related papers

Exact quantum algorithm for searching of multiple sets intersection

Sheng-Ao Mao, Lin Zhang, Bo Li

Grover's algorithm achieves a quadratic speedup for unstructured search when a global oracle for the target set is available. However, its success probability is generally below $100\%$. To overcome this issue, Long presented a modified version of Grover's search algorithm by introducing a phase-matching condition, which can search for the target set with zero theoretical failure rate. Nevertheless, in many applications, the target set is determined by the intersection of multiple constrained sets. Most existing Grover-based methods are limited to the intersection of only two sets and are not always successful in searching for the target set. In this work, based on Long's method, we propose an algorithm for exactly searching the intersection of multiple sets. We derive and prove a phase-matching condition for searching the intersection exactly. Furthermore, we present a quantum circuit that implements exact intersection search. Finally, we support our theoretical results with numerical simulations.

quant-pharXiv:2609.36908•Sep 30, 2026•0 citations

Deterministic Grover search with a restricted oracle

Tanay Roy, Liang Jiang, David Schuster

Grover's quantum search algorithm provides a quadratic quantum advantage over classical algorithms across a broad class of unstructured search problems.The original protocol is probabilistic, returning the desired result with significant probability on each query but, in general, requiring several iterations of the algorithm.We present a modified version to return the correct result with certainty without having user control over the quantum search oracle.Our deterministic, two-parameter "D2p" protocol utilizes generalized phase rotations replacing the phase inversions after a standard oracle query.The D2p protocol achieves a 100% success rate in no more than one additional iteration compared to the optimal number of steps as in the original Grover's search enabling the same quadratic speedup.We also provide a visualization using the Bloch sphere for enhanced geometric intuition.

arXiv:2201.00091•Physical Review Research•Apr 21, 2022•60 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

Grover's search algorithm for nnn qubits with optimal number of iterations

Simanraj Sadana

The success probability of a search of $M$ targets from a database of size $N$, using Grover's search algorithm depends critically on the number of iterations of the composite operation of the oracle followed by Grover's diffusion operation. Although the required number of iterations scales as $\mathcal{O}(\sqrt{N})$ for large $N$, the asymptote is not a good indicator of the optimal number of iterations when $\sqrt{M/N}$ is not small. A scheme for the determination of the exact number of iterations, subject to a threshold set for the success probability of the search (probability of detecting the target state(s)), is crucial for the efficacy of the algorithm. In this work, a general scheme for the construction of $n$-qubit Grover's search algorithm with $1 \leq M \leq N$ target states is presented, along with the procedure to find the optimal number of iterations for a successful search. It is also shown that for given $N$ and $M$, there is an upper-bound on the success probability of the algorithm.

arXiv:2011.04051•Nov 8, 2020•1 citation

Quantum Query Complexity for Nonstandard Oracles with Tight Bounds and Tradeoffs Beyond Grover

Yalla Jnan Devi Satya Prasad

Quantum query complexity underpins much of our understanding of quantum speedups, yet nearly all existing lower and upper bounds are derived for simple Boolean oracles. Many practical tasks-noisy database search, stochastic optimization, adaptive learning, and time-varying systems-are best modeled by richer oracle classes. This paper systematically extends quantum query complexity theory to four non-standard oracle models: (1) stochastic oracles that return random outputs drawn from a distribution; (2) multi-solution oracles encoding a solution set of size k; (3) time-dependent oracles whose internal state evolves between queries; and (4) relational oracles encoding structured constraints rather than simple membership. Using generalized adversary methods, polynomial method techniques, and hybrid arguments, we derive tight (up to polylog factors) lower bounds for each model and construct matching algorithms where possible. For instance, we show that searching for any one of k marked items in an unstructured database still admits a Grover-like quadratic speedup, but with optimal complexity Θ(N/k), and that stochastic noise in oracle outputs degrades the advantage gracefully as a function of the noise parameter. For certain time-dependent and relational models, we prove that no better-than-classical speedup is possible, clarifying the limits of quantum advantage in adaptive settings. These results provide a more realistic foundation for quantum algorithms targeting noisy search, stochastic optimization, and constraint satisfaction, and they highlight the precise structural features that enable or preclude query-based quantum speedups.

•Dec 19, 2025•0 citations

Quantum algorithm for unstructured search of ranked targets

Kota Tani, Shunji Tsuchiya, Seiichiro Tani +1 more

Abstract Grover’s quantum algorithm can find a marked item from an unstructured database faster than any classical algorithm, and hence it has been used for several applications such as cryptanalysis and optimization. When there exist multiple marked items, Grover’s algorithm has the property of finding one of them uniformly at random. To further broaden the application range, it was generalized so that it finds marked items with probabilities according to their priority by encoding the priority into amplitudes applied by Grover’s oracle operator. In this paper, to achieve a similar generalization, we examine a different encoding that incorporates the priority into phases applied by the oracle operator. We compare the previous and our oracle operators and observe that which one performs better depends on priority parameters. Since the priority parameters can be considered as the magnitude of the correlated phase error on Grover’s oracle operator, the analysis of our oracle operator also reveals the robustness of the original Grover’s algorithm against correlated noises. We further numerically show that the coherence between multiple marked items tends to increase the probability of finding the most prioritized one in Grover’s algorithm with our oracle operator.

arXiv:2412.00332•Physica Scripta•Jun 10, 2025•2 citations
Grover's algorithm achieves a quadratic speedup for unstructured search given a global oracle for the target set. In many applications, however, the target set is specified as the intersection of multiple constraint sets. Constructing a global oracle for the intersection can be costly, whereas the individual constraint oracles are often much simpler to implement.
We study a randomized Grover search algorithm that directly uses these constraint oracles. At each iteration, one of the corresponding Grover operators is selected at random. For the two-operator case with uniform sampling, we prove that the success probability approaches one after [ Θ\left(\frac\pi4\sqrt{\frac{N}{r}}\right) ] iterations, where (r) is the size of the intersection. Thus, the algorithm achieves the same asymptotic query complexity as standard Grover search but without requiring a global oracle. We then generalize the analysis to arbitrary sampling distributions and an arbitrary number of Grover operators through an auxiliary operator that approximates the expected Grover evolution, while retaining the same asymptotic complexity. We further show that highly biased sampling distributions can still achieve near-unit success probability, enabling cheaper Grover operators to be used more frequently. Finally, we prove asymptotic optimality and support the theoretical results with numerical simulations.
Grover's algorithm achieves a quadratic speedup for unstructured search when a global oracle for the target set is available. However, its success probability is generally below 100%100\%100%. To overcome this issue, Long presented a modified version of Grover's search algorithm by introducing a phase-matching condition, which can search for the target set with zero theoretical failure rate. Nevertheless, in many applications, the target set is determined by the intersection of multiple constrained sets. Most existing Grover-based methods are limited to the intersection of only two sets and are not always successful in searching for the target set. In this work, based on Long's method, we propose an algorithm for exactly searching the intersection of multiple sets. We derive and prove a phase-matching condition for searching the intersection exactly. Furthermore, we present a quantum circuit that implements exact intersection search. Finally, we support our theoretical results with numerical simulations.
Grover's quantum search algorithm provides a quadratic quantum advantage over classical algorithms across a broad class of unstructured search problems.The original protocol is probabilistic, returning the desired result with significant probability on each query but, in general, requiring several iterations of the algorithm.We present a modified version to return the correct result with certainty without having user control over the quantum search oracle.Our deterministic, two-parameter "D2p" protocol utilizes generalized phase rotations replacing the phase inversions after a standard oracle query.The D2p protocol achieves a 100% success rate in no more than one additional iteration compared to the optimal number of steps as in the original Grover's search enabling the same quadratic speedup.We also provide a visualization using the Bloch sphere for enhanced geometric intuition.
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.
The success probability of a search of MMM targets from a database of size NNN, using Grover's search algorithm depends critically on the number of iterations of the composite operation of the oracle followed by Grover's diffusion operation. Although the required number of iterations scales as O(N)\mathcal{O}(\sqrt{N})O(N​) for large NNN, the asymptote is not a good indicator of the optimal number of iterations when M/N\sqrt{M/N}M/N​ is not small. A scheme for the determination of the exact number of iterations, subject to a threshold set for the success probability of the search (probability of detecting the target state(s)), is crucial for the efficacy of the algorithm. In this work, a general scheme for the construction of nnn-qubit Grover's search algorithm with 1≤M≤N1 \leq M \leq N1≤M≤N target states is presented, along with the procedure to find the optimal number of iterations for a successful search. It is also shown that for given NNN and MMM, there is an upper-bound on the success probability of the algorithm.
Quantum query complexity underpins much of our understanding of quantum speedups, yet nearly all existing lower and upper bounds are derived for simple Boolean oracles. Many practical tasks-noisy database search, stochastic optimization, adaptive learning, and time-varying systems-are best modeled by richer oracle classes. This paper systematically extends quantum query complexity theory to four non-standard oracle models: (1) stochastic oracles that return random outputs drawn from a distribution; (2) multi-solution oracles encoding a solution set of size k; (3) time-dependent oracles whose internal state evolves between queries; and (4) relational oracles encoding structured constraints rather than simple membership. Using generalized adversary methods, polynomial method techniques, and hybrid arguments, we derive tight (up to polylog factors) lower bounds for each model and construct matching algorithms where possible. For instance, we show that searching for any one of k marked items in an unstructured database still admits a Grover-like quadratic speedup, but with optimal complexity Θ(N/k), and that stochastic noise in oracle outputs degrades the advantage gracefully as a function of the noise parameter. For certain time-dependent and relational models, we prove that no better-than-classical speedup is possible, clarifying the limits of quantum advantage in adaptive settings. These results provide a more realistic foundation for quantum algorithms targeting noisy search, stochastic optimization, and constraint satisfaction, and they highlight the precise structural features that enable or preclude query-based quantum speedups.
Abstract Grover’s quantum algorithm can find a marked item from an unstructured database faster than any classical algorithm, and hence it has been used for several applications such as cryptanalysis and optimization. When there exist multiple marked items, Grover’s algorithm has the property of finding one of them uniformly at random. To further broaden the application range, it was generalized so that it finds marked items with probabilities according to their priority by encoding the priority into amplitudes applied by Grover’s oracle operator. In this paper, to achieve a similar generalization, we examine a different encoding that incorporates the priority into phases applied by the oracle operator. We compare the previous and our oracle operators and observe that which one performs better depends on priority parameters. Since the priority parameters can be considered as the magnitude of the correlated phase error on Grover’s oracle operator, the analysis of our oracle operator also reveals the robustness of the original Grover’s algorithm against correlated noises. We further numerically show that the coherence between multiple marked items tends to increase the probability of finding the most prioritized one in Grover’s algorithm with our oracle operator.