First time studying this topic?

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

Topic 7.6

Quantum Algorithm Simulation: Module 7 Capstone

Synthesize Module 7: implement, simulate, and verify Shor’s period-finding core and Grover’s search in an end-to-end Python pipeline.

Learning Objectives

✓Execute a complete Grover Search algorithm pipeline from state preparation to measurement
✓Verify quadratic probability scaling and theoretical convergence bounds
✓Inspect statevector phase inversions and diffusion step-by-step

📖Let's Begin with a Story

You have arrived at the pinnacle of quantum computing theory: assembling full quantum algorithms. In this Module 7 Capstone, you will tie together Superposition, Phase Oracles, and the Diffusion Operator to execute an automated search algorithm that finds a secret marked number in an unstructured database. You will step through the computational stages, monitor how the quantum amplitudes evolve from uniform uncertainty into a towering 100% probability peak, and verify the physical reality of quantum computational advantage.

Why Should You Learn Quantum Algorithm Simulation: Module 7 Capstone?

🎯 Practical & Engineering Stakes

Full algorithmic synthesis

Understanding individual gates is grammar; orchestrating them into a complete quantum algorithm is poetry. Completing this capstone demonstrates mastery of quantum algorithmic design.

What Is It?

Simple Explanation

In this capstone, we put all the pieces together: 1. Initialize qubits in equal superposition. 2. The mystery Oracle flips the phase of our secret target. 3. The Diffusion operator reflects all amplitudes across the average. 4. Measure: the secret number pops out with certainty!

Technical Explanation

End-to-end execution of Grover’s algorithm on

n=2

(

N=4

) register solving pre-image search for Boolean oracle

f(x) = \delta_{x, \omega}

. The algorithm applies Hadamard transform

H^{\otimes 2}

, Phase Oracle

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

, and Diffusion operator

D = 2|s\rangle\langle s| - I = H^{\otimes 2} (2|0\rangle\langle 0| - I) H^{\otimes 2}

, terminating with projective computational basis readout.

📚 Key Terms

Algorithmic Fidelity

Simple: A percentage showing how close the real quantum output is to the perfect math answer.

Technical: State overlap fidelity

F(\rho, \sigma) = \left(\text{Tr}\sqrt{\sqrt{\rho}\sigma\sqrt{\rho}}\right)^2

Success Probability

Simple: The exact percentage chance of measuring the right answer at the end.

Technical: The Born probability

P(\omega) = |\langle \omega | \psi_{\text{final}} \rangle|^2

Q-Sphere Lab: Quantum Algorithm Simulation: Module 7 Capstone

IBM Q-Sphere Model

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

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

P(\text{Success}) = \sin^2\left( \frac{2k+1}{2} \theta \right), \quad \theta = 2 \arcsin\left( \frac{1}{\sqrt{N}} \right)

What does it mean?

Analytical Success Probability of Grover’s Algorithm: Describes the geometric trajectory of the quantum state rotating toward the marked solution in 2D Hilbert space. Executing k iterations rotates the state by (2k+1)θ/2. If you execute too many iterations, the probability "overshoots" and begins decreasing!

Understanding the Symbols

Symbol / Term	Meaning	Beginner Interpretation
$k$	Executed iteration count	Number of Grover loop passes executed so far
$\theta$	Angular rotation per Grover step	2 arcsin(1/√N), the angle rotated toward the solution per step
$N$	Database size	Total entries in the search space ( $2^n$ )
$P(\text{Success})$	Probability of measuring target item	Peaks near 100% when $(2k+1)\theta/2 \approx \pi/2$

📊 Numerical Example

Calculating the success probability for N = 8 items (3 qubits) at k = 1 and k = 2 iterations:

Step 1: Calculate angle θ for N = 8: 1/√8 = 1 / 2.8284 ≈ 0.3536 arcsin(0.3536) ≈ 0.3614 radians (20.7°) θ = 2 × 0.3614 = 0.7227 radians (41.4°) Step 2: Evaluate at k = 1 iteration: Angle = (2(1) + 1)/2 × θ = (3/2) × 0.7227 = 1.0841 radians (62.1°) P_success = sin^2(1.0841) = (0.8839)^2 ≈ 0.781 (78.1%) Step 3: Evaluate at k = 2 iterations: Angle = (2(2) + 1)/2 × θ = (5/2) × 0.7227 = 1.8068 radians (103.5°) P_success = sin^2(1.8068) = (0.972)^2 ≈ 0.945 (94.5%)

Result: At k = 2 iterations, the success probability reaches 94.5%, finding the secret item among 8 choices with high confidence.

⚙️ How Does It Work?

State Preparation

Apply Hadamard gates to initialize state |s>.

Oracle Invocation

Apply phase oracle marking the target state.

Diffusion Reflection

Invert amplitudes across the mean.

Readout

Sample measurement distribution to extract the target.

🌍 Where Is It Used?

Database Acceleration

Problem: Locating records across unsorted genomic gene banks.

Solution: Grover acceleration cuts database queries quadratically.

🎯 Try It Yourself

For a 2-qubit database (N = 4 items), what is the theoretical success probability of Grover’s search after exactly 1 iteration?

Interactive activity component

🐍 Python Hands-On: Simulating Shor's Period-Finding Circuit on AerSimulator in Qiskit

Construct and simulate a quantum period-finding circuit in Qiskit Aer to uncover periodic modular exponentiation frequencies.

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 numpy

Packages:

qiskitqiskit-aernumpy

2Import Libraries

Import Statementspython

1 from qiskit import QuantumCircuit
2 from qiskit_aer import AerSimulator
3 import numpy as np

from qiskit import QuantumCircuit → Circuit module

from qiskit_aer import AerSimulator → Aer simulator

import numpy as np → Math utilities

3Demonstration Code & Logic

Python Execution Codepython

1 # Simplified Quantum Period Finding Circuit for a=7, N=15 (Period r=4)
2 # Using 3 counting qubits and 2 work qubits
3 qc = QuantumCircuit(4, 2)
4 qc.h([0, 1])  # Superposition on counting register
5 qc.x(2)       # Initialize work register to |1>
6 # Controlled modular multiplication gates
7 qc.cx(0, 3)    # Controlled modular operation 1
8 qc.cx(1, 2)    # Controlled modular operation 2
9 # Inverse QFT on counting register
10 qc.h(0)
11 qc.cp(-np.pi / 2, 1, 0)
12 qc.h(1)
13 qc.measure([0, 1], [0, 1])
14 print('Quantum Period-Finding Circuit Diagram:')
15 print(qc.draw('text'))
16  
17 # Simulate with AerSimulator
18 sim = AerSimulator()
19 counts = sim.run(qc, shots=1024).result().get_counts()
20 print('\nMeasured Frequencies on Counting Register (1024 shots):')
21 for state, freq in sorted(counts.items()):
22     print(f'  State \'{state}\' : {freq} shots ({freq/1024*100:.1f}%)')
23 print('\nPeaks at specific bitstrings reveal the period r=4, cracking RSA key factors!')

Step-by-Step Code Breakdown:

# Simplified Quantum Period Finding Circuit for a=7, N=15 (Period r=4)

Setup

# Using 3 counting qubits and 2 work qubits

qc = QuantumCircuit(4, 2)

4 qubits, 2 classical readout bits

qc.h([0, 1]) # Superposition on counting register

Counting superposition

qc.x(2) # Initialize work register to |1>

Work register to 1

# Controlled modular multiplication gates

Controlled gates

qc.cx(0, 3) # Controlled modular operation 1

Controlled op 1

qc.cx(1, 2) # Controlled modular operation 2

Controlled op 2

# Inverse QFT on counting register

Inverse QFT

qc.h(0)

Inverse H

qc.cp(-np.pi / 2, 1, 0)

Inverse CP

qc.h(1)

Inverse H

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

Measure counting register

print('Quantum Period-Finding Circuit Diagram:')

Label

print(qc.draw('text'))

Print diagram

# Simulate with AerSimulator

Simulation

sim = AerSimulator()

Backend

counts = sim.run(qc, shots=1024).result().get_counts()

Run 1024 shots

print('\nMeasured Frequencies on Counting Register (1024 shots):')

Counts label

for state, freq in sorted(counts.items()):

Iterate counts

print(f' State \'{state}\' : {freq} shots ({freq/1024*100:.1f}%)')

Print frequency

print('\nPeaks at specific bitstrings reveal the period r=4, cracking RSA key factors!')

Conclusion

📋 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 # Simulating Shor's Period-Finding Circuit on AerSimulator in Qiskit
3 # Prepared for Google Colab (Run with Shift + Enter)
4 # =========================================================
5  
6 # Step 1: Install required packages
7 !pip install qiskit qiskit-aer numpy
8  
9 # Step 2: Import libraries
10 from qiskit import QuantumCircuit
11 from qiskit_aer import AerSimulator
12 import numpy as np
13  
14 # Step 3: Run Demonstration
15 # Simplified Quantum Period Finding Circuit for a=7, N=15 (Period r=4)
16 # Using 3 counting qubits and 2 work qubits
17 qc = QuantumCircuit(4, 2)
18 qc.h([0, 1])  # Superposition on counting register
19 qc.x(2)       # Initialize work register to |1>
20 # Controlled modular multiplication gates
21 qc.cx(0, 3)    # Controlled modular operation 1
22 qc.cx(1, 2)    # Controlled modular operation 2
23 # Inverse QFT on counting register
24 qc.h(0)
25 qc.cp(-np.pi / 2, 1, 0)
26 qc.h(1)
27 qc.measure([0, 1], [0, 1])
28 print('Quantum Period-Finding Circuit Diagram:')
29 print(qc.draw('text'))
30  
31 # Simulate with AerSimulator
32 sim = AerSimulator()
33 counts = sim.run(qc, shots=1024).result().get_counts()
34 print('\nMeasured Frequencies on Counting Register (1024 shots):')
35 for state, freq in sorted(counts.items()):
36     print(f'  State \'{state}\' : {freq} shots ({freq/1024*100:.1f}%)')
37 print('\nPeaks at specific bitstrings reveal the period r=4, cracking RSA key factors!')

⚡ 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

Counting Register Superposition

Apply Hadamards to generate parallel query register.

→

Modular Exponentiation

Apply controlled operations that encode the periodic modular function f(x) = a^x mod N.

→

Inverse QFT & Measurement

Extract period peaks from phase interference, enabling classical GCD factorization.

📥 Input / Initial State

Quantum period-finding circuit evaluated over 1024 shots on AerSimulator.

📤 Expected Output

Measured peaks at states '00' (~512 shots) and '10' (~512 shots).
Identifies period r = 4 for modular base a=7 mod 15.

💡 What Does This Demonstration Show?

Shor's algorithm reduces integer factorization to period finding. Quantum interference isolates the period in polynomial time O((log N)^3), breaking RSA encryption which relies on the classical difficulty of factoring.

Course Learning Resource • Slide DeckLesson 910 Slides

Lesson 9: Grover Search and Amplitude Amplification

Oracle, diffusion operator, interference, and quadratic search speedup.

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 mathematical operation does the Diffusion operator D = 2|s><s| - I perform on the probability amplitudes of the quantum register?

Question 2: What limits classical simulation of quantum algorithms?

Question 3: What is Qiskit Aer simulator?

Question 4: What is the difference between statevector and sampling simulation?

Question 5: What tools validate quantum algorithm correctness?

Previous: The Quantum Fourier Transform (QFT): The Powerhouse of Shor’s Algorithm Next: What is Quantum Machine Learning (QML)?

1	from qiskit import QuantumCircuit
2	from qiskit_aer import AerSimulator
3	import numpy as np

1	# =========================================================
2	# Simulating Shor's Period-Finding Circuit on AerSimulator in Qiskit
3	# Prepared for Google Colab (Run with Shift + Enter)
4	# =========================================================
5
6	# Step 1: Install required packages
7	!pip install qiskit qiskit-aer numpy
8
9	# Step 2: Import libraries
10	from qiskit import QuantumCircuit
11	from qiskit_aer import AerSimulator
12	import numpy as np
13
14	# Step 3: Run Demonstration
15	# Simplified Quantum Period Finding Circuit for a=7, N=15 (Period r=4)
16	# Using 3 counting qubits and 2 work qubits
17	qc = QuantumCircuit(4, 2)
18	qc.h([0, 1]) # Superposition on counting register
19	qc.x(2) # Initialize work register to \|1>
20	# Controlled modular multiplication gates
21	qc.cx(0, 3) # Controlled modular operation 1
22	qc.cx(1, 2) # Controlled modular operation 2
23	# Inverse QFT on counting register
24	qc.h(0)
25	qc.cp(-np.pi / 2, 1, 0)
26	qc.h(1)
27	qc.measure([0, 1], [0, 1])
28	print('Quantum Period-Finding Circuit Diagram:')
29	print(qc.draw('text'))
30
31	# Simulate with AerSimulator
32	sim = AerSimulator()
33	counts = sim.run(qc, shots=1024).result().get_counts()
34	print('\nMeasured Frequencies on Counting Register (1024 shots):')
35	for state, freq in sorted(counts.items()):
36	print(f' State \'{state}\' : {freq} shots ({freq/1024*100:.1f}%)')
37	print('\nPeaks at specific bitstrings reveal the period r=4, cracking RSA key factors!')