Mark and mix: searching four boxes
Grover's search algorithm uses a pattern of three steps: spread the amplitudes over every possibility, mark the ones that pass a check with a minus sign, and mix so that interference turns the signs into different odds. With two qubits there are four possibilities, so you can follow every number. You choose where the prize is; the experiment shows what each step does. It goes with How a quantum algorithm works (the section on searching four boxes) and builds on Interference: split, turn, recombine.
The experiment
Hide a prize in one of four boxes. Two qubits spread over all four, a check marks the prize with a minus sign, and a mix step turns that sign into a difference in odds. Predict, then measure.
Hide the prize
The four boxes represent the four possible results when two qubits are measured in the computational basis: 00, 01, 10 and 11. You choose the prize; you can change it at any time.
- Start at 00
- Spread (H, H)same for every box
- Check (mark)built for your box
- Mixsame for every box
- Repeat check and mix
- Measure
Only the check is built for the box you chose. Spread and Mix are the same operations whichever box holds the prize. The amplitudes and chances still depend on your choice, because the check changes the state that Mix then acts on. In a real search, the check is built from the problem's rule (for example, ‘does this candidate satisfy the conditions?’). It doesn't read a stored answer or a label.
Predict first
Prediction 1 of 4
Round 1, after the check.
Predictions aren't scored or saved.
The controls are yours: try any box and any number of rounds.
The controls unlock when you check your prediction, or skip.
The amplitudes, the chances and the explanation are hidden until you check your prediction.
Pick a box to hide the prize in.
Above the solid line: plus. Below it: minus. Each value is printed under its bar, above the box label. The dashed line, shown from the check onwards, is the average that Mix reflects around.
| Box | Amplitude | Chance |
|---|
Simulated measurements
Measuring after 0 complete rounds.
Simulated results from the exact chances above, drawn at random on this device. This is not a run on a quantum computer.
Latest result –
- Last run
- –
- Total at this setting
- 0
Each measurement uses a freshly prepared copy and gives one box.
In this demonstration, each copy is prepared, runs the selected number of rounds without any measurement in between, and is measured once at the end. Measuring partway through would disturb the superposition this search needs. (Other kinds of quantum circuits do use measurements during a computation.)
A run of 100 won't necessarily give exactly 25 of each. See ‘Why the counts don't match exactly’.
Why the counts don't match exactly
Each copy gives one box when it's measured, so every measurement uses a freshly prepared copy. Where each box has a 25% chance, 100 copies won't necessarily give exactly 25 of each; the more copies you measure, the closer the observed shares usually get to the prediction. Where the prize's chance is 100%, as after one round or four, every copy gives the prize in this ideal experiment.
Counts add up until you change the prize or the number of rounds, or press Clear counts; then they're cleared, so results from different settings are never mixed. Changing which step is shown doesn't clear them, because measurement always uses the completed rounds.
The maths, step by step: check your prediction to unlock the maths.
The maths, step by step
- Spread. Two H gates turn 00 into an even blend: every box has amplitude ½, and ½ squared is ¼.
- Check. The check multiplies the prize box's amplitude by −1 and leaves the others alone. Squares don't change, so neither do the odds.
- Mix. Take the average of the four amplitudes. Each new amplitude is 2 × average − old amplitude: every amplitude is reflected around the average. The average itself doesn't change.
- Rounds. With four boxes, the prize's amplitude after k rounds is sin((2k + 1) × 30°), so its chance is sin²((2k + 1) × 30°): 25%, 100%, 25%, 25%, 100%, 25%, 25% for k = 0 to 6.
Technical view
Start in |00⟩. H⊗H gives |s⟩ = (|00⟩ + |01⟩ + |10⟩ + |11⟩)/2. The check for prize w is the oracle Ow = I − 2|w⟩⟨w|. The mix is the diffuser D = 2|s⟩⟨s| − I. One round is G = D Ow. Write |s⟩ = sin θ |w⟩ + cos θ |rest⟩, where |rest⟩ is the equal superposition of the unmarked states and sin θ = ½ (θ = 30°). Each round rotates the state by 60° in the plane spanned by the marked state and the equal superposition of the unmarked states. After k rounds the prize amplitude is sin((2k + 1)θ).
After three rounds the state is −|s⟩ and after six it is |s⟩. An overall sign on every amplitude (a global phase) changes no probability. Some texts define the diffuser with the opposite overall sign, −D; that changes only this global sign, not any chance.
What the experiment shows
- Marking alone changes an amplitude's sign, but not the odds of measuring each box. The check flips the sign of the prize's amplitude, and a number and its negative have the same square.
- Mixing turns the sign into odds. Reflecting every amplitude around their average moves amplitude onto the marked box. With four boxes, one round moves all of it.
- More rounds aren't always better. A second round overshoots and the prize falls back to 1 in 4; the chance rises and falls in a cycle as you keep going.
- Only the check depends on the prize. Spread and Mix are the same for every box. The results still depend on your choice, because the check changes the state that Mix acts on.
What it leaves out
- Four is a special size. With four boxes one round gives the prize every time. With more boxes you need about √N rounds, and the prize becomes very likely, not certain.
- The check is the hard part. Here the check is simply built for the box you chose. In a real problem it's a circuit that tests a candidate against the problem's rule, without knowing the answer in advance. Building it takes work, and it runs on every step of the search.
- It isn't ‘trying every box at once’. All four boxes share the amplitudes, but a measurement gives one box. The advantage comes from interference steering amplitude to the prize over about √N rounds, which is a square-root speed-up, not an exponential one.
- Not a database lookup. Grover's algorithm searches for inputs that pass a check; it doesn't read a stored table faster.
- Ideal machine. No noise or errors. Real hardware adds errors, and error correction adds overhead (see What quantum computers are good at).
- Simulated results. The amplitudes are calculated exactly; the measured counts are random samples drawn from those chances on this device.
Check yourself
How a quantum algorithm works walks through the same four boxes as a static figure, and What quantum computers are good at explains what a square-root speed-up is worth in practice.
The experiment runs entirely in your browser. Your choice of box, your predictions and your results aren't stored, and this page's own code doesn't send them anywhere. Cloudflare Web Analytics runs on every Plain Quantum page and measures how each page loads and responds, including to clicks and key presses, and the typefaces load from Google; see Privacy. The model is tested automatically: every amplitude, chance and sampling result is checked against the formulas on this page.
Sources and further reading
Tags show what kind of source each one is (how this site is made). Spotted an error? Email hello@plainquantum.com.
- Peer-reviewed paperA fast quantum mechanical algorithm for database searchLov Grover, STOC, 1996
- BookQuantum Computation and Quantum Information (10th anniversary edition)Michael Nielsen and Isaac Chuang, Cambridge University Press, 2010
- Vendor documentationGrover's algorithm (tutorial): an oracle marks states with a phase of −1, then amplification raises their amplitudeIBM Quantum documentation