# Form D — `cuda-clifford-stabilizer` implementation plan

You will not build this binary yet. This document gives you (fox) a
fully-specified runway you can hand to a CUDA + quantum-sim engineer or
to a future blackops session. Catalog entry lives at
`CATALOG.md` (Form D). Numbers cited here all carry URLs.

## 1. Reference selection — what you can fork vs what you must write

Three candidates surveyed 2026-06-05:

- **STABSim** (Garner, Liu, Wang, Stein, Li — UW lead, seangarn@uw.edu)
  arXiv 2507.03092 https://arxiv.org/abs/2507.03092 . Warp-level CUDA
  primitives, scales better than CPU on QEC workloads. **No public
  repo.** GitHub search for `stabsim cuda` returns zero results
  https://github.com/search?q=stabsim+cuda&type=repositories . Treat as
  reference design only. Email seangarn@uw.edu before sinking weeks
  into a clean-room port. Our CATALOG's 186× figure derives from the
  equivalence-checking benchmark — re-extract once you have full PDF
  in hand.

- **Qimax** (Vu Tuan Hai et al, NAIST) arXiv 2505.03307
  https://arxiv.org/abs/2505.03307 . Extended-stabilizer on multi-core
  / GPU; compares vs Qiskit & PennyLane, **not vs Stim**. No GitHub
  on arXiv landing. A re-implementation matching Qimax does not yet
  beat our CPU floor.

- **Clean-room Aaronson-Gottesman tableau on CUDA**
  https://arxiv.org/abs/quant-ph/0406196 . ~500 LoC CUDA for a binary
  symplectic tableau (2n × 2n bits + sign), gates H/S/CNOT/X/Z + M —
  every Clifford gate boils down to row-XOR + sign twiddle. **Our
  recommended target** because (a) you own our wire format, (b) STABSim
  & Qimax did not release source, (c) Aaronson-Gottesman runs at known
  O(n²) per gate, maps cleanly onto a CUDA warp.

Recommendation: write our own, citing STABSim's per-warp parallelism
as inspiration. Re-evaluate STABSim source if UW responds.

## 2. Circuit format — translate, do not adopt

Our circuit lives as Phase B lumbda Scheme & emits to QECCOPS1
`ops.bin` (op kinds in `ecdsa/cuda/sim.h:21-38`). Stim's `.stim` text
format is the de-facto wire for stabilizer circuits
(https://github.com/quantumlib/Stim , gate names `H S CX CZ SWAP R M
TICK`).

Pick **(b)** — `demo_stab_sim_ops.cu` accepts our existing QECCOPS1
`ops.bin` natively, treats Clifford ops as primary. Reasons:

- `ops.bin` already exists, generated by every lumbda tier; a `.stim`
  translator adds a redundant emission path.
- Op kinds `OP_X, OP_Z, OP_CX, OP_CZ, OP_SWAP, OP_R, OP_HMR` map 1:1
  onto Aaronson-Gottesman tableau ops. `OP_CCX, OP_CCZ` route to our
  Toffoli handler (§3).
- Cross-validation against Stim CPU still happens via a one-shot
  `emit-stim-circuit.lsp` test utility under `ecdsa/tests/` — small
  circuits only, byte-equivalence spot checks, never our production
  wire.

## 3. Toffoli problem — pick option (b), score symbolically

Stabilizer formalism handles Clifford only. Our Roetteler 12-step
point-add (`ecdsa/lumbda/point-add-real.lsp`) carries both Clifford &
Toffoli. Our CUDA sim already tracks them separately:
`ecdsa/cuda/sim_gpu.cu:155` counts `OP_CCZ / OP_CCX` as Toffoli, all
others as Clifford.

Three options surfaced in our brief; you pick **(b)**:

- **(a) Decompose each CCX into 7T.** Inflates op count ~7× per
  Toffoli, requires magic-state tracking. Wrong for a scoring sim.
- **(b) Run Clifford fragment only on GPU; fold Toffoli count from
  circuit structure.** Our score is a *count*, not a measurement
  outcome. Toffoli ops are symbolic — you tally them at circuit-emit
  time, skip them in our stabilizer kernel. GPU lane handles only
  Clifford ops; CPU emits Σ-Toffoli alongside as a static circuit
  property. **This is sufficient for our metric.** Speedup numbers in
  CATALOG (186× equivalence-checking) come from Clifford-only
  benchmarks, so this matches what published work measures.
- **(c) Extended stabilizer / magic-state sim.** Qimax territory.
  Slower & more code; only revisit if our scoring metric changes to
  require sampled outcomes through Toffoli gates.

Phase B point-add Toffoli fraction (from existing kernel counters):
roughly half of all gates per circuit are CCX / CCZ at current ancilla
widths. Confirm exact ratio by running `bend-cuda` against
`point-add.bin` — GPU counters at `sim_gpu.cu:238-239` emit
`cliff_out` & `toff_out` per batch. Record this ratio before you sink
time into Form D: if Toffoli > 90% of ops, a Clifford-only sim
accelerates only 10% of work & a 186× fragment win yields 1.1× overall
(Amdahl).

## 4. Wire protocol — BSHK reuse

Reuse the BSHK / BSHR framing already wired through `gpu-worker.lsp`
(handler `handle-binary-shake` at lines 253-267). Layout:

- Request: `BSHK | u32 op_id=0x02 | u32 n_qubits | u32 n_shots |
  u32 circuit_blob_size | circuit_blob[N]`
- circuit_blob: our existing QECCOPS1 `ops.bin` bytes, no translation.
- Response: `BSHR | u32 status | u32 n_shots |
  samples[n_shots * ceil(n_qubits/8)]` bit-packed measurement outcomes.

Confirm match: STABSim & Qimax did not publish wire schemas, so you
own this protocol fully — design freedom, no compatibility tax.
`op_id` discriminator lets the daemon serve both `cuda-sim-ops-bin`
(kickmix, `op_id=0x01`) and `cuda-clifford-stabilizer`
(`op_id=0x02`) without renegotiating magic bytes.

## 5. `gpu-worker.lsp` handler sketch

Mirror `handle-cuda-sim-ops-bin` (lines 187-233). Pseudocode:

```scheme
(define *binary-stab-sim*
  (or (get-environment-variable "STAB_SIM")
      "/home/fox/git/www.foxhop.net/ecdsa/cuda/demo_stab_sim_ops"))

(define (handle-cuda-clifford-stabilizer args)
  (let* ((ops-path  (car args))
         (n-qubits  (car (cdr args)))
         (n-shots   (car (cdr (cdr args))))
         (portal    (gensym-path "/tmp/bend-stab" ".portal"))
         (t-start   (current-time-ms))
         (argv      (list ops-path
                          (number->string n-qubits)
                          (number->string n-shots)
                          "--portal" portal))
         (daemon    (cdr (assoc 'cuda-clifford-stabilizer *daemons*))))
    (daemon-process daemon ops-path portal #t)
    ;; portal carries (cuda-stab-result (samples blob) (sigma-clifford k)
    ;;                                  (sigma-toffoli k) (timing-ms ...))
    ;; same shape as cuda-sim-ops-bin, parse via existing portal-find-number.
    ...))
```

Dispatch line in `handle-request`:

```scheme
((eq? op 'cuda-clifford-stabilizer)
 (handle-cuda-clifford-stabilizer args))
```

Register daemon at startup:

```scheme
(register-daemon! 'cuda-clifford-stabilizer *binary-stab-sim*)
```

## 6. Daemon protocol

Mirror `shake256-fanout --daemon` (called via `start-daemon` line 62).
On stdin one line per request, on stdout one line per response.
Two modes — text (`process`) for dev, binary (`process-bin`) for hot
path:

```
> process-bin /tmp/in.bin /tmp/out.bin\n
< done\n             (or `error <message>\n`)
```

On start, daemon prints `ready\n` after CUDA context init &
tableau-row buffer allocation. CUDA context warm-up pays once per
worker lifetime.

## 7. Build recipe

Add to `ecdsa/cuda/Makefile`:

```make
demo_stab_sim_ops: stab_sim_gpu.o ops_loader.o main_stab_sim.o
	nvcc -O3 -arch=sm_80 -o $@ $^

stab_sim_gpu.o: stab_sim_gpu.cu
	nvcc -O3 -arch=sm_80 -c $< -o $@
```

`arch=sm_80` covers RTX 3090 (sm_86) & RTX 4090 (sm_89) via JIT;
hard-code at deploy time if you measure a perf loss.

Source files to write fresh:

- `stab_sim_gpu.cu` — Aaronson-Gottesman tableau kernel, one CUDA
  block per circuit (= per candidate), threads cooperate on the
  tableau rows. Reference: quant-ph/0406196 §3 update rules.
  https://arxiv.org/abs/quant-ph/0406196
- `main_stab_sim.c` — daemon loop, ops.bin load, dispatch.
- Reuse `ops_loader.c` from existing simulator (already parses
  QECCOPS1).

## 8. Validation plan

Two axes:

- **Σ-Clifford equivalence vs Stim CPU.** Generate a 16-qubit
  toy circuit covering every supported gate; run our sim on
  CPU+GPU; emit the same circuit through
  `emit-stim-circuit.lsp` (one-shot translator, test-only); run
  Stim CPU via `stim sample --in toy.stim` (Stim install on
  permacomputer fleet, not on host). Σ-Clifford & measurement
  outcomes must match byte-for-byte over 1024 shots seeded
  identically.

- **Per-candidate axis flip benchmark.** Run N independent candidate
  circuits as N GPU blocks (= N lanes). Compare:
  - existing `bend-cuda` per-shot: N candidates × 8192 shots each = 8192N
    threads, one thread per shot of a single candidate;
  - new `demo_stab_sim_ops` per-candidate: N candidates × 1 lane each,
    each lane runs its candidate to completion serially in tableau.
  At N=256 candidates expect Stim CPU to take ~2 s/candidate (512 s
  total); Form D target on RTX 3090 ~2.7 s total based on a 186×
  scaling factor. Record actual numbers; if our ratio < 30× you
  surface our crossover N on CATALOG.

Bench target: a 16-qubit, 1000-Clifford-gate test circuit (small
enough to avoid memory blowup on first run; large enough that
kernel-launch overhead amortizes).

## 9. Risks & open questions

- **STABSim source.** No public repo. Either email seangarn@uw.edu &
  wait, or build clean-room from quant-ph/0406196. Clean-room is our
  default path. Risk: clean-room reaches Aaronson-Gottesman baseline,
  not STABSim's published wins (likely 10-30× over CPU, not 186×).
- **Per-candidate axis vs per-shot axis.** STABSim hints at warp-level
  parallelism without specifying whether warps map to circuits or
  shots. Read PDF §III before committing — our axis-flip thesis
  depends on per-circuit being the right grain.
- **Toffoli ratio.** If point-add ends up >90% Toffoli, Form D wins
  only 1.1× overall (Amdahl). Measure Toffoli fraction before build.
- **Memory.** A 16-qubit tableau is ~1 KB per candidate; a 256-qubit
  point-add fragment is 128 KB per candidate. N=1024 × 128 KB = 128
  MB GPU state — fits. Cap N×state at 8 GB on 3090.
- **Stim install footprint.** Validation needs Stim on fleet;
  `pip install stim`. Test-only dep, not a worker dep.

## 10. Effort estimate

For one experienced CUDA + quantum-sim engineer (assumes prior
Aaronson-Gottesman familiarity):

- Day 1: read STABSim PDF, read Aaronson-Gottesman paper, run
  existing `bend-cuda` to measure Toffoli ratio, decide go/no-go.
- Days 2-4: `stab_sim_gpu.cu` kernel — tableau rep, X/Z/H/S/CX/M
  update rules, warp-level row-XOR primitive.
- Day 5: `main_stab_sim.c` daemon loop, BSHK plumbing.
- Day 6: `gpu-worker.lsp` handler, daemon registration, smoke run.
- Days 7-8: validation vs Stim CPU on 16-qubit toy, fix divergence.
- Days 9-10: per-candidate benchmark, record numbers, update
  CATALOG.

**Total: ~10 working days.** Halve to 5 if STABSim source surfaces;
double to 20 if Toffoli folding turns out insufficient & you must add
extended-stabilizer (option c) support.

You decide go/no-go after Day 1 measurement.
