Educational Shor Walkthrough

Factoring 15, one visible circuit step at a time.

This guide explains the small-scale Shor-style factorization path in miniQ. The goal is to show the shape of the algorithm on N = 15, not to provide cryptographic-scale factoring.

What miniQ Demonstrates

The factor-15 path combines a counting register, a work register, modular exponentiation, work-register measurement, inverse QFT, phase-to-period recovery, and classical factor extraction.

Example Sequence

Run these examples in order to see the circuit assembled, measured, transformed, and postprocessed.

01

Start With Modular Exponentiation

Inspect the reversible arithmetic block used by the circuit.

modular exponentiation 
cargo run --example modular_exponentiation_demo
02

Inspect Order Finding Before Measurement

See the counting and work registers after modular exponentiation.

order-finding circuit 
cargo run --example shor_order_finding_circuit_15
03

Measure The Work Register

Measurement collapses the counting register into a periodic pattern tied to the hidden period.

work-register measurement 
cargo run --example shor_work_measurement_15
04

Recover A Phase Sample

Apply inverse QFT, measure the counting register, and try to recover the period with continued fractions.

period recovery 
cargo run --example shor_period_recovery_15
05

Run The Retrying Factor-15 Example

Some measurements are uninformative, so this example repeats the attempt until it finds nontrivial factors or reaches its limit.

factor 15 
cargo run --example shor_factor_15

Register Layout

miniQ uses little-endian register indexing. Displayed bitstrings are MSB-first, so the left side of a printed label corresponds to the highest-index qubits.

  • work register: qubits [0, 1, 2, 3]
  • counting register: qubits [4, 5, 6]

Why This Is Not RSA Factoring

This walkthrough runs on a classical state-vector simulator. The memory required by the simulator doubles with every added qubit. RSA-scale Shor factoring would require fault-tolerant quantum hardware, many logical and physical qubits, error correction, and far deeper coherent computation than miniQ can represent.

The factor-15 path is intentionally small-scale and educational.