Grover's Search

Algorithm
Quantum speedup for unstructured search

Classical: O(N) → Quantum: O(√N)

Based on Grover (1996)

 T H E PR O BL E M

Unordered Database Search

Find the one item satisfying f(x) = 1 — with no index, no sorting

Example: N = 8 items
Problem Setup
• Database of N items: a₁, a₂, …, aₙ
• No index, no sorting — completely unordered
a₁ a₂ a₃ ★
• Oracle f(x) = 1 if aₓ = target, else 0
• We only have query access to f — treat it as a black box
• Cost metric: number of queries to f a₅ a₆ a₇ a₈
Queries needed

Classical: must check items one by one N Classical Quantum

→ O(N) queries worst case (proven lower bound) 100 100 10

10,000 10,000 100

Quantum (Grover): O(√N) queries 1,000,000 1,000,000 1,000

→ Quadratic speedup — proven optimal

 TH E ORA CLE

Standard Oracle vs Phase Oracle

Two equivalent ways to implement the oracle — phase version is what Grover needs

Standard (Bit-flip) Oracle Phase Oracle (what Grover uses)

Of |x⟩|y⟩ = |x⟩|y ⊕ f(x)⟩ Of |x⟩ = (−1)^f(x) |x⟩

• Query register: ⌈log N⌉ qubits for index x • Achieved by setting |y⟩ = |−⟩ = (|0⟩−|1⟩)/√2
• Answer register: 1 qubit, receives f(x) • Target state |a⟩ gets phase −1 (sign flips)
• If |y⟩ = |0⟩: result is |x⟩|f(x)⟩ • All other states unchanged (phase +1)
• If |y⟩ = |1⟩: result is |x⟩|f̄(x)⟩ (flipped) • Probabilities |amplitude|² unchanged!

Why does setting |y⟩ = |−⟩ produce the phase oracle?

Of |x⟩|−⟩ = (Of|x⟩|0⟩ − Of|x⟩|1⟩) / √2 = (|x⟩|f(x)⟩ − |x⟩|f̄(x)⟩) / √2
If f(x)=0: (|x⟩|0⟩ − |x⟩|1⟩)/√2 = |x⟩|−⟩ → phase +1
If f(x)=1: (|x⟩|1⟩ − |x⟩|0⟩)/√2 = −|x⟩|−⟩ → phase −1
In both cases: Of|x⟩|−⟩ = (−1)^f(x) |x⟩|−⟩ The |−⟩ register is unchanged and can be ignored.
 SETUP

Initial State & Geometric Picture

The algorithm lives entirely in a 2-dimensional plane

Creating the initial state |ψ₀⟩

Step: Apply H⊗ⁿ to |0ⁿ⟩ (n = log₂N Hadamard gates)

|ψ₀⟩ = (1/√N) Σₓ |x⟩ — equal superposition of all N

Result:
states

Decompose: |ψ₀⟩ = (1/√N)|a⟩ + √((N−1)/N) |e⟩

|a⟩ = target state, |e⟩ = uniform mix of all non-

Where:
targets
State stays in span{|a⟩, |e⟩} throughout the
Key:
algorithm
sin θ₀ = ⟨a|ψ₀⟩ = 1/√N → θ₀ ≈ 1/√N (very small for
Angle:
large N)
 ITERATIO N S TEP 1

Oracle = Reflection About |e⟩

The phase oracle geometrically reflects the state across the |e⟩ axis

BEFORE Oracle
What the oracle does in the 2D plane
|a⟩
On |a⟩: Of |a⟩ = (−1)^f(a) |a⟩ = −|a⟩ (target → sign flip)

On |e⟩: Of |e⟩ = |e⟩ (non-targets → unchanged, since f(x)=0)

|ψ⟩
General: Of (α|a⟩ + β|e⟩) = −α|a⟩ + β|e⟩

The |a⟩ component negates. |e⟩ component

Effect:
unchanged. |e⟩

Geometry: This is exactly a reflection across the |e⟩ axis!

 ITERATIO N S TEP 1

Oracle = Reflection About |e⟩

The phase oracle geometrically reflects the state across the |e⟩ axis

What the oracle does in the 2D plane AFTER Oracle |a⟩

On |a⟩: Of |a⟩ = (−1)^f(a) |a⟩ = −|a⟩ (target → sign flip)

On |e⟩: Of |e⟩ = |e⟩ (non-targets → unchanged, since f(x)=0) |ψ⟩

General: Of (α|a⟩ + β|e⟩) = −α|a⟩ + β|e⟩

Reflected |e
The |a⟩ component negates. |e⟩ component across |e⟩ ⟩
Effect:
unchanged.

Geometry: This is exactly a reflection across the |e⟩ axis! Of|ψ⟩

 ITERATIO N S TEP 2

Diffuser = Reflection About |U⟩

H⊗ⁿ · R|0⟩ · H⊗ⁿ reflects the state about the uniform superposition |U⟩

Building the Diffuser Circuit Diffuser Circuit

Goal: Reflect the state about |U⟩ = (1/√N) Σ|x⟩

Reflecting about |U⟩ directly is complex. Reduce to |0ⁿ⟩ H⊗ⁿ R|0⟩ H⊗ⁿ
Problem:
reflection.

Step 1: Apply H⊗ⁿ → maps |U⟩ to |0ⁿ⟩ (since H⊗ⁿ|U⟩ = |0ⁿ⟩) Hadamard Phase flip Hadamard

Reflect about |0ⁿ⟩: R|0⟩ keeps |0ⁿ⟩, negates all other basis
Step 2: = Reflection about |U⟩
states

Key Lemma
Step 3: Apply H⊗ⁿ again → maps |0ⁿ⟩ back to |U⟩

Two reflections about axes separated by angle θ

R|0⟩ details: |0ⁿ⟩ Combined:
Result: → |0ⁿ⟩ (unchanged); |b₁…bₙ⟩
H⊗ⁿ · R|0ⁿ⟩ · H⊗ⁿ→= −|b₁…bₙ⟩
Reflectionforabout
all others.
|U⟩ Equiv: = rotation by 2θ toward the first axis.
phase (−1)^(b₁∨b₂∨…∨bₙ)
 CO R E G E O M ET R Y

Two Reflections = One Rotation

Each Grover iteration rotates the state by exactly 2θ₀ toward |a⟩

Why does this work?

• |e⟩ and |U⟩ are the two reflection axes
• Angle between them = θ₀ (since |U⟩ ≈ |ψ₀⟩)
• Reflect about |e⟩ (oracle): state flips across horizontal
• Reflect about |U⟩ (diffuser): state flips across |U⟩ axis
• Net effect of two reflections: rotation by 2θ₀

After T iterations, angle from |e⟩ = (2T+1)θ₀

We want angle close to π/2 → pointing at |a⟩

Solve: (2T+1)θ₀ ≈ π/2
→ T ≈ π/(4θ₀) ≈ (π/4)√N = O(√N)
Success probability after T steps:
P(|a⟩) = sin²((2T+1)θ₀) ≥ cos²(π/4) = 1/2
 TH E ALGORITH M

Grover's Algorithm — Complete

Every step explained

Algorithm Initialize
① n = ⌈log₂N⌉ qubits. H gate on each puts qubit in |+⟩ = (|0⟩+|1⟩)/√2.
1. Prepare |0ⁿ⟩ Together: uniform superposition of all N states.

2. Apply H⊗ⁿ → |ψ₀⟩ = (1/√N) Σ|x⟩ Oracle call

② Phase oracle marks target: |a⟩ → −|a⟩, all others unchanged.
3. Repeat T = ⌈(π/4)√N⌉ times:
Geometrically: reflects state about |e⟩ axis. 1 oracle query.
a. Apply phase oracle Of
Diffuser
(reflect about |e⟩) ③ H⊗ⁿ·R|0⟩·H⊗ⁿ reflects about |U⟩. No oracle call needed — built
from Hadamards and a phase gate. Cost: O(n) gates.
b. Apply H⊗ⁿ · R|0ⁿ⟩ · H⊗ⁿ
(reflect about |U⟩) Measure
④ After T = O(√N) iterations, amplitude on |a⟩ is ≈ 1. Standard basis
4. Measure in computational basis → x measurement returns |a⟩ with prob ≥ 1/2.

5. If f(x) = 1: return x ✓ Verify & repeat

Else: repeat from step 1 ⑤ Check oracle on measured x. If success: done. Else try again. k
independent runs → failure prob ≤ (1/2)ᵏ → 0.
 INTUITION

Why It Works: Amplitude Amplification

Each iteration boosts the target's amplitude at the expense of all others

t=0 t=1 t=T

— — — ★
— — —

— — —

0.250 0.250 0.250 0.25 0.176 0.176 0.176 0.65 0.020 0.020 0.020 1.00
amplitude amplitude amplitude
 ANA LYS IS

Complexity & Optimality Provably Optimal

O(√N) is tight — no quantum algorithm can do better
Bennett, Bernstein, Brassard & Vazirani (1997)
proved using the polynomial method that any
How many iterations T? quantum algorithm for unstructured search
requires Ω(√N) queries. Grover's algorithm
Start: Angle of |ψ₀⟩ from |e⟩ is θ₀, sin θ₀ = 1/√N matches this exactly.

Each iter: Angle increases by 2θ₀ → angle after T iters = (2T+1)θ₀

Target: Want angle ≈ π/2 (so state points at |a⟩)

O(√N) O(N)
Solve: (2T+1)θ₀ ≈ π/2 → T ≈ π/(4θ₀)
Quantum queries Classical queries
Substitute: θ₀ ≈ 1/√N → T ≈ (π/4)√N = O(√N)

Formally: T = ⌈(π/(4θ₀) − 1)/2⌉, chosen so (2T+1)θ₀ ∈ [π/4, 3π/4]

Success prob: P(|a⟩) = sin²((2T+1)θ₀) ≥ sin²(π/4) = 1/2

≥50%
Success per run
Repeat k times: P(failure)ᵏ ≤ (1/2)ᵏ → success → 1 as k grows
 E X ER C I SE

Exercise: Work Through N = 4 by Hand

Target state: |11⟩ — just one Grover iteration needed

Setup

N = 4 items: {|00⟩, |01⟩, |10⟩, |11⟩}. Target is |11⟩. Iterations needed: T = ⌈(π/4)·√4⌉ = ⌈π/2⌉ = 1.

Write |ψ₀⟩ = (H⊗H)|00⟩ explicitly.

A Hint: H|0⟩ = (|0⟩+|1⟩)/√2. Apply to each qubit then tensor product. → |ψ₀⟩ = ½(|00⟩ + |01⟩ + |10⟩ + |11⟩) — each state has amplitude ½

Apply phase oracle for target |11⟩. Write the new state.
B Hint: Oracle flips sign of |11 ⟩ only. f(11) = 1, f(others) = 0. → ½(|00⟩ + |01⟩ + |10⟩ − |11⟩) — only |11⟩ amplitude negated

Apply the diffuser. Compute new amplitudes.

C Hint: Mean = (½+½+½−½)/4 = ¼. New amp = 2·mean − old_amp. → |00⟩,|01⟩,|10⟩ get 2·(¼)−½ = 0. |11⟩ gets 2·(¼)−(−½) = 1.

Calculate P(measuring |11⟩). What does this tell you?

D Hint: P = |amplitude|² → P(|11⟩) = |1|² = 1. Perfect success in 1 iteration for N=4!
Summary
The problem:
1.
Find a marked element in an unordered list of N items. Classical lower bound: O(N). Quantum: O(√N) — a quadratic speedup.

Key tool: phase oracle:

2.
Marks the target by flipping its sign (phase). Achieved via phase kickback. Probabilities unchanged — the tag is hidden.

Geometric picture:
3. State lives in a 2D plane {|a⟩, |e⟩}. Oracle reflects about |e⟩. Diffuser (H⊗R₀H⊗) reflects about |U⟩. Two reflections = rotation by
2θ₀.

The iteration count:

4.
θ₀ ≈ 1/√N. Need ≈ π/2 total rotation. T = (π/4)√N iterations. Success probability ≥ 1/2, amplified with repetition.

Optimality:
5.
Bennett et al. (1997): no quantum algorithm can solve unstructured search in o(√N) queries. Grover is tight.

References: Grover (1996) · Bennett et al. (1997) · Nielsen & Chuang (2002)