Modular arithmetic kit + real small-N Shor
mul_const_mod / pow_const_mod on the same ripple-carry shape as G2. Real period-finding for N = 15.
Results · real Selene shots
real_modexp_period_verified · work_orbit_intactReal quantum modular exponentiation for (a=2, N=15) on 4+4 qubits. Controlled mul-by-2 / mul-by-4 (mod 15) implemented as CSWAP-chain cyclic shifts. 2048 Selene shots: peaks land exactly at {0,4,8,12} (peak share 100%), continued-fractions recovers r=4, and the work register stays inside the orbit {1,2,4,8} on every single shot.
Why this matters
G2's add_const_controlled is the only modular primitive in the repo. Real period-finding requires controlled modular multiplication on the work register, not a compiled-oracle shortcut. With cmul_2_mod15 and cmul_4_mod15 in hand, full Shor for (a=2, N=15) becomes a 250-line driver.
What the repo already has
Real controlled mul-by-2-mod-15 and mul-by-4-mod-15 (CSWAP-chain cyclic shifts) in quantum/nadarasa_g11_real.py, wired into the existing QPE + continued-fractions backend.
What's missing
Generic mul_const_mod for arbitrary N is future work (would require ancilla-based modular adders à la Beauregard). For the N=15 case the cyclic-shift implementation is exact on the orbit the algorithm actually reaches.
Smallest experiment
Build it or kill itQubits
4 control + 4 work = 8 qubits
Ancilla pattern
None for N=15. Work register holds a true superposition of modular powers throughout.
Shots
2048 shots; QPE on 4 control qubits; continued-fractions decode.
Predicted outcome
Histogram of QFT readout peaks exactly at {0, 4, 8, 12} = j·2^m/r for r=ord_15(2)=4. Continued-fractions decode recovers r=4. Work register stays in the orbit {1, 2, 4, 8} on 100% of shots.
Refutation criterion
If recovered_period ≠ 4, or peak_share on expected < 0.90, or the work register ever lands outside {1, 2, 4, 8}, the mul-mod-15 circuit is buggy.
Kernel sketch
Untested — sketch only@guppy
def cswap(c: qubit, a: qubit, b: qubit) -> None:
cx(b, a); toffoli(c, a, b); cx(b, a)
@guppy
def cmul2_mod15(c, w0, w1, w2, w3) -> None:
# Controlled mul-by-2 mod 15 = left cyclic shift by 1
cswap(c, w3, w2); cswap(c, w2, w1); cswap(c, w1, w0)
@guppy
def cmul4_mod15(c, w0, w1, w2, w3) -> None:
# Controlled mul-by-4 mod 15 = left cyclic shift by 2
cswap(c, w0, w2); cswap(c, w1, w3)
# pow_const_mod for a = 2, N = 15:
cmul2_mod15(c0, w0, w1, w2, w3) # 2^(2^0) mod 15 = 2
cmul4_mod15(c1, w0, w1, w2, w3) # 2^(2^1) mod 15 = 4
# c2, c3 → mul by 1 (identity, omitted)Host pipeline
Compile once → 2048 shots on 8 qubits → measured control bits → continued-fractions → recovered r. Sanity: work-register histogram must concentrate on {1,2,4,8}.
Related
Files in this repo
- · quantum/nadarasa_g11_real.py
- · src/data/demos/nadarasa_g11_real.json
- · quantum/nadarasa_g11.py
- · quantum/nadarasa_g11_lib.py
- · src/routes/nadarasa.g11.tsx