67. Project 2 — Quantum Algorithm Laboratory

Implement: Deutsch, Deutsch–Jozsa, Bernstein–Vazirani, Simon, Grover, QFT, phase estimation, Shor. (Chapter-by-chapter: 19–26.)

Specification. A package qalgo built on your Project 1 simulator (primary) and Qiskit (cross-check), with one module per algorithm, each exposing: the oracle interface it needs, the circuit constructor, a run(shots) method, and a verifier — code that checks the guarantee (Deutsch: one query, correct f(0)⊕f(1) every shot; DJ: deterministic constant/balanced answer; BV: exact a; Simon: linear-algebra post-processing recovering s from ~2n samples; Grover: marked-state probability peaking at the theoretical ⌊(π/4)√(2ⁿ/η)⌋ iterations — plot the oscillation; QFT: verify against exact DFT matrix on random states; PEP: eigenphase recovery to k bits with the right success probability; Shor: full pipeline on N=15 and N=21 — modular exponentiation circuits, QFT, continued-fraction post-processing, factor found in ≥ some fraction of runs).

Milestones. M1: the four oracle algorithms with verifiers green. M2: QFT exact-matrix validation + approximate-QFT (dropped rotations) error vs. savings. M3: phase estimation with success-probability curve. M4: Shor N=15 factoring end-to-end (both coprime bases), then N=21. M5: noise module — run each algorithm under depolarizing noise swept 0.1–5%, chart failure thresholds.

Acceptance criteria. Every algorithm reproduces its theoretical behavior in an automated test (deterministic exactness where promised, correct success probabilities where probabilistic); Shor factors 15 and 21 with documented success rates; the noise-threshold figure exists and its ordering (Grover fragile vs. DJ robust, etc.) is explained in the README from the mathematics.

What it proves. Part VII internalized at the level where you could debug someone else's algorithm implementation. Effort: 3–4 weekends.