Skip to main content

deq_runtime/coordinator/
loss_handler.rs

1//! Loss-handling strategy: what a coordinator does with heralded atom losses.
2//!
3//! The coordinator config exposes two fields — a [`LossStrategy`] and an opaque
4//! `loss_config` JSON blob — instead of one flag per mechanism. The blob is
5//! parsed and validated *once*, here, into a [`LossHandler`]; a coordinator then
6//! only asks the handler what to do. Options that belong to another strategy are
7//! rejected at construction rather than silently ignored, which is the failure
8//! mode the flat `loss_envelope_matching` / `loss_weight_fraction` /
9//! `loss_mle_decoding` triple invited.
10
11use super::reweight_handler::{DecodeProjection, ProjectedErrors, apply_reweights};
12use crate::decoder::blackbox_decoder;
13use crate::jit::loss_compiler::CrossGadgetLossSite;
14use crate::misc::index::ErrorIndex;
15use crate::misc::util::{exclusive_probability_of, probability_of_weight, union_probability_of, weight_of};
16use chacha20::ChaCha8Rng;
17use hashbrown::{HashMap, HashSet};
18use rand::{Rng, SeedableRng};
19use serde::{Deserialize, Serialize};
20use std::collections::BTreeSet;
21#[cfg(feature = "cli")]
22use structdoc::StructDoc;
23
24/// Default envelope-matching exponent.
25///
26/// Swept on a `d = 3` mid-swap memory (`eta = 0.7`) over `f` in `[0.05, 1.0]`.
27/// At low loss rates the logical error rate is flat in `f` — a 10x range moves it
28/// by less than noise — because most edges are activated by a single site. At
29/// `p_loss` of `1-2%`, where several sites share an edge, the curve is a clear
30/// `5-6 sigma` bowl with a broad optimum at `0.5-0.7`: below it the loss edges
31/// get cheap enough for the decoder to chain them, above it (up to the
32/// undiscounted `f = 1`) the envelope stops helping. `0.5` is best or tied-best
33/// at every rate measured, and coincides with the reference's space-like value.
34const DEFAULT_WEIGHT_FRACTION: f64 = 0.5;
35
36/// One possible loss site projected onto a decode window, before its generator
37/// indices are mapped onto decoder hyperedges.
38///
39/// `local_eid` identifies the error model whose generator list the site
40/// addresses. It is `None` for structural pass-through sites, which remain in
41/// the graph to preserve probability, herald, and child relationships.
42pub(crate) struct RawLossSite {
43    pub(crate) local_eid: Option<usize>,
44    pub(crate) probability: f64,
45    pub(crate) source_generators: Vec<usize>,
46    pub(crate) continuation_generators: Vec<usize>,
47    pub(crate) children: Vec<usize>,
48    pub(crate) heralds: Vec<usize>,
49}
50
51impl RawLossSite {
52    pub(crate) fn from_compiled(site: CrossGadgetLossSite, local_eid: Option<usize>) -> Self {
53        Self {
54            local_eid,
55            probability: site.probability,
56            source_generators: site.source_generators,
57            continuation_generators: site.continuation_generators,
58            children: site.children,
59            heralds: site.heralds,
60        }
61    }
62}
63
64/// Map window-local loss generators onto decoder hyperedge indices.
65///
66/// Generators absent from `error_reference` have no decoder-visible effect and
67/// are omitted. Child and herald indices already address the flat shot-local
68/// loss payload and are preserved.
69pub(crate) fn build_loss_info(loss_sites: &[RawLossSite], error_reference: &[ErrorIndex]) -> blackbox_decoder::LossInfo {
70    let mut edge_of: hashbrown::HashMap<(usize, usize), u64> = hashbrown::HashMap::with_capacity(error_reference.len());
71    for (index, error) in error_reference.iter().enumerate() {
72        let index = u64::try_from(index).unwrap();
73        edge_of.insert((error.eid, error.error_index), index);
74    }
75    let map_edges = |local_eid: Option<usize>, generators: &[usize]| -> Vec<u64> {
76        let Some(local_eid) = local_eid else {
77            return vec![];
78        };
79        generators
80            .iter()
81            .filter_map(|&generator| edge_of.get(&(local_eid, generator)).copied())
82            .collect::<BTreeSet<_>>()
83            .into_iter()
84            .collect()
85    };
86    let sites = loss_sites
87        .iter()
88        .map(|site| blackbox_decoder::LossSite {
89            source_edges: map_edges(site.local_eid, &site.source_generators),
90            continuation_edges: map_edges(site.local_eid, &site.continuation_generators),
91            probability: site.probability,
92            children: site.children.iter().map(|&child| u64::try_from(child).unwrap()).collect(),
93            heralds: site.heralds.iter().map(|&herald| u64::try_from(herald).unwrap()).collect(),
94        })
95        .collect();
96    blackbox_decoder::LossInfo { sites }
97}
98
99fn loss_imputation_rng(seed: u64, gid: u64) -> ChaCha8Rng {
100    let components = [seed.to_le_bytes(), gid.to_le_bytes(), *b"deq-loss"];
101    let mut rng_seed = [0; 32];
102    for (destination, component) in rng_seed.as_chunks_mut::<8>().0.iter_mut().zip(components) {
103        destination.copy_from_slice(&component);
104    }
105    ChaCha8Rng::from_seed(rng_seed)
106}
107
108pub(crate) fn apply_loss_random_imputation(
109    outcomes: &mut crate::util::BitVector,
110    loss_mask: Option<&crate::util::BitVector>,
111    seed: u64,
112    gid: u64,
113) {
114    use crate::misc::bit_vector;
115    let Some(loss_mask) = loss_mask else {
116        return;
117    };
118    assert_eq!(
119        outcomes.size, loss_mask.size,
120        "loss_mask size {} does not match outcomes size {}",
121        loss_mask.size, outcomes.size,
122    );
123    assert_eq!(outcomes.data.len(), loss_mask.data.len());
124    if bit_vector::is_zero(loss_mask) {
125        return;
126    }
127    let mut rng = loss_imputation_rng(seed, gid);
128    let mut random = vec![0; outcomes.data.len()];
129    rng.fill_bytes(&mut random);
130    for ((outcome, mask), random) in outcomes.data.iter_mut().zip(&loss_mask.data).zip(random) {
131        *outcome ^= random & mask;
132    }
133}
134
135/// Whether `gtype` carries the static model needed by the loss pipeline.
136pub(crate) fn has_loss_model(
137    gadget_types: &hashbrown::HashMap<u64, std::sync::Arc<crate::bin::GadgetType>>,
138    gtype: u64,
139) -> bool {
140    gadget_types.get(&gtype).is_some_and(|gadget| gadget.loss_model.is_some())
141}
142
143/// How a coordinator handles the atom losses heralded by ``Outcomes.loss_mask``.
144///
145/// Independent of ``loss_random_imputation``, which decides what the *syndrome*
146/// does with a lost measurement bit and applies under every strategy.
147#[derive(Debug, Clone, Copy, PartialEq, Eq, Default, Serialize, Deserialize)]
148#[cfg_attr(feature = "cli", derive(StructDoc))]
149#[serde(rename_all = "snake_case")]
150pub enum LossStrategy {
151    /// Discard the loss information. The lost measurements still take part in
152    /// the syndrome (imputed when ``loss_random_imputation`` is on), but the
153    /// decoder is never told a loss happened. Takes no options.
154    Ignore,
155    /// Raise each observed loss's Pauli-envelope generator edges from their
156    /// (typically zero) prior to a weight comparable to ordinary edges, softly
157    /// enforcing the per-atom exclusivity, then hand the decoder an ordinary
158    /// problem. The default: it needs no decoder support, and costs nothing on a
159    /// program whose gadget types declare no loss model. Options:
160    /// ``weight_fraction`` and ``scale``.
161    #[default]
162    Reweight,
163    /// Pass the assembled loss sites to the decoder as a structured
164    /// [`LossInfo`](crate::decoder::blackbox_decoder::LossInfo) and let it do
165    /// the work — the loss-aware decode path, used by decoders such as the
166    /// ``mle_loss_decoder``. Takes no options.
167    Handoff,
168}
169
170impl LossStrategy {
171    fn name(self) -> &'static str {
172        match self {
173            Self::Ignore => "ignore",
174            Self::Reweight => "reweight",
175            Self::Handoff => "handoff",
176        }
177    }
178}
179
180/// Options accepted by [`LossStrategy::Ignore`] and [`LossStrategy::Handoff`].
181#[derive(Debug, Deserialize)]
182#[serde(deny_unknown_fields)]
183struct NoOptions {}
184
185/// How observed losses reweight their Pauli-envelope edges.
186#[derive(Debug, Clone, Copy, PartialEq, Serialize, Deserialize)]
187#[serde(deny_unknown_fields)]
188pub struct EnvelopeReweightPolicy {
189    /// Exponent applied to each observed loss's Pauli-envelope edges,
190    /// equivalently the fraction of the edge's own scale weight it is lowered
191    /// to. Near ``1`` the loss edges barely help; near ``0`` they become free
192    /// and the decoder chains them into logical errors.
193    #[serde(default = "default_weight_fraction")]
194    pub weight_fraction: f64,
195    /// Which scale weight the fraction is taken of.
196    #[serde(default)]
197    pub scale: ReweightScale,
198}
199
200/// Which scale weight [`EnvelopeReweightPolicy`] lowers an activated edge to.
201#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, Serialize, Deserialize)]
202#[cfg_attr(feature = "cli", derive(StructDoc))]
203#[serde(rename_all = "snake_case")]
204pub enum ReweightScale {
205    /// The edge's own prior combined with the probability a loss activates it.
206    #[default]
207    Local,
208    /// The mean weight of the graph's regular edges -- the reference
209    /// construction, kept for comparison.
210    GlobalMean,
211    /// The mean weight of the regular edges adjacent to the activated edge: the
212    /// reference's semantics without a graph-wide statistic.
213    NeighbourhoodMean,
214}
215
216impl Default for EnvelopeReweightPolicy {
217    fn default() -> Self {
218        Self {
219            weight_fraction: DEFAULT_WEIGHT_FRACTION,
220            scale: ReweightScale::Local,
221        }
222    }
223}
224
225impl EnvelopeReweightPolicy {
226    #[must_use]
227    pub fn new(weight_fraction: f64) -> Self {
228        Self {
229            weight_fraction,
230            scale: ReweightScale::Local,
231        }
232    }
233
234    /// Apply the configured fraction to a supplied scale weight.
235    #[must_use]
236    pub fn scaled_probability(self, scale_weight: f64) -> f64 {
237        probability_of_weight(self.weight_fraction * scale_weight.max(0.0))
238    }
239
240    /// Reweight against the edge's own prior combined with its activation.
241    #[must_use]
242    pub fn locally_reweighted_probability(self, edge_probability: f64, activation_probability: f64) -> f64 {
243        let scale = exclusive_probability_of(edge_probability, activation_probability);
244        probability_of_weight(self.weight_fraction * weight_of(scale).max(0.0))
245    }
246}
247
248fn loss_reweights(
249    loss: &blackbox_decoder::LossInfo,
250    hypergraph: &blackbox_decoder::DecodingHypergraph,
251    policy: EnvelopeReweightPolicy,
252) -> Vec<(u64, f64)> {
253    let accumulated = accumulated_site_probabilities(&loss.sites);
254    let prior_of = |edge: u64| -> f64 {
255        hypergraph
256            .hyperedges
257            .get(edge as usize)
258            .map_or(0.0, |hyperedge| hyperedge.probability)
259    };
260
261    let mut order = Vec::new();
262    let mut activation_of: HashMap<u64, f64> = HashMap::new();
263    let mut activate = |edge: u64, site_probability: f64, order: &mut Vec<u64>| match activation_of.entry(edge) {
264        hashbrown::hash_map::Entry::Occupied(mut slot) => {
265            let combined = exclusive_probability_of(*slot.get(), site_probability);
266            slot.insert(combined);
267        }
268        hashbrown::hash_map::Entry::Vacant(slot) => {
269            slot.insert(site_probability);
270            order.push(edge);
271        }
272    };
273    for (index, site) in loss.sites.iter().enumerate() {
274        for &edge in &site.source_edges {
275            let probability = if site.continuation_edges.contains(&edge) {
276                accumulated[index]
277            } else {
278                site.probability
279            };
280            activate(edge, probability, &mut order);
281        }
282        for &edge in &site.continuation_edges {
283            if !site.source_edges.contains(&edge) {
284                activate(edge, accumulated[index], &mut order);
285            }
286        }
287    }
288
289    let neighbourhood = if policy.scale == ReweightScale::NeighbourhoodMean {
290        Some(NeighbourhoodScale::new(hypergraph))
291    } else {
292        None
293    };
294    let global_mean = if policy.scale == ReweightScale::GlobalMean {
295        regular_mean_weight(hypergraph)
296    } else {
297        0.0
298    };
299
300    order
301        .into_iter()
302        .map(|edge| {
303            let activation = activation_of[&edge];
304            let probability = match policy.scale {
305                ReweightScale::Local => policy.locally_reweighted_probability(prior_of(edge), activation),
306                ReweightScale::GlobalMean => policy.scaled_probability(global_mean),
307                ReweightScale::NeighbourhoodMean => {
308                    match neighbourhood.as_ref().and_then(|scale| scale.mean_weight(edge, hypergraph)) {
309                        Some(mean) => policy.scaled_probability(mean),
310                        None => policy.locally_reweighted_probability(prior_of(edge), activation),
311                    }
312                }
313            };
314            (edge, probability)
315        })
316        .collect()
317}
318
319/// Adjacency index for the optional neighbourhood-mean reweighting policy.
320///
321/// Each syndrome vertex maps to the decoder edges incident on it. To find a
322/// scale for one activated edge, [`Self::mean_weight`] gathers every edge that
323/// shares at least one of its syndrome vertices. An edge can be found through
324/// several vertices, so the collected indices are deduplicated before their
325/// weights are averaged.
326struct NeighbourhoodScale {
327    /// Decoder-edge indices keyed by incident syndrome vertex.
328    edges_of_vertex: HashMap<u64, Vec<u32>>,
329}
330
331impl NeighbourhoodScale {
332    fn new(hypergraph: &blackbox_decoder::DecodingHypergraph) -> Self {
333        let mut edges_of_vertex: HashMap<u64, Vec<u32>> = HashMap::new();
334        for (index, hyperedge) in hypergraph.hyperedges.iter().enumerate() {
335            if hyperedge.probability == 0.0 {
336                continue;
337            }
338            let index = u32::try_from(index).expect("hyperedge index must fit in u32");
339            for &vertex in &hyperedge.vertices {
340                edges_of_vertex.entry(vertex).or_default().push(index);
341            }
342        }
343        Self { edges_of_vertex }
344    }
345
346    fn mean_weight(&self, edge: u64, hypergraph: &blackbox_decoder::DecodingHypergraph) -> Option<f64> {
347        let hyperedge = hypergraph.hyperedges.get(edge as usize)?;
348        let mut seen = HashSet::new();
349        let mut total = 0.0;
350        for vertex in &hyperedge.vertices {
351            for &neighbour in self.edges_of_vertex.get(vertex).into_iter().flatten() {
352                if seen.insert(neighbour) {
353                    total += weight_of(hypergraph.hyperedges[neighbour as usize].probability);
354                }
355            }
356        }
357        (!seen.is_empty()).then(|| total / seen.len() as f64)
358    }
359}
360
361fn regular_mean_weight(hypergraph: &blackbox_decoder::DecodingHypergraph) -> f64 {
362    let mut total = 0.0;
363    let mut count = 0usize;
364    for hyperedge in &hypergraph.hyperedges {
365        if hyperedge.probability == 0.0 {
366            continue;
367        }
368        total += weight_of(hyperedge.probability);
369        count += 1;
370    }
371    if count == 0 { 0.0 } else { total / count as f64 }
372}
373
374fn accumulated_site_probabilities(sites: &[blackbox_decoder::LossSite]) -> Vec<f64> {
375    let mut parents: Vec<Vec<usize>> = vec![Vec::new(); sites.len()];
376    for (index, site) in sites.iter().enumerate() {
377        for &child in &site.children {
378            if let Some(slot) = parents.get_mut(child as usize) {
379                slot.push(index);
380            }
381        }
382    }
383    let mut accumulated = vec![None; sites.len()];
384    let mut visiting = vec![false; sites.len()];
385    for index in 0..sites.len() {
386        accumulate_site(index, sites, &parents, &mut accumulated, &mut visiting);
387    }
388    accumulated.into_iter().map(|value| value.unwrap_or(0.0)).collect()
389}
390
391fn accumulate_site(
392    index: usize,
393    sites: &[blackbox_decoder::LossSite],
394    parents: &[Vec<usize>],
395    accumulated: &mut [Option<f64>],
396    visiting: &mut [bool],
397) -> f64 {
398    if let Some(value) = accumulated[index] {
399        return value;
400    }
401    if visiting[index] {
402        return 0.0;
403    }
404    visiting[index] = true;
405    let mut total = sites[index].probability;
406    for &parent in &parents[index] {
407        total = union_probability_of(total, accumulate_site(parent, sites, parents, accumulated, visiting));
408    }
409    visiting[index] = false;
410    accumulated[index] = Some(total);
411    total
412}
413
414fn default_weight_fraction() -> f64 {
415    DEFAULT_WEIGHT_FRACTION
416}
417
418/// A validated loss strategy together with its options.
419///
420/// Build with [`LossHandler::new`] at coordinator construction; every later
421/// decision is a total function on this value, so a decode never fails on
422/// configuration.
423#[derive(Debug, Clone, Copy, PartialEq)]
424pub enum LossHandler {
425    Ignore,
426    Reweight(EnvelopeReweightPolicy),
427    Handoff,
428}
429
430pub(crate) struct ProjectedShot {
431    pub(crate) reweights: Vec<blackbox_decoder::EdgeReweight>,
432    pub(crate) loss: Option<blackbox_decoder::LossInfo>,
433    pub(crate) errors: ProjectedErrors,
434}
435
436/// Matches [`LossStrategy::default`]: reweight at [`DEFAULT_WEIGHT_FRACTION`].
437impl Default for LossHandler {
438    fn default() -> Self {
439        Self::Reweight(EnvelopeReweightPolicy::default())
440    }
441}
442
443impl LossHandler {
444    /// Parse and validate `config` against `strategy`.
445    ///
446    /// Returns a human-readable error when the blob carries an option the
447    /// chosen strategy does not accept, or a value outside its domain.
448    pub fn new(strategy: LossStrategy, config: serde_json::Value) -> Result<Self, String> {
449        let config = if config.is_null() {
450            serde_json::Value::Object(serde_json::Map::new())
451        } else {
452            config
453        };
454        let name = strategy.name();
455        match strategy {
456            LossStrategy::Ignore | LossStrategy::Handoff => {
457                serde_json::from_value::<NoOptions>(config)
458                    .map_err(|e| format!("loss_config is not valid for loss_strategy \"{name}\", which takes none: {e}"))?;
459                Ok(if strategy == LossStrategy::Ignore {
460                    Self::Ignore
461                } else {
462                    Self::Handoff
463                })
464            }
465            LossStrategy::Reweight => {
466                let policy: EnvelopeReweightPolicy = serde_json::from_value(config)
467                    .map_err(|e| format!("loss_config is not valid for loss_strategy \"{name}\": {e}"))?;
468                if !(policy.weight_fraction > 0.0 && policy.weight_fraction <= 1.0) {
469                    return Err(format!(
470                        "loss_config.weight_fraction must lie in (0, 1], got {}",
471                        policy.weight_fraction
472                    ));
473                }
474                Ok(Self::Reweight(policy))
475            }
476        }
477    }
478
479    /// Whether observed losses have to be recorded per gadget and assembled into
480    /// loss sites. False only for [`LossStrategy::Ignore`], which lets the
481    /// coordinator skip the whole loss pipeline.
482    pub fn tracks_losses(self) -> bool {
483        !matches!(self, Self::Ignore)
484    }
485
486    /// Whether the assembled sites go to the decoder as a structured `LossInfo`
487    /// rather than being flattened into reweighted hyperedges.
488    pub fn hands_off_to_decoder(self) -> bool {
489        matches!(self, Self::Handoff)
490    }
491
492    /// The configured policy when this handler reweights loss envelopes.
493    pub fn reweight_policy(self) -> Option<EnvelopeReweightPolicy> {
494        match self {
495            Self::Reweight(policy) => Some(policy),
496            Self::Ignore | Self::Handoff => None,
497        }
498    }
499
500    /// Apply this strategy to loss sites projected onto a freshly built graph.
501    pub(crate) fn apply_sites(
502        self,
503        mut hypergraph: blackbox_decoder::DecodingHypergraph,
504        loss_sites: &[RawLossSite],
505        error_reference: &[ErrorIndex],
506    ) -> (blackbox_decoder::DecodingHypergraph, Option<blackbox_decoder::LossInfo>) {
507        if !self.tracks_losses() || loss_sites.is_empty() {
508            return (hypergraph, None);
509        }
510        let loss = build_loss_info(loss_sites, error_reference);
511        if self.hands_off_to_decoder() {
512            return (hypergraph, Some(loss));
513        }
514        let policy = self.reweight_policy().expect("non-ignore, non-handoff handler must reweight");
515        for (edge, probability) in loss_reweights(&loss, &hypergraph, policy) {
516            if let Some(hyperedge) = hypergraph.hyperedges.get_mut(edge as usize) {
517                hyperedge.probability = probability;
518            }
519        }
520        (hypergraph, None)
521    }
522
523    /// Project one shot's probability updates and loss onto a loaded graph.
524    pub(crate) fn project_shot(
525        self,
526        projection: &DecodeProjection,
527        probability_reweights: &[(u64, f64)],
528        loss_sites: &[RawLossSite],
529    ) -> ProjectedShot {
530        if probability_reweights.is_empty() && loss_sites.is_empty() {
531            let (_, errors) = projection.project_reweights(&[]);
532            return ProjectedShot {
533                reweights: vec![],
534                loss: None,
535                errors,
536            };
537        }
538        let loss =
539            (self.tracks_losses() && !loss_sites.is_empty()).then(|| build_loss_info(loss_sites, &projection.base_errors));
540        if self.hands_off_to_decoder() {
541            let (reweights, errors) = projection.project_reweights(probability_reweights);
542            return ProjectedShot {
543                reweights: reweights
544                    .into_iter()
545                    .map(|(edge, probability)| blackbox_decoder::EdgeReweight { edge, probability })
546                    .collect(),
547                loss,
548                errors,
549            };
550        }
551        let mut combined = probability_reweights.to_vec();
552        if let Some(loss) = loss {
553            let live_hypergraph;
554            let hypergraph = if probability_reweights.is_empty() {
555                &projection.base_hypergraph
556            } else {
557                live_hypergraph = {
558                    let mut hypergraph = projection.base_hypergraph.clone();
559                    apply_reweights(&mut hypergraph, probability_reweights.iter().copied());
560                    hypergraph
561                };
562                &live_hypergraph
563            };
564            let loss_reweights = loss_reweights(&loss, hypergraph, self.reweight_policy().unwrap());
565            let mut position_of = hashbrown::HashMap::with_capacity(combined.len() + loss_reweights.len());
566            for (position, &(edge, _)) in combined.iter().enumerate() {
567                position_of.insert(edge, position);
568            }
569            for (edge, probability) in loss_reweights {
570                if let Some(&position) = position_of.get(&edge) {
571                    // This is the final loss transform of the user-updated
572                    // prior, not a competing assignment. Combining both would
573                    // apply the user update twice.
574                    combined[position].1 = probability;
575                } else {
576                    position_of.insert(edge, combined.len());
577                    combined.push((edge, probability));
578                }
579            }
580        }
581        let (reweights, errors) = projection.project_reweights(&combined);
582        ProjectedShot {
583            reweights: reweights
584                .into_iter()
585                .map(|(edge, probability)| blackbox_decoder::EdgeReweight { edge, probability })
586                .collect(),
587            loss: None,
588            errors,
589        }
590    }
591}
592
593#[cfg(test)]
594#[path = "../../tests/unit/loss_handler_test.rs"]
595mod tests;