open-standards/wai/wai-quantum/docs/qec.md

# Error correction and mitigation

`engine::qec` answers three calls, the same on every surface: the command
line (`wai-quantum qec code|decode|threshold`), both MCP servers (`qec_code`,
`qec_decode`, `qec_threshold`), the job service (`POST /v1/qec/code`,
`/v1/qec/decode`, `/v1/qec/threshold`), the Studio's error-correction pane,
the desktop app and Python (`wai_quantum.qec_code`, `qec_decode`,
`qec_threshold`). Each answer is `{"request", "result"}`, the result sealed
in a job's receipt, so `wai-quantum verify` and `wai_quantum.verify` check
it. A request the engine cannot answer is refused with `J009`; the job
service's bounds on shots, points and distances refuse with `J031`.

Mitigation is part of a job: `"mitigate"` beside `"noise"` and
`"observables"` (`wai-quantum run --mitigate zne`, `wai_quantum.run(...,
mitigate="zne")`, the Studio's Noise section). Its refusals are `J008`.

## Codes

| Name | Code | Notes |
|---|---|---|
| `surface:D` | the rotated surface code, `[[D², 1, D]]`, odd `D` from 3 to 15 | |
| `toric:L` | the toric code, `[[2L², 2, L]]`, `L` from 2 to 12 | |
| `steane` | `[[7, 1, 3]]` | the `d = 3` colour code |
| `color:D` | the triangular 6.6.6 colour code, `[[(3D² + 1)/4, 1, D]]`, odd `D` from 3 to 15 | `quantum_color` |
| `bb:72`, `bb:90`, `bb:108`, `bb:144` (`gross`), `bb:288` | the bivariate-bicycle codes | `quantum_ldpc` |

A code's answer gives its checks (Z-type: they see X errors) and stabilizers
(X-type), `k` counted by rank, a layout to draw it, and the decoders it
takes.

### The distance certificate

`quantum_distance::certify` finds, in each sector, the least weight of a
logical operator: a support that commutes with every check and is not in the
span of the stabilizers. The search grows connected supports (a lightest
logical of these codes can always be taken connected in the graph where two
qubits meet when they share a check), branching on the first violated check,
barring siblings already tried, and pruning by the least number of qubits that
could still satisfy the violated checks. A code's symmetries (a
bivariate-bicycle code's translations) shrink the search to one support per
orbit; each symmetry is checked to map the checks onto themselves before it
is used.

The certificate (`wai.quantum.distance/1`) gives, per sector, the distance,
a witness of that weight, `no_logical_below` and the search's node count, and
a digest of the code's checks. Checking one (`"certificate"` in the request,
`--check FILE`, `certificate=` in Python) verifies each witness is a logical
of its stated weight and runs the search again, node for node. A search
stopped by `bound` says no logical is lighter than the bound and settles
nothing past it. The colour codes are certified to `d = 9` in the test suite
(`d = 7` in a debug build), the bivariate-bicycle codes from 72 to 144 qubits
in a release build; `bb:288` (`[[288, 12, 18]]`, 575 million search nodes, about
18 s in a release build) is certified on the command line, and the job
service refuses its certification as more work than one request takes.

## Decoders

Every decoder here is held to one test before any rate is measured: **every
error below half the distance is corrected to a trivial residual** (at
circuit level: every set of edges below half the matching graph's distance,
with every edge at one probability). That test has found bugs that aggregate
rates did not show.

### At code capacity (`"code"` with `"syndrome"` or `"error"`)

| Decoder | For | Guarantee |
|---|---|---|
| `matching` | codes whose qubits sit in at most two checks of a kind (surface, toric) | exact minimum-weight perfect matching: every error below half the distance corrected |
| `union_find` | the same codes | linear time in the fired checks; the same ground truth checked |
| `color` | colour codes | restriction to matching on the three restricted lattices, lifted at each colour, completed below half the distance by an exact search: every error below half the distance corrected (checked to `d = 9`) |
| `relay_bp` | any code | belief propagation with relayed memory; it can stall on a degenerate error of a topological code and then says it did not converge |
| `search` | any code | the lightest error with the syndrome, up to `max_weight` (at most 8) |

Given an `error`, the answer decodes its syndrome and judges the residual:
a product of stabilizers (the logical state is unharmed), a logical
operator, or a correction that does not explain the syndrome.

### At circuit level (`"memory"`, `"circuit"` or `"model"`)

`memory` is the rotated surface-code memory experiment (`distance`,
`rounds`, `p`); `circuit` is a noisy Clifford circuit in the ecosystem's
circuit text; `model` is a detector error model in its text. With
`detectors` the answer predicts which observables flipped; with `shots`
(a circuit is needed) it samples and decodes, and gives the failures, the
rate and its standard error, `(rate·(1 − rate)/shots)^½`.

| Decoder | What it does | Guarantee |
|---|---|---|
| `matching` | exact minimum-weight perfect matching (blossom, integer weights) | every edge set below half the graph's distance corrected |
| `correlated` | matches once, lowers the weight of the other parts of each decomposed fault the first matching used, matches again, and keeps the second answer only when the model's mechanisms explain it more cheaply | the same edge-set guarantee; on the `d = 5`, two-round experiment's 95,703 sets of one or two faults it misses 73 pairs where matching misses 103, and neither misses a single fault |
| `union_find` | union-find over the same graph | the edge-set ground truth checked |
| `bp_osd` | belief propagation with ordered-statistics post-processing | for models that are not graphlike |
| `window` | a sliding window as the syndrome arrives: `window: {commit, buffer}` rounds | a window that covers everything is the batch decoder on every shot; every edge set below half the distance is corrected once `buffer ≥ (d + 1)/2` |

The sliding window commits the matched edges that start in its first
`commit` rounds and decides the buffer's again in the next window. A buffer
shorter than the longest mechanism is refused; one round of buffer at
`d = 5` mispredicts 286 of the 166,176 sets of at most two edges, and a
buffer of `(d + 1)/2` rounds none. A stream states its **latency budget per
round** (`budget_ns`, the hardware's cycle time): a window must decode within
`commit × budget_ns` or work piles up behind it. `quantum_window::measure`
times every window on the machine it runs on and says which fit; the
prediction is the same bits everywhere, the timing is a measurement of that
machine and is labelled so.

## Thresholds

`threshold` measures logical failure rates over `distances` and physical
rates `p`: `family: "surface"` at circuit level (decoders `matching`,
`correlated`, `union_find`; the code model `P(d) = a·(p/p*)^((d+1)/2)` per
round fitted to the points), or `color`, `toric`, `surface_capacity` at code
capacity. Each point gives its shots, failures, rate and standard error;
`below_threshold` says, at each `p`, whether every larger distance failed
less. A crossing measured on few shots is not a threshold: quote rates with
their errors.

## The circuit and model texts

`quantum_qec_text` reads and writes the ecosystem's circuit text and detector
error model text, the subset the crate's circuits use and more: tags on
instructions (`DEPOLARIZE1[leak](0.01) 0`), Pauli-target observables
(`OBSERVABLE_INCLUDE(0) X0 Z3`), detector coordinates, `REPEAT` blocks,
`SHIFT_COORDS`, the axis-cycling gates `C_XYZ` and `C_ZYX`, correlated errors
(`E(p) X1 Y2 Z3`, also `CORRELATED_ERROR`) and one-qubit Pauli channels
(`PAULI_CHANNEL_1(px, py, pz)`), and in models `^`-separated decompositions,
`detector` and `logical_observable` declarations, `repeat` and
`shift_detectors`. A correlated error is a flip on a qubit of its own, handed
to its targets, so a circuit with one holds one qubit more than its text
names. A Pauli channel becomes the independent X, Y and Z flips with its law,
a rate above 1/2 among them where the law needs one; a channel with no such
flips (`PAULI_CHANNEL_1(0.1, 0.1, 0)`) is refused, since a model of
independent mechanisms cannot state it. A circuit's model written back keeps
its tags and coordinates. What the reader does not take it refuses with the
line, never skipping it. Blocks nest at most 32 deep (`MAX_BLOCK_DEPTH`), a
circuit names qubits below 2²⁴ (`MAX_QUBITS`; with its correlated errors'
carrier, it holds at most that many) and a model detectors below 2²⁴
(`MAX_DETECTORS`, offsets counted): what is made for an index is as long as
the index, so each is refused on its line, as is a block nested deeper, on the
line that opens it, so neither reading, unrolling nor writing a text recurses
past that. Every pass through a block counts toward the bound on what a text
unrolls to, so a block repeated without end that writes nothing still ends,
refused. The
[conformance vectors](../../quantum-conformance/qec-text/) hold each form,
the model each circuit gives, and each refusal.

## Mitigation

| Method | What it does | Bias | Variance |
|---|---|---|---|
| `zne` | zero-noise extrapolation: the program folded (`U U† U`) to odd noise scales (`factors`, default 1, 3, 5) and extrapolated to zero (`extrapolation`: `richardson`, `linear`, `exponential`) | assumes the value varies smoothly with the noise scale and that folding multiplies the noise by the factor; a curve of another shape leaves a bias the error bar does not include | each factor's shot noise carried through the extrapolation's coefficients, `(Σ c_i² σ_i²)^½`; a value outside [−1, 1] is reported as computed, not clipped |
| `pea` | error amplification: a sparse Pauli–Lindblad model learned from the device (here, from simulated benchmarking of the job's noise), its rates multiplied by each factor, and extrapolated | assumes the noise is the learned model under twirling; an error in the learned rates remains as bias (learned against true rates is in the details) | as `zne`; the learning's shot noise enters as model error, not in the error bar |
| `pec` | probabilistic error cancellation: each gate's learned channel inverted as a quasi-probability and sampled (`samples`) | unbiased when the learned model is the noise; `converges_to` says where the estimate goes for this learned model | grows as `γ²`; the error bar is the sampled circuits' signed, `γ`-scaled spread over `√samples` |
| `cdr` | Clifford data regression: near-Clifford circuits made from the program (`training`, keeping `keep` non-Clifford rotations) fit a line from noisy to ideal values | assumes one line relates noisy to ideal values for the program and its training circuits | the program's shot noise through the slope and the fit's residual spread |
| `vd` | virtual distillation: `Tr(ρ² O)/Tr(ρ²)` on two copies | the dominant eigenvector's distance from the ideal state remains | the ratio's, to first order, from shots on each |
| `readout` | the job's counts with each qubit's readout error inverted | assumes independent, symmetric misreads | amplified by `(1 − 2p)^−k`; negative quasi-probabilities kept |

Every mitigated value is reported beside the raw one, each with its error
bar, and labelled with the method, its options and its stated assumptions.
In simulation the ideal value is known and given too, so the bias can be
read; on a device it would not be. A job's own expectation values stay the
unmitigated ones; the mitigation sits beside them in the result and is
sealed with it. Mitigation needs a noise model and observables (counts, for
`readout`), refuses a program that measures in the middle, and is bounded at
8 qubits and a stated amount of work.

Pauli twirling and dynamical decoupling are compile passes, checked by the
equivalence ladder: see [the compiler page](compiler.md).

## Sampling a circuit

`quantum_frame` samples a noisy Clifford circuit by Pauli frames, 64 shots to
a machine word, noise placed by geometric gaps:

- `sample` gives the detection events and observable flips;
- `sample_measurements` gives every measurement's result. A frame is a
  difference from one noiseless run; that run (`reference`) is found once by
  an inverse tableau, which reads a measurement that is determined without
  noise in one pass over a row, and a shot's record is the reference's with
  its frame's flips. A measurement that is random without noise reads each
  way in half the shots: on small circuits the sampled records are held to
  the law a state vector gives, branch by branch.

One `(circuit, shots, seed)` gives the same bits on every machine. The
algorithm is fixed in the simulation extension (`extensions/quantum-sim.md`
§10) and the conformance set pins a reference record and two digests for
every circuit it holds.

```sh runnable
wai-quantum lab qec -d 3 --rounds 3 --p 0.001 --circuit > circuit.txt
wai-quantum lab qec --file circuit.txt --records --shots 4 --seed 7      # a line of 0s and 1s a shot
wai-quantum lab qec --file circuit.txt --digest --shots 1000 --seed 7    # the digests §10.5 defines
wai-quantum lab qec -d 7 --rounds 7 --p 0.001 --bench --shots 400000     # shots a second, one thread
```

Measured on one thread of the build host (an arm64 desktop processor), the
rotated surface-code memory experiment at distance 7, 7 rounds, every noise
knob at `p = 0.001` (118 qubits, 4,667 operations, 336 detectors):
6.0 million shots a second of detection events and 6.2 million of full
measurement records. The rate follows the noise: 13 million a second at
`p = 0.0001` and 1.6 million at `p = 0.01`.

## Cultivation circuits

`quantum_cultivate` generates the core of magic-state cultivation in the
triangular colour code, at distance 3 and 5 (`wai-quantum lab cultivate`):

1. `T|+⟩` or its conjugate on one qubit, encoded by a circuit read off the
   code's checks;
2. one round of the code's checks, each flagged;
3. checks of the transversal operator `⊗ (X ± Y)/√2`, which is the logical
   `(X ± Y)/√2` on the code and fixes the injected state: a check qubit
   controls it onto every data qubit (`T†`, `CX`, `T`) beside a flag.

A run is kept when every measurement reads 0. Two forms come out: the circuit
itself as OpenQASM 3 (`--qasm`), and its Clifford form (every `T` an `S`) in
the circuit text with noise, a detector on every measurement and the logical
operator as observable 0 (`--circuit`, `--dem`).

```sh runnable
wai-quantum lab cultivate -d 3 --checks 2                      # the circuit's counts and the Clifford form's check
wai-quantum lab cultivate -d 3 --checks 2 --exact --faults 1   # every Pauli fault, on the state vector (2: every pair)
wai-quantum lab cultivate -d 3 --checks 2 --qasm > t.qasm
wai-quantum run t.qasm --shots 200                             # the engine's own job: every shot reads all zeros
wai-quantum lab cultivate -d 5 --checks 2 --circuit --p 0.001 > t.circuit
wai-quantum lab qec --file t.circuit --digest --shots 1000
```

What the engine checks, and what it finds:

| | distance 3, two checks | distance 5 |
|---|---|---|
| circuit | 9 qubits, 29 `T` gates, 16 measurements | 21 qubits |
| without a fault, exactly | every run kept, the state the encoded `T` state | the same |
| as a job of the engine (`wai-quantum run`, state vector) | every shot reads 16 zeros | not run in the docs |
| Clifford form: the fewest faults that fire no detector and flip the logical operator | 3 | 3, whatever the checks and verification rounds |
| exactly: single Pauli faults kept with a wrong state | none | none of 3,587 (on the command line, seven minutes; not in the test suite) |
| exactly: pairs of Pauli faults kept with a wrong state | none of 668,731 | not enumerated |

The exact check found what the Clifford form could not: with the data qubits
met in index order, 18 pairs of faults leave a wrong state in a kept run while
the Clifford form reports none. The order the circuits use removes them.

## What is not here

- Cultivation as published. The circuits above are this crate's own, not the
  published ones: one check qubit couples to every data qubit, and there is
  no growth into a larger code and no escape into a matchable one. The
  distance-5 circuit is protected no better than the distance-3 one. No
  logical error rate or discard rate is measured; the architecture model
  (`wai-quantum lab arch cultivate`) still prices cultivation from the
  published rates.
- Decoders for hypergraph faults other than through decomposition
  (`bp_osd` takes them undecomposed).