A windowed, modally-restricted dihedral coset sieve: a conjectural sub-exponential improvement under a structured-reflection promise

1. Setup

Let G = D_N = Z_N ⋊ Z_2 with N = 2^n. Let H ≤ G be a hidden order-2 subgroup generated by a reflection r_s parameterized by slope s ∈ Z_N. Standard coset states have the form |0⟩|x⟩ + |1⟩|x + s⟩. We work under the structured-reflection promise (SRP): s ≡ s₀ (mod p) for known small prime p and known residue s₀, with the slope otherwise uniform mod N/p. SRP is the modal restriction; it is strictly more general than knowing s exactly and strictly less general than no promise.

2. Statement (conjectural)

Conjecture C1. Under SRP with fixed prime p, there exists a quantum algorithm solving the dihedral HSP with quantum query complexity 2^(c_p · √log N) where c_p < c_Kuperberg, and additional classical time 2^O(√log N · log p). The improvement factor c_Kuperberg / c_p tends to 1 as p → 1 (no promise) and to ≈ 1/√p as p grows, up to the obvious p ≪ N constraint.

3. Proof sketch

Step 3.1 (modal projection). After generating a coset state, apply a projector P_p,s₀ implemented by a quantum addition + comparison + uncompute pattern; success amplitude is 1/√p under SRP. [GAP G1] We claim the projected coset state's effective slope register lives in Z_{N/p}, reducing the sieve target size by factor p. Verifying that the projection commutes with the combination map up to phase requires a representation-theoretic argument we have not completed.

Step 3.2 (windowed combination). Partition the √log N sieve depth into k windows. Each window runs a Kuperberg combination on 2^(√log N / k) coset states held coherently. Between windows, the classical glue layer takes a measurement on a partial sum register and re-prepares the next window's input conditioned on the classical outcome. [GAP G2] We claim the partial measurement does not collapse the structurally relevant phase. The argument rests on the modal restriction making the relevant phase information classical, but we have not proved this; it is the central technical gap.

Step 3.3 (combination). Standard Kuperberg combination within each window; analysis carries over because the projected states have the same structural form. [GAP G3] Constant-factor analysis of the per-window query count is omitted; the conjectured factor √p is heuristic, based on the modal residue narrowing the search space.

4. Subroutine (Selene toy, G1) — v0.3 real-QFT readout

We implement Step 3.1 for N ∈ {16, 32} and p ∈ {2, 3, 5} in Guppy and execute on Selene. The kernel prepares the coset superposition, applies a controlled-phase ladder to encode the |x⟩ + ω^{s x} |1, x⟩ structure, mixes the label out, then applies a REAL little-endian QFT to the data register (controlled-phase ladder + bit-reversal SWAPs implemented as triple-CX).

Closed form: P(y | s) = (1/2)[δ_{y, 0} + δ_{y, (N − s) mod N}]. Two delta peaks of mass 1/2; concentration on (y mod p = 0) is C(s, p) = 1/2 + 1/2·𝟙{s ≡ N mod p}. Observed on Selene at 600 shots/slope: SRP branch lands at predicted within 0.013 across the entire grid. Verdict: `modal_projector_works_when_p_divides_N`.

• When p | N (rows N=16,p=2 and N=32,p=2): SRP concentration 1.000, violating 0.500, SRP−violating gap +0.499. The modal projector is exact — the kernel produces a perfect classical witness for SRP membership.

• When p ∤ N (rows for p=3 and p=5): SRP concentration 0.500, violating 0.620–0.750, SRP−violating gap NEGATIVE (≈ −0.25). The projector inverts: half the violating slopes happen to land on the second delta peak with (N − s) mod p = 0.

Migration note: the same kernel re-run through SweepRunner (`nadarasa_g1_via_sweep.py`) reproduces the verdict; the per-cell |observed − predicted| stays < 0.012.

Methodology note (the v0.2 → v0.3 fix): the v0.2 driver applied H^n + Z-basis readout and the docstring claimed it matched the Fourier-basis (1 + cos(2π s y / N))/N distribution. That is FALSE — H^n is the Walsh–Hadamard transform, not the QFT. The Phase 3 in-Worker mini-sim caught the mismatch the first time we tried to live-verify it: the histogram converged to the Walsh–Hadamard distribution, disagreeing with the docstring's analytic by ~0.4. We then derived the closed form for the actual circuit (Walsh–Hadamard + Z-basis), saw the gap was structural rather than a sampling artifact, and rewrote both the Guppy lib (adding `cphase_true_on` and an emitted bit-reversal QFT) and the mini-sim (adding `cphaseTrue` and `qft`) to execute the readout we actually wanted. The lesson — derive the predictor from the gates, not the docstring — is now a Quantinuum-skill reference.

@guppy
def coset_modal_z16(reg: array[qubit, 4], anc: qubit, s: int) -> None:
    # Prepare coset superposition |x> + |x+s>
    h(anc)
    for i in range(4):
        h(reg[i])
    # Controlled add of s into reg, controlled on anc
    add_const_controlled(reg, anc, s)
    # Modal projector: keep only outcomes where reg[0] == S0 (mod 2)
    if measure(reg[0]) != S0_BIT:
        discard(anc)
        for q in reg[1:]:
            discard(q)

5. Analogy ledger

• Modal jazz → Section 1 SRP and Step 3.1 projection. Breaks if the cryptographic instance has no natural residue structure (most do not — this is the price of the conjecture). • Polyphasic consolidation → Step 3.2 windowing. Breaks if classical glue destroys interference (this is [GAP G2]). • Wright wind tunnel → Sections 4–8 Selene toys. Breaks if toy-scale behavior does not extrapolate; calibration check is that the G4/G8/G9/G10/G11 primitive toys all PASS their refutation gates. • Game Boy constraint discipline → choosing dihedral with SRP rather than general lattice. Breaks if SRP cuts cryptographic relevance to zero. • TeX composability → the GAP-marker draft format itself.

6. Prior-art delta

Kuperberg 2003 (quant-ph/0302112) gives 2^O(√log N) without structural promise. Our conjecture assumes SRP — strictly weaker target, hopefully strictly cheaper algorithm. Kuperberg 2011 (1112.3333) improves constants via a different sieve combination tree; our windowing is orthogonal and could compose. Regev 2004 (quant-ph/0406151) trades query for space; we trade nothing for query, paying instead with the SRP assumption. Moore–Russell–Schulman 2008 (quant-ph/0501056) rules out polynomial strong-Fourier-sampling for dihedral generally; SRP changes the relevant representation-theoretic statement and the impossibility argument does not transfer automatically — verifying this is [GAP G4-MRS] (renamed from the original G4 to avoid clash with the Selene G4 feed-forward primitive demo).

7. QSP phase-finder primitive (G10)

A separate Selene toy (quantum/nadarasa_g10_phasefinder.py) closes the QSP/QSVT primitive loop end-to-end: take a target polynomial f(x) (here Chebyshev sign(x) on [-1, 1]); run a NumPy phase-finder loop (scipy.optimize Powell, 40 random restarts, loss = SSE + 8·worst-case over a 51-point grid) to recover a phase sequence φ̂; render the qsp_sequence kernel under φ̂; execute it on Selene and check `max |measured − target| < 0.05` over a 16-point x grid. Verdict: `qsp_phase_finder_verified`. This is the spectral-sharpener primitive named in the QSVT adjacent-primitive entry above — `<SeleneRunView />` rendering at /nadarasa/g10. Its role in the draft is calibration, not load-bearing: if the wind-tunnel can faithfully execute an arbitrary phase sequence on a degree-3 polynomial, the wind-tunnel is not the bottleneck for any future QSVT-style spectral-sharpener on the coset-combination operator.

8. Real Shor modexp primitive (G11)

A second primitive toy (quantum/nadarasa_g11_real.py) replaces the compiled-oracle shortcut of the original G11 with a real controlled `pow_const_mod` for a = 2, N = 15. The controlled mul-by-(2^(2^i) mod 15) on the 4-qubit work register is implemented as a controlled cyclic shift (CSWAP-chain): the work register, initialised to |0001⟩ = 1, cycles through the orbit {1, 2, 4, 8} of 2 mod 15. The shift IS the correct mul-mod on every state in that orbit — and only on that orbit; off-orbit states (3, 5, 6, 7, 9, ...) would diverge, but the QPE preparation never reaches them. QPE on a 4-bit control register with inverse-QFT-without-final-swap gives peaks at bins {0, 4, 8, 12} with peak share 1.0; continued-fractions recovers r = 4. Verdict: `real_modexp_period_verified`. Again calibration, not Conjecture C1 — but it certifies that the wind-tunnel can host a real period-finding pipeline, which means a future SRP-aware modexp surrogate could be benchmarked on the same rig.

1. Make the p | N precondition explicit in Conjecture C1 and Section 1; restate Step 3.1's success amplitude in that regime.
2. Apply the same Phase-3 live-sampler discipline to G2 (dihedral coset window): derive the predictor from the actual two-window kernel and rerun.
3. Survey the SQ-access dequantization literature to confirm SRP with p | N does NOT inadvertently expose an SQ structure.
4. Submit v0.3 to Zenodo for a DOI; cite the DOI on /cite.
5. Identify one collaborator from the HSP community and the lattice community to independently audit before any arXiv-style preprint.
6. Only then: consider a formal preprint, with conservative framing.

9. Failure modes (mapped to GAPs)

See the GAP table below. Each GAP has a concrete Selene-runnable refutation experiment. If the experiment fails, the corresponding step is dead and the draft is retracted or branched. G12 (modal-projection scaling) is the next extension and the v0.3 candidate — does the G1 SRP-vs-violating signal flip sign, narrow, or hold at N ∈ {64, 128} and p ∈ {2, 3, 5, 7}?

10. Next steps

See the explicit checklist below.