macquerel Implementation Plan — Completed Work
This document is the historical record of implementation steps that have shipped.
It is kept separate from plan.md, which tracks only remaining work. Steps
retain their original numbering. For each step the rationale, design notes, and (for the
performance work) the measured A/B results are preserved, because they document why the
code is shaped the way it is.
v0.1 — core simulator
macquerel is a quantum state-vector simulator targeting Apple Silicon's unified-memory architecture. The v0.1 milestone delivered the CPU reference backend + MLX backend, single/two-qubit gates, gate fusion, measurement/sampling, and a differential test harness, following the spec's layered architecture: gate library → CPU reference backend → frontend API → MLX backend → compiler → tests.
Step 1: Fix packaging and project structure
The original CMakeLists.txt wrongly treated simulator.py as a C++ library and
__init__.py was empty. Fixed: removed the broken src/ subdirectory add (no C++ in
v0.1), exported Circuit, Simulator, Gate from __init__.py, and created the
src/macquerel/backends/ package.
Verified: python -c "import macquerel" succeeds; uv sync completes cleanly.
Step 2: Gate matrix library (src/macquerel/gates.py)
All standard unitary matrices as np.ndarray (complex64), plus helpers.
- Single-qubit:
I,H,X,Y,Z,S,T,Rx(θ),Ry(θ),Rz(θ),P(λ) - Two-qubit:
CNOT,CZ,SWAP,CP(λ) - Helper:
controlled(U)— lifts a single-qubit gate to a 2-qubit controlled gate classify(matrix) -> GateKindwhereGateKind = Literal["diagonal", "permutation", "dense"]
Verified (tests/test_gates.py): H @ H ≈ I, X @ X ≈ I, S @ S ≈ Z,
Rz(θ) @ Rz(-θ) ≈ I, unitarity for all gates, and correct classify() kind for each gate.
Step 3: CPU reference backend (src/macquerel/backends/cpu.py)
The oracle against which all other backends are differentially tested. State is an
np.ndarray of shape (2**n,), dtype complex64, reshaped to (2,)*n for gate
application. apply_matrix uses np.tensordot + transpose back to canonical order;
measure, sample, and allocate implemented per spec.
Verified (tests/test_cpu_backend.py): Bell, GHZ, QFT-vs-np.fft, norm preservation
after every gate, measurement collapse, and GHZ sampling χ² test.
Step 4: Frontend API (src/macquerel/circuit.py, src/macquerel/simulator.py)
Gate dataclass (name, matrix, targets, controls, kind); Circuit with gate
builder methods (h, x, y, z, s, t, rx, ry, rz, cx, cz, swap, cp),
measure/measure_all, and index validation; Simulator with run(circuit, shots) →
Counter[str], statevector(circuit), and backend selection.
Verified (tests/test_circuit.py): API round-trip, index validation raises
ValueError, measure_all on a 3-qubit circuit.
Step 5: MLX backend (src/macquerel/backends/mlx_backend.py)
GPU backend with diagonal/permutation fast paths and a Metal-kernel dense path (see the
perf section for the layout that eventually shipped). measure/sample use
mx.random.categorical. Raises a helpful ImportError when mlx is absent.
Verified (tests/test_mlx_backend.py): differential tests against the CPU oracle to
1e-5 on all amplitudes — the primary correctness gate.
Step 6: Gate fusion compiler pass (src/macquerel/compiler.py)
fuse_gates(circuit, max_fused_qubits=4) -> Circuit: greedily merges adjacent gates whose
combined target set is ≤ max_fused_qubits, composing matrices into a single unitary.
MeasureOp is a fusion barrier; controlled qubits count toward the set size.
Verified (tests/test_compiler.py): fused == unfused statevectors, single-gate circuits unchanged, measurement barriers respected, fused-matrix unitarity.
Step 7: Test suite
tests/test_known_circuits.py (Bell, GHZ, Grover, QFT on CPU + MLX),
tests/test_properties.py (norm preservation + fusion equivalence over random circuits),
tests/test_edge_cases.py (1-qubit, all-identity, empty circuit, max-controls).
v0.1 completion — performance-critical gaps
These items were described in the v0.1 spec but initially deferred to a simpler correct implementation.
Step 8: Permutation gate fast path (mlx_backend.py)
Permutation gates (X, SWAP, CNOT) dispatch to a dedicated _apply_permutation
(gather/scatter, no arithmetic) instead of falling through to the general dense path.
Step 9: SoA state representation (mlx_backend.py)
The state stays in struct-of-arrays form across gate calls (later superseded — see P4), with the complex64 view reconstructed only at the API boundary.
Step 10: mx.fast.metal_kernel gate hot path (mlx_backend.py)
Custom Metal kernel where each GPU thread owns one (i, i ⊕ 2ᵏ) amplitude pair, with
double-buffering (MLX kernel inputs are const device).
Step 11: Reproducible RNG (mlx_backend.py, simulator.py)
Simulator.__init__ takes an optional seed, threaded through to the backends'
sampling. (mx.random.key(seed) for MLX.)
Step 12: Backend Protocol ABC (src/macquerel/backends/__init__.py)
A typing.Protocol (@runtime_checkable) declaring the full backend interface
(allocate, apply_matrix, measure, sample, to_numpy, expectation_pauli,
abs2sum) so type checkers can verify backend conformance.
MLX backend performance optimization
After the permutation fast path (Step 8), SoA state (Step 9), and the custom Metal kernel (Step 10), the MLX backend was still slower than CPU across 16–24 qubits. Profiling a depth-50 random circuit at 22 qubits identified these root causes:
- Per-gate
mx.eval()forced a GPU sync on every gate, defeating MLX's lazy graph (50 elementwise ops: 17.4 ms with per-gate eval vs 6.0 ms once — a 3× penalty). - Host-side O(2ⁿ) work per gate in
_apply_permutation(NumPy table rebuild ~9 ms/gate - ~0.2 ms host→device copy).
- Diagonal path rebuilt device scratch (
arange,gate_idx, bitwise intermediates) every call. - SoA real/imag split turned each complex multiply into 3–4 real kernels.
- Full transpose+copy per dense gate in
_dense_apply. - The old raw backend benchmark did not fuse (deliberate - it measured per-gate throughput).
- Minor per-gate host overhead (
classify,astype).
Optimizations (ranked, as shipped):
- P1 — Defer evaluation. ✅ DONE (
3c74da8). Dropped per-gatemx.evalfrom all five gate paths; eval forced only at segment boundaries (measure /to_numpy/ sample). Targets cause (1). Measured 1.1–1.8×. - P2 — Eliminate host-side permutation work. ✅ DONE (
81e96e3). Compute the gather index on-device withmx.arange+ bitwise ops; only the tiny2**kinverse lookup stays on host. Targets cause (2); removed ~9 ms/gate at 22q. This flipped MLX from slower to faster than CPU. - P3 — Cache per-gate device constants. ✅ DONE (
6178f2f). Caches the reusedarange(2ⁿ)index, the scalar mask, andclassify()memoized by matrix bytes. Targets causes (3) and (7). Deliberately does not cache full2ⁿper-target index tables (unbounded memory; on-device rebuild is cheap after P2). - P4 — Native
complex64storage. ✅ DONE (1eb61db). State is now a single complex64 array: one complex tensordot instead of four real ones, one complex gather for diagonal/permutation, and the SoA-only Metal 1q kernel dropped. A/B vs SoA: neutral on the raw backend benchmark (1.01-1.04× at 18-22q), faster on dense/fused circuits at 20q: dense 1.16×, QFT 1.08×. This refutes the spec's "SoA up to 6.9× over interleaved" claim on MLX 0.31 — the layouts are equivalent here, and complex64 is simpler. Targets cause (4).
Note — why complex64 can look slower at large n with low reps. At 20–22q the random circuit is memory-bandwidth-bound, and a complex64 amplitude (8 bytes) equals two float32 (SoA
real+imag), so both layouts move identical bytes per gate — theory predicts parity. The genuine difference is below the benchmark's noise floor: GPU clock/thermal variance swings a single 22q config by ~10–15% (44.8 ms vs 51.4 ms observed). With--reps 3the min can land on a lucky-fast SoA run, making complex64 look ~0.85×; another pair reverses it. Higher reps (9+) and interleaved measurement collapse the gap to parity. complex64's real win is on dense/fused circuits.
- P5 — Avoid the full transpose copy via einsum. ❌ TRIED & REVERTED (
b4b0171→50d3d54). A single canonical-ordereinsumwas slower on every dense/fused workload at 18q (QFT 5.3→6.2, QAOA 2.8→4.2, dense 21.3→26.2 ms): MLX'seinsumdecomposes to a costlier sequence thantensordot+transpose. Premise false on MLX 0.31. - P6 — Fuse before MLX dispatch. ✅ ALREADY SATISFIED. The simulator already runs the
fusion pass on the hot path (
statevector()/run()). The historical raw backend benchmark deliberately stayed unfused. No code change needed. - P7 — Re-tune the auto-select crossover. ✅ DONE (
351376c)._select_backendroutes ≤16 qubits to CPU (was ≤14) and MLX for 17–31, matching the measured crossover. - P8 —
mx.compilethe hot gate kernels. ✅ DONE (b6bef6f). Compiled the diagonal phase kernel and permutation gather. A/B (reps=5): 20q 1.09×, 22q 1.12×, with a ~0.88× compile-overhead regression at 18q. Kept for the large-n gain.
Net result: P1 (defer eval) and P2 (kill host-side perm work) together flipped MLX from
slower to faster than CPU. P3, P7, P8, and P4 added incremental gains and simplification,
leaving MLX 2.4–5.6× faster at 18–22 qubits (see benchmarks/data/ and
benchmark-2.png). P5 was tried and reverted; P6 needed no change. Every perf-sensitive
step was decided by A/B benchmark on the harness rather than implemented blind.
Metal backend, qubit remapping, expectation values
Step 13: Qubit remapping / cache-blocking compiler pass (compiler.py)
remap_qubits(circuit) -> Circuit: a second pass after gate fusion (Doi–Horii technique)
that relabels qubits so the most frequently targeted ones land on the lowest indices
(minimizing stride 2ᵏ). Verified (tests/test_compiler.py): remapped circuits produce
measurement distributions identical to the unremapped originals.
Step 14: expectation_pauli and abs2sum (cpu.py, mlx_backend.py)
abs2sum(sv, qubits) — marginal probability sum over the given qubits, exposed as a
first-class method. expectation_pauli(sv, pauli_strings) — expectation value of a Pauli
operator or sum of Pauli strings. Verified against analytic values in
tests/test_backend_protocol.py (⟨Z⟩ = 1 for |0⟩, ⟨X⟩ = 1 for |+⟩).
Step 15: MetalBackend — native backend for the >30-qubit regime
Status: IMPLEMENTED (2026-06-02). Gate 0 = GO (outcome 1). Released MLX caps at ≤30 qubits; 31q+ is reachable only by a native backend. Built as a PyObjC driver (
src/macquerel/backends/metal_backend.py), not the metal-cpp + nanobind + scikit-build-core extension originally specified — that offline.metal→.metallibpath is unbuildable on the target machine (Metal Toolchain CLI missing; Xcode downloader broken). PyObjC reaches the same goals with no build system: shaders compile at runtime vianewLibraryWithSource, amplitudes live in one unified-memoryMTLBufferwith 64-bit indexing, updates are in-place. Verified: runs 31q, 32q, and 33q — the realistic 64 GiB ceiling, using 64.06 GiB resident (analytic GHZ spot-check exact), plus differential-tested vs CPU to 1e-5, wired into auto-select (Metal ≥31q). Surprise result: Metal also beats MLX from ~22q up (≈13× at 30q) because it avoids MLX's double-buffering + gather temporaries under memory pressure — seebenchmark-3.png.
Gate 0 — ceiling re-validation (RESULTS, 2026-06-02, M-series, 128 GB unified memory)
benchmarks/probe_mlx_ceiling.py exercised allocate / scalar-multiply / arange / gather
/ readback on a 2ⁿ complex64 state, each n in an isolated subprocess:
| n | elements | complex64 size | result |
|---|---|---|---|
| 29 | 5.37e8 | 4 GiB | ✅ all ops OK |
| 30 | 1.07e9 | 8 GiB | ✅ all ops OK |
| 31 | 2.15e9 | 16 GiB | ❌ rejected before allocation |
The break is a hard type ceiling, not a memory limit. At n=31 (2³¹ elements) MLX
0.31.2 raises TypeError because the shape value 2³¹ does not fit MLX's int32
ShapeElem — the binding refuses the call before any allocation. This is the
ShapeElem = int32_t root cause of MLX issue #3327, and it would reject 31q even with
infinite RAM. The newest MLX on PyPI is 0.31.2; building from main does not help (PR
#3524 keeps ShapeElem = int32_t and only adds overflow detection — verified by
reading the PR). So no released or development MLX reaches 31q; the ceiling is a
deliberate upstream design choice.
Verdict: GO — outcome (1), the only outcome on offer. A native backend is the only way to reach 31q+: 31q (16 GiB), 32q (32 GiB), 33q (64 GiB) are all MLX-unreachable. In-place updates add a +1-qubit capacity edge over MLX's double-buffering.
The capacity argument (why in-place matters)
MLX custom kernels cannot write back into their inputs (const device, issue #2547),
so every gate double-buffers — costing one qubit of headroom. In GiB (2ⁿ × 8
bytes; this 128 GB Mac reports ≈ 128 GiB):
| n | 1 state | MLX (double-buffered) | Metal (in-place) |
|---|---|---|---|
| 31 | 16 GiB | 32 GiB ✅ | 16 GiB ✅ |
| 32 | 32 GiB | 64 GiB ✅ | 32 GiB ✅ |
| 33 | 64 GiB | 128 GiB ⚠️ byte-fit only | 64 GiB ✅ realistic max |
| 34 | 128 GiB | 256 GiB ❌ impossible | 128 GiB ⚠️ byte-fit only |
Realistic max: 33 qubits in-place (64 GiB state leaves 64 GiB for everything else). 34q is byte-fit only. Concrete payoff: 33q vs MLX's 32q (+1 usable qubit), plus the analogous gain on a 64 GB machine.
As-built architecture
A pure-Python PyObjC driver behind the existing Backend Protocol. State held as one
interleaved complex64 MTLBuffer (bit-identical to NumPy for zero-copy readback, fits
33q at 64 GiB < the 80.6 GiB maxBufferLength measured on this M5 Max). Two
runtime-compiled kernels: a per-amplitude diagonal fast path and a per-group dense
kernel covering dense/permutation/controlled. A 3D grid reconstructs a uint64 linear
index from thread_position_in_grid (a 1D grid can't address >2³² threads) — the actual
mechanism that lifts the ceiling. In-place is race-free: each kernel writes each output
element exactly once and reads only its own group.
Implementation phases (as built)
- ✅ Gate 0 — ceiling re-validation. GO.
- PyObjC needs no build step; the
metalextra (pyobjc-framework-Metal) was added topyproject.toml/uv.lock. (The original CMake/nanobind/metallib skeleton was obsolete.) - ✅ Allocate + zero-copy
to_numpyreadback. Differential-tested vs CPU. - ✅ Diagonal kernel → differential test vs CPU (exact).
- ✅ Permutation → handled by the general dense kernel, differential-tested, in-place.
- ✅ Dense group kernel (1–4q fused) + controlled (control-bit mask) → differential tested, including non-adjacent targets and a 12-seed random-circuit fuzz.
- ✅ Wired into
_select_backend(Step 16): CPU ≤16q, MLX 17–30q, Metal ≥31q. - ✅ Large-n validation: 31q and 32q GHZ spot-check on a subset of amplitudes matches the analytic prediction exactly; in-place confirmed (single 1× buffer per state).
Testing (tests/test_metal_backend.py)
pytest.importorskip to keep CI green without the extension. Differential vs CPU to 1e-5
on the fuzzed random-circuit corpus (the most important test), boundary tests (31→32 switch,
all-identity, max-controls, empty), and an env-gated (MACQUEREL_BIG_TESTS=1) large-n test.
Outcome vs pre-build expectations
The pre-build expectation was that Metal would only match MLX's ms/gate (both
bandwidth-bound). In practice Metal beats MLX from ~22q up (≈13× at 30q,
benchmark-3.png): MLX's per-gate double-buffering and full-width gather temporaries thrash
unified memory at 28–30q, while Metal's in-place single-buffer path scales as the
bandwidth-bound ideal. Metal is slower below ~20q (per-gate waitUntilCompleted sync vs
MLX's lazy-graph fusion), so auto-select keeps CPU ≤16q and MLX 17–30q. Success criteria —
running 31–33q at all, and half the memory of MLX — both met.
Step 16: Automatic backend selection (simulator.py)
backend='auto' (the default): CPUBackend for ≤16 qubits, MLXBackend for 17–30,
MetalBackend for ≥31. Implemented as _select_backend. MLX's tier ends at 30q because
its int32 ShapeElem rejects 2**31 amplitudes.
Test additions (tests/)
- ✅
test_compiler.py— remapping equivalence (remap on/off yields identical distributions). - ✅
test_metal_backend.py— differential CPU vs Metal up to 32+ qubits. - ✅
test_backend_protocol.py— Protocol conformance for CPU/MLX/Metal;expectation_pauliandabs2sumagainst analytic values. - ✅
test_simulator.py— seed reproducibility (two seeded runs return identical counts).
Remaining test gap: Quantum Volume circuits and random-circuit-sampling spot checks in
test_known_circuits.pyare still outstanding — tracked inplan.md.
Cirq/Qiskit adapters
Step 17: Cirq/Qiskit front-end adapters (src/macquerel/adapters/)
macquerel.from_cirq(circuit) and macquerel.from_qiskit(circuit) converters (exported
conditionally from __init__.py when the optional extras are installed), so existing
circuits run unmodified on macquerel backends. Tested in tests/test_adapters.py.
Benchmarking suite
Step 18: Benchmarking suite (benchmarks/)
The maintained suite was consolidated around the benchmarks that are still used:
- ✅ Framework comparison (
bench_statevector.py): macquerel CPU/MLX/Metal vs Qiskit Aer and Qulacs, with endianness/precision/convention handling. - ✅ Fusion-width sweep (
bench_fusion_width.py): QFT, random, QAOA, and Quantum Volume circuits swept overmax_fused_qubits ∈ {1..6}. - ✅ Released-version regression checks (
bench_versions.py,plot_versions.py): compare CPU/MLX/Metal across PyPI releases and the current checkout.
Quantum Volume benchmark coverage shipped in the v0.2 line - see below.
v0.2 — autotuning + benchmark completion
Step 18 (completed): Benchmarking suite gaps
Closed the two outstanding §9 items from the v0.1 benchmarking suite:
- ✅ Quantum Volume macrobenchmark (
bench_fusion_width.py): Haar-random SU(4) model circuit (depth = n), added to the swept circuit set alongside QFT/random/QAOA/dense. Exercises the worst-case dense (non-diagonal, non-permutation) path. - ✅ Framework comparison cleanup (
bench_statevector.py): macquerel backends run alongside Qiskit Aer and Qulacs, and optional frameworks degrade gracefully when absent. - ✅ Companion tests (
tests/test_known_circuits.py): QV normalization + exact-inverse identity known-answer tests, and a random-circuit-sampling spot check that shot frequencies track |ψ|².
Step 19: Shot batch-size autotuning (src/macquerel/simulator.py)
Simulator gained a batch_shots parameter (default "auto"), threaded through to each
backend's sample() (and added to the Backend Protocol). The MLX backend autotunes the
mx.random.categorical batch size by doubling from a 1024-shot base until throughput
plateaus (Tsim heuristic), memoized per category count (2**len(qubits)). An explicit int
pins the batch and draws in chunks with deterministic per-chunk subkeys; a seeded "auto"
run draws in a single deterministic pass so results stay reproducible. CPU/Metal accept the
kwarg for interface parity (host NumPy sampling has nothing to tune).
Step 20: Fusion-width default + opt-in per-chip autotuning (src/macquerel/compiler.py)
fuse_gates(max_fused_qubits=None) resolves to a fixed width of 4 — the zero-config
default, with no measurement on the hot path. Autotuning is opt-in via
MACQUEREL_FUSION_WIDTH: an int pins the width; auto runs autotune_fusion_width(), which
measures the optimal width on the local chip once and caches it
(~/.cache/macquerel/fusion_width.json + in-memory). Measurement failures fall back to 4 and
never raise.
Why 4, and the ideal width per qubit count. The optimal width drifts with qubit count,
because fusion trades a one-time matrix-composition cost against the per-apply cost of a full
pass over the 2ⁿ state. Benchmarked on an M5 Max (fuse+apply, MLX backend):
| qubits n | ideal max_fused_qubits |
regime |
|---|---|---|
| ≤ ~16 | 1–2 (immaterial) | apply is sub-ms; composition overhead dominates |
| ~20 | 3 | apply starting to dominate |
| ~22 | 4–5 | |
| ~24 | 5–6 | apply-bound — wider fusion = fewer passes |
| 17–30q aggregate | 4 | normalized winner across the measured regime |
No single width is optimal everywhere, but 4 wins on normalized aggregate across the measured 17–30q MLX tier, so it is the default. This was settled by re-running the benchmarks: a first cut autotuned on a single QFT at n=18 and picked width 2, which regressed the large-n path by up to ~2× (22q QFT: 617ms→1376ms on CPU; 131→222ms on MLX) while only shaving negligible ms off sub-16q circuits. The opt-in autotuner now measures fuse+apply across a span straddling the regime (MLX 20q/22q, else CPU 14q/16q), normalizes each qubit count by its own fastest width, and picks the lowest aggregate (ties within 2% break toward 4); on this chip it confirms 4. Full benchmark write-up: https://github.com/guenp/macquerel/pull/8#issuecomment-4636543327.
v0.2.x — GPU backend performance (Steps 21-30)
Status: SHIPPED (2026-06-10), branch
gpu-perf-plan. Goal: make the MLX and Metal backends competitive with Qiskit Aer / Qulacs on runtime. Every step was A/B-benchmarked withbenchmarks/run_step_bench.sh(subprocess-isolated, min-of-3, per-step JSONs named<step>-<commit>-<backend>.json); full data, charts, and per-step justifications inbenchmarks/data/steps/README.md. Execution order was 21 → 22 → 24 → 23 → 25 → 26 → 27 → 28 (24 moved before 23 after review so the memory-cliff fix would not confound 23's large-n A/B).
Step 21: Auto-select 22q+ → Metal ✅ (7cad261, superseded by 0806f3e)
Routing-only quick win from the baseline data (Metal beat MLX 2.7–5.1× at 24–28q while
auto still routed there to MLX). Re-tuned at the end of the line: after Steps 22+25,
Metal wins at every measured count ≥17q, so the tiers are now CPU ≤16q / Metal ≥17q,
with MLX serving 17–30q only when pyobjc-framework-Metal is absent.
Step 22: Metal batched command-buffer encoding ✅ (58cc612) — Metal 1.30× geomean
Gates are encoded into one open command buffer and committed at observation boundaries
(_view) or every 256 dispatches, instead of commit + waitUntilCompleted per gate;
_const matrix/index buffers are cached by content (in-flight safety rests on the
command buffer's default retention of referenced resources — regression-tested by
shrinking the cache cap). random@6 22.6→12.1 ms, random@20 106.8→64.2 ms; neutral at
26–28q (bandwidth-bound).
Step 24: MLX periodic mx.async_eval ✅ (bf78f05) — random@28 1.56×
P1 removed per-gate eval but left a depth-d lazy graph holding O(d) full-width
temporaries (peak ≥ ~16× state size → swap at 28q). async_eval(sv.data) every 16
gates (only ≥24 qubits) bounds the working set: random@28 40.0→25.6 s. Interval 8–64
measured flat (±1%); every non-swapping cell unchanged.
Step 23: MLX axis-order tracking ✅ (7bbc216) — 1.05–1.15× on dense circuits
MLXState.perm records the post-tensordot axis order instead of paying a full-state
transpose+copy per dense gate; diagonal/permutation/controlled paths translate targets
through the map; the permutation is materialized once at readback. Verified by
mixed-kind fuzz (dense+diagonal+permutation+controlled interleaved), partial
abs2sum/sampling, and readback-ordering tests. Gain bounded because mx.tensordot
still permutes its input internally — the planned Step 29 custom kernel became
unnecessary once Step 27 landed.
Step 25: Kind-specialized Metal kernels ✅ (bc346fb) — Metal 1.36× geomean, random@24–28 2.7–3.1×
(a) Pipelines compiled per gate width with K_FIXED baked in as a preprocessor macro:
the per-group amp[]/idx[] arrays unroll into registers (runtime-k indexing was
spilling) — this is where the ~3× on fused 4q dense gates came from. (b) A monomial
kernel applies permutation-class gates with 2^k multiplies per group instead of 4^k
MACs (1.9× on 4q monomials at 20q; neutral ≥24q). (c) Threadgroup sweep 64/256/1024
was flat; 256 kept.
Step 26: Diagonal-run wide fusion + CPU diagonal path ✅ (14cdf74) — QFT-focused
Second fusion pass merges adjacent diagonal gates (including diagonal composites such
as CX·Rz·CX from pass 1) into up-to-8-qubit diagonals via an O(2^k) elementwise
product. Width sweep: 7–8 win; 10 regresses (materializing + classifying 1024×1024
dense matrices outweighs the saved passes) — MACQUEREL_DIAG_FUSION_WIDTH overrides.
The CPU backend gained a broadcast in-place diagonal multiply (with memoized classify;
an unmemoized check cost ~10µs/gate on the raw path, caught by bench_versions).
cpu qft@22 680→268 ms; metal qft@28 1393→1025 ms; mlx qaoa@28 1.19×.
Step 27: Commutation-aware fusion grouping ✅ (3a742e8) — largest single step
Replaced the single greedy in-order group with a multi-open-group scheduler: each gate lands in or after the latest open group it shares a qubit with (the only real ordering constraint; disjoint-qubit gates commute), joining the first group with capacity, with at most 8 open groups. Brickwork circuits collapse into rolling neighborhood groups: mlx random@24 1314→171 ms (7.7×), random@28 23.5→2.7 s (8.5×); metal random@24 180→99 ms; cpu random@22 1528→664 ms. GHZ unchanged (a CX chain has nothing to reorder). Geomeans step-over-step: mlx 1.46×, cpu 1.17×, metal 1.15×.
Step 28: Qubit remapping wired, gated OFF ❌ kept disabled (f55fea2)
remap_qubits_with_perm returns the applied permutation; statevector() inverts it at
readback and counts stay in caller order for free (MeasureOp labels are rewritten in
list order). The A/B lost on every backend/circuit at 24q (metal qft 61→79 ms, random
89→126 ms): the readback inverse transpose outweighs any stride benefit and the GPU
kernels are stride-insensitive. Ships disabled; MACQUEREL_REMAP=1 opts in.
Step 30: Per-backend, qubit-aware fusion-width defaults ✅ (3a745fb) — metal 1.30× / cpu 1.32× geomean
A fusion-width re-sweep (benchmarks/data/fusion_width.json: widths 1–6 ×
{QFT, random, QAOA, QV} × 16–24q, all three backends) showed the optimal
max_fused_qubits became a backend property after Steps 22/25: with Metal's per-gate
overhead mostly gone, wide fusion at small/mid n only pays host-side matrix
composition and densifies cheap diagonal/monomial gates. Defaults are now resolved per
(backend, qubit count) by default_fusion_width: metal 2 ≤22q, cpu 3 ≤18q,
otherwise 4; mlx 4 everywhere — fuse_gates takes the target backend and the
Simulator passes the one it selected; MACQUEREL_FUSION_WIDTH still pins a global
width and auto still runs the autotuner. The qubit tiering is load-bearing: a flat
metal width 2 won the sweep's normalized aggregate (1.58× vs width 4) but the step A/B
exposed 2.7–3.7× regressions on random@24–28 — at 24q+ every backend is apply-bound
and 4 still wins. Shipped A/B: metal 1.3–2.15× at 6–20q (qft@20 21→10 ms, random@20
41→28 ms), cpu 1.4–1.8× ≤16q, large n flat at 1.00×; mlx re-measured as a no-change
control (1.01×). Known compromise: metal random@22 0.85× (22q nets ~1.17× across
circuits).
Net result
Cumulative vs the line's baseline (geomean over ghz/qft/random/qaoa): Metal 2.5–2.9×
across 6–28q; MLX 1.9–2.6× at 22–28q (best cell random@28 14.7×: 40.0 s →
2.7 s); CPU 1.5–2.0× (best cell qft@22 3.6×). Versus Qiskit Aer
(benchmarks/data/large): macquerel-metal wins from 20q (random 28 vs 51 ms), 5–12×
faster at 24q+ (random@24 99 ms vs 914 ms). The release-regression harness
(bench_versions.py) shows current faster than v0.2.0 on every backend at 8–12q. G3
(28q cliff) and G4 (auto picks measured-fastest) met; G2 (Metal crossover) moved from
≥22q to ~20q; G1 met at the system level (Metal tier), with MLX itself still behind
Aer only on QFT at 24q+.
v0.2.x+ — performance candidates (Steps 31-35)
Status: SHIPPED (2026-06-10), branch
perf-candidates. The five measured candidates that came out of the backend comparison (backends.md), each A/B-benchmarked per the protocol: re-baselined at the 0.2.1 release commit (step32-baseline, a 0.99-1.00× no-change control vs Step 30), per-step JSONs inbenchmarks/data/steps/, full write-ups inbenchmarks/data/steps/README.md. Execution order was 32 → 33 → 34 → 35 → 31.
Step 32: MLX broadcast diagonal path ✅ (fef6417) — mlx 1.20× geomean, qft@22-28 2.5-4.3×
The diagonal path built a full-width gather table (k shift/or passes to build a 2^n gate-row index, plus a full-width phase gather) before the multiply. Replaced with a single broadcast elementwise multiply: the state viewed with one length-2 axis per target qubit (gaps collapsed, so the view stays ≤2k+1-dimensional) times the (2,)*k diagonal. This was the "in-place-style diagonal path" candidate aimed at the wide-diagonal QFT cells where MLX trailed Metal 6-10×: qft@28 9.08→2.12 s, qaoa@28 2.4×; everything else flat within GPU clock variance.
Step 33: custom MLX dense kernel via mx.fast.metal_kernel ✅ (4fff625) — mlx 1.09× geomean, random@22-28 1.16-1.61×
The deferred Step 29. Dense/controlled gates now use the native Metal backend's
group-per-thread kernel design (Step 25), with gate width and control count baked
into per-(k, nc) generated source so the loops unroll — bypassing mx.tensordot's
internal input permutation, the dominant cost on scattered-target circuits and the
half that Step 23's axis-order tracking could not remove. MLX kernel inputs are
const device (issue #2547), so the result double-buffers; tensordot remains the
k>6 fallback (fusion never emits those). Matters for the no-PyObjC fallback tier.
Cumulative with Step 32: mlx 1.30× geomean, 2.16× at 28q vs the 0.2.1 baseline.
Step 34: lower the Metal small-n floor ✅ (4e05d01) — metal 1.07× geomean, ghz@24-26 1.6-1.8×, init 7.5 ms → 30 µs
(a) Device, command queue, and per-k compiled pipelines are process-wide;
MetalBackend() construction — paid on every backend="auto" call — drops from
~7.5 ms to ~30 µs, and the Simulator now reuses backend instances across
auto-mode calls (seeded simulators keep fresh-per-call backends so reruns stay
bit-identical). (b) State buffers recycle through a size-keyed per-backend pool;
buffers whose state dies while the open command buffer may still reference them
are parked until the next flush. (c) Redundant per-dispatch setBuffer/setBytes
ObjC calls are skipped. Apparent small-n regressions in the min-of-3 A/B did not
reproduce at reps=9 (ghz@12 1.31→0.86 ms, a win — the baseline cell was a
lucky-fast outlier).
Step 35: per-chip backend-tier autotuning; CPU tier default 16 → 15 ✅ (800691d)
The CPU/GPU crossover is a chip property (the old 16q constant was measured on an
M5 Max). Mirroring the fusion-width pattern: MACQUEREL_BACKEND_TIERS=<int> pins
the CPU tier's max qubit count; auto measures the crossover once (QFT +
brickwork random on both backends across 10-20q, requiring the GPU to win
sustainably, not at one lucky count) and caches to
~/.cache/macquerel/backend_tiers.json; failures fall back to the default and
the zero-config path never measures. The default moved to 15: after Step 34,
Metal wins qft/random/qaoa at 16q (qft 5.6 ms vs cpu 9.2 ms) and the autotuner
independently measures cpu_max=15 on this chip.
Step 31: BatchedSimulator ✅ (9b00708) — 26-47× at 4q, 20-45× at 8q, 14-23× at 12q, 2.2× at 16q vs a per-circuit loop
The v0.3 batched small-circuit feature, pulled forward. The small-n regime is
dispatch-bound, so a B-circuit parameter sweep run one circuit at a time pays the
fixed per-run costs B times. BatchedSimulator groups the batch by structure
signature (gate positions/targets/controls) and evolves each group as one
(B, 2^n) tensor: one batched matmul per gate position — or one broadcast phase
multiply when every circuit's matrix there is diagonal — with controlled gates
lifted to plain unitaries on controls+targets. Engines: NumPy and MLX (lazy
graph; the whole batched circuit evaluates in a few fused kernels); auto
routes on total size log2(B)+n against the Step 35 tier boundary, which picks
the faster engine in every measured cell (benchmarks/data/batched.json).
Design findings: per-circuit gate fusion was 99% of a fused prototype's
runtime — batching already amortizes dispatch, so the batched path skips
fusion entirely; and run() requires explicit MeasureOps (no implicit
measure-all), keeping batched semantics unambiguous. Differential-tested against
the per-circuit Simulator on parameter sweeps, mixed-structure batches,
controlled/diagonal gates, and sampling distributions (tests/test_batched.py).
Net result
Cumulative over the line (vs 0.2.1 baseline, geomean over ghz/qft/random/qaoa): mlx 1.30× overall, growing to 2.16× at 28q (best cell qft@28 4.5×) — the MLX fallback tier no longer has a pathological QFT gap; metal 1.07× overall concentrated at 20-26q plus the 250× construction-cost removal on the auto path; cpu untouched. Against the full two-line arc, the cumulative geomean vs the step20 baseline stands at metal 2.85×, mlx 2.04×, cpu 1.63×. The batched API turns small-circuit sweeps from a per-run-overhead problem into a single launch per gate position (up to 47× measured).
v0.3 — noise channels / density matrices
Status: SHIPPED (2026-06-11), branch
feat/density-matrix-noise. The first v0.3 feature:DensityMatrixSimulatorwith Kraus-operator channels.
DensityMatrixSimulator ✅
The density matrix is carried as its row-major vectorization — a 4**n
complex64 array the existing statevector backends treat as an ordinary 2n-qubit
state (ket axes 0..n-1, bra axes n..2n-1). That single representational
choice meant zero backend changes:
- a unitary
rho -> U rho U^daggeris twoapply_matrixcalls (U on the ket axes,conj(U)on the bra axes; controls shift with their targets); - a Kraus channel
rho -> sum_k K_k rho K_k^daggeris one dense superoperatorsum_k K_k (x) conj(K_k)applied to the channel's paired ket+bra axes — a width-2q dense gate the backends already dispatch; - measurement probabilities are the diagonal
rho_ii, the stride-2**n + 1slice of the vectorization, read through a zero-copy host view on CPU/Metal (no full-matrix readback);purityis one BLASvdotover the same view.
Channels live on the circuit (Circuit.bit_flip/.phase_flip/.depolarizing/
.amplitude_damping/.phase_damping/.kraus, validated for completeness at build
time) as ChannelOps, which the fusion pass treats as barriers — gate runs
between channels still fuse, with the width resolved at the doubled qubit count
where the applies actually happen. The statevector Simulator and
BatchedSimulator reject noisy circuits with a pointer to the DM simulator.
Memory: an n-qubit density matrix costs exactly a 2n-qubit statevector, so
the backend ceilings land at n=15 (MLX, int32 ShapeElem at 2n=30) and n=16
(Metal, 32 GiB). Measured (bench_memory.py --series dm): metal stays on the
theoretical 4**N x 8 B line (32.2 GiB at N=16), cpu peaks ~3x, mlx ~16-25x —
the same multipliers as the statevector series at the doubled count. Runtime
(bench_density.py): crossovers mirror the statevector tiers — cpu wins
through N~6-7, metal everywhere above (noisy GHZ@16 in 6.0 s, random@16 8.5 s).
Correctness: differential-tested against a direct dense rho reference on
random noisy circuits, against Simulator on noiseless circuits
(rho == |psi><psi|), and against analytic channel formulas; physicality
(trace, hermiticity, positivity, purity decay) holds across all three backends
(tests/test_density.py, tests/test_noise.py).
v0.3.x — RAM usage candidates (Steps 36-40)
In progress on branch
perf/v0.3.x-ram; remaining steps tracked inplan.md.
Step 36: MLX monomial kernel + eval cadence + pool release ✅ (3decb13) — peaks 19-25× → 3-5×, ghz@24-28 6.5-7.9× faster
The measured 19-25× MLX memory peaks were mostly not the eval cadence: the monomial gather path built its source-index table on-device out of ~5 full-width uint32 lazy-graph intermediates per fused permutation gate — a 28q GHZ held 10-12 GiB live for a 2 GiB state, and the lazy graph keeps every index temporary alive until evaluation. Three changes landed together:
- Register-resident monomial kernel (the Step 33 design applied to generalized permutations): one thread owns a group, computes its indices in registers, reads the group through the gate's row permutation, and applies the per-row phase — the only full-width buffers are the input and output state. The on-device gather path remains the k>6 fallback.
- Tight eval cadence with backpressure above 26 effective qubits:
async_evalevery 2 gates (was 16), blocking on the checkpoint from one interval ago before kicking the next. The blocking half matters becauseasync_evalalone never blocks — a shallow circuit encodes its whole graph before the GPU retires anything, keeping every intermediate live regardless of cadence (measured: cadence alone only halved the peaks). - Pool release at observation boundaries, gated on the freed-buffer pool exceeding ⅛ of unified memory; smaller pools stay warm. (An unconditional clear cost qaoa@24q 2.4× in re-allocation; a 1 GiB threshold still paid it.)
A/B (GHZ memory cells vs benchmarks/data/memory.json baseline): sv peaks drop
3.5-3.8× — 28q 39.2 → 10.2 GiB (19.6× → 5.1× theory), 26q 9.15 → 2.65 GiB —
and dm n=14 49.2 → 8.15 GiB. Newly fitting cells: sv 29q/30q at 3.0×
(12.1/24.2 GiB; 30q previously drove the machine into swap at ~16×) and the
previously-skipped dm n=15 (32.2 GiB), both un-skipped by recalibrating
_PEAK_MULT (mlx 16.0 → 6.0). Runtime improved in every measured cell
(benchmarks/data/steps/step36-baseline-0c4c9dc-mlx.json vs
step36-3decb13-mlx.json): ghz@24-28 6.5-7.9×, qft 2.1-2.6×, random 1.2-1.8×,
qaoa par-1.09×. Buffer-donation audit: MLXState and the simulator hot path
hold no extra state references; the per-n arange cache and the pending-eval
checkpoint (cleared at boundaries) are the only retained arrays.
Step 37: TrajectorySimulator — Monte-Carlo wavefunction noise ✅ (2b63036) — noisy circuits at 2**n memory, 30q GHZ 10.3 s/trajectory
Noisy simulation without the density matrix's 4**n cost: each trajectory evolves
an ordinary statevector; every Kraus channel applies one operator sampled with the
Born probability p_k = <psi|K_k^dagger K_k|psi>, then renormalizes. Exact in
expectation (Mølmer–Castin–Dalibard); error ~1/sqrt(trajectories). Reuses the
backends, ChannelOps, and fusion (channels stay barriers) unchanged, with auto
selection at the statevector count — noisy circuits reach the Metal range instead
of the DM's n=16 cap. Jump probabilities need no state copies: every built-in
channel has diagonal effect operators E_k, so all p_k come from one
abs2sum marginal over the channel qubits (compatible with Metal's in-place
state); arbitrary non-diagonal kraus(...) channels fall back to the channel-qubit
reduced density matrix off a host view.
Two measured-at-30q memory findings shaped the implementation: (a) a fresh seeded
backend per trajectory pinned a new state buffer each time — now one derived-seed
backend per call keeps reproducibility (the whole stream derives from seed) and
shares the pool; (b) re-allocating the state per trajectory accumulated one
state-sized footprint per trajectory — released multi-GiB MTLBuffers are
reclaimed lazily by the driver and the Step 34 pool caps at 1 GiB — so trajectories
reset the state in place through the zero-copy view (4 trajectories at 30q:
47.3 → 21.5 GB peak, now constant in trajectory count). Demo: noisy 30q GHZ
(depolarizing ×3), 4 trajectories, 4000 shots on Metal — 10.3 s/trajectory.
Tests: noiseless exactness vs Simulator, stochastic agreement with
DensityMatrixSimulator (probabilities, Pauli expectations, a non-diagonal-effect
channel forcing the fallback), sampling semantics, seeding, backend parity
(tests/test_trajectory.py).
Step 38: expectation_pauli via monomial gather ✅ (fe6e0a7) — 6.3× faster, 2.9× less peak (n=14, 4 terms, Metal)
A Pauli string is monomial — P|i> = phase(i)|i ^ mask> with mask the X/Y bit
pattern — so tr(rho P) = sum_i phase(i) * rho[i, i ^ mask] with
phase(i) = i**(#Y) * (-1)**popcount(i & zy_mask): one 2**n-element gather off
the zero-copy host view (CPU array / Metal unified-memory buffer; MLX pays one
readback), like probabilities already does for the diagonal. Replaces the full
4**n host readback plus a state-sized copy and two CPU gate applies per term —
at the n=16 Metal ceiling the old path's transients alone were ~3 state sizes
(~96 GB), past the machine's safe budget. density_matrix() gains an opt-in
copy=False zero-copy view with the same mechanism. A/B at n=14 (GHZ +
depolarizing, 4 mixed terms incl. Y, post-evolve call): 1.63 → 0.26 s and
13.0 → 4.45 GB peak, identical values; correctness gated against tr(rho P) on
the dense reference across backends (tests/test_density.py).
Step 39: CPU in-place chunked dense apply ✅ (bb230f0) — peaks 3.0× → 1.03×, runtime up to 1.70× faster
The tensordot dense path made ~3 full state copies per gate (its internal input
permutation, its output, and the non-contiguous reshape on write-back). Replaced
with an in-place chunked apply: transpose the (2,)*n view so the target axes
lead (a stride trick, no data movement), then loop bounded chunks over the
non-target axes — gather a chunk into contiguous scratch, one GEMM into a second
scratch, scatter back to the same positions (safe in place: each group depends
only on its own amplitudes). Chunk size 2¹⁶ columns measured fastest (16 MiB of
scratch at k=4); the controlled path reuses the same routine on its control-slice
view. Stage (a) of the plan — np.einsum(..., out=...) — was prototyped and
rejected: without optimize einsum loses BLAS (14× slower at 24q/k=4), with
it the intermediates return. A/B: cpu peaks drop from 3.0× to ~1.03× of theory
(28q GHZ 6.04 → 2.05 GiB, dm n=14 6.04 → 2.06 GiB) and runtime improves in every
measured cell, growing with size — random@24q 1.70×, qaoa@22q 1.49×, ghz@22-24q
1.33×, qft@24q 1.31× (benchmarks/data/steps/step39-*.json). _PEAK_MULT cpu
4.0 → 1.5.
Step 40: single-pass ket⊗bra superoperator for narrow DM gates ✅ (8361126) — metal/cpu/mlx 1.0-1.09×, two variants rejected on measurement
Control-free DM unitaries now apply as one kron(U, conj(U)) gate over their
paired ket+bra axes — one pass over the 4**n state instead of two — when the
doubled gate stays inside the backend fast envelope. Eligibility is per gate
kind, because kron preserves it: diagonal superoperators stay diagonal
(broadcast multiply; eligible to k=4, where the materialized 4**k × 4**k
matrix is still small), monomial stays monomial (k≤3 — doubled width 6, the MLX
kernel cap), dense caps at k=2. Superoperators are memoized by matrix bytes;
controlled gates keep two passes (a controlled-U's ket⊗bra product
cross-multiplies its control projectors and is not a single controlled gate).
The decisive findings were the rejections: dense superops at doubled width 6
spill GPU registers (random_noise@12-14q on Metal 5× slower), and capping
the DM fusion width at the superop width (so every fused gate qualifies) loses
more to extra passes than single-pass saves (ghz_noise on cpu −21%). The
shipped kind-aware rule is a small, consistent win with no regressions: metal
1.00-1.09×, cpu 1.02-1.07× (reps=7 where reps=3 looked noisy), mlx 0.99-1.06×
(benchmarks/data/steps/step40-*.json).