macquerel Implementation Plan — Remaining Work
macquerel is a quantum state-vector simulator targeting Apple Silicon's unified-memory
architecture. Completed implementation and optimization work lives in
plan_completed.md, including the per-step A/B results and design
notes for completed lines.
This document tracks only work that has not been implemented yet. Steps keep their original numbering for continuity with the completed record.
A/B Protocol
Each optimization step is measured as a commit-pinned A/B test against the immediately
previous baseline: run the same benchmark cells before and after the change, in isolated
subprocesses to avoid GPU memory-pool and lazy-graph contamination, using min-of-reps
timings to reduce noise. Correctness is gated first with the test suite, then performance
is accepted only if the affected backend/circuit/qubit ranges improve without meaningful
regressions elsewhere. Per-step JSONs and plots are saved under benchmarks/data/steps/,
and changes that lose their A/B, like default qubit remapping, are left disabled or
reverted rather than folded into the hot path.
Implemented steps are moved to plan_completed.md, where each
completed optimization records its commit ID alongside the measured A/B result and design
notes.
v0.3
- Memory-mapped out-of-core backend — state vector backed by an NVMe file via
np.memmap, for single large runs past DRAM capacity. Investigated and expanded into the explicit out-of-core design under v0.3.x below — passive OS paging turned out to be the wrong mechanism. - Multi-Mac over Thunderbolt — distributed state vector using index-bit partitioning across machines.
v0.3.x — Out-of-core statevectors (disk-streamed past RAM capacity)
DuckDB runs analytical queries
on larger-than-memory data by giving every operator a fixed memory budget
(memory_limit, default 80% of RAM) and a buffer manager: intermediates live in
buffer-managed blocks that are spilled to a temporary directory when the budget is
exceeded and read back in large sequential chunks, so sort/join/aggregate
degrade gracefully to NVMe
bandwidth instead of failing or swapping. This section investigates whether that
model transfers to statevector simulation and turns the v0.3 "memory-mapped
out-of-core backend" bullet into a concrete design.
What transfers and what doesn't
DuckDB's buffer manager does two separable jobs. It is a cache: keep hot blocks in RAM, evict cold ones by LRU, fault blocks in on demand — necessary because a query's access pattern is unknown until it runs. And it is a bounded-memory streaming mechanism: a fixed budget, explicitly pinned working blocks, large sequential spill/reload I/O instead of random page faults.
The caching job does not transfer. A cache earns its keep on skew — a query touches
data selectively, so cold blocks can sit on disk untouched. A gate pass touches
every amplitude exactly once: there is no cold data to leave behind and no reuse
for a replacement policy to exploit, so a demand-paged cache degenerates to pure
overhead (LRU is the textbook-worst policy for a cyclic scan — each block is evicted
just before it is needed again). Naively backing the state with np.memmap and
letting the OS page (the v0.3 sketch) fails for exactly this reason: the kernel is a
generic reactive cache, evicting 16 KiB pages with no knowledge of the access plan,
and a 34-qubit gate pass becomes random-fault-ordered I/O.
The streaming job is what this design keeps — and because a gate's access pattern is known at compile time from its target qubits (unlike a query's), it can be kept in a stronger, policy-free form: no faulting, no eviction decisions, just a fixed schedule. Concretely, what transfers:
- An explicit budget instead of passive paging. A
memory_limit-style knob (e.g.MACQUEREL_MEMORY_LIMIT, defaulting to today's min(0.45 × RAM, 64 GiB) benchmark gate) and an explicit chunk manager that owns the I/O schedule. - Sequential, partitioned access. DuckDB radix-partitions a spilling hash join so each partition is processed fully while resident. The statevector analog is index-bit partitioning — the same scheme already planned for multi-Mac: split the state into 2^m chunks by the top m index bits. Gates on the low n−m local qubits act independently inside each chunk; only gates on the top m global bits pair amplitudes across chunks. The chunk visit order falls straight out of the gate's target qubits — static, not adaptive.
- Maximize work per residency. The unit of I/O is a "chunk episode": load a chunk (sequential multi-GiB read), apply every gate that can run before the next global-bit barrier (the existing fusion + commutation-aware grouping machinery, re-targeted), write it back, prefetch the next chunk meanwhile. This is Doi–Horii cache blocking lifted one level — DRAM as the cache, NVMe as main memory — and it is the entire performance story: one episode costs a full-state read+write regardless of how many gates it carries.
- Graceful degradation. Budget ≥ state size → explicitly bypass the chunk manager
and route to today's in-RAM backend, preserving the existing hot path. Budget <
state size → stream chunks. Metal should compose directly via
newBufferWithBytesNoCopy:over page-aligned chunk buffers, but this is the riskiest systems assumption and must be validated before scheduler work: confirm no hidden copies, no page-fault collapse, and stable throughput with a tiny-budget prototype. - Clean pages skip writeback. DuckDB drops unmodified cached pages instead of spilling them. The analog: read-only passes (sampling, probabilities, expectation values) stream chunks without writing them back — half the I/O.
What replaces the buffer pool
The pool's replacement is the Step 42 three-buffer ring: exactly three pinned
chunk-sized RAM buffers — one being computed on, one being prefetched (the next chunk
in the schedule, read sequentially while compute runs), one being written back (the
previous chunk) — rotating roles as the schedule advances. It is a buffer pool
collapsed to its degenerate case. What survives: pinning (a chunk never moves while
the GPU is reading it) and the budget (3 × chunk size ≤ MACQUEREL_MEMORY_LIMIT
fixes the partition count 2^m). What disappears: the cache. There is no hit/miss, no
replacement policy, no demand faulting — "eviction" is the scheduled writeback of a
chunk the plan is finished with, "admission" is the scheduled prefetch of the chunk
the plan needs next.
That also pins down how it helps, because it is not by avoiding I/O — an episode reads and writes the full state no matter what. The ring's entire contribution is hiding the I/O: with compute and both I/O directions overlapped, an episode costs max(compute, I/O) rather than their sum, and since local gate work runs at unified-memory bandwidth (~93 GiB/s measured full-state pass) while the NVMe sustains ~7 GB/s, I/O is the roofline — the pipeline's one job is to keep the NVMe queue never idle.
Relative to the shipped in-RAM backends, the genuinely new concepts are four — everything else is existing machinery re-targeted:
- A memory budget (
MACQUEREL_MEMORY_LIMIT). Today allocation is all-or-nothing: the state fits in RAM or the run fails. - A chunked state (
ChunkedState, Step 41): one logical state stored as 2^m file-backed partitions split by top index bits, vs today's single contiguous buffer. - The episode as the unit of cost (Step 43). Today's cost unit is the per-gate full-state pass and fusion minimizes passes; out of core, the unit is the chunk residency — load once, run every gate up to the next global-bit barrier, write once — and the same fusion + commutation-aware grouping machinery is re-aimed at minimizing episodes (full-state I/O round-trips) instead.
- The three-buffer ring above.
The remap pass (Step 44) is not new machinery either: it is the existing
disabled-by-default remap_qubits pass, finally facing the ~13× bandwidth asymmetry
it was built for (it lost its in-RAM A/B because no such asymmetry exists there).
Feasibility numbers (assuming a 128 GiB Mac with NVMe at ~6–8 GB/s sequential)
| n | state (2ⁿ × 8 B) | fits | episode cost (read+write @ 7 GB/s) |
|---|---|---|---|
| 33 | 64 GiB | RAM (today's ceiling) | — (in-memory) |
| 34 | 128 GiB | NVMe | ~37 s |
| 35 | 256 GiB | NVMe | ~75 s |
| 36 | 512 GiB | NVMe | ~150 s |
| 37 | 1 TiB | NVMe | ~5 min |
To be explicit about what kind of feature this is: capacity, never speed. There is no input where the out-of-core path beats the in-RAM path — when the state fits the budget, Step 41's bypass routes to today's backend untouched (Step 46 gates the ship on zero in-RAM regression). Per axis: qubits +1 to +4 (33q → 37q, bounded by free disk); RAM pinned to the budget regardless of state size — the state is not smaller, it lives on disk; speed strictly a cost, with a hard floor of ~13× per full-state pass (~93 GiB/s in RAM vs ~7 GB/s NVMe), ~2× more again when the pass writes back. The alternative the spilled path competes against is not "slower" — it is "fails to allocate". (The one piece of the line that can speed things up is Step 47's complex32: halving bytes per amplitude in a bandwidth-bound simulator.)
So out-of-core execution buys +1 to +4 qubits of capacity at a slowdown set by the local/global structure of the circuit: GHZ at 34q is a handful of episodes (~minutes); a QFT, whose controlled-phase gates are diagonal (diagonal gates never touch a global bit's pairing, only its phase — they are chunk-local at any width), spills cheaply; a random dense circuit on scattered qubits is the worst case and needs the remap step below to stay off the global bits. Note the asymmetry that makes scheduling decisive: local work runs at unified-memory bandwidth, global work at NVMe bandwidth — a ~13× gap on measured numbers (~93 GiB/s effective full-state pass vs ~7 GB/s sequential NVMe), far steeper than the cache-blocking gap that lost remapping its single-machine A/B.
Steps
- Step 41: chunked state store + no-copy Metal proof — first build the smallest
useful
ChunkedState: one page-aligned file (MACQUEREL_TEMP_DIR, default alongside the platform temp dir; checked against free disk up front, deleted on exit — DuckDB'stemp_directory/max_temp_directory_sizesemantics), aMACQUEREL_MEMORY_LIMITbudget, and an explicit in-RAM bypass when the budget covers the state. Prototype one local gate over artificially chunked small states, feeding Metal withnewBufferWithBytesNoCopy:. Ship this step only if the prototype produces identical amplitudes vs the in-RAM path, peak RSS respects the tiny budget, Instruments/benchmarks show no hidden full-state copy, and sequential read/write + compute throughput stays near the measured NVMe/Metal roofline. - Step 42: three-buffer streaming pipeline — generalize Step 41 into the compute / prefetch / writeback pipeline with exactly three live pins, plus read-only streaming that skips writeback for sampling, probabilities, and expectation values. Benchmark this before the full scheduler: report effective GB/s for raw sequential read/write, read-only streaming, and one local-gate episode at forced-small budgets.
- Step 43: episode scheduler + gate classification — compile the fused gate stream into chunk-local episodes split at global-bit barriers. Make locality rules explicit: gates whose non-diagonal target action is wholly local stay inside a chunk; diagonal/phase gates on global bits stay local because they never pair chunks; controls on global bits are local when the target action is local because they only mask chunks; non-diagonal global targets are barriers. Skip writeback for read-only passes. A/B metric: episodes per circuit (= full-state I/O passes), then wall time.
- Step 44: global bits via remap passes — when a non-diagonal gate needs a global
target bit, emit one explicit remap episode (swap a global bit with a cold local bit
— a paired-chunk streaming pass) instead of pairing chunks ad hoc, then proceed
chunk-locally. Reuses the existing disabled-by-default
remap_qubitsmachinery, which finally has the cost asymmetry it was built for. A/B: remap-pass count and wall time on the random-circuit benchmark at 34q. - Step 45: optional lz4 writeback compression — only after the raw pipeline works, add opt-in lz4 chunk compression on the writeback path with a raw fallback when the ratio is poor. Being lossless, its ceiling is information-theoretic, not a tooling question: a structured state like GHZ is mostly zero bytes and compresses nearly for free, but a Haar-random chunk is incompressible past ~1.1–1.2× — the mantissa bits are effectively uniform random, and the only slack is in the exponents, which Porter-Thomas concentration leaves a few bits of entropy. So gate it on wall time, not just ratio, and make the raw fallback short-circuit quickly enough that failed compression does not disturb GPU/I/O overlap.
- Step 46: out-of-core benchmark + ship gate — extend
bench_memory.pywith a spilled series (peak RAM must respect the budget; report episodes and effective GB/s against the NVMe roofline) and a 34q GHZ/QFT/random wall-time table. Ship only if 34q runs end-to-end under the default budget without swap and the in-RAM path shows zero regression. SSD-endurance note in the docs: an episode writes the full state (128 GiB at 34q), so deep unfused circuits are a TBW consideration — documented, not engineered around, in v0.3.x. - Step 47: block-float
complex32states — opt-in half-precision amplitude storage (dtype="complex32"): two float16s per amplitude plus one float32 max-magnitude scale per chunk. The per-chunk scale is load-bearing, not a nicety: at 34q the typical amplitude magnitude is ~2⁻¹⁷ ≈ 8e-6, below float16's normal range (6e-5), so naive fp16 lands in subnormals or underflows — block floating point restores the range. A deterministic, circuit-independent 2× on every byte count, and GPU-native (Metal and MLX both have first-classhalf), so chunks stay compressed in unified memory too: it composes with spilling and raises the in-RAM ceiling 33q → 34q (and the DM ceiling toward n=17) with no disk involved. Cost: a 10-bit mantissa gives ~2⁻¹¹ relative rounding per gate pass, accumulating roughly with √depth — fine for sampling and expectation values at moderate depth, not for amplitude-level verification. Ship opt-in only; gate with the existing differential tests against complex64 and publish a fidelity-vs-depth table. This is the cheapest +1 qubit of the v0.3.x line and depends only on chunk-granular scaling, not on the disk pipeline — it can ship before Steps 41–44.
Considered and deferred: error-bounded lossy compression (SZ/ZFP) — the
strongest published precedent for compressed full-state simulation (Wu et al.,
Full-state quantum circuit simulation by using data compression, SC'19,
arXiv:1810.14582, which kept the state
compressed in memory, decompressing blocks on the fly, and reached a 61-qubit
Grover), but a poor fit here for now. Unlike lossless coding, lossy compression
does keep working on dense Haar-random states — truncating mantissas is exactly
how high-entropy floats compress, regardless of structure — so the objection is not
the ratio in principle but the practical terms: SZ/ZFP throughput is ~1-5 GB/s per
CPU core (below the NVMe without multithreading or a Metal port — ZFP has CUDA
kernels, no Metal), the error bound is consumed once per compress/decompress cycle
and every chunk episode is a cycle, and on random states the ratio settles toward
the precision-reduction floor — at which point it is buying the same bytes as Step
47's complex32, at lower speed and with an adaptive error model instead of a fixed,
characterizable one. The credible way back in is a zfp fixed-rate Metal port
(guaranteed ratio, bounded error, GPU speed), which would slot into Step 45's
wall-time gate unchanged. Also deferred: an in-RAM "blocked backend"
as its own feature — partitioning never reduces the bytes a state occupies, and
Metal already stores the state once at a measured ~1.0x of theory, so in-RAM block
partitioning adds zero qubits; it falls out of Step 41 anyway as
the trivial budget ≥ state bypass. (A gate on a global bit is a 2×2 block matrix
multiply over chunk pairs at identical traffic to a local pass, so the in-RAM
partitioning tax is ~zero — but so is the benefit.) One conditional exception: an
mlx-chunked mode (chunks ≤ 2³⁰ elements) would lift MLX's upstream int32
ShapeElem ceiling from 30q to Metal parity at 33q while collapsing its ~3-5×
peak multiplier toward ~1× (lazy-graph temporaries become chunk-sized) — same
scheduler, RAM tier; only worth building if MLX-only machines (no PyObjC) turn out
to matter. Also deferred: changed representations — matrix product states now
have their own roadmap line (v0.4 below);
decision diagrams and sparse amplitude dictionaries remain deferred without one —
and a general buffer pool with LRU eviction (no selectivity in the access
pattern, so there is nothing to cache — see "What replaces the buffer pool" above;
the three-buffer ring is the whole pool). The multi-Mac
item (v0.3) and this section share the index-bit partitioning compiler work;
whichever ships first pays most of the cost of the second.
v0.4 — Matrix product state simulator
Everything in v0.3.x buys single qubits at the 2ⁿ byte wall (complex32 +1, spilling
+1 to +4). A changed representation is the only lever that escapes it: an
MPSSimulator stores the state as a chain of n tensors of shape (χ, 2, χ), where
the bond dimension χ measures entanglement across each cut — memory is
n · 2χ² · 8 B, scaling with entanglement instead of 2ⁿ. 100 qubits at χ = 1024
is 1.6 GiB; a GHZ state is χ = 2 at any width; MPS storage beats the full vector at
33q for any χ below ~10⁴. The honest trade: each entangling layer can double χ, so a
deep random circuit forces χ → 2^(n/2) and the representation collapses back to 2ⁿ —
this is a new regime (50–1000+ low-entanglement qubits: GHZ/Clifford-lite states,
QFT, shallow VQE/QAOA ansätze, 1D Trotterized time evolution), not a replacement for
the statevector simulator.
Design constraints, from a back-of-envelope study:
- Sibling-simulator pattern. Same
CircuitAPI, alongsideDensityMatrixSimulatorandTrajectorySimulator. χ capped with exact tracked truncation fidelity (computed from the discarded singular values, reported per run), nearest-neighbor routing via SWAP chains, exactO(n χ²)-per-shot sampling by sweeping the chain. - Gate costs. 1-qubit gates are free contractions. A 2-qubit neighbor gate
contracts two site tensors (~χ³ GEMM), applies the gate, then SVDs the
2χ × 2χmatrix to split back and truncate —O(8χ³), the dominant cost and the one new primitive. - CPU/GPU split. The χ³ contractions are GEMMs — exactly what the existing
Metal/MLX backends are best at, on far friendlier tensor shapes than 2ⁿ vectors.
But SVD has no GPU path on Apple Silicon today: MLX's
mx.linalg.svdis CPU-stream-only (verified on 0.31.2) and Metal Performance Shaders has no SVD, so truncation runs on Accelerate LAPACK (~0.1–0.5 s at χ = 1024). Unified memory makes the GPU-GEMM/CPU-SVD hybrid copy-free — the spot where discrete-GPU simulators pay PCIe tax. QR-based or randomized-SVD truncation is the later GPU offload path. - A/B references. Qiskit Aer
method="matrix_product_state", quimb, ITensor, TeNPy. Document therandombenchmark as the adversarial case MPS is not for.
Considered and deferred: contraction-based simulation (qsimh / cuTensorNet / cotengra style — the whole circuit as one tensor network, contracted per amplitude batch with slicing). It is a sampling/amplitude tool with no state, no cheap mid-circuit measurement, and a contraction-order search problem that mature dedicated tools already own — a different product than this simulator's contract.
Verification
After each step, run uv run pytest tests/ -x -q and confirm the new tests pass before
moving to the next step. Final verification: