What is Grover's algorithm?

The problem it solves

Grover's algorithm solves unstructured search: you have N possible answers, no order or pattern to exploit, and a test that says yes for the right one and no for every other. Classically the only option is to try them one by one. With one right answer you need N/2 tries on average and N in the worst case.

The test is called the oracle. In a real application it is a circuit that checks a candidate, for example whether a key decrypts a message or whether an assignment satisfies a set of constraints. Grover's algorithm does not need to know how the oracle works inside. It only needs to be able to run it on a superposition of every candidate at once.

How it works, in three moves

Grover's algorithm repeats one short routine, the Grover iteration, about (π/4)√N times. Everything happens to the amplitudes of the N possible answers.

1. Start in an equal superposition. A Hadamard gate on every qubit gives each of the N answers the same amplitude, 1/√N. Measuring now would be a blind guess.
2. Ask the oracle. The oracle flips the sign of the right answer's amplitude and leaves every other amplitude alone. The probabilities have not changed yet, because a probability is the amplitude squared, but the right answer is now marked.
3. Reflect about the mean. The diffusion step replaces every amplitude a by 2·mean − a. The marked amplitude is far below the mean, so it lands far above it. Every other amplitude shrinks a little.

Repeat steps 2 and 3, and the right answer's amplitude grows with each round while the rest fade. Then measure.

Try it yourself

Pick a number of items, then press Oracle and Diffuse in turn, or Step to do both. Watch the marked bar: the oracle flips it below the line and the diffusion throws it up past everything else. The dashed line is the mean.

A worked example with four items

With N = 4, every amplitude starts at 1/2. The oracle makes the marked one −1/2. The mean is now (1/2 + 1/2 + 1/2 − 1/2)/4 = 1/4. Reflecting about it sends each unmarked amplitude to 2·(1/4) − 1/2 = 0, and the marked one to 2·(1/4) + 1/2 = 1.

So after a single iteration, the right answer has probability exactly 1. A classical search of four items can need up to three checks. Grover's algorithm needs one.

Grover's algorithm in 13 lines of Python

You do not need a quantum computer or a quantum library to see the algorithm work. The state of three qubits is just eight numbers, and the two steps are one line each. This is a complete simulation with NumPy, searching eight items for item 5 (binary 101):

import numpy as np

n = 3                        # 3 qubits, so N = 8 possible answers
N = 2 ** n
marked = 5                   # the answer the oracle recognises: |101>

state = np.ones(N) / np.sqrt(N)          # Hadamard on every qubit
iterations = int(np.pi / 4 * np.sqrt(N)) # about (pi/4) * sqrt(N), here 2

for step in range(1, iterations + 1):
    state[marked] *= -1                  # oracle: flip the sign of the answer
    state = 2 * state.mean() - state     # diffusion: reflect about the mean
    print(f"after iteration {step}: P(answer) = {state[marked] ** 2:.4f}")

probabilities = state ** 2
print("most likely result:", format(int(np.argmax(probabilities)), f"0{n}b"))
print("chance of reading it:", round(float(probabilities[marked]), 4))

after iteration 1: P(answer) = 0.7812
after iteration 2: P(answer) = 0.9453
most likely result: 101
chance of reading it: 0.9453

After two iterations the right answer comes out 94.5% of the time. That is the best possible for eight items: the algorithm can never quite reach 100% unless N is a special value such as 4.

Why about √N steps?

Each Grover iteration turns the state by the same small angle, 2θ, where sin θ = 1/√N, in a plane spanned by "the right answer" and "everything else". The state starts almost pointing at "everything else" and has to turn through about 90°. That takes about (π/2)/(2θ) ≈ (π/4)√N iterations, because θ ≈ 1/√N when N is large.

Too many steps make it worse

Because each iteration is a rotation, going past the target overshoots it. Keep iterating on the same eight items and the success probability falls, then rises again:

import numpy as np

N, marked = 8, 5
state = np.ones(N) / np.sqrt(N)
for step in range(1, 7):
    state[marked] *= -1
    state = 2 * state.mean() - state
    print(step, round(float(state[marked] ** 2), 4))

1 0.7812
2 0.9453
3 0.3301
4 0.0122
5 0.548
6 0.9998

The best answer arrives after 2 iterations (94.5%), falls to 1.2% after 4, and comes back to 99.98% after 6. In practice you stop at the first peak, which is why you need to know, or estimate, how many right answers there are. With M right answers the best number of iterations is about (π/4)√(N/M).

How big is the speedup?

The speedup is quadratic. That is far less dramatic than Shor's algorithm, which gives an exponential speedup for factoring, but it applies to almost any problem where you can check an answer quickly. It is also the best possible: in 1997, Bennett, Bernstein, Brassard and Vazirani proved that no quantum algorithm can search an unstructured list in fewer than about √N oracle calls.

Can Grover's algorithm break AES?

Not in any practical sense. Against a symmetric cipher such as AES, Grover's algorithm turns a brute-force search of 2ⁿ keys into roughly 2^(n/2) runs of the cipher on a quantum computer, so it halves the key length in bits. AES-128 would need on the order of 2⁶⁴ steps run one after another on a large, error-corrected machine, and the steps cannot be spread out across many machines as easily as a classical search.

The simple defence is longer keys. AES-256 still leaves about 2¹²⁸ steps, which is out of reach. That is why long-term guidance, such as the US NSA's CNSA 2.0 suite, asks for AES-256. The real quantum threat to encryption today is Shor's algorithm against RSA and elliptic curves, covered in can quantum computers break encryption?

What Grover's algorithm cannot do

• It does not speed up looking things up in an ordinary database. Loading N records into a quantum computer already takes about N steps, which wipes out the gain. The algorithm pays off when the "list" is implicit, such as every possible key or every possible assignment, and the oracle computes the check on the fly.
• It does not give certainty. The answer comes out with high probability. You check it classically, which is cheap, and run again if it is wrong.
• It needs a large, reliable quantum computer to matter. Each oracle call is a deep circuit, and hundreds of thousands of them in a row need quantum error correction.

Frequently asked questions

Who invented Grover's algorithm?

Lov Grover, a computer scientist at Bell Labs, published it in 1996 in a paper titled "A fast quantum mechanical algorithm for database search".

Is Grover's algorithm faster than Shor's algorithm?

They solve different problems. Shor's algorithm gives an exponential speedup for factoring and discrete logarithms. Grover's algorithm gives a quadratic speedup for general search. For the problems Shor's algorithm handles, it is far faster.

How many qubits does Grover's algorithm need?

Searching N = 2ⁿ items needs n qubits to hold the candidates, plus whatever extra qubits the oracle uses to compute its check. The example above searches 8 items with 3 qubits.