Your first algorithm: Grover search

Build and run, step by step, Grover’s algorithm, which finds the marked option among four in a single step. How big is the quantum speed-up, and what doesn’t it speed up?

The problem: which box holds the prize?

One of four closed boxes holds a prize. You can’t look inside without opening a box, but you can ask a “checking device”. Classically you need 1 question if you are lucky and 3 in the worst case (if three are empty you don’t need to ask about the fourth); 2.25 questions on average.

Grover’s algorithm solves this problem with a single question, with certainty. In this lesson the boxes are numbered 00, 01, 10 and 11. The prize is in box 11.

Step 1: put all boxes into superposition

We apply H to each of the two qubits. Now each of the four results has a 25% probability. Measuring at this point would pick a random box.

Step 2: mark the right answer (oracle)

The checking device (oracle) flips the sign of the right box’s amplitude: +0.5 becomes −0.5. In this example a CZ gate does it, because CZ changes the sign only when both qubits are 1.

Note that the probabilities are still 25%. The sign change is invisible, but as you learned in the previous lesson it will make a difference through interference.

Step 3: reflect about the average (diffusion)

The diffusion step (H, X, CZ, X, H gates) mirrors every amplitude about the average of all amplitudes. The average is +0.25. The other three boxes’ amplitudes of +0.5 become 0 when reflected. The marked box’s amplitude of −0.5 becomes +1.

Result: box 11 has a probability of 100%. With a single oracle query we found the prize with certainty.

How fast?

With N options classical search needs N/2 questions on average. Grover finds the answer in about 0.785 × √N questions. With a million options that is about 785 questions instead of 500,000.

To be honest, this is a “quadratic” speed-up, not an unlimited one. On today’s noisy devices it is not yet practical for large searches. For some problems (such as factoring with Shor’s algorithm) quantum computers are expected to give a much larger, exponential advantage.

What’s next?

Congratulations, you have run your first quantum algorithm! Click “Bu devrenin Qiskit kodu” (this circuit’s Qiskit code) in the playground to run the same program on your own computer.

To continue, take the intermediate course, where you build Deutsch–Jozsa, Bernstein–Vazirani, the quantum Fourier transform and phase estimation.

Try it yourself

Measure 1000 times: the result is 11 every time. Then click the third gate in the circuit (the first CZ, the oracle) to remove it and measure again. Without marking, the algorithm can’t bring any box forward and all four results are 25%.

Open the circuit in your browser

The circuit playground is in Turkish. Button guide: “1000 kez ölç” = measure 1000 times, “Durum vektörünü göster” = show the state vector, “Bu devrenin Qiskit kodu” = this circuit’s Qiskit code, “Geri al” = undo, “Temizle” = clear. Click a gate in the circuit to remove it.

Key points

Grover’s algorithm consists of superposition, marking (oracle) and diffusion steps.
The oracle flips the sign of the right answer’s amplitude; diffusion amplifies it through interference.
With 4 options a single query is enough; with N options about √N queries are needed.
Grover’s speed-up is quadratic; for some problems the quantum advantage is much larger.

Test yourself

What does the oracle step do in Grover’s algorithm?

It measures the right answer and prints it
It flips the sign of the right answer’s amplitude
It deletes the wrong answers from the circuit

Show the answer

It flips the sign of the right answer’s amplitude. The oracle makes the right answer’s amplitude negative without changing the probabilities. The diffusion step turns this sign difference into a large probability through interference.

← Interference: the hidden power of quantum computers · Intermediate course: quantum algorithms →