Skip to main content

deq_runtime/decoder/
blackbox_util.rs

1use crate::decoder::blackbox_decoder::{DecodingHypergraph, ParityFactor};
2use crate::misc::bit_vector::to_sparse_indices;
3use crate::util::BitVector;
4use hashbrown::HashSet;
5
6/// Hypergraph indices of the hyperedges a core decoder should be built from:
7/// those with a usable prior probability.
8///
9/// The decoding hypergraph may carry mechanisms with probability zero so their
10/// stable edge indices remain available for shot-scoped updates. Core solvers
11/// should omit those infinite-weight edges until a reweight makes them usable.
12pub fn active_edge_indices(hypergraph: &DecodingHypergraph) -> Vec<u64> {
13    hypergraph
14        .hyperedges
15        .iter()
16        .enumerate()
17        .filter(|(_, hyperedge)| hyperedge.probability > 0.0)
18        .map(|(index, _)| index as u64)
19        .collect()
20}
21
22pub fn is_parity_factor(
23    decoding_hypergraph: &DecodingHypergraph,
24    parity_factor: &ParityFactor,
25    syndrome: &BitVector,
26) -> bool {
27    let mut selected_edges = HashSet::with_capacity(parity_factor.subgraph.len());
28    let mut flips = HashSet::<u64>::new();
29    for &edge_index in &parity_factor.subgraph {
30        if !selected_edges.insert(edge_index) {
31            return false;
32        }
33        let Ok(edge_index) = usize::try_from(edge_index) else {
34            return false;
35        };
36        let Some(edge) = decoding_hypergraph.hyperedges.get(edge_index) else {
37            return false;
38        };
39        for &vertex in &edge.vertices {
40            if !flips.insert(vertex) {
41                flips.remove(&vertex);
42            }
43        }
44    }
45
46    let syndrome = to_sparse_indices(syndrome);
47    let mut flips: Vec<u64> = flips.into_iter().collect();
48    flips.sort_unstable();
49    syndrome == flips
50}
51
52pub fn assert_parity_factor(decoding_hypergraph: &DecodingHypergraph, parity_factor: &ParityFactor, syndrome: &BitVector) {
53    if !is_parity_factor(decoding_hypergraph, parity_factor, syndrome) {
54        panic!(
55            "the provided parity factor does not match the syndrome: parity factor {parity_factor:?}, syndrome {syndrome:?}"
56        );
57    }
58}
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63
64    fn single_edge_graph() -> DecodingHypergraph {
65        DecodingHypergraph {
66            vertex_num: 1,
67            hyperedges: vec![crate::decoder::blackbox_decoder::Hyperedge {
68                observable_flips: None,
69                vertices: vec![0],
70                probability: 0.1,
71            }],
72        }
73    }
74
75    #[test]
76    fn parity_factor_rejects_invalid_and_duplicate_edges() {
77        let hypergraph = single_edge_graph();
78        let syndrome = crate::misc::bit_vector::from_sparse_indices(1, &[0]);
79
80        assert!(is_parity_factor(&hypergraph, &ParityFactor { subgraph: vec![0] }, &syndrome));
81        assert!(!is_parity_factor(&hypergraph, &ParityFactor { subgraph: vec![1] }, &syndrome));
82        assert!(!is_parity_factor(
83            &hypergraph,
84            &ParityFactor { subgraph: vec![0, 0] },
85            &syndrome
86        ));
87    }
88}