Implementation and Demonstration of Shor's Algorithm for Integer Factorization Using Qiskit

This project implements and demonstrates the core workflow of Shor's quantum factoring algorithm using Qiskit and Qiskit Aer simulation.

The implementation focuses on integer factorization for N = 15 and demonstrates the interaction between quantum period finding and classical post-processing.

The project includes:

• Quantum period estimation using the inverse Quantum Fourier Transform
• Reversible modular multiplication
• Controlled modular exponentiation
• Randomized base selection
• Classical GCD-based factor detection
• Classical factor recovery from the detected period
• Controlled quantum measurement experiments
• 200-trial experimental analysis
• Statistical and visual analysis of experimental outcomes
• Reproducible simulation using seeded execution

Scope: This project uses an ideal Qiskit Aer simulator. No noisy hardware simulation or execution on real quantum hardware is included.

The main objectives of this project are:

1. Implement the period-finding component of Shor's algorithm using Qiskit.
2. Demonstrate reversible modular multiplication and controlled modular exponentiation for N = 15.
3. Estimate the multiplicative period from quantum measurements.
4. Recover non-trivial factors through classical post-processing.
5. Demonstrate both GCD and quantum execution branches.
6. Experimentally evaluate the implementation across randomized trials.
7. Analyze successful and failed factorization attempts.
8. Provide reproducible quantum simulation results.

For a selected base a, the implementation follows:

Randomly select a
       │
       ▼
Calculate gcd(a, N)
       │
       ├── gcd(a, N) > 1
       │       │
       │       ▼
       │   Immediate factor found
       │
       └── gcd(a, N) = 1
               │
               ▼
       Prepare quantum registers
               │
               ▼
       Controlled modular exponentiation
               │
               ▼
       Inverse Quantum Fourier Transform
               │
               ▼
          Measurement
               │
               ▼
        Period estimation
               │
               ▼
       Classical factor recovery
               │
               ▼
          Factorization

For the quantum branch, the implementation uses a 4-qubit counting register and a 4-qubit work register.

For each counting qubit j, the modular multiplier

a^(2^j) mod N

is constructed and applied as a controlled operation.

The inverse QFT is then applied to the counting register. Measurement results are converted into phase estimates and candidate periods are verified using modular arithmetic.

For an even period r, classical post-processing attempts to recover factors using:

x = a^(r/2) mod N

gcd(x - 1, N)
gcd(x + 1, N)

A reversible modular multiplication operation is constructed using a unitary matrix:

|y> → |a*y mod N>

for computational basis states satisfying y < N.

States outside the modular range are left unchanged so that the operation remains a valid permutation over the complete computational basis.

For N = 15, four work qubits provide 16 computational basis states, allowing the operation to be represented as a 16 × 16 unitary matrix.

Measured values are converted into phases using:

phase = measured_value / 2^counting_qubits

A rational approximation is obtained using a continued-fraction-based approach through Python's Fraction.limit_denominator().

Candidate periods are then verified by checking:

a^r mod N = 1

When an even period is detected, the implementation calculates:

x = a^(r/2) mod N

and attempts to obtain non-trivial factors through the two GCD operations.

A result is accepted only when both recovered values are non-trivial and smaller than N.

The implementation was evaluated using 200 randomized trials for:

N = 15

The complete experimental dataset is stored in:

results/experiment_results.csv

The experiment randomly selects bases from:

a ∈ {2, 3, 4, ..., 14}

The observed selection frequencies are analyzed and visualized in:

results/base_selection_frequency.png

The detected quantum periods in the 200-trial experiment were:

r = 2 → 48 trials
r = 4 → 62 trials

Visualization:

results/period_distribution.png

The complete sequence of GCD branches, successful quantum outcomes, and quantum failures is visualized in:

results/trial_outcomes.png

A separate controlled quantum measurement experiment records the measurement bitstrings, integer values, counts, and probabilities.

The dataset is stored in:

results/measurement_results.csv

and visualized in:

results/measurement_distribution.png

The 200-trial experiment produced:

14 failed trials

All 14 failures occurred for:

a = 14

For this base:

gcd(14, 15) = 1

The quantum period-finding procedure successfully detects:

r = 2

However, classical post-processing produces trivial factors rather than two non-trivial factors.

Therefore these trials are recorded as quantum-branch failures.

This demonstrates an important property of the factoring procedure:

Correct period detection does not necessarily guarantee successful factor recovery.

The verified failure trials can be examined directly in:

results/experiment_results.csv

The project also includes a controlled quantum demonstration using a fixed base.

Example:

N = 15
a = 2
gcd(2, 15) = 1
r = 4
15 = 3 × 5

The measurement distribution for this demonstration is stored in:

results/measurement_results.csv

The core implementation supports a seed parameter.

The seed controls:

• Python's randomized base selection
• Qiskit Aer simulator sampling through seed_simulator

Therefore, controlled demonstrations can reproduce the same base selection and quantum measurement counts when the same seed is used.

For example:

from src.shor_core import run_shor

result = run_shor(
    N=15,
    base=2,
    seed=42
)

print(result)

Shors-Algorithm-Qiskit/
│
├── results/
│   ├── base_selection_frequency.png
│   ├── experiment_results.csv
│   ├── measurement_distribution.png
│   ├── measurement_results.csv
│   ├── period_distribution.png
│   └── trial_outcomes.png
│
├── src/
│   ├── analyze.py
│   ├── experiment.py
│   ├── measurement_demo.py
│   ├── shor_core.py
│   ├── shor_n15.py
│   ├── visualize_measurements.py
│   ├── visualize_results.py
│   └── visualize_trials.py
│
├── .gitignore
├── requirements.txt
└── README.md

Clone the repository and create a virtual environment:

git clone <repository-url>
cd Shors-Algorithm-Qiskit

Create and activate the environment.

python -m venv .venv
.venv\Scripts\activate

python -m venv .venv
source .venv/bin/activate

Install the dependencies:

pip install -r requirements.txt

python src/shor_n15.py

python src/experiment.py

python src/analyze.py

python src/measurement_demo.py

python src/visualize_results.py
python src/visualize_measurements.py
python src/visualize_trials.py

This project is an educational and experimental demonstration of Shor's algorithm for the small composite number N = 15.

The implementation uses:

• A small fixed register size
• Explicit unitary matrices for modular multiplication
• Qiskit Aer simulation
• Ideal simulated quantum operations

It does not attempt to demonstrate the resource requirements or practical scalability of Shor's algorithm for cryptographically relevant integers.

No noisy quantum simulation or execution on real quantum hardware is included in the current project scope.

Possible extensions include:

• Testing larger composite integers
• More general modular arithmetic circuits
• Improved period-estimation methods
• Resource and circuit-depth analysis
• Noisy quantum simulation
• Execution on real quantum hardware
• Comparison of different quantum circuit implementations

• Python
• Qiskit
• Qiskit Aer
• NumPy
• Matplotlib
• Git / GitHub

Completed: Core implementation, controlled demonstrations, 200-trial experimental evaluation, failure analysis, reproducibility testing, and result visualization.

The repository contains the finalized implementation, experimental datasets, analysis scripts, and generated visualizations for the project.

This project was developed as a practical implementation following the completion of Qiskit Global Summer School 2026 training by IBM Quantum, with the objective of applying quantum computing concepts to a complete Shor's algorithm workflow.