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

Grover search with smaller oracles

Dan Li

Published Jul 6, 2020• 0 citations
arXivHTMLPDF

Abstract

Grover search is one of the most important quantum algorithms. In this paper, we consider a kind of search that the conditions of satisfaction $T$ can be rewritten as $T=T_1\bigcap T_2$. Then we present a new Grover search with smaller oracles. The time complexity of this algorithm $O(\fracπ{4}\sqrt{\frac{N}{bλ}}+\fracπ{4}\sqrt{\frac{b}τ})$, which is smaller than the time complexity of original Grover search, i.e. $O(\fracπ{4}\sqrt{\frac{N}{M}})$.

DOI
10.48550/arxiv.2007.03526

Related papers

An adiabatic oracle for Grover's algorithm

Bin Yan, Nikolai A. Sinitsyn

Grover's search algorithm was originally proposed for circuit-based quantum computers. A crucial part of it is to query an oracle -- a black-box unitary operation. Generation of this oracle is formally beyond the original algorithm design. Here, we propose a realization of Grover's oracle for a large class of searching problems using a quantum annealing step. The time of this step grows only logarithmically with the size of the database. This suggests an efficient path to application of Grover's algorithm to practically important problems, such as finding the ground state of a Hamiltonian with a spectral gap over its ground state.

arXiv:2207.05665•Jul 12, 2022•1 citation

Exact quantum lower bound for Grover's problem

Catalin Dohotaru, Peter Høyer

One of the most important quantum algorithms ever discovered is Grover's algorithm for searching an unordered set. We give a new lower bound in the query model which proves that Grover's algorithm is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same time an exact bound.

arXiv:0810.3647•Quantum Information and Computation•May 1, 2009•4 citations

Accelerated quantum search using partial oracles and Grover's algorithm

Bolton, Fintan M.

Grover's algorithm, orginally conceived as a means of searching an unordered database, can also be used to extract solutions from the result sets generated by quantum computations. The Grover algorithm exploits the concept of an oracle function, which abstracts the process of matching a search item (returning 1 for a match and 0 otherwise), where searching for 1 target item in a search space of size $N$ scales as $\mathcal{O}(\sqrt{N})$ oracle queries. In this article, we explore the idea of associating a separate oracle with each bit of the matching condition, obtaining multiple partial oracle functions which can be tested independently. Exploring this idea leads to a multi-stage hybrid search algorithm, whose performance can fall within a wide range, anywhere between $\mathcal{O}(\sqrt{N})$ (same as Grover) or $\mathcal{O}(\log(N))$. The algorithm is validated against the simplest kind of search scenario, where the incoming index bits are scrambled using a permutation operation.

arXiv:2403.13035•Mar 19, 2024•0 citations

Exact quantum lower bound for Grover's problem

Catalin Dohotaru, Peter Høyer

One of the most important quantum algorithms ever discovered is Grover's algorithm for searching an unordered set. We give a new lower bound in the query model which proves that Grover's algorithm is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same time an exact bound.

Quantum Information and Computation•May 1, 2009•7 citations

Depth optimization of quantum search algorithms beyond Grover's algorithm

Kun Zhang, V. E. Korepin

Grover's quantum search algorithm provides a quadratic speedup over the classical one. The computational complexity is based on the number of queries to the oracle. However, depth is a more modern metric for noisy intermediate-scale quantum computers. We propose a depth optimization method for the quantum search algorithm. We show that Grover's algorithm is not optimal in depth. We propose a quantum search algorithm, which can be divided into several stages. Each stage has a new initialization, which is a rescaling of the database. This decreases errors. The multistage design is natural for parallel running of the quantum search algorithm.

arXiv:1908.04171•Physical Review A•Mar 26, 2020•55 citations

Coherence Fraction in Grover Search Algorithm

Si-Qi Zhou, Hai Jin, Jin-Min Liang +3 more

The question of which resources drive the advantages in quantum algorithms has long been a fundamental challenge. While entanglement and coherence are critical to many quantum algorithms, our results indicate that they do not fully explain the quantum advantage achieved by the Grover search algorithm. By introducing a generalized Grover search algorithm, we demonstrate that the success probability depends not only on the querying number of oracles but also on the coherence fraction, which quantifies the fidelity between an arbitrary initial quantum state and the equal superposition state. Additionally, we explore the role of the coherence fraction in the quantum minimization algorithm, which offers a framework for solving complex problems in quantum machine learning. These findings offer insights into the origins of quantum advantage and open pathways for the development of new quantum algorithms.

quant-pharXiv:2511.06835•Physical Review A•Nov 11, 2025•6 citations
Grover search is one of the most important quantum algorithms. In this paper, we consider a kind of search that the conditions of satisfaction TTT can be rewritten as T=T1⋂T2T=T_1\bigcap T_2T=T1​⋂T2​. Then we present a new Grover search with smaller oracles. The time complexity of this algorithm O(π4Nbλ+π4bτ)O(\fracπ{4}\sqrt{\frac{N}{bλ}}+\fracπ{4}\sqrt{\frac{b}τ})O(4π​bλN​​+4π​τb​​), which is smaller than the time complexity of original Grover search, i.e. O(π4NM)O(\fracπ{4}\sqrt{\frac{N}{M}})O(4π​MN​​).
Grover's search algorithm was originally proposed for circuit-based quantum computers. A crucial part of it is to query an oracle -- a black-box unitary operation. Generation of this oracle is formally beyond the original algorithm design. Here, we propose a realization of Grover's oracle for a large class of searching problems using a quantum annealing step. The time of this step grows only logarithmically with the size of the database. This suggests an efficient path to application of Grover's algorithm to practically important problems, such as finding the ground state of a Hamiltonian with a spectral gap over its ground state.
One of the most important quantum algorithms ever discovered is Grover's algorithm for searching an unordered set. We give a new lower bound in the query model which proves that Grover's algorithm is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same time an exact bound.
Grover's algorithm, orginally conceived as a means of searching an unordered database, can also be used to extract solutions from the result sets generated by quantum computations. The Grover algorithm exploits the concept of an oracle function, which abstracts the process of matching a search item (returning 1 for a match and 0 otherwise), where searching for 1 target item in a search space of size NNN scales as O(N)\mathcal{O}(\sqrt{N})O(N​) oracle queries. In this article, we explore the idea of associating a separate oracle with each bit of the matching condition, obtaining multiple partial oracle functions which can be tested independently. Exploring this idea leads to a multi-stage hybrid search algorithm, whose performance can fall within a wide range, anywhere between O(N)\mathcal{O}(\sqrt{N})O(N​) (same as Grover) or O(log⁡(N))\mathcal{O}(\log(N))O(log(N)). The algorithm is validated against the simplest kind of search scenario, where the incoming index bits are scrambled using a permutation operation.
One of the most important quantum algorithms ever discovered is Grover's algorithm for searching an unordered set. We give a new lower bound in the query model which proves that Grover's algorithm is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same time an exact bound.
Grover's quantum search algorithm provides a quadratic speedup over the classical one. The computational complexity is based on the number of queries to the oracle. However, depth is a more modern metric for noisy intermediate-scale quantum computers. We propose a depth optimization method for the quantum search algorithm. We show that Grover's algorithm is not optimal in depth. We propose a quantum search algorithm, which can be divided into several stages. Each stage has a new initialization, which is a rescaling of the database. This decreases errors. The multistage design is natural for parallel running of the quantum search algorithm.
The question of which resources drive the advantages in quantum algorithms has long been a fundamental challenge. While entanglement and coherence are critical to many quantum algorithms, our results indicate that they do not fully explain the quantum advantage achieved by the Grover search algorithm. By introducing a generalized Grover search algorithm, we demonstrate that the success probability depends not only on the querying number of oracles but also on the coherence fraction, which quantifies the fidelity between an arbitrary initial quantum state and the equal superposition state. Additionally, we explore the role of the coherence fraction in the quantum minimization algorithm, which offers a framework for solving complex problems in quantum machine learning. These findings offer insights into the origins of quantum advantage and open pathways for the development of new quantum algorithms.