Grover's Algorithm

Search an unstructured space of N items in O(√N) queries — a quadratic speedup over the classical O(N). It is the canonical example of amplitude amplification.

The problem it solves

Imagine a function f(x) that returns 1 for exactly one "winning" input and 0 for every other. You have no structure to exploit — no sorting, no index, just the ability to test inputs. A classical computer can do no better than trying them one at a time: on average N/2 tests, and N in the worst case. Grover finds the winner in about √N tests.

The speedup is quadratic, and it compounds at scale:

Note: the “≈√N” column is the order of magnitude of the query complexity, not the exact iteration count; the optimal number of iterations is ⌊(π/4)·√N⌋.

Geometric intuition — amplitude amplification

The whole algorithm lives in a 2-D plane spanned by two vectors: the winning state |w⟩ and an equal mixture of all the losers, |s'⟩. The starting uniform superposition |s⟩ sits almost on top of |s'⟩, leaning toward |w⟩ by only a tiny angle θ — because a random guess has just a 1/N chance of being right.

Each Grover iteration performs two reflections, and two reflections make a rotation. Specifically, every iteration rotates the state by 2θ toward |w⟩. Repeat enough times and the state swings around to point almost exactly at |w⟩, so a measurement returns the winner with high probability.

Why √N iterations — and why not more

The initial lean satisfies sin θ = 1/√N, so for large N the angle is θ ≈ 1/√N (in radians). Each step adds 2θ, and we need to travel from ≈0 to π/2 (the |w⟩ axis). That takes about

(π/2) / (2θ) ≈ (π/4)·√N iterations.

This is why Grover is periodic, not monotonic: keep iterating past the optimum and the state rotates past |w⟩, and the success probability falls again. More shots help; more iterations do not.

The two operators

Oracle then diffusion = one rotation by 2θ. That pairing, repeated, is the engine of the algorithm.

What it is — and isn't — good for

• Quadratic, not exponential. Grover does not "break" hard problems the way Shor breaks factoring; it just square-roots the cost of brute force.
• The oracle must be a cheap quantum function. Loading N unstructured classical records into an oracle itself costs O(N) — which would erase the speedup. The win comes when the oracle is a compact rule (a hash, a constraint check), not a literal database.
• It is provably optimal. No quantum algorithm beats O(√N) for truly unstructured search, so this is the end of the road for this problem — not a stepping stone to more.
• It generalises. The same reflect-and-rotate trick, called amplitude amplification, is a reusable building block inside larger algorithms.

The algorithm, step by step

1. Prepare a uniform superposition with Hadamards — the starting state |s⟩.
2. Apply the oracle to phase-flip the marked state.
3. Apply the diffusion operator to amplify its amplitude (one rotation of 2θ).
4. Repeat about (π/4)·√N times, rounded to the nearest integer, then measure.

Seeing it in code

The kernel below makes the marked state the all-ones string 11…1. Read it against the theory above: h(q) builds the uniform superposition; the multi-controlled z.ctrl(...) is the oracle that phase-flips that one state; the h(q); x(q) … x(q); h(q) sandwich is the diffusion operator; and iters is the nearest integer to (π/4)·√N. The optimal count is more precisely k ≈ round(π/(4θ) − 1/2) — the nearest integer, since the success probability sin²((2k+1)θ) peaks at k = π/(4θ) − 1/2 — with sin θ = 1/√N.

This implementation differs from the standard diffusion operator D = 2|s⟩⟨s| − I by at most a global phase / equivalent convention, which does not affect measurement probabilities.

The example assumes n ≥ 2; for n = 1 the semantics of a multi-controlled gate with an empty control list is framework-dependent.

import qalgora, math

@qalgora.kernel
def grover(n: int, iterations: int):
    q = qalgora.qvector(n)
    h(q)
    for _ in range(iterations):
        # oracle: mark the all-ones state
        z.ctrl(q[0:n-1], q[n-1])
        # diffusion operator
        h(q); x(q)
        z.ctrl(q[0:n-1], q[n-1])
        x(q); h(q)
    mz(q)

n = 3
iters = round(math.pi / 4 * math.sqrt(2 ** n))
print(qalgora.sample(grover, n, iters))   # peaks at "111"

References

• L. K. Grover, "A fast quantum mechanical algorithm for database search," Proc. 28th ACM STOC, 212-219 (1996). arXiv:quant-ph/9605043