Skip to content

Latest commit

 

History

History
199 lines (162 loc) · 8.89 KB

decoders.md

File metadata and controls

199 lines (162 loc) · 8.89 KB

Experimental decoders

Experimental decoder engines live in exp/ and may change without notice. Frontier and BP-Trellis are available through pecos_rslib_exp.frontier() and pecos_rslib_exp.bp_trellis() for unified parallel batch decoding. Install the optional pecos-rslib-exp package to use them. Standard decoder imports work without this package. The detailed-result APIs described here are also reached through pecos_rslib_exp.

Two capabilities live here that the production decoders do not offer:

  • Complementary-gap output — how much more likely the winning logical class was than the runner-up, per shot. Production decoders return a correction and, for some backends, a weight or cost; none return a gap.
  • Hyperedge decoding with a confidence signal — Frontier and BP-Trellis decode a model containing mechanisms that touch three or more detectors, which matching-style decoders cannot represent at all.

Frontier and BP-Trellis

FrontierDecoder.from_dem and BpTrellisDecoder.from_dem take a Stim-format DEM string and expose the same result surface. FrontierDecoder.from_factors also accepts the factor model described below. Each is a single trellis decoder over the same machinery (BP-Trellis adds BP-informed pruning scores); the separate FrontierCommitteeDecoder runs a two-leg forward/backward committee over them. Start with whichever you like and compare.

from pecos_rslib_exp import BpTrellisDecoder, FrontierDecoder

# The only mechanism carrying L0 touches three detectors, so this model is not
# graphlike: matching-style decoders (pymatching, fusion_blossom, pecos_uf,
# k_mwpm, ...) reject it (see below).
dem = "error(0.1) D0 D1 D2 L0\nerror(0.05) D0\nerror(0.05) D1\nerror(0.05) D2\n"

result = FrontierDecoder.from_dem(dem).decode_syndrome([1, 1, 1])

assert list(result.observable_flips) == [True]
assert result.status == "exact"
print(f"status={result.status} gap={result.runner_up_gap:.3f}")

decode_batch takes a list of syndromes and returns one result per shot:

batch = FrontierDecoder.from_dem(dem).decode_batch([[1, 1, 1], [0, 0, 0]])

assert [list(shot.observable_flips) for shot in batch] == [[True], [False]]

For FrontierDecoder, FrontierCommitteeDecoder (Rust FrontierCommittee), and BpTrellisDecoder, decode_batch(shots, workers=N) decodes on N workers sharing one model (both leg models for the committee), with results returned in input order. The default is workers=1 (sequential). Workers are capped at one per shot, with one worker for an empty batch. Zero or negative workers raises ValueError; integers outside the signed 64-bit range raise OverflowError. If a shot fails, the raised error includes the first failing shot's zero-based index.

BP-Trellis exposes the identical result surface:

trellis = BpTrellisDecoder.from_dem(dem).decode_syndrome([1, 1, 1])

assert list(trellis.observable_flips) == [True]
assert trellis.status == "exact"

Factor models

FrontierDecoder.from_factors(factors, num_detectors, num_observables, ...) accepts a list of independent factors, each containing (probability, detector_indices, observable_indices) outcome tuples. The outcome probabilities in each factor must sum to 1. Binary-shaped factors with an empty baseline delegate to the same binary engine as the equivalent DEM.

import math

from pecos_rslib_exp import FrontierDecoder

factors = [
    [(0.60, [], []), (0.25, [0], [0]), (0.15, [0], [])],
    [(0.80, [], []), (0.20, [0], [])],
]
result = FrontierDecoder.from_factors(
    factors,
    num_detectors=1,
    num_observables=1,
    k=10**9,
    delta=1e6,
).decode_syndrome([1])
masses = dict(result.logical_masses)

assert result.observable_flips.mask == 0
assert math.isclose(masses[0], math.log(0.24), abs_tol=1e-9)
assert math.isclose(masses[1], math.log(0.20), abs_tol=1e-9)

Reading the complementary gap

logical_masses holds (observable_mask, log_mass) pairs ordered by decreasing mass, and runner_up_gap is the log-mass difference between the first two -- None whenever fewer than two logical classes survive to the end, which includes a fully exact decode with a single reachable class, so treat a missing gap as "no runner-up existed", not as a pruning signal, and handle it before comparing. With the default float metric, when status is "exact" (nothing was pruned), the masses are the true unnormalized posteriors: a large gap means one logical class really was overwhelmingly more likely, and a gap near zero means the shot was nearly a coin flip -- a natural candidate for post-selection or a soft-output pipeline. Under the integer maxlog_int metric (accepted by Python FrontierDecoder as metric_mode="maxlog_int"; int_metric_scale sets the quantization units per natural-log unit and defaults to 1024; the committee remains float-only), each terminal mass is instead the best-route (Viterbi) mass for that logical class, the gap is a route-mass margin, and log_evidence is the winning route mass rather than evidence. When the result was pruned, the gap and the masses describe only what the search retained, not a certified confidence -- treat them as search diagnostics, not posteriors.

assert result.status == "exact"
if result.runner_up_gap is not None:
    winner, runner_up = result.logical_masses[0], result.logical_masses[1]
    assert winner[1] - runner_up[1] == result.runner_up_gap
    print(f"winner mask={winner[0]} log-mass={winner[1]:.3f}")

The remaining fields describe the search itself rather than the answer: log_evidence (total retained log evidence under the default float metric), status ("exact" when nothing was pruned), dropped_states and dropped_log_mass (what pruning discarded), peak_retained_states, processed_columns, escalation_rungs_used, and bp_seconds. dropped_log_mass counts only the mass states carried when they were pruned -- a state dropped early would have branched through later columns, so it is not a bound on the probability the answer is missing.

Decoding a hyperedge model with a matching decoder

Graph decoder specs now project raw hyperedges using disjoint components from standalone faults in the same model. They preserve retained fault probabilities and observable effects. The default irreducible="refuse" reports any faults that cannot be decomposed. pymatching(correlated=True, irreducible="drop") (or "pymatching:irreducible=drop") explicitly removes those faults from the decoder's model, without changing sampling. Hyperedge-capable alternatives include bp_osd(), tesseract(), Frontier, and BP-Trellis. Effects with more than 12 detectors or reducible only with overlapping components are refused under either policy; irreducible="drop" does not apply to them. Use a hyperedge-capable decoder such as bp_osd() or tesseract() for these effects.

A supplied ^ decomposition is still used verbatim if each component touches at most two detectors. Mixing supplied decompositions and raw hyperedges is rejected. Hybrid belief matching retains its separate full/decomposed input contract.

Circuit provenance offers another way to supply a decomposed model. coherent_dem_decomposed traces a TickCircuit and uses Pauli provenance to split each hyperedge into its X and Z components, fitting the probabilities to Heisenberg-exact marginals. It needs a circuit whose detectors are defined -- one built by the QEC layer rather than a bare TickCircuit, which yields an empty model:

from pecos_rslib_exp import coherent_dem_decomposed

raw_dem, decomposed_dem = coherent_dem_decomposed(
    tick_circuit,
    p1=0.001,
    p2=0.001,
    p_meas=0.001,
)

The second return value is graphlike and can go to any matching decoder. noise_characterization exposes the same machinery with an explicit max_order. Note the distinction from ParsedDem.to_string_decomposed(), which splits only mechanisms whose provenance is already recorded and raises for the rest — it has no circuit to re-derive provenance from.

BP-Trellis no-path outcomes

The direct BP-Trellis methods support on_no_path="report" for explicit placeholders, while the spec route stays strict. See the BP-Trellis user guide for ladder parameters, no-path causes, and per-shot telemetry.

What is not here yet

frontier() and bp_trellis() are not DecoderSpec values: DecoderSpec.parse does not know their names and the composite factories such as windowed(...) cannot wrap them. They run through SampleBatch.decode(...) and DemSampler.decode(...) only, and those return predictions and aggregate scores; per-shot confidence, pruning status and retry telemetry still come from the direct decode_syndrome / decode_batch methods.