First time studying this topic?

Launch the interactive walkthrough to discover each component, including the 3D Q-Sphere Lab & Python in Colab.

Topic 7.4

Grover’s Search Algorithm: Quadratic Speedup

Master the crown jewel of unstructured search: the Phase Oracle, Inversion about the Mean (Diffusion Operator), and O(sqrt(N)) speedup.

Learning Objectives

✓Understand unstructured database search: N items in classical O(N) vs Grover O(sqrt(N))
✓Deconstruct the Grover Iteration: Oracle Phase Inversion + Diffusion Reflection
✓Visualize geometric rotation in 2D subspace spanned by target and non-target states

📖Let's Begin with a Story

Imagine you have a lock with a 4-digit code (10,000 possible combinations from 0000 to 9999). You don't know the code, and you have no clues. On a classical computer, you have to try combinations one by one: 0000, 0001, 0002... On average, you will try 5,000 attempts before the lock clicks open (

N/2

). In 1996, an Indian-American computer scientist at Bell Labs named Lov Grover published an algorithm that blew the doors off classical search theory. Grover showed that a quantum computer can find the secret code in approximately:

\frac{\pi}{4} \sqrt{10{,}000} \approx \frac{3.14}{4} \times 100 \approx \mathbf{78 \text{ attempts!}}

Instead of 5,000 tries, Grover cracks the lock in just 78 quantum iterations!

Why Should You Learn Grover’s Search Algorithm: Quadratic Speedup?

🎯 Practical & Engineering Stakes

The universal quadratic accelerator

Grover’s algorithm provides a provable quadratic speedup for ANY problem that can be verified in polynomial time (NP problems), including constraint satisfaction, SAT solvers, and hash function pre-image attacks.

What Is It?

Simple Explanation

Grover's algorithm works in two alternating steps: 1. The Oracle (Mark the Target): Put a tiny minus sign on the winning answer. (Like sticking a tiny sticky note on the right book). 2. The Diffusion Operator (Inversion about the Mean): Imagine all the book heights on a shelf. The marked book has an upside-down height. When you reflect all books across their average height, the marked book shoots up like a giant skyscraper, and all the wrong books shrink down to ants! Repeat this

\approx \sqrt{N}

times, and the right book stands out with almost 100% height!

Technical Explanation

Grover’s algorithm solves the unstructured search problem for unique target

\omega \in \{0, 1\}^n

(

N = 2^n

) in

R \approx \frac{\pi}{4}\sqrt{N}

iterations. Each Grover operator

G = D U_\omega

consists of: 1. **Phase Oracle

U_\omega

**: Reflection about orthogonal subspace

I - 2|\omega\rangle\langle\omega|

. 2. **Diffusion Operator

D

**: Reflection about uniform superposition state

|s\rangle

2|s\rangle\langle s| - I

. In the 2D subspace spanned by

|\omega\rangle

and

|s'\rangle = \frac{1}{\sqrt{N-1}}\sum_{x \ne \omega}|x\rangle

G

executes a planar rotation by angle

\theta = 2\arcsin(1/\sqrt{N}) \approx 2/\sqrt{N}

📚 Key Terms

Grover Diffusion Operator

Simple: The math operation that flips all amplitudes upside-down across their average, making the target huge.

Technical: The unitary operator

D = 2|s\rangle\langle s| - I

performing inversion about the mean amplitude.

Quadratic Speedup

Simple: Reducing the time from N down to square root of N.

Technical: Complexity reduction from

\mathcal{O}(N)

\mathcal{O}(\sqrt{N})

Overcooking (Over-rotation)

Simple: Running Grover too many times causes the target to rotate past the peak and shrink back down!

Technical: Periodic probability oscillation

P(\omega) = \sin^2((2k+1)\theta/2)

; exceeding optimal iterations reduces success probability.

Q-Sphere Lab: Grover’s Search Algorithm: Quadratic Speedup

IBM Q-Sphere Model

Interactive 3D state vector exploration, unitary transformation gates, and Born rule collapse for Topic 7.4

Azimuth: 45°Elevation: 25°(Click & drag sphere to orbit)

Q-Sphere Phase Color:

0 π/2 π 3π/2

Quantum Statevector

dim(H) = 2

|ψ⟩ = (1.000 + 0.000i)|0⟩
+ (0.000 + 0.000i)|1⟩

Polar Angle (θ):0.0° (0.000π rad)

Phase Angle (ϕ):0.0° (0.000π rad)

Born Rule Probabilities: P(x) = |⟨x|ψ⟩|²Σ P = 1.00

P(|0⟩) = |α|²100.0%

P(|1⟩) = |β|²0.0%

Quantum Measurement

Apply Single-Qubit Unitary Gates

Presets:

Continuous Polar Angle θ (0° = |0⟩, 180° = |1⟩):0.0°

Continuous Phase Angle ϕ (0° to 360°):0.0°

Recent Operations Log:

#1Initial state: |0⟩

📐 Mathematical Foundation

LaTeX KaTeX

R \approx \left\lfloor \frac{\pi}{4} \sqrt{N} \right\rfloor, \quad D = 2|s\rangle\langle s| - I, \quad \theta = 2 \arcsin\left(\frac{1}{\sqrt{N}}\right)

What does it mean?

Grover Amplitude Amplification & Inversion About the Mean: Searches an unsorted database of

N

items. Each iteration applies an Oracle (which flips the sign of the marked item) followed by the Grover Diffusion operator

D = 2|s\rangle\langle s| - I

(which reflects all amplitudes across their average mean). Repeating this

R \approx (\pi/4)\sqrt{N}

times boosts the target item probability to near 100%.

Understanding the Symbols

Symbol / Term	Meaning	Beginner Interpretation
$N$	Total search space size	Number of items in the unsorted database ( $N = 2^n$ )
$R$	Optimal iteration count	Number of times to run the Oracle + Diffusion loop
$\|s\rangle$	Uniform superposition state	Equal mixture of all states: $\|s\rangle = \frac{1}{\sqrt{N}} \sum \|x\rangle$
$D$	Diffusion operator (Inversion about mean)	$2\|s\rangle\langle s\| - I$ , reflecting amplitudes across the average
$\theta$	Rotation angle per Grover step	Angular step rotating the state vector toward the target item in 2D Hilbert space

📊 Numerical Example

Searching for 1 marked item among N = 4 items (2 qubits, |s⟩ = [0.5, 0.5, 0.5, 0.5]^T) where target is |11⟩:

Initial State:

|s\rangle

= [0.5, 0.5, 0.5, 0.5]^T (each has 25% probability) Optimal iterations: R = (π/4) × √4 = (3.1415 / 4) × 2 ≈ 1.57 → R = 1 iteration! Step 1: Apply Oracle (flips target

|11\rangle

): Amplitudes become: [+0.5, +0.5, +0.5, -0.5]^T Step 2: Calculate Mean Amplitude (μ): μ = (0.5 + 0.5 + 0.5 - 0.5) / 4 = 1.0 / 4 = +0.25 Step 3: Apply Diffusion Operator (Invert about mean: a_new = 2μ - a_old): • For non-targets: 2(0.25) - 0.5 = 0.5 - 0.5 = 0.0 • For target

|11\rangle

: 2(0.25) - (-0.5) = 0.5 + 0.5 = 1.0 New Amplitudes: [0.0, 0.0, 0.0, 1.0]^T

Result: In just 1 single iteration, the target item $|11\rangle$ reaches exactly 100% probability (P( $|11\rangle$ ) = 1.0² = 1.00)!

⚙️ How Does It Work?

Equal Superposition

Initialize register into |s> using Hadamard gates: all items have equal height 1/sqrt(N).

Oracle Phase Flip

Invert the sign of the target item |omega> -> -|omega>.

Inversion About the Mean

Apply Diffusion operator; target amplitude shoots up while non-targets shrink.

Optimal Stopping

Halt after exactly R iterations and measure target with probability > 99%.

🌍 Where Is It Used?

AES-256 Cryptographic Security

Problem: Evaluating symmetric key strength against quantum brute-force search.

Solution: Grover cuts effective key security in half ($2^{256} \rightarrow 2^{128}$), prompting security standards to recommend 256-bit keys.

🎯 Try It Yourself

You want to find 1 marked item in a database of 64 items using Grover’s algorithm. Approximately how many Grover iterations should you run?

Interactive activity component

🐍 Python Hands-On: Lesson 9: Grover Search and Amplitude Amplification

Implement Grover’s quantum search algorithm to find target state |11> using Oracle (CZ) and Diffusion Operator functions composed onto a 2-qubit circuit with Aer simulation and histogram plotting.

Open Colab

1Install Required Packages

For Google Colab or Jupyter notebooks, run this shell command to install the required dependencies:

Terminal / Notebook Install Commandbash

!pip install qiskit qiskit-aer matplotlib

Packages:

qiskitqiskit-aermatplotlib

2Import Libraries

Import Statementspython

1 from qiskit import QuantumCircuit
2 from qiskit.visualization import plot_histogram
3 from qiskit_aer import Aer
4 import matplotlib.pyplot as plt

from qiskit import QuantumCircuit → Assemble quantum circuits in Qiskit

from qiskit.visualization import plot_histogram → Visualize measurement distribution

from qiskit_aer import Aer → Import Aer simulator backend

import matplotlib.pyplot as plt → Matplotlib plotting backend

3Demonstration Code & Logic

Python Execution Codepython

1 # Define the Oracle (marks the |11⟩ state)
2 def grover_oracle():
3     oracle = QuantumCircuit(2)
4     oracle.cz(0, 1)  # Controlled-Z gate to mark |11⟩
5     return oracle
6  
7 # Define the Diffusion Operator (amplifies the correct state)
8 def diffusion_operator():
9     diffusion = QuantumCircuit(2)
10     diffusion.h([0, 1])  # Apply Hadamard gates
11     diffusion.x([0, 1])  # Apply X gates
12     diffusion.cz(0, 1)   # Apply Controlled-Z gate
13     diffusion.x([0, 1])  # Apply X gates again
14     diffusion.h([0, 1])  # Apply Hadamard gates again
15     return diffusion
16  
17 # Create a 2-qubit quantum circuit
18 qc = QuantumCircuit(2, 2)
19  
20 # Step 1: Initialize with Hadamard gates
21 qc.h([0, 1])
22  
23 # Step 2: Apply Grover's Oracle using .compose()
24 qc = qc.compose(grover_oracle())
25  
26 # Step 3: Apply the Diffusion Operator using .compose()
27 qc = qc.compose(diffusion_operator())
28  
29 # Step 4: Measure the qubits
30 qc.measure([0, 1], [0, 1])
31  
32 # Execute on Aer simulator
33 simulator = Aer.get_backend('aer_simulator')
34 job = simulator.run(qc, shots=1000)
35 result = job.result()
36 counts = result.get_counts(qc)
37 print("Grover Search Measurement Results (Lesson 9):", counts)
38 plot_histogram(counts)
39 plt.show()

Step-by-Step Code Breakdown:

# Define the Oracle (marks the |11⟩ state)

Oracle function

def grover_oracle():

Function definition

oracle = QuantumCircuit(2)

2-qubit circuit for oracle

oracle.cz(0, 1) # Controlled-Z gate to mark |11⟩

Controlled-Z adds negative phase to |11>

return oracle

Return oracle circuit

# Define the Diffusion Operator (amplifies the correct state)

Diffusion function

def diffusion_operator():

Function definition

diffusion = QuantumCircuit(2)

2-qubit circuit for diffusion

diffusion.h([0, 1]) # Apply Hadamard gates

H on all wires

diffusion.x([0, 1]) # Apply X gates

X on all wires

diffusion.cz(0, 1) # Apply Controlled-Z gate

Controlled phase inversion

diffusion.x([0, 1]) # Apply X gates again

Uncompute X

diffusion.h([0, 1]) # Apply Hadamard gates again

Uncompute H

return diffusion

Return diffusion circuit

# Create a 2-qubit quantum circuit

Main algorithm circuit

qc = QuantumCircuit(2, 2)

Allocate 2 qubits and 2 classical bits

# Step 1: Initialize with Hadamard gates

Equal superposition

qc.h([0, 1])

Put register into uniform superposition

# Step 2: Apply Grover's Oracle using .compose()

Mark target state

qc = qc.compose(grover_oracle())

Append oracle sub-circuit

# Step 3: Apply the Diffusion Operator using .compose()

Amplify marked amplitude

qc = qc.compose(diffusion_operator())

Append diffusion sub-circuit

# Step 4: Measure the qubits

Readout

qc.measure([0, 1], [0, 1])

Measure qubits into classical bits

# Execute on Aer simulator

Run simulation

simulator = Aer.get_backend('aer_simulator')

Load aer_simulator backend

job = simulator.run(qc, shots=1000)

Execute 1,000 shots

result = job.result()

Get simulation results

counts = result.get_counts(qc)

Retrieve measurement counts

print("Grover Search Measurement Results (Lesson 9):", counts)

Display counts (100% |11>)

plot_histogram(counts)

Render histogram of measurement counts

plt.show()

Display figure

📋 Complete Script (All-in-One)

Click "Copy for Colab", open Google Colab, paste into a single cell, and run.

Google Colab Notebook Scriptpython

1 # =========================================================
2 # Lesson 9: Grover Search and Amplitude Amplification
3 # Prepared for Google Colab (Run with Shift + Enter)
4 # =========================================================
5  
6 # Step 1: Install required packages
7 !pip install qiskit qiskit-aer matplotlib
8  
9 # Step 2: Import libraries
10 from qiskit import QuantumCircuit
11 from qiskit.visualization import plot_histogram
12 from qiskit_aer import Aer
13 import matplotlib.pyplot as plt
14  
15 # Step 3: Run Demonstration
16 # Define the Oracle (marks the |11⟩ state)
17 def grover_oracle():
18     oracle = QuantumCircuit(2)
19     oracle.cz(0, 1)  # Controlled-Z gate to mark |11⟩
20     return oracle
21  
22 # Define the Diffusion Operator (amplifies the correct state)
23 def diffusion_operator():
24     diffusion = QuantumCircuit(2)
25     diffusion.h([0, 1])  # Apply Hadamard gates
26     diffusion.x([0, 1])  # Apply X gates
27     diffusion.cz(0, 1)   # Apply Controlled-Z gate
28     diffusion.x([0, 1])  # Apply X gates again
29     diffusion.h([0, 1])  # Apply Hadamard gates again
30     return diffusion
31  
32 # Create a 2-qubit quantum circuit
33 qc = QuantumCircuit(2, 2)
34  
35 # Step 1: Initialize with Hadamard gates
36 qc.h([0, 1])
37  
38 # Step 2: Apply Grover's Oracle using .compose()
39 qc = qc.compose(grover_oracle())
40  
41 # Step 3: Apply the Diffusion Operator using .compose()
42 qc = qc.compose(diffusion_operator())
43  
44 # Step 4: Measure the qubits
45 qc.measure([0, 1], [0, 1])
46  
47 # Execute on Aer simulator
48 simulator = Aer.get_backend('aer_simulator')
49 job = simulator.run(qc, shots=1000)
50 result = job.result()
51 counts = result.get_counts(qc)
52 print("Grover Search Measurement Results (Lesson 9):", counts)
53 plot_histogram(counts)
54 plt.show()

⚡ How to Run in Google Colab (3 Quick Steps)

Click "Copy for Google Colab" above.
Click Open New Google Colab Notebook (opens in a new tab).
Click on the first empty code cell, press Ctrl + V (or Cmd + V) to paste, then press Shift + Enter to execute!

Launch Blank Colab Notebook

🔄 Algorithmic Execution Flow

Superposition Initialization

Apply Hadamard gates to initialize both qubits into uniform equal superposition.

→

Oracle Invocation

The CZ gate adds a -1 phase to target state |11>, marking it without altering classical probabilities.

→

Diffusion Transformation

The H-X-CZ-X-H sequence inverts amplitudes about their mean, amplifying |11> to 100% amplitude.

→

Measurement Verification

1,000 shots on AerSimulator reveal 100% probability for the marked target |11> in a single query.

📥 Input / Initial State

2-qubit circuit initialized to |00>, CZ oracle targeting |11>, and Grover diffusion operator.

📤 Expected Output

Grover Search Measurement Results (Lesson 9): {'11': 1000}

💡 What Does This Demonstration Show?

Demonstrates quadratic speedup: in an unsorted 4-item search space, Grover algorithm finds target |11> in exactly one quantum iteration with 100% deterministic success.

Course Learning Resource • Slide DeckLesson 910 Slides

Lesson 9: Grover Search and Amplitude Amplification

Oracle, diffusion operator, interference, and quadratic search speedup — Presentation by Dr. Syed Muzamil Basha.

Author: Dr. Syed Muzamil Basha• FDP Approved Curriculum

Open in New Tab

📝 Learning Check

Test your understanding with these questions. Remember, this is for learning, not examination!

Question 1: What happens if you run Grover’s algorithm for too many iterations (e.g., 20 iterations when the optimal count was 6)?

Question 2: What is the speedup of Grover's algorithm?

Question 3: What is amplitude amplification in Grover's?

Question 4: What is the Grover diffusion operator?

Question 5: How many Grover iterations for N=1024 items?

Previous: The Deutsch-Jozsa Algorithm: First Proof of Quantum Speedup Next: The Quantum Fourier Transform (QFT): The Powerhouse of Shor’s Algorithm

1	from qiskit import QuantumCircuit
2	from qiskit.visualization import plot_histogram
3	from qiskit_aer import Aer
4	import matplotlib.pyplot as plt

1	# =========================================================
2	# Lesson 9: Grover Search and Amplitude Amplification
3	# Prepared for Google Colab (Run with Shift + Enter)
4	# =========================================================
5
6	# Step 1: Install required packages
7	!pip install qiskit qiskit-aer matplotlib
8
9	# Step 2: Import libraries
10	from qiskit import QuantumCircuit
11	from qiskit.visualization import plot_histogram
12	from qiskit_aer import Aer
13	import matplotlib.pyplot as plt
14
15	# Step 3: Run Demonstration
16	# Define the Oracle (marks the \|11⟩ state)
17	def grover_oracle():
18	oracle = QuantumCircuit(2)
19	oracle.cz(0, 1) # Controlled-Z gate to mark \|11⟩
20	return oracle
21
22	# Define the Diffusion Operator (amplifies the correct state)
23	def diffusion_operator():
24	diffusion = QuantumCircuit(2)
25	diffusion.h([0, 1]) # Apply Hadamard gates
26	diffusion.x([0, 1]) # Apply X gates
27	diffusion.cz(0, 1) # Apply Controlled-Z gate
28	diffusion.x([0, 1]) # Apply X gates again
29	diffusion.h([0, 1]) # Apply Hadamard gates again
30	return diffusion
31
32	# Create a 2-qubit quantum circuit
33	qc = QuantumCircuit(2, 2)
34
35	# Step 1: Initialize with Hadamard gates
36	qc.h([0, 1])
37
38	# Step 2: Apply Grover's Oracle using .compose()
39	qc = qc.compose(grover_oracle())
40
41	# Step 3: Apply the Diffusion Operator using .compose()
42	qc = qc.compose(diffusion_operator())
43
44	# Step 4: Measure the qubits
45	qc.measure([0, 1], [0, 1])
46
47	# Execute on Aer simulator
48	simulator = Aer.get_backend('aer_simulator')
49	job = simulator.run(qc, shots=1000)
50	result = job.result()
51	counts = result.get_counts(qc)
52	print("Grover Search Measurement Results (Lesson 9):", counts)
53	plot_histogram(counts)
54	plt.show()