wai-quantum 0.3.32: union-find decoding in near-linear time #155

Merged

dcharlot merged 2 commits from wai-quantum-uf into main 2026-10-05 10:56:33 -04:00

Conversation 0 Commits 2 Files changed 14 +934 -14

dcharlot commented 2026-10-05 07:46:16 -04:00

Owner

Copy link

Stacked on #151 (0.3.31). Merge that first; this diff then reduces to the one commit.

What

quantum_uf (wai-quantum 0.3.32) is a union-find decoder over the same matching graph that exact matching uses.

• Growth. Clusters grow from the fired detectors on integer weights. An edge between two growing clusters fills at double speed.
• Merge and peel. Clusters merge as edges fill and stop when they touch the boundary. Each cluster's spanning tree is then peeled to a correction.
• Speed. Growth is event-driven: each frontier edge has a fill time, and a merge reschedules only the frontier whose growth changed. Fill times never run backwards, so events sit in a radix heap. The workspace is reused and resets in time proportional to the last shot.
• CLI. wai-quantum qec --decoder uf|exact. Example: uf_bench.

Checked

• Single faults. Every single edge of the d = 3 and d = 5 graphs is corrected exactly.
• Two growth schedules agree. The event-driven schedule matches a round-by-round one (kept in the tests) on 2,000 shots at each of three distances, apart from the order ties resolve in.
• Accuracy against exact matching, same 20,000 shots. Union-find fails 0.92–1.18× as often as exact matching (d = 3–9, p = 0.003–0.007). At p = 0.007 its failures stop falling with distance, so its threshold sits a little lower.
• Speed.
  • Union-find is 77× faster than exact matching at d = 11, p = 0.005.
  • Time per shot grows linearly with the number of fired detectors, about 1.1–1.5 µs each from d = 9 to d = 21.
  • Profiling found 45% of the time in a binary heap. Switching to the radix heap halved the time per shot at d = 21.
• Determinism. The new pin holds natively and under wasm32-wasip2; all 17 pins pass. CLI output is byte-identical between the two.
• Lint and tests. Clippy is clean on the new code, the prose checks pass, and all 409 library tests pass.

🤖 Generated with Claude Code

Stacked on #151 (0.3.31). Merge that first; this diff then reduces to the one commit. ## What `quantum_uf` (wai-quantum 0.3.32) is a union-find decoder over the same matching graph that exact matching uses. - **Growth.** Clusters grow from the fired detectors on integer weights. An edge between two growing clusters fills at double speed. - **Merge and peel.** Clusters merge as edges fill and stop when they touch the boundary. Each cluster's spanning tree is then peeled to a correction. - **Speed.** Growth is event-driven: each frontier edge has a fill time, and a merge reschedules only the frontier whose growth changed. Fill times never run backwards, so events sit in a radix heap. The workspace is reused and resets in time proportional to the last shot. - **CLI.** `wai-quantum qec --decoder uf|exact`. Example: `uf_bench`. ## Checked - **Single faults.** Every single edge of the d = 3 and d = 5 graphs is corrected exactly. - **Two growth schedules agree.** The event-driven schedule matches a round-by-round one (kept in the tests) on 2,000 shots at each of three distances, apart from the order ties resolve in. - **Accuracy against exact matching, same 20,000 shots.** Union-find fails 0.92–1.18× as often as exact matching (d = 3–9, p = 0.003–0.007). At p = 0.007 its failures stop falling with distance, so its threshold sits a little lower. - **Speed.** - Union-find is 77× faster than exact matching at d = 11, p = 0.005. - Time per shot grows linearly with the number of fired detectors, about 1.1–1.5 µs each from d = 9 to d = 21. - Profiling found 45% of the time in a binary heap. Switching to the radix heap halved the time per shot at d = 21. - **Determinism.** The new pin holds natively and under wasm32-wasip2; all 17 pins pass. CLI output is byte-identical between the two. - **Lint and tests.** Clippy is clean on the new code, the prose checks pass, and all 409 library tests pass. 🤖 Generated with [Claude Code](https://claude.com/claude-code)

dcharlot added 2 commits 2026-10-05 07:46:17 -04:00

wai-quantum 0.3.31: quantum-inspired optimisation, a re-runnable classical baseline ... 92f9e000cd

Optimisation is the claim made most often for quantum hardware, and each such
claim is a comparison with a classical solver. quantum_qio is that solver,
deterministic and re-checkable:

- Ising problems (sparse symmetric J, fields h) and Max-Cut (J = -w), a G-set
  reader, and the +-1 all-to-all spin glass.
- Simulated bifurcation from its published update rules: symplectic Euler,
  perfectly inelastic walls, ballistic (f = Jx) and discrete (f = J sgn x)
  forces, and both heated (arXiv:2203.08361), with c0 = c1 / (rms(J) sqrt N).
  Fields ride on an extra spin fixed at +1.
- Eight trials advance per pass over the couplings; each trial's arithmetic is
  unchanged, so a batched run leaves the same final positions bit for bit as
  one trial at a time. The test fails on a 1e-15 change to one lane.
- Simulated annealing (single-spin Metropolis, linear beta), single-flip
  descent, an exact Gray-code referee up to 34 spins (threaded), and
  step-to-solution S = N_s ln 0.01 / ln(1 - P).

Checked:
- every variant and annealing reach the exact ground state on 20-spin glasses;
- G-set best-known cuts reached (seed 1): G1 11624 (39% of 2,000-step
  trials), G2 11620, G3 11622, G11 564, G14 3064 (annealing; bifurcation
  stops at 3062), G22 13359, G43 6660; G55 reaches 10292 of 10299;
- the published dense-glass step (1.1) is unstable on sparse Max-Cut graphs:
  the stiffest mode has w^2 = a0(a0 - c0 mu_min) and mu_min = -degree, so G1's
  limit is near 0.88; documented, with the settings that work.

CLI: wai-quantum qio (--gset FILE | --sk N) --method dsb|bsb|hdsb|hbsb|sa|exact
[--descend --target --spins --json]. Example: qio_gset. Pinned bit for bit
natively and under wasm32-wasip2 (16 pins); CLI output byte-identical across
the two, threaded or not, G-set files included.

Co-Authored-By: Claude Opus 5.5 <[email protected]>

wai-quantum 0.3.32: union-find decoding in near-linear time ... e76acbe9e5

A fault-tolerant machine must decode each syndrome round before the next
arrives. Exact matching (quantum_match) is the accuracy reference; quantum_uf
is the fast decoder over the same matching graph:

- Grow: every fired detector starts a cluster; odd clusters (not on the
  boundary) grow all frontier edges at once, on the graph's integer weights,
  an edge between two growing clusters at double speed.
- Merge: a filled edge joins its clusters; a cluster on the boundary stops.
- Peel: each cluster's filled edges as a spanning tree, rooted at the
  boundary when it holds it, peeled leaves-first into a correction.
- Growth is event-driven: each frontier edge carries a fill time, and a merge
  reschedules only the frontier of a side whose growth changed. Fill times
  never run backwards, so events sit in a radix heap at amortised O(1).
  Profiling put 45% of the time in a binary heap before; the radix heap
  halved the time per shot at d = 21. Time now grows linearly with fired
  detectors, about 1.1-1.5 us each from d = 9 to d = 21.
- A reusable workspace resets in time proportional to the last shot.

Checked:
- every single edge of d = 3 and d = 5 graphs is corrected exactly;
- the event-driven schedule agrees with a round-by-round one (kept in the
  tests) on 2,000 shots at each of three distances, up to tie order;
- on the same 20,000 shots, union-find fails 0.92-1.18x as often as exact
  matching (d = 3-9, p = 0.003-0.007), 77x faster at d = 11; its threshold sits
  a little lower (at p = 0.007 its failures stop falling with distance).

CLI: wai-quantum qec --decoder uf|exact. Example: uf_bench. Pinned bit for bit
natively and under wasm32-wasip2 (17 pins); CLI output byte-identical.

Co-Authored-By: Claude Opus 5.5 <[email protected]>

dcharlot referenced this pull request 2026-10-05 08:08:11 -04:00

wai-quantum 0.3.33: noisy circuits, and where the digital error model is off #156

dcharlot added 1 commit 2026-10-05 09:07:54 -04:00

wai-quantum 0.3.32: close the optimisation pin's test function ... 79dd50d20b

The restack onto 0.3.31 left tests/bit_identity.rs with an unclosed function,
so the integration tests did not compile (the linux energy-receipts job). The
fix was staged after the commit by mistake. Also trims the union-find vs exact
matching comparison to 6,000 shots per distance (about 25 s in debug).

Co-Authored-By: Claude Opus 5.5 <[email protected]>

dcharlot referenced this pull request 2026-10-05 09:50:45 -04:00

wai-quantum 0.3.34: ground states of spin chains by DMRG, held to exact answers #159

dcharlot merged commit 1fc3297855 into main 2026-10-05 10:56:33 -04:00

dcharlot referenced this pull request from a commit 2026-10-05 10:56:34 -04:00

Merge pull request 'wai-quantum 0.3.32: union-find decoding in near-linear time' (#155) from wai-quantum-uf into main

dcharlot referenced this pull request 2026-10-05 11:14:04 -04:00

wai-quantum 0.3.35: time evolution of spin chains by TDVP, held to exact answers #160

Sign in to join this conversation.

Reviewers

No reviewers

Labels

Clear labels

No items

No labels

Milestone

Clear milestone

No items

No milestone

Projects

Clear projects

No items

No project

Assignees

Clear assignees

No assignees

1 participant

Notifications

Subscribe

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set

Reference

Transaction-Science/open-standards!155

No description provided.