Method

Grover's algorithm explained: fewer queries, not always less time

Grover's algorithm finds one marked item among N unsorted candidates with about π4N\frac{\pi}{4}\sqrt{N} calls to an oracle that recognises it, where a classical search needs about N/2N/2 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 xx with f(x)=1f(x) = 1 among NN candidates, when ff can only be evaluated, not inspected
Oracle calls
About π4N\frac{\pi}{4}\sqrt{N}[2] for one marked item, against about N/2N/2 for a classical search; Grover's paper gives order N\sqrt{N}[1]
Best possible
No quantum algorithm needs fewer than order N\sqrt{N} calls for unstructured search[3], so the gain is quadratic and no more
Success after k rounds
sin⁡2((2k+1)θ)\sin^2((2k + 1)\theta), with sin⁡2θ=M/N\sin^2\theta = M/N for MM marked items[2]
Qubits
log⁡2N\log_2 N 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 Grover circuit 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 N=2nN = 2^n indices carry the same amplitude 1/N1/\sqrt{N} (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 sin⁡2θ=M/N\sin^2\theta = M/N when MM of the NN indices are marked. Each round rotates the state by 2θ2\theta towards the marked part, so after kk rounds the chance of measuring a marked index is sin⁡2((2k+1)θ)\sin^2((2k + 1)\theta)[2]. The best number of rounds is ⌊π/(4θ)⌋\lfloor \pi/(4\theta) \rfloor, which is about π4N/M\frac{\pi}{4}\sqrt{N/M} for large NN.

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 MM 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 N/M\sqrt{N/M} 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 ff, and it holds only when ff 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 N\sqrt{N} 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

Python
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 circuit

eigenkit 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 sin⁡θ=1/N\sin\theta = 1/\sqrt{N}. Rounds k=⌊π/(4θ)⌋k = \lfloor \pi/(4\theta) \rfloor, success probability sin⁡2((2k+1)θ)\sin^2((2k + 1)\theta), and the classical figure is the average number of checks when items are tried in random order until the oracle says yes, (N+1)/2(N + 1)/2. The gap between the two counts grows with NN, and so does the length of the circuit that has to run without an error.

Items NGrover roundsSuccess probabilityClassical checks on average
4 (2 qubits)1100%2.5
8 (3 qubits)294.5%4.5
16 (4 qubits)396.1%8.5
1,024 (10 qubits)2599.95%512.5
about 10610^{6} (20 qubits)804above 99.99%524,288.5
about 101210^{12} (40 qubits)823,549above 99.99%about 5.5×10115.5 \times 10^{11}

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 NN checks, or N−1N - 1 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 PP machines save only a factor P\sqrt{P}, while PP classical machines save a factor PP. Cryptography shows what this does: NIST puts key recovery on AES-128 at 2170/MAXDEPTH2^{170}/\mathrm{MAXDEPTH} quantum gates against 21432^{143} classical gates[9], where MAXDEPTH, the longest serial run an attacker can afford, is taken between 2402^{40} and 2962^{96} 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 NN classical records into one already takes NN steps, the cost Grover was meant to avoid. An indexed classical lookup takes O(1)O(1) or O(log⁡N)O(\log N) time anyway.

Claims you will see, and what holds

ClaimWhat holds
Quadratically faster searchQuadratically 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 tractableA search space of 2n2^{n} still needs about 2n/22^{n/2} rounds. The exponent is halved, not removed.
Speeds up database searchOnly for a database given as a quantum oracle, which needs QRAM. Sorted or indexed classical data is already searched in far fewer than N\sqrt{N} steps.
Breaks symmetric encryptionHalves 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 optimisationMinimum finding over an unstructured list in order N\sqrt{N} probes[6]. Structured problems such as scheduling are solved classically by methods that do not scan every candidate.
Demonstrated on hardwareOn 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 AA that puts probability a=sin⁡2θa = \sin^2\theta on a "good" outcome, and the operator Q=AS0A†SgoodQ = A S_0 A^\dagger S_{\mathrm{good}} rotates by 2θ2\theta 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 AA and then QmQ^{m} turns the probability into sin⁡2((2m+1)θ)\sin^2((2m + 1)\theta), which changes faster with θ\theta than a single sample does. Amplitude estimation reads θ\theta off those amplified probabilities and reaches error ε\varepsilon with order 1/ε1/\varepsilon calls to AA, where direct sampling needs order 1/ε21/\varepsilon^2[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

  1. 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.
  2. 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.
  3. 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.
  4. C. Zalka. Grover's quantum searching algorithm is optimal. Physical Review A 60, 2746–2751, 1999. arXiv:quant-ph/9711070.
  5. 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.
  6. C. Dürr, P. Høyer. A quantum algorithm for finding the minimum. arXiv preprint, 1996. arXiv:quant-ph/9607014.
  7. 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.
  8. 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.
  9. National Institute of Standards and Technology. Submission requirements and evaluation criteria for the post-quantum cryptography standardization process. NIST call for proposals, 2016.
  10. 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