Grover's algorithm explained: fewer queries, not always less time
Grover's algorithm finds one marked item among N unsorted candidates with about calls to an oracle that recognises it, where a classical search needs about on average, and no quantum algorithm can do better. That is a proven reduction in oracle calls, not in running time: on error-corrected hardware each call is slow enough that a quadratic gain only pays off after very long runs. Its lasting use today is amplitude amplification, the same rotation inside amplitude estimation.
Updated
At a glance
- The problem
- Find an input with among candidates, when can only be evaluated, not inspected
- Oracle calls
- About [2] for one marked item, against about for a classical search; Grover's paper gives order [1]
- Best possible
- No quantum algorithm needs fewer than order calls for unstructured search[3], so the gain is quadratic and no more
- Success after k rounds
- , with for marked items[2]
- Qubits
- for the index register, plus whatever the oracle circuit needs as work space
- On hardware
- A complete search over 8 items on 3 trapped-ion qubits in 2017[8]; larger searches need longer circuits and collect more noise
- In eigenkit
- No Grover search solver; the amplification operator ships as a
Grovercircuit block and runs inside IQAE (amplitude estimation)
How Grover search works
The algorithm starts with a Hadamard gate on every qubit of an n-qubit register, so all indices carry the same amplitude (see quantum superposition for what that means). It then repeats one round of two reflections. The oracle flips the sign of the amplitude of every marked index and leaves the rest alone. The diffusion step reflects every amplitude about their mean, so the one amplitude that was pushed below the mean comes out above it[1].
Two reflections make a rotation. Write the start state as a mix of the marked and unmarked parts, with when of the indices are marked. Each round rotates the state by towards the marked part, so after rounds the chance of measuring a marked index is [2]. The best number of rounds is , which is about for large .
The rotation keeps going past the target. Run too many rounds and the success probability falls again, which is why the count has to be fixed in advance. When is not known, Boyer, Brassard, Høyer and Tapp choose the number of rounds at random from a growing range, and still find a marked item with order calls on average.
Grover's own paper framed this as searching a database, and the name stuck. The framing misleads. The speed-up is a count of calls to , and it holds only when is a black box that has no structure to exploit. Dürr and Høyer use the same search to find the minimum of an unsorted list with order probes[6], which is the honest version of "Grover for optimisation": it applies to an unstructured list of values, not to a scheduling problem that a classical solver can prune.
A 16-item search, built from gates
import math
from eigenkit import Circuit, CircuitBuilder, Z
n, marked = 4, "1011" # N = 16 items, one of them marked
qubits = range(n)
def flip_zeros(qc, bits):
for q, bit in enumerate(bits):
if bit == "0":
qc.x(q)
def grover(iterations):
qc = CircuitBuilder(n_qubits=n)
for q in qubits:
qc.h(q) # uniform superposition over all 16 indices
for _ in range(iterations):
flip_zeros(qc, marked) # oracle: phase flip on the marked index
qc.mcz(*qubits)
flip_zeros(qc, marked)
for q in qubits: # diffusion: reflect about the mean amplitude
qc.h(q)
qc.x(q)
qc.mcz(*qubits)
for q in qubits:
qc.x(q)
qc.h(q)
probs = Circuit(qc.build(), observables=Z(0)).probabilities([])
return probs[int(marked, 2)]
for k in range(6):
print(k, round(float(grover(k)), 4))
# 0 0.0625 1 0.4727 2 0.9084 3 0.9613 4 0.5817 5 0.1255
theta = math.asin(1 / math.sqrt(16))
print(math.floor(math.pi / (4 * theta)), round(math.sin(7 * theta) ** 2, 4))
# 3 0.9613: the formula agrees with the circuiteigenkit has no Grover search solver (its Grover block is the amplitude-estimation operator, which marks the good state on an ancilla), so this is the textbook search circuit written gate by gate with the multi-controlled Z gate. The built-in NumPy simulator returns exact probabilities. Three rounds give 96.1%; a fourth overshoots to 58.2%.
The textbook numbers, computed
One marked item, so . Rounds , success probability , and the classical figure is the average number of checks when items are tried in random order until the oracle says yes, . The gap between the two counts grows with , and so does the length of the circuit that has to run without an error.
| Items N | Grover rounds | Success probability | Classical checks on average |
|---|---|---|---|
| 4 (2 qubits) | 1 | 100% | 2.5 |
| 8 (3 qubits) | 2 | 94.5% | 4.5 |
| 16 (4 qubits) | 3 | 96.1% | 8.5 |
| 1,024 (10 qubits) | 25 | 99.95% | 512.5 |
| about (20 qubits) | 804 | above 99.99% | 524,288.5 |
| about (40 qubits) | 823,549 | above 99.99% | about |
Computed from the formula with Python's math module; the 16-item row is also what the circuit above prints. The classical worst case is checks, or if the last unchecked item is taken without checking it.
Why fewer queries is not the same as faster
The query count compares one oracle call with one classical check, as if both took the same time. They do not. On a quantum computer the oracle is a reversible circuit that evaluates f on a superposition of inputs, so every classical step inside f becomes several quantum gates, and the diffusion step adds gates that grow with n.
Error correction makes each of those gates slow. Babbush and colleagues estimate a Toffoli gate at about 170 µs[7] in a surface code on superconducting qubits, against about 330 ps[7] for one clock cycle of a classical processor. With the kindest assumption they could defend, an oracle of only 100 Toffoli gates, a quadratic speed-up overtakes one classical core only after 2.4 hours[7] of quantum running time, and overtakes a classical rival that is 1,000 times faster through parallelism only after 100 days[7]. For a compiled example, quantum-accelerated simulated annealing, the break-even time against one core is 320 days[7]. Their conclusion is that quadratic speed-ups will not give an advantage on early fault-tolerant machines unless error correction gets much faster, while quartic ones look far more practical.
Parallel hardware does not rescue it. Zalka proved that Grover search cannot be parallelised better than by splitting the search space between independent machines[4], so machines save only a factor , while classical machines save a factor . Cryptography shows what this does: NIST puts key recovery on AES-128 at quantum gates against classical gates[9], where MAXDEPTH, the longest serial run an attacker can afford, is taken between and logical gates[9]. NIST's lowest post-quantum security category is still defined by AES-128 key search, and the same document notes that Grover's long serial runs make the quantum speed-up less dramatic in a realistic attack.
Data is the last catch. A "database" can only be searched this way if it is available as a quantum oracle, which for stored records means a quantum memory (QRAM) that answers in superposition. None exists at scale, and writing classical records into one already takes steps, the cost Grover was meant to avoid. An indexed classical lookup takes or time anyway.
Claims you will see, and what holds
| Claim | What holds |
|---|---|
| Quadratically faster search | Quadratically fewer oracle calls, which is proven. Whether it is faster in wall-clock time depends on the cost of each call on error-corrected hardware, and for now that cost wins. |
| Exponential problems become tractable | A search space of still needs about rounds. The exponent is halved, not removed. |
| Speeds up database search | Only for a database given as a quantum oracle, which needs QRAM. Sorted or indexed classical data is already searched in far fewer than steps. |
| Breaks symmetric encryption | Halves the effective key length in query count, but the serial depth makes the attack impractical; NIST still uses AES-128 as its baseline category[9]. |
| Speeds up optimisation | Minimum finding over an unstructured list in order probes[6]. Structured problems such as scheduling are solved classically by methods that do not scan every candidate. |
| Demonstrated on hardware | On 3 qubits, the average success probability of a single-answer search was 38.9% (Boolean oracle) and 43.7% (phase oracle)[8], against a noise-free 78.1%[8] after one round and 25%[8] for the best classical strategy with one query. Better than classical, well short of the ideal, and on 8 items. |
Where the idea is used today: amplitude amplification
Brassard, Høyer, Mosca and Tapp showed that nothing in Grover's rotation depends on the starting state being uniform[5]. Replace the first layer of Hadamards with any state-preparation circuit that puts probability on a "good" outcome, and the operator rotates by exactly as before. This is amplitude amplification, and it is the form in which Grover's idea is most used.
Its most useful application is not to find the good outcome but to measure how likely it is. Running and then turns the probability into , which changes faster with than a single sample does. Amplitude estimation reads off those amplified probabilities and reaches error with order calls to , where direct sampling needs order [5]. Iterative quantum amplitude estimation (IQAE) does this without phase estimation, choosing m adaptively from round to round[10]. Risk and pricing models mark an event such as "the loss exceeds this threshold" on an ancilla and estimate its probability this way. The same caveat applies as for search: it is a count of oracle calls, and the oracle must still be built and run on error-corrected hardware.
eigenkit ships this part. Its IQAE solver takes your state-preparation circuit, applies the Grover operator, and returns an estimate, a confidence interval and the number of oracle calls it used. It does not ship a Grover search solver, an oracle library, minimum finding or QRAM; the circuit above is as far as search goes, written by hand. The docs glossary calls the Grover operator "the engine of IQAE", and the Algorithms guide has a call you can run.
Run it on a real QPU with EigenOrbit RouterThe 16-item search above, where hardware noise shows up as a success probability well under the ideal 96.1%.In eigenkit: pip install "eigenkit[router]", then provider=RouterConfig(device=...) (docs).
Questions
What is Grover's algorithm used for?
In principle, for any search where the only way to recognise a solution is to test candidates, with a quadratic saving in the number of tests. In practice its main use is amplitude amplification: the same rotation inside amplitude estimation, which estimates a probability with fewer calls to a circuit than direct sampling. Large search problems are not solved with it today.
How many iterations does Grover's algorithm need?
For M marked items among N, the best number of rounds is the floor of π/(4θ), where sin²θ = M/N, which is about (π/4)√(N/M). For one marked item among 16 that is 3 rounds, with a success probability of 96.1%. More rounds overshoot: a fourth round drops it to 58.2%.
Is Grover's algorithm faster than classical search?
It needs quadratically fewer oracle calls, and that is proven optimal. It is not faster in wall-clock terms on any machine that exists, and resource estimates for error-corrected hardware put the break-even point for a quadratic speed-up at hours to years of quantum running time, depending on the oracle and on how many classical processors it is compared against.
Does Grover's algorithm break AES encryption?
It halves the effective key length in query count, so a 128-bit key needs about 2^64 Grover rounds. Those rounds must run one after another, and Grover search parallelises poorly, so the attack is far beyond any realistic machine. NIST still uses AES-128 key recovery as the reference for its lowest post-quantum security category.
Can Grover's algorithm run on a real quantum computer?
Yes, for a handful of qubits. A complete search over 8 items on 3 trapped-ion qubits beat the best classical strategy but reached about half of the ideal success probability. Each extra qubit lengthens the circuit, so larger searches lose the signal in noise until error correction is available.
Does eigenkit implement Grover's algorithm?
Not as a search solver. eigenkit provides the gates to build the textbook circuit, including a multi-controlled Z, and runs it on its exact simulator. Its IQAE solver uses the Grover operator for amplitude estimation, which is the part of the idea it ships as a tested algorithm.
Sources
- L. K. Grover. A fast quantum mechanical algorithm for database search. Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), 1996. arXiv:quant-ph/9605043.
- M. Boyer, G. Brassard, P. Høyer, A. Tapp. Tight bounds on quantum searching. Fortschritte der Physik 46, 493–506, 1998. arXiv:quant-ph/9605034.
- C. H. Bennett, E. Bernstein, G. Brassard, U. Vazirani. Strengths and weaknesses of quantum computing. SIAM Journal on Computing 26(5), 1510–1523, 1997. arXiv:quant-ph/9701001.
- C. Zalka. Grover's quantum searching algorithm is optimal. Physical Review A 60, 2746–2751, 1999. arXiv:quant-ph/9711070.
- G. Brassard, P. Høyer, M. Mosca, A. Tapp. Quantum amplitude amplification and estimation. AMS Contemporary Mathematics 305, 53–74, 2002. arXiv:quant-ph/0005055.
- C. Dürr, P. Høyer. A quantum algorithm for finding the minimum. arXiv preprint, 1996. arXiv:quant-ph/9607014.
- R. Babbush, J. R. McClean, M. Newman, C. Gidney, S. Boixo, H. Neven. Focus beyond quadratic speedups for error-corrected quantum advantage. PRX Quantum 2, 010103, 2021. arXiv:2011.04149.
- C. Figgatt, D. Maslov, K. A. Landsman, N. M. Linke, S. Debnath, C. Monroe. Complete 3-qubit Grover search on a programmable quantum computer. Nature Communications 8, 1918, 2017. arXiv:1703.10535.
- National Institute of Standards and Technology. Submission requirements and evaluation criteria for the post-quantum cryptography standardization process. NIST call for proposals, 2016.
- D. Grinko, J. Gacon, C. Zoufal, S. Woerner. Iterative quantum amplitude estimation. npj Quantum Information 7, 52, 2021. arXiv:1912.05559.
Run it yourself with eigenkit
eigenkit is EigenOrbit's open-source Python library: write a circuit once, run it on any simulator or QPU, and test it against a classical baseline on your own data before you invest in it or rule it out.
$ pip install eigenkit