Order Finding Mod 15

This is the quantum core of Shor's algorithm. Build the controlled modular multiplications by a^(2^j) mod 15 yourself, run phase estimation, and let the counting register reveal the period of a^x mod 15.

Objective

build_order_finding(a, num_counting) returns a (t + 4)-qubit circuit with counting qubits 0..t-1 (qubit 0 = least significant bit) and a 4-qubit work register on t..t+3 (qubit t = least significant bit). Initialize the work register to |1> yourself. After the inverse QFT, the counting register must be uniform over {k * 2^t / r}, where r is the order of a mod 15, for a in {2, 7, 8, 11, 13}.

Constraints

• No unitary / permutation / PhaseEstimation shortcuts.
• The counting and work registers must actually be entangled by the multiplications.

Entry Point

Checks

• Exports build_order_finding(a, num_counting).
• Counting peaks, work-register orbit and entanglement are correct for a in {2, 7, 8, 11, 13}, t in {3, 4}.