# Applications and limits of the Grover Quantum Algorithm

David R.C. Hill, Benjamin A. Antunes

<figure><img src="image_1.png" /></figure>

## To cite this version:

David R.C. Hill, Benjamin A. Antunes. Applications and limits of the Grover Quantum Algorithm. 2026. [https://uca.hal.science/hal-05474430v2](https://uca.hal.science/hal-05474430v2)

HAL Id: hal-05474430

https://uca.hal.science/hal-05474430v2

Preprint submitted on 3 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Applications and limits of the Grover Quantum Algorithm

David R.C. HILL¹ and Benjamin A. ANTUNES²

¹ Université Clermont Auvergne, CNRS,
Clermont Auvergne INP, Mines St-Etienne,
ISIMA/LIMOS UMR 6158
1 rue de la Chebarde Aubière, F-63178
France - [David.Hill@uca.fr](mailto:David.Hill@uca.fr)

² Université Perpignan Via Domitia, DALI,
Perpignan, France, LIRMM, Université
Montpellier, CNRS UMR 5506
52 Av. Paul Alduy, 66100 Perpignan France -
[Benjamin.Antunes@univ-perp.fr](mailto:Benjamin.Antunes@univ-perp.fr)

**Abstract:** The Grover algorithm is a fundamental quantum algorithm that achieves a quadratic speedup for unstructured search problems, requiring O(√N) queries instead of O(N) classically. It works by repeatedly applying an oracle and a diffusion operator to amplify the probability of marked states. This advantage makes it relevant to cryptography, optimization, constraint satisfaction, and as a general primitive via amplitude amplification in areas like quantum machine learning and simulation. However, practical implementations are severely constrained by current Noisy Intermediate Scale Quantum machines with limited coherence, deep oracle circuits and lack of scalable QRAM, restricting demonstrations to small-scale experiments with reproducibility challenges.

**Keywords:** Grover's Algorithm, Quantum Search, Amplitude Amplification, NISQ Limitations, Reproducibility

**Roles:** D.R.C. Hill, writing—original draft preparation — conceptualization — review and editing — supervision.
The main author want to thank Dr. B.A. Antunes for his review and comments integrated as minor revision.

## 1. Introduction

During a lecture at MIT in the early 1980s on the possibilities and limits of numerical simulation [1], Richard Feynman posed a now-famous question: “*Can quantum systems be simulated probabilistically by a classical computer with local connections?*”. He argued that classical simulations do not scale, as they face fundamental complexity barriers, most notably exponential growth in time and memory requirements. From this observation, Feynman concluded that classical computers cannot faithfully reproduce quantum mechanics, a realization that laid the conceptual foundations of quantum computing. Three years later, David Deutsch introduced the notion of a universal quantum Turing machine [2], providing the first formal model of quantum computation. While early work remained largely theoretical, concrete applications began to emerge about a decade later. In particular, Peter Shor's factoring algorithm demonstrated an exponential speedup for integer factorization, threatening widely used cryptographic schemes and triggering intense global interest in universal quantum computing [3]. Beyond factoring, Shor also made a crucial, though less widely known, contribution by developing quantum error-correcting codes, which address the intrinsic fragility and decoherence of quantum systems. Around the same time, advancement were achieved by Lov Grover and Seth Lloyd in different areas. Lloyd showed how quantum systems could be simulated using Hamiltonians (operators that describe the total energy of a system), it opened the path to simulation quantum computers [4]. This theoretical framework significantly advanced our ability to model and understand quantum dynamics. Grover on his side offered a glimpse into the potential of quantum systems to process information in fundamentally different ways than classical computers. The Grover's algorithm, in particular, is known for its ability to search unsorted databases quadratically faster than its classical counterparts [5], representing a significant leap in computing efficiency. Quantum computing exploits the unique properties of quantum mechanics, such as superposition and entanglement, to
perform computations [6]. This paradigm shift from classical computing opens new frontiers in various fields.

While cryptography has considerable implications, optimization and operations research in general are not far behind. In this encyclopedic article, we have chosen to present the Grover's algorithm, since it is useful in many fields. We will first present the approach behind this algorithm, then we show the potential applications where this algorithm is useful, and next, we explain the current limitations encountered. Lastly, we give an example of implementation and show reproducibility issues with different simulators and machines.

## 2. Presentation of the Grover Quantum Algorithm

The Grover's algorithm is a foundational quantum algorithm that provides a quadratic speed-up for unstructured search problems. By iteratively applying an oracle that marks solution states and a diffusion operator that performs inversion about the mean, the algorithm amplifies the probability amplitude of the desired state within a uniform superposition. After approximately $O(\sqrt{N})$ iterations, where N denotes the size of the search space, measurement shows the marked element with high probability. This improvement over a classical query with $O(N)$ complexity is often presented as the most compelling demonstration of the quantum computational advantage.

Imagine we have an unsorted list of N items and want to find one specific item. A Classical computer will check the items one by one. In the worst case, we need N checks, and on average, N/2 checks. No classical algorithm can do better if the list is unstructured. But the Grover's algorithm shows that a quantum computer can find the item in about $O(\sqrt{N})$ steps, which is a quadratic speed-up. To achieve this, quantum computers exploit two principles of quantum mechanics: superposition and interference. With superposition, a quantum bit (or qubit) can be in a superposition of states: $\alpha|0\rangle + \beta|1\rangle$ (with $\alpha$ and $\beta$ being complex numbers). At measurement, all qubits will collapse to a single value, 0 or 1. Due to this property, with n qubits, we can represent all $2^n$ states at once. With interference, Quantum amplitudes can reinforce each other (constructive interference) or cancel out (destructive interference). The key idea of the Grover's algorithm is to carefully engineer interference so the correct answer becomes more likely when we measure.

To prepare the algorithm initial state, we begin with n qubits initialized to: $|0\rangle^{\otimes n}$. Then, we apply a Hadamard quantum gate to each qubit, placing them in superposition to guess all answers at once, each with equal probability (eq. 1).

$$ (1) \quad |\psi_0\rangle = \frac{1}{\sqrt{N}} \sum_x |x\rangle $$

After initialization, we apply an Oracle. This is a quantum operation that recognizes the correct answer. The oracle does not tell us the answer directly, it only marks it by a phase change, and phase alone is invisible to measurement, so we need another step (eq. 2).

$$ (2) \quad O_f |x\rangle = (-1)^{f(x)} |x\rangle $$

If $x$ is not the solution nothing happens, but if it is, its phase is flipped.

The next step is known as the diffusion operator. It amplifies the marked state using the average amplitude (named Inversion About Mean). First, we compute the average amplitude,
then we reflect all amplitudes around that average. The marked state is below average, therefore, after phase flip, doing symmetry around the average, it becomes larger (eq. 3).

$$ (3) \quad D = 2 |\psi_0\rangle\langle\psi_0| - I $$

With this step, the probability of the correct state increases and the probabilities of incorrect states decrease.

We need to iterate both previous steps. A Grover iteration consists of: (1) applying Oracle $O_f$ and (2) applying the diffusion operator. If we look for a single solution, the number of iterations is: $k \approx \frac{\pi}{4} \sqrt{N}$. Table 1 below gives rounded values for some search space sizes.

The general number of iterations if we mark S states is given below (eq. 4):

$$ (4) \quad k \approx \frac{\pi}{4} \sqrt{\frac{N}{S}} $$

<table><caption>**Table 1.** Number of steps of the Grover algorithm vs. the classical number of steps</caption><thead><tr><th>Search Space Size</th><th>Classical Steps</th><th>Grover Steps for 1 state</th></tr></thead><tbody><tr><td>N = 4</td><td>4 (average 4/2 = 2)</td><td>1</td></tr><tr><td>N = 16</td><td>16 (average 16/2 = 8)</td><td>3</td></tr><tr><td>N = 1 000 000</td><td>1 000 000 (average 500 000)</td><td>~785</td></tr></tbody></table>

If we want a geometric interpretation of the Grover's algorithm, we can say that it operates in a 2D space. Each Grover iteration performs a rotation toward the solution state. We start pointing mostly at “wrong answers”, but each iteration rotates closer to “correct answer”.

<figure><img src="image_3.png" /><figcaption>**Figure 1.** Visual representation of the Grover algorithm with its main steps</figcaption></figure>
The figure above summarizes all the steps. After applying the correct number of Grover iterations, it is important to measure the qubits at the right time. The correct state will appear with the highest probability. Measuring too early or too late reduces success, timing matters. Further reading to understand the mathematics behind the Grover algorithm can be found in [7], this paper analyzes the mathematical structure of the classical Grover's algorithm using linear algebra over complex numbers.

### 3. Potential applications

Potential applications of the Grover's algorithm can be found in various computational domains. Grover's algorithm isn't just one algorithm but a framework, often called "Amplitude amplification". This technique can boost the probability of finding a correct solution in other quantum algorithms, making them more efficient [8]. In [9], the authors explain the operation of Grover's Quantum Search Algorithm (QSA) and discusses its applications as a "subroutine" in other quantum algorithms for wireless communication applications.

In cryptography, it reduces the effective security of symmetric-key algorithms and hash functions by enabling quadratic improvements in brute-force search and preimage attacks. For instance, breaking symmetric cryptography with brute-force for a key of length $k$ takes $O(2^k)$ classically. With Grover's algorithm, this complexity reduces to $O(2^{k/2})$. This effectively halves the key length from a security standpoint (e.g. and AES-256 would only provide ~128-bit security against quantum attackers. For Hash function inversion, given a hash value, finding a preimage can also be sped up from $O(2^n)$ to $O(2^{n/2})$. Message Authentication Codes and Pseudorandom Functions, when attacked generically, will also lose half their effective security.

In optimization and constraint satisfaction, the algorithm accelerates the search for assignments that satisfy complex conditions. Many optimization problems can be cast as searching for a solution that minimizes, or satisfies, certain conditions. Grover's algorithm can be used as a subroutine to speed up constraint satisfaction problems like satisfiability problems known as SAT (or B-SAT). A SAT problem tries to determine if we can find an interpretation satisfying given boolean formula. With QUBO (Quadratic Unconstrained Binary Optimization), we try to solve quadratic combinational optimization problems with binary variables. This is interesting in finance, where Quantum-inspired algorithm are used for collateral optimization. Additionally, Grover's algorithm is also useful in general optimization, scheduling, logistics, and resource allocation.

While practical large-scale quantum databases don't currently exist, the Grover algorithm is a theoretical tool for searching an unstructured database. In the context of unstructured search problems, if you have a list of $N$ items and want to find the one that satisfies some property, a classical algorithm requires $O(N)$ checks, while Grover's algorithm reduces this to $O(\sqrt{N})$, which is extremely significant for very large datasets. It can also be useful in Artificial Intelligence (AI) and Machine Learning (ML) where finding matching data points or nearest neighbors can be formulated as search. Detecting certain entries in large data lakes is promising whereas Quantum search engines remain currently theoretical. This algorithm does not magically index classical databases; the speedup will only apply when the database will be represented in quantum-accessible form.

When dealing with Graph Problems, Grover's algorithm can help finding a specific node or path in a graph that satisfies certain properties, this can be applied to the detection of anomaly or marked elements in networks. The search for collisions or matches across two sets, or speedups in graph property testing are expected. Although not as dramatic as quantum walk algorithms, Grover still provides generic enhancements. For general Pattern Matching, Grover's algorithm
enables speeding up problems in text and image pattern recognition by framing them as search problems.

In the ML & AI domain, though it is not as fundamental as quantum machine-learning primitives quantum kernels or the Harrow–Hassidim–Lloyd (HHL) algorithm [10], the Grover algorithm helps with Quantum-enhanced search in ML pipelines (search over model architectures, search over hyperparameters, search over example(s) satisfying a condition and also feature selection). A generalization of Grover technique using “Amplitude Amplification” also helps to boost the success probability of quantum subroutines such as Quantum recommendation systems, Quantum sampling and Quantum boosting algorithms.

More broadly, the Grover's algorithm and its generalization through amplitude amplification, can also serve as a powerful primitive Scientific Computing. Monte Carlo simulation, where quantum subroutines benefit from boosted success probabilities. Quantum Monte Carlo simulations, Quantum chemistry (speeding up sampling procedures), solving differential equations (via subroutine boosting) and searching state spaces in physics simulations can benefit from amplitude amplification.

The Grover algorithm is not a universal solution but a general quadratic speedup for search-like problems. Table 1 gives a large summary of the application coverage, however, its biggest practical impact is expected in cryptanalysis and optimization tasks.

<table><caption>**Table 2.** Potential applications of the Grover Algorithm</caption><thead><tr><td>Domain</td><td>Example Uses</td><td>Benefit</td></tr></thead><tbody><tr><td>Cryptography</td><td>Key search, hash preimages</td><td>Reduces security from n to n/2 bits</td></tr><tr><td>Search Problems</td><td>Unstructured database lookup</td><td>√N speed-up</td></tr><tr><td>Optimization</td><td>SAT, CSPs, global search</td><td>Quadratic speed-up</td></tr><tr><td>Machine Learning</td><td>Model search, sampling</td><td>Boosts success probability</td></tr><tr><td>Graph Problems</td><td>Marked vertex search</td><td>Generic √N improvement</td></tr><tr><td>Physics & Simulation</td><td>Monte Carlo, chemistry</td><td>Faster sampling</td></tr></tbody></table>

## 4. Limits at the NISQ Era

Despite its theoretical significance, the practical implementation of the Grover's algorithm on current hardware remains highly limited. Realistic problem sizes require deep quantum circuits, but yet the Noisy Intermediate-Scale Quantum (NISQ) hardware devices suffer from short coherence times, limited qubit connectivity, and significant gate noise. Although Grover is theoretically powerful, today's hardware cannot yet execute it at meaningful scale. We give hereafter the main current limitations.

An implementation will need a circuit depth that far exceeds the NISQ capabilities. The Grover algorithm requires multiple iterations of the oracle (the most complex part), and of the diffusion operator, which involves many multi-qubit gates.

We need: $\frac{\pi}{4}\sqrt{2^n}$ iterations

Even for modest problem sizes, for instance searching among $N = 2^{30}$, we need more than 25000 iterations. Most NISQ machines can handle tens to a few hundred layers of logic before decoherence destroys the computation. Grover's algorithm requires thousands to millions of
coherent gates for any non-toy problem, and this is an important limit for current machines. If there are multiple marked items, the optimal number of iterations changes. NISQ noise makes it impossible to fine-tune the number of Grover iterations accurately in this case.

In addition, the Grover's speedup depends critically on having an efficient oracle that marks the solution. In theory, the oracle is a “black box,” but on real hardware oracles must be explicitly decomposed into elementary gates, complex conditions require deep circuits and finally the oracle implementation dominates total cost of the circuit. In practice, on NISQ machines, the time to build/run the oracle outweighs the quadratic speedup, thus, even if Grover's iteration were perfect, the oracle cost cancels the benefit.

Grover's speedup can only be guaranteed in a fault-tolerant regime, where circuits run with negligible noise. On NISQ hardware, we have noisy qubits, uncorrected errors, crosstalk and short coherence times. All these prevent Grover's algorithm from reaching its theoretical efficiency. Grover relies on very precise amplitude rotations and our NISQ architectures remain noisy as stated by their name. Noise accumulation kills the “Amplitude Amplification” since it leads to amplitude distortion, phase misalignment and thus it reduces the probability of measuring correctly the marked state. Because noise compounds across iterations, the probability of success quickly collapses as you add more steps. In NISQ, only 1–3 Grover iterations are realistically feasible, which corresponds to a maximum searching a space of size of N around 16, we will show how we fail for $N = 32$. Currently, NISQ devices cannot outperform classical computers for Grover-like tasks.

The last limitation we will mention is the lack of scalable QRAM (Quantum Random Access Memory). For Grover to search a database, we should be able to store the database in quantum-accessible memory, and accessible in superposition! We do not have QRAM at meaningful scale, current theoretical designs require extremely deep, error-sensitive circuits. Physical implementations are far beyond current hardware, but without QRAM, Grover cannot search a real dataset; it can only work on tiny synthetic examples such as the one we will present.

## 5. Reproducibility issues

Although fully universal quantum computers are not yet available, existing quantum hardware already supports nontrivial quantum circuits, enabling the implementation of algorithms through different paradigms depending on hardware architectures and vendor-specific constraints. By essence, quantum computers are stochastic, the results obtained are probabilistic and we do not obtain the “bitwise identical results” that we could expect from our classical deterministic computers (perfect repeatability is needed for debugging on a classical computer). For any serious scientific study with a Quantum computer, we need however reproducibility: finding the same probabilistic trend, i.e. statistically identical results, the same scientific conclusion. Too many studies claiming significant results could not be reproduced and this issue has recently attracted attention since we now have the evidence that research is often not reproducible particularly when using High Performance Computing and quantum computing [11].

Implementing Grover's algorithm on NISQ devices is extremely challenging but remains interesting to test the hardware evolution with a small number of qubits since we cannot scale with the current technology as explained in the previous section. Reproducibility in quantum computing is a major concern; we would need thousands of excellent qubits to obtain a single “perfect” qubit and it is physically difficult to obtain reliable qubits due to decoherence, noise, lack of error correction, and so on. In [12], the authors report the results of a 3 qubit Grover algorithm using trapped atomic ions. The author's of [13] have tested the current viability of using publicly available IBM quantum computers for data-driven tasks using Grover's algorithm to investigate the impacts of factors like qubit number, device choice, and qubit choices (up to 4
qubits). Thanks to IBM, which offers free access to its quantum machines, we implemented since 2019 a three and a five-qubits Grover algorithm. In [14] we have tested the algorithm with three simulators and obtained reproducible results (all simulations giving the expected solution with a probability around 94%). However, when running the experiment on different real quantum machines, the results were not so good, since we found a lot of variability with very bad results for 5 qubits as expected. At best, we obtained the correct solution with 60% accuracy (which is much less than predicted by the simulation, but still usable). The reproducibility problem arose when running this experiment multiple times on the same quantum machine, or on different quantum machines. With exactly the same code and parameters, we obtained statistically different results each time, most of which were not the expected ones. This confirms what we said in the previous section dealing with the limitations at the NISQ era, but it is worth noting improvements since 2019 when we first started to test the implementation of the Grover algorithm. Even when we do not obtain what we expect, the use of simulators or hybrid quantum machines is interesting for developing skills and for learning purposes.

## 6. Conclusion

Grover's algorithm is one of the cornerstone quantum algorithms, introduced by Lov Grover in 1996 [7]. It provides a quadratic speedup for searching an unstructured database or, more generally, for solving problems that can be reduced to an unstructured search problem. Its principle is to amplify the probability amplitude of a marked state (or states) through repeated operations called Grover iterations. This algorithm is not a universal solution but thanks to its "Amplitude Amplification" technique, it can boost the probability of finding a correct solution in other quantum algorithms, making them more efficient. Its biggest practical impact is expected in cryptanalysis and optimization tasks. Implementing efficiently the Grover algorithm requires circuit depth that is out of reach on today's quantum machines while the absence of scalable QRAM prevents true quantum access to classical datasets. Lastly, noise accumulation disrupts the delicate amplitude rotations central to the algorithm, reducing feasible iterations to only a few. Hence, Grover's algorithm implementations are available only at small-scale. Even there, quantum computing faces numerous practical challenges. Among them, obtaining the same scientific conclusions with our quantum machines is essential. Reproducibility is an epistemological cornerstone for the advancement of science, which is not obvious to reach at the era of Noisy Intermediate Scale Quantum machines since identical quantum experiments currently yield different statistical results. Readers interested to go further in the explanation of the fundamental principles of the algorithm can refer to [15], it will also give the latest trends in applying Grover's algorithm to various problems, including large-scale database searches, cryptanalysis, and optimization.

## References

1. Feynmann R., "Simulating Physics with computers, physics and Computation", International Journal of Theoretical Physics, 1982, **21**, pp. 467–488.

2. Deutsch D., "Quantum Theory, the Church-Turing principle and the universal quantum computer", In Proceedings of the Royal Society of London A, 1985, **400**(1818), pp. 97–117.

3. Shor P.W. "Good quantum error-correcting codes exist", *Physical review A*, 1996, **54**(2), pp. 1098–1106.

4. Lloyd S. "Universal quantum simulators", *Science*, 1996, **273**(5278), pp. 1073–1078.

5. Grover L.K., "A fast quantum mechanical algorithm for database search". In: *Proceedings of the twenty-eighth annual ACM symposium on Theory of computing*, 1996. pp. 212-219.
6. Nielsen M.A. and Chuang I.L. Quantum computation and quantum information. Cambridge university press, 2010, 702 p.

7. Szablowski P.J., "Understanding mathematics of Grover's algorithm". *Quantum Information Processing*, Springer, 2021, **20**(191), 21 p.

8. Brassard G., Hoyer P., Mosca M. et al. "Quantum amplitude amplification and estimation". *arXiv preprint* quant-ph/0005055, 2000.

9. Botsinis P., Alanis D., Babar Z. et al., "Quantum search algorithms for wireless communications". *IEEE Communications Surveys & Tutorials*, 2018, **21**(2), pp. 1209-1242.

10. Harrow A.W., Hassidim A. and Lloyd S., "Quantum algorithm for linear systems of equations". *Physical Review Letters*. 2008, **103**(15), 50502.

11. Antunes B.A., Hill D.R.C., "Reproducibility, Replicability and Repeatability: A survey of reproducible research with a focus on high performance computing". *Computer Science Review*, 2024, **53**, p. 100655.

12. Figgatt C., Maslov D., Landsman K.A. et al., "Complete 3-Qubit Grover search on a programmable quantum computer". *Nature Communications*, 2017, **8**(1918), 2.

13. Mandviwalla A, Ohshiro K. and Ji B., "Implementing Grover's algorithm on the IBM quantum computers. In proceedings of the 2018 IEEE international conference on big data. IEEE, 2018. pp. 2531-2537.

14. Hill D.R.C., Antunes B.A., Cluzel T., Mazel C., "A few words about quantum computing, epistemology, repeatability and reproducibility". In proceedings of the 21st EU/Meeting x Quantum School; Emerging optimization methods: from metaheuristics to quantum approaches. 2023. p. 4p.

15. Bae J., "Current status and prospects of quantum search algorithm: Grover's algorithm.". *New Physics*, 2024, pp. 1080-1091.