lumbda/examples/cuda-fanout/plans/form-D-build-progress.md

Form D — build progress, halted 2026-06-05

Plan: form-D-clifford-stabilizer.md. Status: HALTED before kernel-write. No code committed. Reason below.

What ran

Step 0 of plan workflow only: Toffoli-fraction measurement on /tmp/ops.bin (716 MB, 12,788,119 ops, Phase B point-add-toy emission on this host).

Per-kind histogram:

kind	name	count	%
1	REGISTER	4	0.00%
2	APPEND_REG	1,024	0.01%
6	X	1,810,486	14.16%
8	CX	5,336,861	41.73%
9	CZ	1,319,391	10.32%
10	SWAP	447,076	3.50%
11	R	800,099	6.26%
12	HMR	1,300,167	10.17%
13	CCX	1,773,011	13.86%

• Toffoli fraction of all quantum ops: 13.87% — well under our 40% STOP threshold. Plan §3's "~half" suspicion did not hold.
• Amdahl ceiling on overall speedup, given Toffoli stays on CPU: 1 / (0.139 + 0.861 / S) where S is the Clifford-only speedup. At the plan's 186× target, overall hits ~6.9× — still meaningful, but the headline number does not apply.

That part of the answer is clean: fraction is fine, proceed gated on the next finding.

Why I stopped before writing the kernel

Re-reading ecdsa/cuda/sim.h & sim_gpu.cu against the plan exposed a structural mismatch:

1. Upstream Roetteler point-add (kinds 0–17 enumerated in sim.h) carries no Hadamard, no S, no Y, no measurement-onto-basis-rotation op. Search across ecdsa/lumbda/, ecdsa/cuda/, and ecdsafail-challenge/ for any H gate emission returned zero hits. The op histogram above is the entire op alphabet that ever fires.
2. With no H or S in the circuit, the quantum state never leaves the computational basis. The "stabilizer simulation" reduces to classical reversible computation + a global phase ledger. That is exactly what sim_gpu.cu's per-shot bit-packed simulator already does — and proven exactly correct for this gateset, not an approximation.
3. Aaronson-Gottesman tableau over 2n × (2n+1) bits gains us nothing we don't already have. Its parallelism win (row-XOR primitives, warp-cooperative tableau updates) shows up only when superposition matters — i.e., when H or S introduce mixed-basis states the per-shot simulator cannot represent in one bit per shot. We have none of that.
4. The existing simulator's 1.07× ceiling on a 3090 (per plan reference to sim_gpu.cu) traces to memory bandwidth on per-shot striped state, not to algorithm choice. Switching the algorithm to AG cannot help; switching the parallelism axis (per- candidate over per-shot, as the plan correctly identifies) might — but the axis flip belongs to the existing kernel, not a clean-room AG re-implementation.

What this means for Form D

The plan's headline target (186× from STABSim-class Clifford speedup) does not transfer because:

• Our circuit is a strict subset of Clifford that the existing kernel already handles exactly in one bit per shot.
• AG's wins come from compressing exponentially-large stabilizer state into 2n bits per shot; we already compress further (1 bit per qubit per shot) because we never leave |0⟩/|1⟩.

The correct Form D, if we still want a per-candidate axis flip, is a refactor of ecdsa/cuda/sim_gpu.cu that:

• maps one CUDA block to one candidate circuit instead of one thread to one batch of shots,
• keeps the existing bit-packed phase/qubits/bits state,
• moves cross-thread cooperation onto the candidate dimension (warp shares work per gate),
• continues to count CCX symbolically alongside the dynamic counter.

That is not a clean-room Aaronson-Gottesman implementation. It is "sim_gpu.cu, axis-flipped." I should not write a binary that pretends to be the former when our real bottleneck wants the latter.

Recommendation to fox

Three options, your call:

1. Re-scope Form D to "axis-flip refactor of existing sim_gpu.cu kernel, per-candidate parallelism." Drop AG framing entirely. Drop BSTB/BSTR magic — reuse BSHK with a new op_id. Aim for the kickmix speedup the plan actually wants. Effort ~3 days.

2. Build Form D as written (clean-room AG tableau) for circuits that do have H/S — e.g. error-correction codes, surface-code patches, future research workloads. Keep the kernel in cuda-fanout/ as a general capability not coupled to our point-add metric. Effort ~10 days, throughput gain on point-add is zero (no AG-eligible structure to exploit).

3. Park Form D, redirect engineering to options the kickmix actually rewards: ops.bin packing (reduce per-op bytes from 56 → 16 to halve global-memory traffic), or per-candidate sim_gpu.cu refactor (option 1 above), or revisit Form B/C numbers.

Hard rule from session: I do not commit broken code & I do not write a kernel that misroutes around the actual bottleneck. Halting here.

Files touched

None — no commit, no kernel write. This progress doc is the only artifact.

Numbers for CATALOG once a path forward is chosen

• Toffoli fraction (point-add-toy): 13.87% of quantum ops
• Op-mix dominated by CX (41.7%), X (14.2%), CCX (13.9%), CZ (10.3%), HMR (10.2%), R (6.3%), SWAP (3.5%)
• No H, no S, no Y in upstream point-add gateset — confirms computational-basis simulator is exact, not approximate.