From knowing nothing to your first quantum speedup
Every time you buy something online, send a message, or log into your bank, your data is protected by encryption. The idea is simple: take your message, scramble it with a secret key, and send the scrambled version. Anyone who intercepts it sees gibberish. Only someone with the key can unscramble it.
Here's what makes modern encryption work: the algorithm that does the scrambling is completely public. Anyone can read exactly how AES or any other cipher works — it's published, studied, and open-source. The security doesn't come from hiding the algorithm. It comes from hiding the key.
Think of it like a padlock. Everyone knows how padlocks work. You can buy one, take it apart, study the mechanism. But that doesn't help you open a locked one — you need the specific key. The lock's security comes from the astronomical number of possible keys, not from the secrecy of how locks work.
Now imagine you're an attacker. You've intercepted an encrypted message. You know the encryption algorithm (it's public). You even know a piece of the original message — maybe the file header, or a standard greeting. You have:
You're missing one thing: the key. If you had the key, you could plug it into the algorithm with the plaintext and check: does it produce the ciphertext you intercepted? If yes, you've found the key and can decrypt everything.
The problem is: how many keys are there to try?
NUMBER OF POSSIBLE KEYS:
════════════════════════
Key length Possible keys Time to try all (1 billion/sec)
────────── ───────────── ────────────────────────────────
3 bits 8 instant
56 bits 72 quadrillion ~833 days
128 bits 3.4 x 10^38 10^22 years (billions of times
the age of the universe)
256 bits 1.2 x 10^77 forget about itWith a 128-bit key, there are more possible keys than atoms in the observable universe. Even if you could test a billion keys per second, it would take trillions of times the age of the universe to try them all. That's why encryption works — not because the algorithm is secret, but because brute-forcing the key is physically impossible.
Or at least, it's impossible for a classical computer.
In 1996, Lov Grover discovered a quantum algorithm that speeds up brute-force search. Instead of trying keys one at a time (N/2 attempts on average), a quantum computer can find the key in about √N attempts.
GROVER'S SPEEDUP:
═════════════════
Key length Classical (N/2) Quantum (pi/4 x sqrt(N))
────────── ─────────────── ────────────────────────
3 bits 4 attempts 2 attempts
56 bits 36 quadrillion 211 million
128 bits 1.7 x 10^38 1.4 x 10^19
256 bits 5.8 x 10^76 2.7 x 10^38Look at the 128-bit row. Classical: 10³⁸ attempts (impossible). Quantum: 10¹⁹ attempts — that's the same order of magnitude as cracking a 64-bit key classically. Grover's algorithm effectively halves the key length. AES-128 becomes as hard to break as AES-64 would be for a classical computer.
This is why cryptography standards are already moving from AES-128 to AES-256 — to stay safe even when quantum computers arrive. If you use the internet, this affects you.
In this article, we'll build a complete quantum circuit that cracks a tiny cipher — a 3-bit key with just 8 possibilities. We use a small example so we can trace every gate, every matrix multiplication, every probability by hand. But the pattern is exactly the same one that would crack AES if you had a big enough quantum computer.
By the end of this article, you'll build the actual quantum circuit that cracks our 3-bit cipher — every gate, every matrix multiplication, every probability calculation. You'll run it on a simulator in a Colab notebook, and then on a real IBM quantum processor. Zero setup, zero cost.
We start from absolute zero. No quantum mechanics background. No physics degree. If you know what a vector is and can read Python, you have everything you need.
But how? How can 2 attempts find the right key among 8? Before we dive into the math, let's build intuition for the whole algorithm in plain language.
Before any equations, let's build intuition for how Grover's algorithm finds the key.
A classical computer tries keys one at a time — like inserting metal keys into a lock, one after another. A quantum computer does something fundamentally different. Think of it like pressing soft clay into the lock. The clay represents all 8 possible keys at once (superposition). Each time you turn the lock (one iteration of the algorithm), the clay deforms slightly — the correct shape gets reinforced, the wrong shapes get smoothed away. After a couple of turns, the clay has molded into the right key. You pull it out (measure), and you have the answer.
That's the core idea: a quantum computer doesn't try keys one at a time. It holds all keys simultaneously and reshapes the superposition so the correct key gradually dominates. But it can't just "read" the answer from the superposition — measurement gives a random key. The algorithm's job is to make the correct key overwhelmingly likely before you measure.
Let's see how this works step by step, using our 8 candidate keys (000 through 111).
The quantum computer starts by putting all 8 keys into equal superposition. Each key has the same amplitude — the same "weight" in the superposition. If you measured right now, you'd get a random key. Each has a 1-in-8 chance.
Think of 8 bars on a chart, all the same height. Each bar represents one candidate key. The height is the amplitude — it determines how likely that key is to be measured.
Now the oracle runs. The oracle is a circuit that checks: "does this key decrypt correctly?" It tests all 8 keys simultaneously (because they're in superposition) and marks the correct one by flipping its amplitude — from positive to negative. Same magnitude, opposite sign.
On the bar chart, one bar flips below the zero line. If you measured now, you'd still get a random key — the flip is invisible to measurement (probability depends on the square of the amplitude, and (-0.354)² = (0.354)²). But the sign difference is there, and it matters for what comes next.
Now comes the clever part. The diffusion step reflects every amplitude about the average of all amplitudes. Let's watch it happen:
Here's the math. After the oracle, seven bars have amplitude +0.354 and one bar (the correct key) has amplitude -0.354. The average of all 8 amplitudes is:
Average = (7 x 0.354 + 1 x (-0.354)) / 8
= (2.475 - 0.354) / 8
= 2.121 / 8
= 0.265
The average is BELOW the normal bars (pulled down by the flipped one)."Reflect about the average" means: whatever distance a bar is from the average, put it the same distance on the other side. The formula is: new value = 2 × average − old value.
REFLECTION ABOUT THE AVERAGE (0.265):
For a wrong key (amplitude = +0.354):
Distance above average: 0.354 - 0.265 = 0.089
Reflected: 0.265 - 0.089 = 0.177 (pushed DOWN toward average)
For the correct key (amplitude = -0.354):
Distance below average: 0.265 - (-0.354) = 0.619
Reflected: 0.265 + 0.619 = 0.884 (pushed WAY UP past average)
After diffusion:
Wrong keys: 0.177 → probability = 0.177^2 = 3.1% each
Correct key: 0.884 → probability = 0.884^2 = 78.1%That's the mechanism. The oracle pulled one bar negative, which dragged the average down. The reflection then flipped everything around that lowered average. The wrong keys, which were only slightly above the average, got reflected to slightly below — they shrank. The correct key, which was far below the average, got reflected to far above — it grew enormously.
This is interference in action. The correct key's inverted amplitude combined with the reflection to produce a much larger amplitude (constructive interference). The wrong keys' amplitudes combined with the reflection to produce smaller amplitudes (destructive interference). No magic — just a reflection that exploits the sign difference the oracle created.
After just one round of oracle + diffusion, the correct key has 78.1% probability.
You repeat steps 2 and 3 one more time. The correct key's amplitude grows further (to 0.972, or 94.5% probability), and the wrong keys shrink even more. Now you measure — and with 94.5% probability, you get the correct key: 101.
Two iterations. Two oracle calls. That's all it took to find the key among 8 candidates.
There's a cleaner way to see what's happening. Instead of tracking all 8 bars separately, we can compress the entire state into just two numbers: how much of the state points at the correct key, and how much points at everything else. This gives us a vector in a 2D plane.
In this plane, the horizontal axis is "wrong keys" and the vertical axis is "correct key." The initial equal superposition sits at a small angle θ₀ from the horizontal (because only 1 out of 8 keys is correct, so the state is mostly "wrong keys" with a tiny bit of "correct key").
Now here's the key: the oracle and diffusion are each a reflection in this plane, and the axes they reflect across are fixed — they never change between iterations.
Let's trace through one iteration step by step:
THE TWO FIXED REFLECTION AXES:
══════════════════════════════
Axis 1 (oracle): the horizontal axis ("wrong keys")
Axis 2 (diffusion): the |s⟩ direction (initial superposition, at angle θ₀)
These axes NEVER CHANGE. They are built into the circuits.
The angle between them is always θ₀.
ITERATION 1:
────────────
Start: state vector at angle +θ₀
Step A — Oracle (reflect across horizontal axis):
The oracle flips the "correct key" component (negates it).
In the 2D plane, this reflects the vector across the horizontal.
Angle goes from +θ₀ to -θ₀.
Step B — Diffusion (reflect across |s⟩ line at angle θ₀):
The diffusion operator reflects the vector across the |s⟩ direction.
To reflect angle -θ₀ across a line at angle θ₀:
reflected = 2 × θ₀ - (-θ₀) = 3θ₀
Angle goes from -θ₀ to +3θ₀.
Net effect: started at θ₀, ended at 3θ₀. Advanced by 2θ₀.Why is it always 2θ₀? Let's follow the numbers. The oracle reflects across the horizontal axis, taking the angle from +θ₀ to -θ₀. Then the diffusion reflects across the |s⟩ line at angle θ₀, taking -θ₀ to 3θ₀ (because reflecting a point at -θ₀ across a line at θ₀ puts it at 2×θ₀ - (-θ₀) = 3θ₀). The net movement: from θ₀ to 3θ₀ = an advance of 2θ₀. This works the same every iteration because both reflection axes are fixed — they're built into the circuits and never change.
The initial state starts at angle θ₀ from the horizontal. How big is θ₀? The initial superposition has amplitude 1/√N for each state, so the component pointing at the correct key is 1/√N. That means sin(θ₀) = 1/√N, so θ₀ = arcsin(1/√N). For N = 8: θ₀ = arcsin(1/√8) = arcsin(0.354) ≈ 20.7°.
Each iteration adds 2θ₀. After k iterations, the angle is (2k+1) × θ₀. We want to reach 90° (pointing straight at the correct key = 100% probability). For N = 8: 2 iterations get us to 5 × 20.7° ≈ 103° — close to 90°, giving 94.5% probability.
For large N, θ₀ is tiny. When angles are small, sin(θ) ≈ θ (in radians). So θ₀ ≈ 1/√N, each step adds 2/√N, and we need about (π/2) / (2/√N) = π√N/4 ≈ π/4 × √N iterations.
That's the whole algorithm: initialize, rotate toward the answer by repeated reflections, measure. Everything that follows is making this precise — what exactly are these "amplitudes," how do you flip one, and how does the interference work mathematically?
A classical bit is either 0 or 1. That's it. At any moment, you can look at it and it's definitively one or the other.
A qubit is different. A qubit is described by two numbers — called amplitudes — that tell you the "weight" of 0 and the "weight" of 1. We write it as a column vector:
CLASSICAL BIT:
Either 0 or 1. Nothing in between.
QUBIT:
A column vector with two entries:
[ alpha ] where alpha and beta are complex numbers
[ beta ] and |alpha|^2 + |beta|^2 = 1
alpha = amplitude of |0⟩
beta = amplitude of |1⟩The notation |ψ⟩ is called a "ket" — it's just a fancy way of writing a column vector. Physicists use it everywhere in quantum mechanics. |0⟩ and |1⟩ are the two basis states, corresponding to the classical 0 and 1.
Think of a qubit like a wave. A classical bit is either a crest (1) or a trough (0). A qubit is a wave that can be any combination of crest and trough — the amplitude tells you how much of each. The wave has a height (magnitude) and a direction (sign/phase). Both matter.
Let's be concrete. Here are some specific qubit states:
THE |0⟩ STATE (definitely 0):
[ 1 ] amplitude of 0: alpha = 1
[ 0 ] amplitude of 1: beta = 0
THE |1⟩ STATE (definitely 1):
[ 0 ] amplitude of 0: alpha = 0
[ 1 ] amplitude of 1: beta = 1
A SUPERPOSITION STATE (equal mix of 0 and 1):
[ 1/sqrt(2) ] = [ 0.707 ] amplitude of 0: alpha = 0.707
[ 1/sqrt(2) ] [ 0.707 ] amplitude of 1: beta = 0.707
Check: |alpha|^2 + |beta|^2 = 0.707^2 + 0.707^2 = 0.5 + 0.5 = 1 ✓Here's the crucial rule: when you measure a qubit, you get either 0 or 1 (never anything in between), and the probability of each outcome is the square of the amplitude's magnitude:
BORN RULE (the most important rule in quantum mechanics):
══════════════════════════════════════════════════════════
If the qubit state is:
[ alpha ]
[ beta ]
Then:
Probability of measuring 0 = |alpha|^2
Probability of measuring 1 = |beta|^2
And these must add to 1: |alpha|^2 + |beta|^2 = 1Let's apply this to our examples:
STATE |0⟩ = [1, 0]:
P(measure 0) = |1|² = 1 ← 100% chance of 0
P(measure 1) = |0|² = 0 ← 0% chance of 1
→ Always gives 0. This is a classical bit.
STATE |1⟩ = [0, 1]:
P(measure 0) = |0|² = 0 ← 0% chance of 0
P(measure 1) = |1|² = 1 ← 100% chance of 1
→ Always gives 1. Also a classical bit.
STATE |+⟩ = [1/√2, 1/√2]:
P(measure 0) = |1/√2|² = 1/2 ← 50% chance of 0
P(measure 1) = |1/√2|² = 1/2 ← 50% chance of 1
→ Perfectly random! Like a fair coin flip.
→ This is a SUPERPOSITION — the qubit has definite amplitudes
for both outcomes until measured.You might wonder: if we only ever measure 0 or 1, why bother with amplitudes? Why not just track probabilities directly?
The answer is interference. Think of sound waves. If two speakers play the same note in sync (both pushing air forward at the same time), the sound gets louder — the waves add up. This is constructive interference. If one speaker is exactly out of sync (one pushes while the other pulls), the sound cancels out — silence. This is destructive interference.
Amplitudes work the same way. They can be positive or negative (or complex). When two quantum paths lead to the same outcome, their amplitudes add. If one amplitude is +0.5 and another is -0.5, they cancel out — the probability becomes zero. This is destructive interference.
If we only tracked probabilities (which are always positive), we could never get cancellation. Probabilities only add up. Amplitudes can cancel.
WHY AMPLITUDES MATTER — INTERFERENCE:
═════════════════════════════════════
Probabilities: 0.25 + 0.25 = 0.50 (always adds up — no cancellation)
Amplitudes: +0.5 + (-0.5) = 0.0 (can cancel!)
Two waves in sync: /\/\ + /\/\ = /\/\/\/\ (louder)
Two waves out of sync: /\/\ + \/\/ = ———————— (silence)
Grover's algorithm works by making the amplitudes of WRONG answers
cancel out and the amplitude of the RIGHT answer grow larger.
This is impossible with classical probabilities.This is the single most important idea in quantum computing. Everything else — gates, circuits, algorithms — is just clever ways of arranging interference.
A quantum gate transforms a qubit's state into a new state. On paper, we represent this as matrix multiplication — multiply the gate's matrix by the qubit's state vector to get the new state vector. This is how we'll calculate and verify everything in this article.
But on a real quantum computer, there's no matrix multiplication happening. The qubit is a physical object — a superconducting circuit cooled near absolute zero, or a trapped ion held by electric fields. A gate is a physical operation applied to that object: a precisely timed microwave pulse, a laser beam at a specific frequency, or a voltage change lasting nanoseconds. The physics of that operation transforms the qubit's state in exactly the way the matrix describes. The matrix is our mathematical model of what the physics does — it gives us the right answer on paper, and the quantum hardware does the same thing in reality.
The only rule for a valid gate: the matrix must be unitary, meaning it preserves the total probability (|α|² + |β|² stays equal to 1). You can't have a gate that creates or destroys probability — that would be unphysical.
We need four gates to build Grover's algorithm. Here's a quick summary of each — read the detailed matrix math below each one, or skip ahead if you just want the big picture.
Flips |0⟩ to |1⟩ and |1⟩ to |0⟩. Like a light switch.
X|0⟩ = |1⟩
X|1⟩ = |0⟩→ Skip to Hadamard gate or read the matrix details below.
X GATE (also called Pauli-X):
═════════════════════════════
Matrix:
X = [ 0 1 ]
[ 1 0 ]
Apply to |0⟩:
[ 0 1 ] x [ 1 ] = [ 0*1 + 1*0 ] = [ 0 ] = |1⟩
[ 1 0 ] [ 0 ] [ 1*1 + 0*0 ] [ 1 ]
Apply to |1⟩:
[ 0 1 ] x [ 0 ] = [ 0*0 + 1*1 ] = [ 1 ] = |0⟩
[ 1 0 ] [ 1 ] [ 1*0 + 0*1 ] [ 0 ]
It swaps the amplitudes. |0⟩ becomes |1⟩, |1⟩ becomes |0⟩.Puts a definite state into equal superposition. Like a half-silvered mirror splitting a beam of light into two paths.
H|0⟩ = |+⟩ = [ +0.707, +0.707 ] (50/50, both positive)
H|1⟩ = |−⟩ = [ +0.707, -0.707 ] (50/50, one negative)H is its own inverse: HH = I (apply twice, get back to start).
→ Skip to Z gate or read the matrix details below.
HADAMARD GATE:
══════════════
Matrix:
H = 1 [ 1 1 ] = [ 0.707 0.707 ]
------ [ 1 -1 ] [ 0.707 -0.707 ]
sqrt(2)
Apply to |0⟩:
1/sqrt(2) x [ 1 1 ] x [ 1 ]
[ 1 -1 ] [ 0 ]
= 1/sqrt(2) x [ 1*1 + 1*0 ] = 1/sqrt(2) x [ 1 ] = [ 0.707 ]
[ 1*1 +(-1)*0 ] [ 1 ] [ 0.707 ]
= |+⟩ (equal superposition, both amplitudes positive)
Apply to |1⟩:
1/sqrt(2) x [ 1 1 ] x [ 0 ]
[ 1 -1 ] [ 1 ]
= 1/sqrt(2) x [ 1*0 + 1*1 ] = 1/sqrt(2) x [ 1 ] = [ 0.707 ]
[ 1*0 +(-1)*1 ] [ -1 ] [ -0.707 ]
= |−⟩ (equal superposition, but NEGATIVE amplitude for |1⟩)H|0⟩ and H|1⟩ both give 50/50 superpositions, but with different signs. The probabilities are identical — both give 50% chance of 0 and 50% chance of 1. But the amplitudes are different, and that difference matters for interference.
Leaves |0⟩ alone, flips the sign of |1⟩. Like inverting a sound wave — same loudness, opposite direction. Invisible on its own, but changes how the qubit interferes with others.
Z|0⟩ = |0⟩ (unchanged)
Z|1⟩ = -|1⟩ (sign flipped)→ Skip to CNOT gate or read the matrix details below.
Z GATE (Pauli-Z):
═════════════════
Matrix:
Z = [ 1 0 ]
[ 0 -1 ]
Apply to |0⟩:
[ 1 0 ] x [ 1 ] = [ 1 ] = |0⟩ (unchanged)
[ 0 -1 ] [ 0 ] [ 0 ]
Apply to |1⟩:
[ 1 0 ] x [ 0 ] = [ 0 ] = -|1⟩ (sign flipped!)
[ 0 -1 ] [ 1 ] [ -1 ]
Apply to |+⟩ = [0.707, 0.707]:
[ 1 0 ] x [ 0.707 ] = [ 0.707 ] = |−⟩
[ 0 -1 ] [ 0.707 ] [ -0.707 ]The Z gate doesn't change any probabilities. It only changes the sign (phase) of the |1⟩ amplitude. Phase flips are the key mechanism behind Grover's oracle.
A 2-qubit gate. Flips the second qubit (target) only when the first qubit (control) is |1⟩. This is the quantum version of XOR — exactly what we need to build our cipher verifier.
CNOT|00⟩ = |00⟩ (control=0, target unchanged)
CNOT|01⟩ = |01⟩ (control=0, target unchanged)
CNOT|10⟩ = |11⟩ (control=1, target FLIPPED: 0→1)
CNOT|11⟩ = |10⟩ (control=1, target FLIPPED: 1→0)The target qubit becomes: target XOR control.
→ Skip to Toffoli gate or read the matrix details below.
CNOT (Controlled-NOT):
══════════════════════
Matrix (4x4, acts on 2 qubits):
CNOT = [ 1 0 0 0 ]
[ 0 1 0 0 ]
[ 0 0 0 1 ]
[ 0 0 1 0 ]
The rows/columns correspond to |00⟩, |01⟩, |10⟩, |11⟩.
Apply to |10⟩ (control=1, target=0):
[ 1 0 0 0 ] x [ 0 ] = [ 0 ]
[ 0 1 0 0 ] [ 0 ] [ 0 ] = |11⟩ (target flipped!)
[ 0 0 0 1 ] [ 1 ] [ 0 ]
[ 0 0 1 0 ] [ 0 ] [ 1 ]
Apply to |00⟩ (control=0, target=0):
[ 1 0 0 0 ] x [ 1 ] = [ 1 ]
[ 0 1 0 0 ] [ 0 ] [ 0 ] = |00⟩ (unchanged)
[ 0 0 0 1 ] [ 0 ] [ 0 ]
[ 0 0 1 0 ] [ 0 ] [ 0 ]Why is CNOT = XOR? Look at the target qubit's output:
Input Output Target out = control XOR target
|00⟩ → |00⟩ 0 XOR 0 = 0 ✓
|01⟩ → |01⟩ 0 XOR 1 = 1 ✓
|10⟩ → |11⟩ 1 XOR 0 = 1 ✓
|11⟩ → |10⟩ 1 XOR 1 = 0 ✓The target qubit always ends up as control XOR target. This is how we'll implement the XOR encryption check in our oracle.
A 3-qubit gate. Flips the third qubit (target) only when BOTH the first and second qubits (controls) are |1⟩. It's the quantum AND gate.
Toffoli|110⟩ = |111⟩ (both controls=1, target FLIPPED)
Toffoli|111⟩ = |110⟩ (both controls=1, target FLIPPED)
Toffoli|100⟩ = |100⟩ (only one control=1, nothing happens)
Toffoli|010⟩ = |010⟩ (only one control=1, nothing happens)Rule: target flips if and only if control₁ AND control₂ are both |1⟩.
TOFFOLI GATE (CCX):
═══════════════════
3 qubits: control_1, control_2, target
Matrix (8x8, acts on 3 qubits):
Rows/columns correspond to |000⟩,|001⟩,|010⟩,|011⟩,|100⟩,|101⟩,|110⟩,|111⟩
CCX = [ 1 0 0 0 0 0 0 0 ]
[ 0 1 0 0 0 0 0 0 ]
[ 0 0 1 0 0 0 0 0 ]
[ 0 0 0 1 0 0 0 0 ]
[ 0 0 0 0 1 0 0 0 ]
[ 0 0 0 0 0 1 0 0 ]
[ 0 0 0 0 0 0 0 1 ] ← |110⟩ and |111⟩ swapped
[ 0 0 0 0 0 0 1 0 ]
It's the identity matrix except the last two rows/columns are
swapped. This swaps |110⟩ ↔ |111⟩ (flips the target when both
controls are 1) and leaves everything else unchanged.
|110⟩ → |111⟩ (both controls=1, target flips: 0→1)
|111⟩ → |110⟩ (both controls=1, target flips: 1→0)
|100⟩ → |100⟩ (control_2=0, nothing happens)
|010⟩ → |010⟩ (control_1=0, nothing happens)
all others → unchanged
It's the quantum version of a classical AND gate:
target_new = target XOR (control_1 AND control_2)This is one of the most important tricks in quantum computing. We'll use it to build the oracle, so it's worth understanding deeply.
The problem: gates like CNOT and Toffoli flip bits (|0⟩ ↔ |1⟩). But for Grover's oracle, we need to flip the phase (multiply by -1) without changing any bits. How do we convert a bit flip into a phase flip?
The trick: put the target qubit into the |−⟩ state using H before the controlled gate, then undo it with H after. Here's why this works:
PHASE KICKBACK — STEP BY STEP:
══════════════════════════════
Recall: H|1⟩ = |−⟩ = 1/sqrt(2) x (|0⟩ - |1⟩)
H|0⟩ = |+⟩ = 1/sqrt(2) x (|0⟩ + |1⟩)
What happens when X (bit flip) hits |−⟩?
X|−⟩ = X x 1/sqrt(2) x (|0⟩ - |1⟩)
= 1/sqrt(2) x (X|0⟩ - X|1⟩) ← X acts on each term
= 1/sqrt(2) x (|1⟩ - |0⟩) ← X swaps 0 and 1
= 1/sqrt(2) x (-(|0⟩ - |1⟩)) ← rewrite: a-b = -(b-a)
= -1 x 1/sqrt(2) x (|0⟩ - |1⟩)
= -|−⟩
The state is still |−⟩, but it picked up a factor of -1.
The bit flip became a PHASE flip!
What about X on |+⟩?
X|+⟩ = 1/sqrt(2) x (|1⟩ + |0⟩)
= 1/sqrt(2) x (|0⟩ + |1⟩) ← a+b = b+a
= |+⟩
No phase change. The + sign makes it symmetric under swapping.Now the key insight for controlled gates. If we use CNOT with the target in |−⟩:
CNOT WITH TARGET IN |−⟩:
════════════════════════
Control = |1⟩, target = |−⟩:
CNOT flips the target (because control is 1).
Target: X|−⟩ = -|−⟩
Result: -|1⟩|−⟩ ← the -1 "kicked back" to the control!
Control = |0⟩, target = |−⟩:
CNOT does nothing (because control is 0).
Target stays |−⟩.
Result: |0⟩|−⟩ ← no phase change.
The target qubit stays |−⟩ in both cases.
The phase flip appears on the CONTROL qubit.
Control |1⟩ gets a -1. Control |0⟩ doesn't.The same works for Toffoli: if both controls are |1⟩ and the target is in |−⟩, the phase flips. If either control is |0⟩, nothing happens. The target stays |−⟩ either way.
The full pattern: H (put target in |−⟩) → controlled gate → H (put target back). This converts any controlled bit-flip into a controlled phase-flip. We'll use this in section 1.6 to build the oracle.
One qubit can represent 2 states (|0⟩ and |1⟩). To search among N items, we need enough qubits to represent N different states. With n qubits, we can represent 2ⁿ states. For N = 8 items, we need n = 3 qubits (since 2³ = 8).
The state of a multi-qubit system is described by the tensor product (also called Kronecker product) of the individual qubit states. Don't let the name intimidate you — it's just a specific way of combining two vectors into a larger one.
TENSOR PRODUCT OF TWO VECTORS:
══════════════════════════════
Given two vectors:
|a> = [ a0 ] |b> = [ b0 ]
[ a1 ] [ b1 ]
Their tensor product is:
[ a0 * b0 ] = [ a0*b0 ]
[ a0 * b1 ] [ a0*b1 ]
[ a1 * b0 ] [ a1*b0 ]
[ a1 * b1 ] [ a1*b1 ]
Each element of the first vector multiplies the ENTIRE second vector.
Result: a vector of length 4 (= 2 x 2).Let's build this up step by step. First, two qubits both in state |0⟩:
TWO QUBITS, BOTH |0>:
═════════════════════
[ 1 ] x [ 1 ]
[ 0 ] [ 0 ]
Step by step:
First element is 1. Multiply entire second vector by 1:
1 x [ 1 ] = [ 1 ]
[ 0 ] [ 0 ]
Second element is 0. Multiply entire second vector by 0:
0 x [ 1 ] = [ 0 ]
[ 0 ] [ 0 ]
Stack them: [ 1 ] = amplitude of |00>
[ 0 ] = amplitude of |01>
[ 0 ] = amplitude of |10>
[ 0 ] = amplitude of |11>
Only |00> has amplitude 1 — the system is definitely in state 00.Now let's do something more interesting — two qubits both in superposition:
TWO QUBITS, BOTH IN SUPERPOSITION:
═══════════════════════════════════
[ 1/sqrt(2) ] x [ 1/sqrt(2) ]
[ 1/sqrt(2) ] [ 1/sqrt(2) ]
= [ 0.707 ] x [ 0.707 ]
[ 0.707 ] [ 0.707 ]
Step by step:
First element (0.707) x second vector:
0.707 x [ 0.707 ] = [ 0.5 ]
[ 0.707 ] [ 0.5 ]
Second element (0.707) x second vector:
0.707 x [ 0.707 ] = [ 0.5 ]
[ 0.707 ] [ 0.5 ]
Stack them: [ 0.5 ] = amplitude of |00>, probability = 0.5^2 = 0.25
[ 0.5 ] = amplitude of |01>, probability = 0.25
[ 0.5 ] = amplitude of |10>, probability = 0.25
[ 0.5 ] = amplitude of |11>, probability = 0.25
All 4 states equally likely! Each has probability 1/4 = 25%.Why does this give equal probabilities? Each qubit independently has a 50/50 chance of being 0 or 1. Two independent 50/50 choices give 4 equally likely outcomes — just like flipping 2 fair coins. Each of the 4 outcomes (HH, HT, TH, TT) has probability 1/4.
For Grover's algorithm on 8 items, we need 3 qubits. The state vector has 2³ = 8 entries, one for each possible 3-bit string:
3-QUBIT STATE VECTOR:
═════════════════════
[ a_000 ] = amplitude of |000⟩ (binary for 0)
[ a_001 ] = amplitude of |001⟩ (binary for 1)
[ a_010 ] = amplitude of |010⟩ (binary for 2)
[ a_011 ] = amplitude of |011⟩ (binary for 3)
[ a_100 ] = amplitude of |100⟩ (binary for 4)
[ a_101 ] = amplitude of |101⟩ (binary for 5)
[ a_110 ] = amplitude of |110⟩ (binary for 6)
[ a_111 ] = amplitude of |111⟩ (binary for 7)
Each entry is the amplitude for one of the 8 possible states.
The probability of measuring state |xyz⟩ is |α_xyz|².
All probabilities must sum to 1.Grover's algorithm starts by putting all 3 qubits into equal superposition using Hadamard gates. Apply H to each qubit individually:
CREATING EQUAL SUPERPOSITION (3 qubits):
═════════════════════════════════════════
Start: |000⟩ = |0⟩ ⊗ |0⟩ ⊗ |0⟩
Apply H to each qubit:
H|0⟩ = 1/√2 × [1, 1] (for each qubit)
Combined state (extending the 2-qubit pattern to 3):
H|0⟩ ⊗ H|0⟩ ⊗ H|0⟩
= 1/√2 × [1, 1] ⊗ 1/√2 × [1, 1] ⊗ 1/√2 × [1, 1]
Each qubit independently has 50/50 chance of 0 or 1.
Three independent 50/50 choices = 8 equally likely outcomes.
Like flipping 3 fair coins — each of the 8 outcomes
(HHH, HHT, HTH, HTT, THH, THT, TTH, TTT) has probability 1/8.
= 1/√8 × [1, 1, 1, 1, 1, 1, 1, 1]
Every amplitude is 1/√8 ≈ 0.354.
Every state has probability |1/√8|² = 1/8 = 12.5%.
All 8 states are equally likely.This is the starting point of Grover's algorithm: a uniform superposition where every possible answer has the same amplitude. The algorithm's job is to increase the amplitude of the correct answer and decrease the amplitudes of the wrong ones.
Now we build the heart of Grover's algorithm — the oracle. This is a real quantum circuit that takes the superposition of all 8 candidate keys as input and flips the phase of the correct one. It doesn't check keys one at a time — it processes the entire superposition in a single pass.
Let's build it step by step, showing exactly how the circuit operates on the state vector.
Our cipher: ciphertext = plaintext XOR key. We know plaintext = 011 and ciphertext = 110. The verifier circuit needs to:
plaintext XOR key — the 3 qubits in superposition represent all 8 keys at once, so the circuit processes all of them in a single pass, not one at a timeThe crucial point: this circuit operates on 3 physical qubits, not 8 separate keys. The superposition means those 3 qubits encode all 8 possible keys at once. Every gate acts on the 3 qubits, and the physics naturally processes all 8 key components in a single pass. We use the 8-element vector on paper to track what's happening, but the hardware is just manipulating 3 qubits.
The verifier needs to compute plaintext XOR key. The key qubits hold the candidate key (in superposition). But where does the result go? We can't overwrite the key qubits — we need them intact. So we add 3 extra qubits called ancilla qubits (from the Latin "ancilla" = helper). They start at |000⟩ and will hold the XOR result.
OUR QUBITS:
═══════════
Key qubits: k2, k1, k0 (in superposition of all 8 keys)
Ancilla qubits: a2, a1, a0 (start at |0⟩, will hold the XOR result)
Total: 6 qubits. The key register is the "input" we're searching over.
The ancilla register is scratch space for the computation.Now, how do we compute XOR? Recall from section 1.4.4 that CNOT does this: it takes two qubits and replaces the target with target XOR control. If the target starts at |0⟩, then after CNOT the target simply equals the control. That's how we copy a value.
But we don't just want to copy the key — we want plaintext XOR key. The plaintext is 011, a fixed classical value we know. Here's the trick: we first set each ancilla qubit to the corresponding plaintext bit, then XOR it with the key bit using CNOT.
Let's go bit by bit:
BIT 0 (rightmost): plaintext bit = 1, key bit = k0
──────────────────────────────────────────────────────
Start: a0 = |0⟩
Step A: Apply X gate to a0.
X flips |0⟩ to |1⟩. Now a0 = |1⟩.
We've "loaded" the plaintext bit (1) into the ancilla.
Step B: Apply CNOT with k0 as control, a0 as target.
CNOT replaces a0 with: (a0 XOR k0) = (1 XOR k0).
That's exactly (plaintext_bit0 XOR key_bit0). ✓
BIT 1 (middle): plaintext bit = 1, key bit = k1
──────────────────────────────────────────────────
Start: a1 = |0⟩
Step A: Apply X to a1. Now a1 = |1⟩. (plaintext bit loaded)
Step B: Apply CNOT(k1 → a1). Now a1 = (1 XOR k1). ✓
BIT 2 (leftmost): plaintext bit = 0, key bit = k2
────────────────────────────────────────────────────
Start: a2 = |0⟩
Step A: Plaintext bit is 0, so we DON'T apply X. a2 stays |0⟩.
Step B: Apply CNOT(k2 → a2). Now a2 = (0 XOR k2) = k2. ✓
SUMMARY: After these 5 gates (2 X gates + 3 CNOTs):
a0 = (1 XOR k0) }
a1 = (1 XOR k1) } = plaintext XOR key
a2 = (0 XOR k2) }The key point: this circuit runs on the superposition of all 8 keys. Each CNOT processes all 8 key values simultaneously. After the circuit, each key in the superposition has been paired with its own XOR result in the ancilla. The 6-qubit state now looks like this:
STATE AFTER XOR COMPUTATION (6 qubits: 3 key + 3 ancilla):
═══════════════════════════════════════════════════════════
The system is in a superposition of 8 terms. Each term has
two parts: the key qubits (unchanged) and the ancilla qubits
(now holding plaintext XOR that key).
Key qubits Ancilla qubits Match ciphertext 110?
(candidate) (= 011 XOR key)
────────── ────────────── ────────────────────
|000⟩ |011⟩ (011 XOR 000) No
|001⟩ |010⟩ (011 XOR 001) No
|010⟩ |001⟩ (011 XOR 010) No
|011⟩ |000⟩ (011 XOR 011) No
|100⟩ |111⟩ (011 XOR 100) No
|101⟩ |110⟩ (011 XOR 101) YES ← ancilla = ciphertext!
|110⟩ |101⟩ (011 XOR 110) No
|111⟩ |100⟩ (011 XOR 111) No
All 8 terms exist simultaneously in superposition, each with
amplitude 1/sqrt(8). The key qubits haven't changed — they still
hold the candidate key. The ancilla qubits now hold the encryption
result for that candidate.
Only one row has ancilla = |110⟩ (the ciphertext): key = |101⟩.
That's the correct key. The next step will flip its phase.Now we need to flip the phase of the term where the ancilla equals the ciphertext (110). We'll use phase kickback (section 1.4.6) — but this time, let's trace what happens to every term in the superposition at each gate, so there's no hand-waving.
The plan: convert the ciphertext pattern 110 to all-ones (using X on the 0-bits), then use Toffoli + phase kickback to flip the phase when all ancilla bits are 1, then undo the conversion.
Let's trace all 8 terms through each gate. We'll focus on the ancilla qubits (a2, a1, a0) since the key qubits don't change in this phase. Remember: every gate acts on ALL 8 terms simultaneously.
STARTING STATE (ancilla qubits only, one row per superposition term):
════════════════════════════════════════════════════════════════════
Key Ancilla (= 011 XOR key) Amplitude
───── ─────────────────────── ─────────
|000⟩ a2=0, a1=1, a0=1 +1/sqrt(8)
|001⟩ a2=0, a1=1, a0=0 +1/sqrt(8)
|010⟩ a2=0, a1=0, a0=1 +1/sqrt(8)
|011⟩ a2=0, a1=0, a0=0 +1/sqrt(8)
|100⟩ a2=1, a1=1, a0=1 +1/sqrt(8)
|101⟩ a2=1, a1=1, a0=0 +1/sqrt(8) ← ancilla = 110 (ciphertext)
|110⟩ a2=1, a1=0, a0=1 +1/sqrt(8)
|111⟩ a2=1, a1=0, a0=0 +1/sqrt(8)GATE 1: X on a0 (flip a0 in every term)
═══════════════════════════════════════
Purpose: ciphertext bit 0 is 0, so we flip a0 to convert 110 → 111.
Key Ancilla BEFORE a0 flipped Ancilla AFTER
───── ────────────── ────────── ─────────────
|000⟩ a2=0,a1=1,a0=1 1→0 a2=0,a1=1,a0=0
|001⟩ a2=0,a1=1,a0=0 0→1 a2=0,a1=1,a0=1
|010⟩ a2=0,a1=0,a0=1 1→0 a2=0,a1=0,a0=0
|011⟩ a2=0,a1=0,a0=0 0→1 a2=0,a1=0,a0=1
|100⟩ a2=1,a1=1,a0=1 1→0 a2=1,a1=1,a0=0
|101⟩ a2=1,a1=1,a0=0 0→1 a2=1,a1=1,a0=1 ← now ALL ones!
|110⟩ a2=1,a1=0,a0=1 1→0 a2=1,a1=0,a0=0
|111⟩ a2=1,a1=0,a0=0 0→1 a2=1,a1=0,a0=1
Only the |101⟩ term now has ancilla = 111 (all ones).GATE 2: H on a0 (in every term)
═══════════════════════════════
Purpose: prepare a0 for phase kickback.
H turns a0=|1⟩ into |−⟩ = (|0⟩-|1⟩)/sqrt(2)
H turns a0=|0⟩ into |+⟩ = (|0⟩+|1⟩)/sqrt(2)
Key a0 before H a0 after H
───── ─────────── ──────────
|000⟩ 0 |+⟩
|001⟩ 1 |−⟩
|010⟩ 0 |+⟩
|011⟩ 1 |−⟩
|100⟩ 0 |+⟩
|101⟩ 1 |−⟩ ← this is the one that matters
|110⟩ 0 |+⟩
|111⟩ 1 |−⟩
Several terms have a0 in |−⟩. But the Toffoli in the next step
only fires when a2=1 AND a1=1 — that narrows it down.GATE 3: Toffoli(a2, a1 → a0)
════════════════════════════
Flips a0 ONLY when a2=1 AND a1=1.
Key a2 a1 Both=1? a0 state Toffoli flips a0? Phase?
───── ── ── ─────── ──────── ───────────────── ──────
|000⟩ 0 1 No |+⟩ No none
|001⟩ 0 1 No |−⟩ No none
|010⟩ 0 0 No |+⟩ No none
|011⟩ 0 0 No |−⟩ No none
|100⟩ 1 1 YES |+⟩ Yes: X|+⟩ = |+⟩ none
|101⟩ 1 1 YES |−⟩ Yes: X|−⟩ = -|−⟩ -1 !!
|110⟩ 1 0 No |+⟩ No none
|111⟩ 1 0 No |−⟩ No none
Two terms have a2=a1=1: keys |100⟩ and |101⟩.
|100⟩: a0 is in |+⟩. X|+⟩ = |+⟩. No phase change.
|101⟩: a0 is in |−⟩. X|−⟩ = -|−⟩. PHASE FLIP! The -1 kicks back.
This is the moment: only key |101⟩ picks up a -1 factor.
Its amplitude changes from +1/sqrt(8) to -1/sqrt(8).GATE 4: H on a0 (undo gate 2)
═════════════════════════════
H turns |−⟩ back to |1⟩, and |+⟩ back to |0⟩ (since H*H = I).
Key a0 after Toffoli Phase H(a0) a0 result
───── ──────────────── ───── ───── ─────────
|000⟩ |+⟩ +1 H|+⟩ |0⟩
|001⟩ |−⟩ +1 H|−⟩ |1⟩
|010⟩ |+⟩ +1 H|+⟩ |0⟩
|011⟩ |−⟩ +1 H|−⟩ |1⟩
|100⟩ |+⟩ +1 H|+⟩ |0⟩
|101⟩ -|−⟩ -1 -H|−⟩ -|1⟩ ← the -1 stays!
|110⟩ |+⟩ +1 H|+⟩ |0⟩
|111⟩ |−⟩ +1 H|−⟩ |1⟩
The -1 on |101⟩ survives the H gate. H converts |−⟩ back to |1⟩,
but the -1 factor is on the amplitude of the whole term, not on
the qubit state. H doesn't touch it.GATE 5: X on a0 (undo gate 1)
═════════════════════════════
X flips a0 back: |0⟩→|1⟩ and |1⟩→|0⟩.
Key a0 before X X(a0) Ancilla restored Amplitude
───── ─────────── ───── ──────────────── ─────────
|000⟩ 0 1 a2=0,a1=1,a0=1 +1/sqrt(8)
|001⟩ 1 0 a2=0,a1=1,a0=0 +1/sqrt(8)
|010⟩ 0 1 a2=0,a1=0,a0=1 +1/sqrt(8)
|011⟩ 1 0 a2=0,a1=0,a0=0 +1/sqrt(8)
|100⟩ 0 1 a2=1,a1=1,a0=1 +1/sqrt(8)
|101⟩ 1 0 a2=1,a1=1,a0=0 -1/sqrt(8) ← phase kept!
|110⟩ 0 1 a2=1,a1=0,a0=1 +1/sqrt(8)
|111⟩ 1 0 a2=1,a1=0,a0=0 +1/sqrt(8)
The ancilla qubits are back to exactly where they were before gate 1.
The ONLY change across all 5 gates: key |101⟩ has amplitude -1/sqrt(8)
instead of +1/sqrt(8). Everything else is identical.After the phase flip, we need to reset the ancilla qubits back to |000⟩. Why? Because the ancilla is currently entangled with the key qubits — each key is paired with a different ancilla value. If we leave it like this, the diffusion step (which only operates on the key qubits) won't produce the right interference.
The fix: run the XOR circuit from step 1 backwards. Since CNOT and X are each their own inverse (applying the same gate twice undoes it), we just apply the same gates in reverse order.
Let's trace it. After gates 1-5 (the phase flip), the ancilla is back to the post-XOR state (same as the table at the end of section 1.6.2, but now |101⟩ has amplitude -1/√8):
STATE ENTERING UNCOMPUTATION:
═════════════════════════════
Key Ancilla (= 011 XOR key) Amplitude
───── ─────────────────────── ─────────
|000⟩ a2=0, a1=1, a0=1 +1/sqrt(8)
|001⟩ a2=0, a1=1, a0=0 +1/sqrt(8)
|010⟩ a2=0, a1=0, a0=1 +1/sqrt(8)
|011⟩ a2=0, a1=0, a0=0 +1/sqrt(8)
|100⟩ a2=1, a1=1, a0=1 +1/sqrt(8)
|101⟩ a2=1, a1=1, a0=0 -1/sqrt(8) ← phase flipped
|110⟩ a2=1, a1=0, a0=1 +1/sqrt(8)
|111⟩ a2=1, a1=0, a0=0 +1/sqrt(8)UNCOMPUTE GATE 1: CNOT(k2 → a2) — undo the XOR on bit 2
════════════════════════════════════════════════════════
CNOT replaces a2 with: a2 XOR k2.
Currently a2 = 0 XOR k2 = k2. After CNOT: a2 = k2 XOR k2 = 0.
Key k2 a2 before a2 XOR k2 a2 after
───── ── ───────── ───────── ────────
|000⟩ 0 0 0 XOR 0 0
|001⟩ 0 0 0 XOR 0 0
|010⟩ 0 0 0 XOR 0 0
|011⟩ 0 0 0 XOR 0 0
|100⟩ 1 1 1 XOR 1 0
|101⟩ 1 1 1 XOR 1 0
|110⟩ 1 1 1 XOR 1 0
|111⟩ 1 1 1 XOR 1 0
a2 = 0 for all terms. ✓UNCOMPUTE GATE 2: CNOT(k1 → a1) — undo the XOR on bit 1
════════════════════════════════════════════════════════
Currently a1 = 1 XOR k1. After CNOT: a1 = (1 XOR k1) XOR k1 = 1.
Key k1 a1 before a1 XOR k1 a1 after
───── ── ───────── ───────── ────────
|000⟩ 0 1 1 XOR 0 1
|001⟩ 0 1 1 XOR 0 1
|010⟩ 1 0 0 XOR 1 1
|011⟩ 1 0 0 XOR 1 1
|100⟩ 0 1 1 XOR 0 1
|101⟩ 0 1 1 XOR 0 1
|110⟩ 1 0 0 XOR 1 1
|111⟩ 1 0 0 XOR 1 1
a1 = 1 for all terms. (Not 0 yet — we still need to undo the X gate.)UNCOMPUTE GATE 3: CNOT(k0 → a0) — undo the XOR on bit 0
════════════════════════════════════════════════════════
Currently a0 = 1 XOR k0. After CNOT: a0 = (1 XOR k0) XOR k0 = 1.
a0 = 1 for all terms. (Same as a1 — need to undo the X gate next.)UNCOMPUTE GATES 4-5: X(a1), X(a0) — undo the plaintext loading
═══════════════════════════════════════════════════════════════
X flips a1 from 1 to 0. X flips a0 from 1 to 0.
Key a2 a1 before X a1 after X a0 before X a0 after X Amplitude
───── ── ─────────── ────────── ─────────── ────────── ─────────
|000⟩ 0 1 0 1 0 +1/sqrt(8)
|001⟩ 0 1 0 1 0 +1/sqrt(8)
|010⟩ 0 1 0 1 0 +1/sqrt(8)
|011⟩ 0 1 0 1 0 +1/sqrt(8)
|100⟩ 0 1 0 1 0 +1/sqrt(8)
|101⟩ 0 1 0 1 0 -1/sqrt(8) ← phase kept!
|110⟩ 0 1 0 1 0 +1/sqrt(8)
|111⟩ 0 1 0 1 0 +1/sqrt(8)
ALL ancilla qubits are now |000⟩ for every term. ✓
The ancilla is completely clean — no longer entangled with the key.
The ONLY trace of the oracle: key |101⟩ has amplitude -1/sqrt(8).THE COMPLETE VERIFIER CIRCUIT:
══════════════════════════════
Key qubits: k2, k1, k0 (in superposition)
Ancilla qubits: a2, a1, a0 (start and end at |000⟩)
Plaintext = 011, Ciphertext = 110
STEP 1 — Compute XOR (plaintext XOR key → ancilla):
X(a0), X(a1) ← load plaintext bits
CNOT(k0→a0), CNOT(k1→a1), CNOT(k2→a2) ← XOR with key
STEP 2 — Check match and flip phase (ancilla = 110?):
X(a0) ← convert 110 to 111
H(a0) ← prepare kickback
Toffoli(a2, a1 → a0) ← phase flip if all ones
H(a0) ← undo H
X(a0) ← undo X
STEP 3 — Uncompute XOR (reset ancilla to |000⟩):
CNOT(k2→a2), CNOT(k1→a1), CNOT(k0→a0) ← undo XOR
X(a1), X(a0) ← undo plaintext loading
RESULT:
Key qubits: unchanged except |101⟩ has amplitude x (-1)
Ancilla qubits: back to |000⟩ (clean, unentangled)This is the real oracle — a single circuit that processes the entire superposition. Every gate acts on all 8 terms simultaneously. The XOR computation, the comparison, and the phase flip all happen in parallel across all candidate keys. Only the key where the XOR result matches the ciphertext picks up the -1 phase.
The diffusion operator is where the interference happens. After the oracle flips the sign of the correct key, the diffusion operator "reflects" all amplitudes about their average. This boosts the correct key's amplitude (which was negative) and shrinks all the others.
Let's work through it step by step with actual numbers.
The diffusion operator takes each amplitude and reflects it about the average of all amplitudes. If an amplitude is below the average, it gets pushed above. If it's above the average, it gets pushed below. The formula is:
REFLECTION ABOUT THE MEAN:
══════════════════════════
For each amplitude aᵢ:
new_aᵢ = 2 × (average of all amplitudes) - aᵢ
Or equivalently:
new_aᵢ = aᵢ + 2 × (average - aᵢ)Let's apply this to our state after the oracle (correct key = |101⟩):
AFTER ORACLE:
Amplitudes: [+1/√8, +1/√8, +1/√8, +1/√8, +1/√8, -1/√8, +1/√8, +1/√8]
In decimals: [+0.354, +0.354, +0.354, +0.354, +0.354, -0.354, +0.354, +0.354]
STEP 1: Compute the average of all amplitudes:
Sum = 7 × (1/√8) + 1 × (-1/√8) = 6/√8
Average = 6/√8 ÷ 8 = 6/(8√8) = 3/(4√8) ≈ 0.265
STEP 2: Reflect each amplitude about the average:
For wrong keys (amplitude = +0.354):
new = 2 × 0.265 - 0.354 = 0.530 - 0.354 = 0.177
For correct key (amplitude = -0.354):
new = 2 × 0.265 - (-0.354) = 0.530 + 0.354 = 0.884
AFTER DIFFUSION:
Amplitudes: [0.177, 0.177, 0.177, 0.177, 0.177, 0.884, 0.177, 0.177]
↑
correct key boosted!
PROBABILITIES:
Unmarked: |0.177|² = 0.031 = 3.1% each (was 12.5%)
Marked: |0.884|² = 0.781 = 78.1% (was 12.5%)
Total: 7 × 0.031 + 0.781 = 0.220 + 0.781 ≈ 1.0 ✓After just one round of oracle + diffusion, the correct key went from 12.5% probability to 78.1%.
The key insight is that the oracle made the correct key's amplitude negative while all others stayed positive. This pulled the average down. When we reflect about this lowered average:
In wave terms: the oracle inverted one wave. The diffusion step makes all waves interact. The inverted wave interferes constructively with the reflection, getting amplified. The non-inverted waves interfere destructively, getting diminished. This is exactly the constructive/destructive interference we described in section 1.2.
Instead of starting with a matrix formula, let's build the diffusion circuit directly and trace our actual post-oracle state through each gate. The circuit has 7 steps, using only H, X, and Toffoli — the same gates as the oracle.
The diffusion circuit has 7 steps. Before we trace each one, here's the overview so you know where we're headed:
DIFFUSION CIRCUIT OVERVIEW (7 steps):
═════════════════════════════════════
Step 1: H on all qubits (convert to computational basis)
Step 2: X on all qubits (flip all bits)
Step 3: H on q0 (prepare for phase kickback)
Step 4: Toffoli(q2,q1→q0) (phase flip via kickback)
Step 5: H on q0 (undo step 3)
Step 6: X on all qubits (undo step 2)
Step 7: H on all qubits (convert back)
Steps 1 and 7 change the "basis" (the frame of reference).
Steps 2-6 flip the phase of one specific state in that basis.
The net effect: reflect all amplitudes about their mean.Our starting state (after the oracle flipped the correct key's phase):
POST-ORACLE STATE (input to diffusion):
═══════════════════════════════════════
Key: |000⟩ |001⟩ |010⟩ |011⟩ |100⟩ |101⟩ |110⟩ |111⟩
Amplitude: +0.354 +0.354 +0.354 +0.354 +0.354 -0.354 +0.354 +0.354STEP 1: Apply H to each qubit (q0, q1, q2)
══════════════════════════════════════════
H acts on each qubit independently. When H acts on one qubit
of a multi-qubit state, it transforms each pair of amplitudes
that differ only in that qubit's value. For a pair with
amplitudes (a, b) where a is the q=0 amplitude and b is the
q=1 amplitude:
After H: q=0 gets (a+b)/sqrt(2), q=1 gets (a-b)/sqrt(2)
QUBIT q0 (rightmost bit):
q0=0 states: |000⟩,|010⟩,|100⟩,|110⟩ amplitudes: +0.354, +0.354, +0.354, +0.354
q0=1 states: |001⟩,|011⟩,|101⟩,|111⟩ amplitudes: +0.354, +0.354, -0.354, +0.354
H acts on each (q0=0, q0=1) pair independently:
H turns [a, b] into [a+b, a-b] / sqrt(2)
For the pair (|000⟩, |001⟩): amplitudes (0.354, 0.354)
After H: ((0.354+0.354)/sqrt(2), (0.354-0.354)/sqrt(2))
= (0.707/1.414, 0/1.414) = (0.500, 0.000)
For the pair (|010⟩, |011⟩): amplitudes (0.354, 0.354)
After H: (0.500, 0.000) (same as above)
For the pair (|100⟩, |101⟩): amplitudes (0.354, -0.354)
After H: ((0.354+(-0.354))/sqrt(2), (0.354-(-0.354))/sqrt(2))
= (0/1.414, 0.707/1.414) = (0.000, 0.500)
For the pair (|110⟩, |111⟩): amplitudes (0.354, 0.354)
After H: (0.500, 0.000)
After H on q0:
Key: |000⟩ |001⟩ |010⟩ |011⟩ |100⟩ |101⟩ |110⟩ |111⟩
Amplitude: +0.500 +0.000 +0.500 +0.000 +0.000 +0.500 +0.500 +0.000
Now apply H on q1 (middle bit), grouping by q1=0 vs q1=1:
(|000⟩,|010⟩): (0.500, 0.500) → H → (0.707, 0.000)
(|001⟩,|011⟩): (0.000, 0.000) → H → (0.000, 0.000)
(|100⟩,|110⟩): (0.000, 0.500) → H → (0.354, -0.354)
(|101⟩,|111⟩): (0.500, 0.000) → H → (0.354, 0.354)
After H on q1:
Key: |000⟩ |001⟩ |010⟩ |011⟩ |100⟩ |101⟩ |110⟩ |111⟩
Amplitude: +0.707 +0.000 +0.000 +0.000 +0.354 +0.354 -0.354 +0.354
Finally, apply H on q2 (leftmost bit), grouping by q2=0 vs q2=1:
(|000⟩,|100⟩): (0.707, 0.354) → H → (0.750, 0.250)
(|001⟩,|101⟩): (0.000, 0.354) → H → (0.250, -0.250)
(|010⟩,|110⟩): (0.000, -0.354) → H → (-0.250, 0.250)
(|011⟩,|111⟩): (0.000, 0.354) → H → (0.250, -0.250)
After H on all three qubits:
Key: |000⟩ |001⟩ |010⟩ |011⟩ |100⟩ |101⟩ |110⟩ |111⟩
Amplitude: +0.750 +0.250 -0.250 +0.250 +0.250 -0.250 +0.250 -0.250STEP 2: Apply X to each qubit (q0, q1, q2)
═══════════════════════════════════════════
X flips every bit: |000⟩↔|111⟩, |001⟩↔|110⟩, |010⟩↔|101⟩, |011⟩↔|100⟩.
Key: |000⟩ |001⟩ |010⟩ |011⟩ |100⟩ |101⟩ |110⟩ |111⟩
Before: +0.750 +0.250 -0.250 +0.250 +0.250 -0.250 +0.250 -0.250
After X: -0.250 +0.250 -0.250 +0.250 +0.250 -0.250 +0.250 +0.750
(Each amplitude moved to its bit-flipped position.
|000⟩'s +0.750 moved to |111⟩. |111⟩'s -0.250 moved to |000⟩. Etc.)STEP 3: H on q0
════════════════
Why q0? Because q0 is the TARGET qubit of the Toffoli in step 4.
The Toffoli uses q2 and q1 as controls and q0 as the target.
We apply H to the target qubit to enable phase kickback — H
converts q0 into a state where the Toffoli's bit flip produces
a phase change instead of a bit change.
Same H pair transformation as step 1, applied only to q0.
For each pair differing in q0:
(a, b) -> ((a+b)/sqrt(2), (a-b)/sqrt(2))
The key pair is (|110⟩, |111⟩) — the only pair where the
Toffoli will fire (q2=1 AND q1=1):
|110⟩ has amplitude +0.250, |111⟩ has amplitude +0.750
After H: |110⟩ gets (0.250+0.750)/1.414 = +0.707
|111⟩ gets (0.250-0.750)/1.414 = -0.354
All other pairs also get H-transformed, but the Toffoli in
step 4 won't touch them (q2 and q1 aren't both 1). So H in
step 5 will undo step 3 for those pairs — they return to
their pre-step-3 values. Only (|110⟩, |111⟩) ends up changed.STEP 4: Toffoli(q2, q1 → q0)
════════════════════════════
Flips q0 only when q2=1 AND q1=1.
This swaps the amplitudes of |110⟩ and |111⟩
(flipping q0 maps |110⟩ ↔ |111⟩):
Before Toffoli: |110⟩ = +0.707, |111⟩ = -0.354
After Toffoli: |110⟩ = -0.354, |111⟩ = +0.707
All other states: q2 and q1 not both 1 → unchanged.STEP 5: H on q0 (undo step 3)
═════════════════════════════
Same H pair transformation again on q0.
For the pair (|110⟩, |111⟩) after step 4:
|110⟩ = -0.354, |111⟩ = +0.707
After H: |110⟩ gets (-0.354+0.707)/1.414 = +0.250
|111⟩ gets (-0.354-0.707)/1.414 = -0.750
Key: |000⟩ |001⟩ |010⟩ |011⟩ |100⟩ |101⟩ |110⟩ |111⟩
Amplitude: -0.250 +0.250 -0.250 +0.250 +0.250 -0.250 +0.250 -0.750
↑
was +0.750, now -0.750STEP 6: X on all qubits (undo step 2)
═════════════════════════════════════
Flips all bits back (same swap as step 2).
Key: |000⟩ |001⟩ |010⟩ |011⟩ |100⟩ |101⟩ |110⟩ |111⟩
Amplitude: -0.750 +0.250 -0.250 +0.250 +0.250 -0.250 +0.250 -0.250
↑
|111⟩'s -0.750 moved back to |000⟩STEP 7: H on all qubits (undo step 1)
═════════════════════════════════════
Same qubit-by-qubit H calculation as step 1. Let's trace it:
After step 6:
Key: |000⟩ |001⟩ |010⟩ |011⟩ |100⟩ |101⟩ |110⟩ |111⟩
Amplitude: -0.750 +0.250 -0.250 +0.250 +0.250 -0.250 +0.250 -0.250
H on q0 (pairs by bit 0):
(|000⟩,|001⟩): (-0.750, +0.250) → ((-0.750+0.250)/1.414, (-0.750-0.250)/1.414)
= (-0.354, -0.707)
(|010⟩,|011⟩): (-0.250, +0.250) → (0.000, -0.354)
(|100⟩,|101⟩): (+0.250, -0.250) → (0.000, +0.354)
(|110⟩,|111⟩): (+0.250, -0.250) → (0.000, +0.354)
H on q1 (pairs by bit 1):
(|000⟩,|010⟩): (-0.354, 0.000) → (-0.250, -0.250)
(|001⟩,|011⟩): (-0.707, -0.354) → (-0.750, -0.250)
(|100⟩,|110⟩): (0.000, 0.000) → (0.000, 0.000)
(|101⟩,|111⟩): (+0.354, +0.354) → (+0.500, 0.000)
H on q2 (pairs by bit 2):
(|000⟩,|100⟩): (-0.250, 0.000) → (-0.177, -0.177)
(|001⟩,|101⟩): (-0.750, +0.500) → (-0.177, -0.884)
(|010⟩,|110⟩): (-0.250, 0.000) → (-0.177, -0.177)
(|011⟩,|111⟩): (-0.250, 0.000) → (-0.177, -0.177)
FINAL STATE AFTER ALL 7 STEPS:
Key: |000⟩ |001⟩ |010⟩ |011⟩ |100⟩ |101⟩ |110⟩ |111⟩
Amplitude: -0.177 -0.177 -0.177 -0.177 -0.177 -0.884 -0.177 -0.177All amplitudes are negative — including the correct key |101⟩ at -0.884. This looks different from the +0.177/+0.884 we calculated in section 1.7.1 using "reflect about the mean." What happened?
The gate circuit produces a global minus sign compared to the formula. Every amplitude is multiplied by -1. This is a known property of this circuit — it implements "reflect about the mean, then negate everything." But the negation affects ALL amplitudes equally, so it has zero effect on probabilities:
PROBABILITIES (amplitude squared — sign doesn't matter):
════════════════════════════════════════════════════════
Wrong keys: |-0.177|^2 = 0.031 = 3.1% each
Correct key: |-0.884|^2 = 0.781 = 78.1%
Total: 7 x 3.1% + 78.1% = 21.7% + 78.1% = 99.8% ~ 100% ✓
Same probabilities as the "reflect about mean" calculation.
The global minus sign is invisible to measurement — only
RELATIVE signs between amplitudes matter for interference.For those interested in the math, the 7-gate circuit above implements the matrix D = 2|s⟩⟨s| - I. This section is optional — skip to section 1.8 without losing anything.
|s⟩ is the column vector 1/√8 × [1,1,1,1,1,1,1,1]ᵀ (the equal superposition). ⟨s| is the same numbers as a row vector — a mathematical notation called a "bra," not a qubit state. |s⟩⟨s| is their outer product — an 8×8 matrix where every entry is 1/8. Multiplying any vector by |s⟩⟨s| replaces every entry with the average. So 2|s⟩⟨s| - I computes: 2 × average - each entry = reflection about the mean.
DIFFUSION MATRIX FOR N = 8:
═══════════════════════════
D = 2|s⟩⟨s| - I
Diagonal entries: 2/8 - 1 = -3/4
Off-diagonal: 2/8 = 1/4
D = [ -3/4 1/4 1/4 1/4 1/4 1/4 1/4 1/4 ]
[ 1/4 -3/4 1/4 1/4 1/4 1/4 1/4 1/4 ]
[ 1/4 1/4 -3/4 1/4 1/4 1/4 1/4 1/4 ]
[ 1/4 1/4 1/4 -3/4 1/4 1/4 1/4 1/4 ]
[ 1/4 1/4 1/4 1/4 -3/4 1/4 1/4 1/4 ]
[ 1/4 1/4 1/4 1/4 1/4 -3/4 1/4 1/4 ]
[ 1/4 1/4 1/4 1/4 1/4 1/4 -3/4 1/4 ]
[ 1/4 1/4 1/4 1/4 1/4 1/4 1/4 -3/4 ]
Our 7-gate circuit implements this matrix. Here's how the
7 steps map to the matrix formula:
D = H⊗³ · (2|0⟩⟨0| - I) · H⊗³
──── ────────────── ────
step 7 steps 2-6 step 1
Reading the circuit in execution order (left to right):
Step 1 (H on all qubits) = the rightmost H⊗³ in the formula.
Converts from superposition basis to computational basis.
This makes |s⟩ (equal superposition) map to |000⟩.
Steps 2-6 (X-all, H, Toffoli, H, X-all) = the middle part.
This is (2|0⟩⟨0| - I): leaves |000⟩ unchanged, flips the
sign of every other state.
Step 7 (H on all qubits) = the leftmost H⊗³ in the formula.
Converts back from computational basis to superposition basis.
Note: in matrix notation, the rightmost term acts first on the
state vector. So D|v⟩ = H⊗³ · (middle) · H⊗³ · |v⟩ means:
first apply H⊗³ (step 1), then the middle (steps 2-6), then
H⊗³ again (step 7). This is why step 1 corresponds to the
rightmost H⊗³ and step 7 to the leftmost.
Why does this equal "reflect about the mean"?
The middle operation reflects about |000⟩. But we want to
reflect about |s⟩. The H gates translate between the two:
step 1 converts the state so |s⟩ sits at |000⟩, the middle
reflects about |000⟩, and step 7 converts back. The net
effect is a reflection about |s⟩ — which equals reflecting
about the mean.That's the entire algorithm. Let's recap in one place:
GROVER'S ALGORITHM — COMPLETE:
══════════════════════════════
1. INITIALIZE: Apply H to all qubits → equal superposition of all N keys
2. REPEAT k times (k ≈ π/4 × √N):
a. ORACLE: the verifier circuit flips the phase of the correct key
b. DIFFUSION: 7-gate circuit reflects all amplitudes about the mean
3. MEASURE → get the correct key with high probability
For our 3-bit cipher (N=8):
k = 2 iterations
After iteration 1: correct key has 78.1% probability
After iteration 2: correct key has 94.5% probability
Measure → almost certainly get |101⟩ = the secret keyNow let's run it for real.
We've built every piece of the algorithm by hand. Now let's run it for real. The Colab notebook below implements the full circuit in Qiskit — the oracle, the diffusion operator, and 2 iterations of Grover's — and prints the state vector after each step so you can verify every amplitude matches our calculations.
EXPECTED OUTPUT (from the notebook):
════════════════════════════════════
After initialization: all 8 keys at 12.5% each
After iteration 1: key |101⟩ at 78.1%, others at 3.1%
After iteration 2: key |101⟩ at 94.5%, others at 0.8%
Measurement (1024 shots): |101⟩ appears ~940 times (93-95%)
The key is 101. Cipher cracked in 2 oracle queries.Everything we just ran was on a classical computer simulating quantum behavior. The simulator tracks all 8 amplitudes as regular floating-point numbers in memory. It multiplies matrices, updates the state vector, and samples from the probability distribution. There's nothing quantum about it — it's just linear algebra on your laptop.
A real quantum computer doesn't store amplitudes in memory. The physics is the computation. Each qubit is a physical object — a superconducting circuit cooled to 15 millikelvin (colder than outer space), or a trapped ion held in place by electric fields, or a photon traveling through a waveguide. Gates are physical operations: microwave pulses lasting nanoseconds, laser beams tuned to precise frequencies. The state vector exists in the physics, not in RAM.
Why does this matter? Because simulating quantum systems on classical computers is exponentially expensive:
SIMULATION MEMORY:
══════════════════
n qubits → 2ⁿ amplitudes × 16 bytes each (complex double precision)
3 qubits: 2³ = 8 amplitudes → 128 bytes (trivial)
10 qubits: 2¹⁰ = 1,024 amplitudes → 16 KB (trivial)
20 qubits: 2²⁰ = 1,048,576 amplitudes → 16 MB (fine)
30 qubits: 2³⁰ = ~1 billion amplitudes → 16 GB (one GPU)
40 qubits: 2⁴⁰ = ~1 trillion amplitudes → 16 TB (cluster)
50 qubits: 2⁵⁰ = ~10¹⁵ amplitudes → 16 PB (impossible)
Every additional qubit DOUBLES the memory.
At 50 qubits, no classical computer on Earth can simulate it.Our 3-qubit simulation was trivial because 8 amplitudes fit in 128 bytes. But Grover's algorithm on 50 qubits — searching among 2⁵⁰ ≈ 10¹⁵ items — would need about 2²⁵ ≈ 33 million iterations. A real quantum computer could do this. A classical simulator cannot even represent the state.
We ran our exact Grover circuit on IBM's ibm_fez quantum processor — a real superconducting quantum computer. Here are the actual results:
REAL QUANTUM HARDWARE RESULTS (ibm_fez, 4096 shots):
═════════════════════════════════════════════════════
key |101⟩: 2355 shots (57.5%) ← THE KEY
key |100⟩: 321 shots ( 7.8%)
key |001⟩: 294 shots ( 7.2%)
key |111⟩: 284 shots ( 6.9%)
key |000⟩: 230 shots ( 5.6%)
key |010⟩: 228 shots ( 5.6%)
key |011⟩: 202 shots ( 4.9%)
key |110⟩: 182 shots ( 4.4%)
Simulator: 94.5% Real hardware: 57.5%The correct key |101⟩ is clearly the winner at 57.5% — but it's lower than the simulator's 94.5%. The gap is larger than our earlier 3-qubit run (76.4%) because the full verifier circuit uses 6 qubits and 364 native gates at depth 218 — more qubits and more gates means more noise accumulates. Despite this, the correct key has 7× more counts than the next-highest key (7.8%). Real quantum computers are noisy, but the signal comes through.
Why the noise? Real quantum computers have errors:
IBM offers free access to real quantum processors. You get 10 minutes of QPU time per month — our circuit uses about 5 seconds. Here's how:
pip install qiskit qiskit-ibm-runtime qiskit-aerfrom qiskit_ibm_runtime import QiskitRuntimeService
QiskitRuntimeService.save_account(
channel="ibm_cloud",
token="YOUR_API_KEY",
overwrite=True
)# Grover's Algorithm on Real Quantum Hardware
# =============================================
# Full verifier circuit matching the article (section 1.6).
#
# Qubit layout (6 qubits total):
# qubit 0 = k0 (key bit 0, rightmost) — Qiskit uses little-endian:
# qubit 1 = k1 (key bit 1, middle) qubit 0 = least significant bit
# qubit 2 = k2 (key bit 2, leftmost)
# qubit 3 = a0 (ancilla for bit 0)
# qubit 4 = a1 (ancilla for bit 1)
# qubit 5 = a2 (ancilla for bit 2)
from qiskit import QuantumCircuit
from qiskit_ibm_runtime import QiskitRuntimeService, SamplerV2
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
# --- Build the full verifier circuit ---
grover = QuantumCircuit(6, 3) # 6 qubits (3 key + 3 ancilla), 3 classical bits
grover.h([0, 1, 2]) # Superposition on key qubits only
def oracle(qc):
# STEP 1: Compute plaintext(011) XOR key on ancilla
qc.x(3); qc.x(4) # load plaintext 011: flip a0,a1 to |1> (a2 stays |0>)
qc.cx(0, 3); qc.cx(1, 4); qc.cx(2, 5) # XOR with key
# STEP 2: Phase flip when ancilla = ciphertext(110)
qc.x(3) # convert 110 to 111
qc.h(3); qc.ccx(5, 4, 3); qc.h(3) # phase kickback
qc.x(3) # undo
# STEP 3: Uncompute
qc.cx(2, 5); qc.cx(1, 4); qc.cx(0, 3) # undo XOR
qc.x(4); qc.x(3) # undo plaintext loading
def diffusion(qc):
qc.h([0, 1, 2])
qc.x([0, 1, 2])
qc.h(0); qc.ccx(1, 2, 0); qc.h(0)
qc.x([0, 1, 2])
qc.h([0, 1, 2])
for _ in range(2): # 2 Grover iterations
oracle(grover)
grover.barrier()
diffusion(grover)
grover.barrier()
grover.measure([0, 1, 2], [0, 1, 2]) # measure key qubits only
# --- Connect to IBM Quantum ---
service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False, min_num_qubits=6)
print(f"Running on: {backend.name}")
# --- Transpile for real hardware ---
pm = generate_preset_pass_manager(backend=backend, optimization_level=3)
transpiled = pm.run(grover)
# --- Submit to the QPU ---
sampler = SamplerV2(backend)
job = sampler.run([transpiled], shots=4096)
print(f"Job submitted. Waiting...")
# --- Get and print results ---
result = job.result()
counts = result[0].data.c.get_counts()
total = sum(counts.values())
for key in sorted(counts, key=counts.get, reverse=True):
pct = counts[key] / total * 100
marker = " <- THE KEY!" if key == "101" else ""
print(f" |{key}>: {counts[key]:4d} ({pct:5.1f}%){marker}")
print(f"\nSuccess rate: {counts.get('101', 0) / total * 100:.1f}%")The job takes about 10-15 seconds total (with about 2 seconds of actual QPU time). Your result will look similar to ours — |101⟩ dominating at 60-80%, with noise spreading some probability to other keys.
We started with a question: how do you crack a secret key? A classical computer tries keys one by one — 500,000 attempts for a million possibilities. We said a quantum computer could do it in 785. That sounded impossible.
Then we built the entire machine, piece by piece. Qubits as vectors. Gates as matrices. Superposition as holding all keys at once. The oracle as a real verifier circuit — built from public information, checking all candidates simultaneously, marking the correct one with an invisible phase flip. The diffusion operator as a reflection that turns that invisible mark into a measurable signal. Two iterations, and the correct key dominates.
We ran it on a simulator and got 94.5%. We ran it on IBM's ibm_fez quantum processor — an actual superconducting chip cooled to 15 millikelvin — and got 57.5%. Noisier, but the correct key was unmistakable — 7× more likely than any wrong key.
Everything in this article — qubits, gates, interference, phase kickback, amplitude amplification — is the foundation for every quantum algorithm that follows. Grover's is the simplest complete quantum algorithm, but the tools it uses are universal.
| Part 2: Entanglement | The resource that makes multi-qubit quantum computing truly powerful. What EPR pairs are, why "spooky action at a distance" isn't magic, and how entanglement enables quantum teleportation and superdense coding. |
| Part 3: Quantum Fourier Transform | The quantum version of the FFT — exponentially faster. The key building block behind Shor's factoring algorithm and quantum phase estimation. |
| Part 4: Shor's Algorithm | The algorithm that breaks RSA encryption. How period-finding plus QFT factors large numbers in polynomial time. |
You went from zero to cracking a cipher on a real quantum computer. The hard part is over — everything from here builds on what you just learned.
| Concept | What it is | Key insight |
|---|---|---|
| Qubit | A 2D complex vector [α, β] | Amplitudes determine probabilities via |α|² |
| Superposition | Non-zero amplitudes for multiple states | Like a wave — has magnitude and direction (phase) |
| Interference | Amplitudes add (can cancel or reinforce) | Same-direction waves amplify; opposite waves cancel |
| Quantum gate | A unitary matrix applied to the state | Just matrix multiplication — nothing mysterious |
| Hadamard (H) | Creates equal superposition from |0⟩ | Like a half-silvered mirror; H² = I |
| Phase kickback | Controlled bit-flip on |−⟩ → phase on control | Converts bit flips to phase flips — the key oracle trick |
| Oracle | Flips the phase of the correct key | A verifier circuit: X gates + Toffoli + phase kickback |
| Diffusion | Reflects amplitudes about their mean | D = H⊗ⁿ(2|0⟩⟨0|-I)H⊗ⁿ — same gates as oracle |
| Grover's algorithm | Initialize → repeat (oracle + diffusion) → measure | Rotation in 2D plane; π/4 × √N iterations |
| Classical search (N items) | N/2 queries average, N worst case |
| Grover's search (N items) | π/4 × √N queries |
| Speedup | Quadratic (N → √N), provably optimal |
| N = 8, optimal iterations | 2 iterations, 94.5% success |
| N = 1,000,000 | 785 iterations (vs 500,000 classical) |
| Simulation cost | 2ⁿ × 16 bytes (exponential in qubits) |
@misc{fofadiya2026grovers,
author = {Darshan Fofadiya},
title = {Zero to Grover's Search — Zero to Quantum, Part 1},
year = {2026},
url = {https://darshanfofadiya.com/zero-to-quantum/grovers-search.html}
}
Get notified when I publish new deep dives
Illustrated guides on LLM inference, quantum computing, and AI research papers.
⚠ After subscribing, check your inbox for a confirmation email. You won't receive posts until you confirm.