← Back to Tools

BP / OSD / LSD Decoder Sandbox

Run a quantum LDPC decoder end to end on a Tanner graph. A parity-check matrix $H$ links checks $C_i$ to qubits $q_j$; an error $e$ gives the syndrome $s = He$. Belief propagation passes log-likelihood messages along the edges and turns them into a belief per qubit. When BP stalls on a degenerate error, a post-processor finishes the job: OSD solves $H\hat e = s$ on the most likely qubits, LSD grows clusters around the unsatisfied checks and solves each one locally. Every message, belief and solve is drawn and written out, and the result is judged against the stabilizer group, not just the syndrome.

Tanner graph T(H) · squares = checks $C_i$, circles = qubits $q_j$, edges = ones of $H$ · click a qubit to toggle an error
no run yet  wide matrix: scroll the graph sideways edge colour = sign of $\lambda_{i\to j}$, thickness = $|\lambda_{i\to j}|$
check with $s_i=1$ check with $s_i=0$ unsatisfied by $\hat e$ qubit $\hat e_j=0$ qubit $\hat e_j=1$ true error $e_j=1$ OSD basis $S$ message favours 0 message favours 1
0 / 0
Build an instance and inject an error to begin.

1 · Instance

Error type
0.10
Each injection uses the seed shown and then advances it by one, so a seed always reproduces its error. Click qubits in the graph to build an error by hand.
Custom matrices (rows of 0/1)
Decoding matrix $H$: one row per check, one column per qubit, space or comma separated. The second matrix is optional: give the checks of the other type (rows must commute with $H$) and the result is judged against the stabilizer group; leave it empty for a classical code.

2 · Decoder

12
Stop rule
$\lambda$

Worked examples load, then step through

3 · Run

Code

Syndrome $s = He \bmod 2$

A check $C_i$ is a defect when $s_i = 1$. The decoder looks for a likely $\hat e$ with $H\hat e = s$.

Parity-check matrix $H \in \mathbb{F}_2^{\,m\times n}$

Red columns carry the true error $e$, yellow the correction $\hat e$, blue the OSD basis $S$.

Beliefs posterior LLR $\Lambda_j$

$\Lambda_j = L_j + \sum_i \lambda_{i\to j}$, hard decision $\hat e_j = [\Lambda_j < 0]$, and $P(e_j{=}1) = 1/(1+e^{\Lambda_j})$ in the last column. Yellow ticks are the exact marginals from brute force; yellow names mark the true error.

Convergence per iteration

Messages

$\lambda_{i\to j}$: check to qubit, computed in this iteration. $\mu_{j\to i} = L_j + \sum_{i'\neq i}\lambda_{i'\to j}$: qubit to check, sent out for the next iteration. Check messages are capped at $\pm 30$.

Compare rules and schedules same instance, no early stop

Exact answer brute force over all $e'$ with $He' = s$

Step log

Notes

What BP computes

Given the syndrome $s$, BP estimates the marginal $P(e_j = 1 \mid s)$ for every qubit, written as the log-likelihood ratio $\Lambda_j = \log \frac{P(e_j=0\mid s)}{P(e_j=1\mid s)}$. Negative means "probably flipped". The prior is the channel, $L_j = \log\frac{1-p}{p}$. On a cycle-free Tanner graph the marginals are exact after as many iterations as the graph is deep; with cycles they are an approximation, and short cycles (4-cycles are unavoidable in CSS codes) make it worse.

Update rules

Check to qubit: $\lambda_{i\to j} = (1-2s_i)\,2\tanh^{-1}\prod_{j'\in N(i)\setminus j}\tanh\frac{\mu_{j'\to i}}{2}$. A satisfied check pushes its qubits toward 0, an unsatisfied one toward 1, never harder than its least certain other qubit. The page evaluates the product pairwise in the box-plus form, which has no overflow. Min-sum replaces the magnitude by $\alpha\min|\mu| - \beta$ (floored at 0): cheaper and overconfident, which sometimes helps and sometimes hurts.

Qubit to check: $\mu_{j\to i} = L_j + \sum_{i'\neq i}\lambda_{i'\to j}$. Flooding updates all checks, then all qubits. The serial schedule sweeps the qubits in order and uses fresh messages immediately; it converges faster and breaks symmetric ties.

Stopping and success

The usual rule stops at the first iteration whose hard decision satisfies $H\hat e = s$. That is a syndrome test, not a correctness test: the Steane example stops after one iteration on a weight-4 output that is a logical error, while two more iterations would have found the weight-1 error.

For a CSS code the residual $r = e \oplus \hat e$ is harmless if it is a stabilizer, i.e. in the row space of the other check matrix. It is a logical error if it anticommutes with a logical operator of the other type. This page tests both; for a classical code only $r = 0$ counts.

Why degeneracy breaks BP

Two errors that differ by a stabilizer have the same syndrome and the same effect; the best decoder only needs the right equivalence class. BP does not know classes. If $e$ and $e' = e \oplus$ (stabilizer) are equally likely, every qubit in their symmetric difference gets belief about one half, so the hard decision flips all of them or none, and neither satisfies the syndrome. The marginals can be exactly right while the decision is wrong: compare the bars with the brute-force ticks in the toric and Shor examples.

OSD

Order the qubits from most to least likely flipped ($\Lambda_j$ ascending). Take the first $\mathrm{rank}(H)$ independent columns as the basis $S$, set the rest $T$ to zero and solve $H_S \hat e_S = s$ by Gaussian elimination: this is OSD-0 and always satisfies the syndrome. Higher orders also try patterns on $T$: OSD-E tries all $2^\lambda$ patterns on the $\lambda$ most likely bits of $T$, OSD-CS tries every weight-1 pattern on $T$ and every weight-2 pattern inside the first $\lambda$. For each pattern $\hat e_S$ is re-solved and the lightest total solution wins.

LSD

Start one cluster at every unsatisfied check. In each round every invalid cluster adds one neighbouring qubit, the one with the lowest $\Lambda_j$, together with all checks on that qubit; clusters that meet merge. A cluster is valid when its local syndrome lies in the column space of its local matrix. Once all clusters are valid, each is solved on its own by OSD and the pieces are joined. The global solve of OSD becomes several small independent solves.