Skip to main content
Back to All Articles
August 2026Noise ModelsBy Guillaume Lessard · 4 min read

Weighted Decoding and Likelihood Priors

Why log((1-p)/p) belongs in the graph and how matching, Union-Find, and space-time paths use weights.

Author: Guillaume Lessard
Series: QECTOR Decoder v3 companion notes, Post 14
Source: QECTOR Decoder v3 Reference Manual v1.0.0
Date: August 2026
DOI: 10.5281/zenodo.21941046 Tags: weighted decoding, likelihood ratios, DEM, MWPM, Union-Find

Abstract

An unweighted graph treats every fault mechanism as equally plausible. That may be acceptable for a uniform code-capacity toy model, but circuit-level decoding normally supplies distinct data and measurement probabilities. QECTOR's matching decoders accept log-likelihood weights, and its weighted Union-Find path uses the same probability information for adaptive growth. This post derives the weight, shows what changes under nonuniform noise, and explains why weighted-correctness claims must be separated from performance claims.

1. From probability to cost

For a binary mechanism with error probability p, the odds of an error versus no error are p/(1-p). The negative log odds are

w(p)=−log⁡(p1−p)=log⁡(1−pp).w(p) = -\log\left(\frac{p}{1-p}\right) = \log\left(\frac{1-p}{p}\right).

Independent mechanisms add log probabilities, so a path cost is the sum of its edge weights. Minimizing that cost is equivalent to selecting the most likely chain under the model assumptions.

The formula is monotone: rare mechanisms have larger costs, common mechanisms smaller costs. A decoder that ignores the variation cannot distinguish the two.

2. A two-edge comparison

Consider two available mechanisms:

p_a = 0.0001  -> w_a ~= 9.21
p_b = 0.01    -> w_b ~= 4.60

A path containing one b edge is cheaper than a path containing one a edge, even when both paths have the same number of edges. Under an unweighted model they would tie. The weighted model therefore uses information the calibration or the DEM already provided.

This example does not say which correction is logically better. It says which representative the declared independent-noise likelihood prefers.

3. Uniform noise is a special case

If every mechanism has the same probability p, every edge receives the same weight. A path with fewer edges then also has lower total weight, so weighted and unweighted matching agree on the ordering. That is why a uniform code-capacity experiment can make an unweighted decoder look adequate.

The agreement does not transfer automatically to circuit-level noise, biased noise, or a model with different temporal and spatial rates.

4. Matching and Union-Find use weights differently

Blossom and Sparse Blossom turn weights into shortest-path distances and matching costs. Weighted Union-Find advances clusters by adaptive time steps that saturate frontier edges according to their lengths. The implementations share the probability-to-weight convention, but not the same optimization contract.

DecoderUse of weightsClaim boundary
BlossomExact weighted MWPM on audited small codesExactness is scoped
Sparse BlossomEvent times and candidate growthTested faithful/near-optimal scope
Union-FindAdaptive weighted cluster growthFaithful graphlike path
BP-OSDPriors and posterior reliabilitiesFaithful residual solve

Weights improve the model fit. They do not make an approximate decoder exact.

5. Space-time anisotropy

In a lifted detector lattice, data and measurement mechanisms commonly use different probabilities:

wspace=log⁡(1−pdatapdata),wtime=log⁡(1−pmeaspmeas).w_{space}=\log\left(\frac{1-p_{data}}{p_{data}}\right),\qquad w_{time}=\log\left(\frac{1-p_{meas}}{p_{meas}}\right).

This creates an anisotropic graph: a measurement glitch may be cheaper to explain with a time-like path than with a spatial data chain. If the prior changes, the preferred path can change while the path-boundary proof remains unchanged.

6. Per-shot reweighting

The manual documents in-place edge-weight replacement in O(E) and a batched path that accepts one weight vector per shot. This supports workflows in which BP posteriors or calibrated mechanism rates alter the graph for each syndrome.

The validation target is equivalence between the reweighted and freshly constructed paths on the tested configurations. It is not a universal statement that all weight updates preserve the same correction or logical result.

7. Weight validation

Before running a weighted decoder, check:

0 < p < 1 for every mechanism
probability ordering matches the calibration source
boundary mechanisms have explicit treatment
parallel DEM mechanisms collapsed consistently
spatial and temporal weights use the intended channels
weight dtype and precision recorded

The decoder should reject invalid weights at construction rather than silently treating them as uniform.

8. Claim boundaries

A weight formula is a mathematical contract. A logical-error curve is an empirical result. To publish the latter, include the circuit or DEM, code, noise model, shots, seed, decoder mode, environment, raw artifact, and confidence interval. Do not compare a weighted circuit-level result with an unweighted code-capacity result just because both use the same nominal p.

Takeaway

Likelihood weights are how a decoder listens to the noise model. Uniform weights are a useful special case, not a universal default. Put the prior into the DEM and the decoder, keep the structural graph/hypergraph guard, and report the resulting logical behaviour only with comparable artifacts.

Reference

Guillaume Lessard, QECTOR Decoder v3: Syndrome-Faithful Decoding - Foundations, Algorithms, and Architecture of a Fifteen-Backend Quantum Error Correction Engine, v1.0.0, August 2026. DOI: 10.5281/zenodo.21941046.