Period finding with a real modular multiplier. The counting register shows all r peaks, and continued fractions plus a gcd give the factors.
The work register (wires 4-7) starts in |1⟩. Counting wire j controls U^(2^j), where U|y⟩ = |a·y mod N⟩ is a permutation of the work register built from multi-controlled X gates: each cycle of the permutation is split into transpositions, and each transposition is a short chain of Toffoli-style gates. Only the middle gate of each chain carries the counting control.
For N = 15 and a = 7 the order is r = 4, so after the inverse QFT the counting register lands on 0, 4, 8 or 12 with probability 1/4 each. A peak k gives k/16 ≈ s/4; continued fractions recover r = 4, and gcd(7² - 1, 15) = 3 and gcd(7² + 1, 15) = 5 finish the job. With a = 11 (order 2) the peaks are 0 and 8.
How it works
-
1
Work register
X 4 prepares |1⟩ = a^0 mod N on wires 4-7.
-
2
Counting superposition
H (0,1,2,3).
-
3
Controlled U^(2^j)
Wire 0 controls multiplication by 7, wire 1 by 7² mod 15 = 4; wires 2 and 3 would multiply by 1, so they need no gates.
-
4
Inverse QFT and readout
Peaks at 0, 4, 8, 12. Continued fractions on 4/16 or 12/16 give r = 4; the factors are 3 and 5.
// Shor.qubi is in the standard library: N = 15, a = 7, 4 counting + 4 work qubits (about 260 gates) Shor()
Function form: Shor(15, 7)
This example expands from a standard-library function. Open it in the simulator to see every gate.
State. Counting register in an equal superposition of 0, 4, 8 and 12, entangled with the work register holding 7^x mod 15.
P(counting = 0) = P(4) = P(8) = P(12) = 1/4. Reading 4 or 12 gives r = 4 and the factors 3 × 5.
| Basis | Amplitude | Probability |
|---|---|---|
|00010000⟩ (work 1, count 0) |
1/4 |
|
|00010100⟩ (work 1, count 4) |
1/4 |
|
|00011000⟩ (work 1, count 8) |
1/4 |
|
|00011100⟩ (work 1, count 12) |
1/4 |
Notes
- The static circuit has about 260 gates, so the docs show the library call; open it in the simulator to see every gate.
- N up to 57 is supported (six work qubits). Larger counting registers give more precision when r does not divide 2^t.
- A base with an odd order still finds the period, but the gcd step then needs another base.
Change parameters
The write-up above is for the default circuit. Use this control to generate other variants and load them in the simulator.