This run was recorded in April 2026 against a Shor kernel that did not find the period, rewritten in September 2026. The shot distribution below is a real measurement, but it is a measurement of a program that no longer exists in this repository, and it has not been re-run against the current kernel.

Shor's algorithm is the canonical example of superpolynomial quantum speedup. Utility requires factoring 2048+ bit integers our 4-bit toy instance demonstrates the algorithm but is far from utility scale.

Problem 09 · Quantum-Accelerated Integer Factorization

Overview

Breaking large RSA-style moduli showcases a flagship quantum advantage through Shor's algorithm. While practical quantum hardware remains distant, we can benchmark classical factoring effort and prepare a Q# scaffold for modular exponentiation, quantum Fourier transforms, and order finding experiments. This problem introduces a Pollard Rho classical baseline to estimate computational effort per instance and enables future integration with full period-finding implementations.

Directory Layout

09_factorization/
├── estimates/                  # JSON artifacts from classical / quantum workflows
├── instances/                  # Semi-prime inputs across difficulty scales
├── plots/                      # Generated figures from analyze.py
├── python/
│   ├── classical_baseline.py   # Pollard Rho factoring statistics per modulus
│   └── analyze.py              # Visualization of iterations / speed trends
└── qsharp/
    ├── qsharp.json            # Modern QDK project file
    └── Program.qs              # Placeholder quantum workflow

Quick Start

cd problems/09_factorization

# Classical factoring baseline (writes estimates/classical_baseline.json)
python python/classical_baseline.py

# Visualize iteration counts and effort
python python/analyze.py

# Quantum placeholder
 python -c "import qsharp; qsharp.init(project_root='qsharp'); print('Build OK')"
 python tooling/run_all_qsharp.py  # runs via qsharp Python package

Next Quantum Milestones

1. Modular Exponentiation Kernel – Implement square-and-multiply circuits with controlled modular multipliers.

2. Quantum Fourier Transform – Integrate QFT-based phase estimation for order finding.

3. Semi-Prime Order Finding – Simulate Shor's algorithm for 15, 21, and 35; extend to 3–4 qubit work registers.

4. Resource Estimation – Analyze logical qubit counts and T-depth for RSA-1024 style moduli via Azure Quantum tools.

This scaffold keeps the classical baseline reproducible while we iterate toward full-scale quantum period finding demonstrations. 🔐⚛️

Objective Maturity Gate

• **Current gate**: **Stage C complete** (hardware-aware validation evidence in place: Shor period-finding workflow runnable, calibration ensemble across runs, backend assumptions documented, estimator profile produced for both ns-e3 superconducting and surface-code-generic models, OpenQASM kernel `shor_n15_a7.qasm` exported for cross-platform validation).
• **Next gate target**: **Stage D** (advantage evidence package hardening: fairness review against GNFS baseline, RSA-2048 scaling extrapolation with residual-risk callouts, claim category locked).

Stage C evidence references for this problem:

• Calibration ensemble: `estimates/quantum_calibration_ensemble.json`, regenerated on 2026-09-25 after three corrections that day: the modular multiplier was right only for a = 2 and 4, the inverse QFT left the counting register uniform whatever the period, and the hardware kernel controlled its one multiplication from the wrong qubit. `estimates/calibration_evidence.json` (2026-03-25) predates them. `tooling/test_shor_kernel.py` now checks the multiplication table, the period for every coprime base, and the kernel.
• Backend assumptions: `estimates/backend_assumptions.md`.
• Estimator profile (ns-e3 + surface-code-generic): `estimates/estimator_profile_summary.md`, `estimates/latest_qubit_gate_ns_e3.json`, `estimates/latest_surface_code_generic_v1.json`. The estimate runs `Main.ShorPeriodFinding(7, 4)`; until 2026-09-25 it ran base 3, which shares a factor with 15, so it contained no modular arithmetic.
• Cross-platform OpenQASM export: `estimates/shor_n15_a7.qasm`, OpenQASM 3 and the same circuit as `qsharp/HardwareKernel.qs`.
• Azure smoke validation: `estimates/azure_smoke_report_small_d1.md`, `estimates/azure_job_manifest_small_d1.json` (2026-03-06, the kernel before the correction; the corrected kernel has not been submitted).
• Reproducible quantum kernel: `qsharp/src/Main.qs` runnable via `qsharp.run('Main.RunShorFactorization()', 1)`.

DiVincenzo Readiness (Stage C/D Overlay)

| Criterion | Status | Evidence / Notes |

|---|---|---|

| Scalable qubit system | partial | Problem-scoped instance baselines are in place; full hardware-scale projections are tracked as Stage C work. |

| Initialization | partial | Input/state initialization path is defined for current workflows, with backend-ready loading fidelity still to be hardened. |

| Coherence vs gate time | not-yet | Backend-calibrated coherence-vs-depth evidence is pending and required for Stage C/D promotion. |

| Universal gate set | partial | Q# scaffold/build path exists; gate-basis decomposition and transpilation evidence remain Stage C tasks. |

| Qubit-specific measurement | partial | Measurement outputs are defined for current validation flows; hardware readout characterization is pending. |

Advantage Claim Contract

• **Claim category (current)**: `theoretical`.
• **Problem class and regime**: Problem-specific challenge instances defined in this directory.
• **Fair baseline**: Problem-local classical baseline in `python/` outputs.
• **Quantum resource scaling claim**: Expected asymptotic advantage depends on algorithm family and implementation assumptions; no hardware-demonstrated speedup claim yet.
• **Data-loading and I/O assumptions**: Must be documented alongside future advantage claims.
• **Noise/error model assumptions**: Backend-specific model and calibration assumptions to be added at Stage C.
• **Confidence/uncertainty method**: To be reported using shot-based confidence intervals or equivalent statistical bounds.
• **Residual risks**: Oracle/state-preparation/transpilation overhead may dominate for near-term instance sizes.