deq-runtime 0.5.2-rc2

deq: Real-time Quantum Error Correction Decoding System
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

use crate::decoder::blackbox_decoder::{DecodingHypergraph, ParityFactor};
use crate::misc::bit_vector::to_sparse_indices;
use crate::util::BitVector;
use hashbrown::HashSet;

/// Hypergraph indices of the hyperedges a core decoder should be built from:
/// those with a usable prior probability.
///
/// The decoding hypergraph may carry mechanisms with probability zero so their
/// stable edge indices remain available for shot-scoped updates. Core solvers
/// should omit those infinite-weight edges until a reweight makes them usable.
pub fn active_edge_indices(hypergraph: &DecodingHypergraph) -> Vec<u64> {
    hypergraph
        .hyperedges
        .iter()
        .enumerate()
        .filter(|(_, hyperedge)| hyperedge.probability > 0.0)
        .map(|(index, _)| index as u64)
        .collect()
}

pub fn is_parity_factor(
    decoding_hypergraph: &DecodingHypergraph,
    parity_factor: &ParityFactor,
    syndrome: &BitVector,
) -> bool {
    let mut selected_edges = HashSet::with_capacity(parity_factor.subgraph.len());
    let mut flips = HashSet::<u64>::new();
    for &edge_index in &parity_factor.subgraph {
        if !selected_edges.insert(edge_index) {
            return false;
        }
        let Ok(edge_index) = usize::try_from(edge_index) else {
            return false;
        };
        let Some(edge) = decoding_hypergraph.hyperedges.get(edge_index) else {
            return false;
        };
        for &vertex in &edge.vertices {
            if !flips.insert(vertex) {
                flips.remove(&vertex);
            }
        }
    }

    let syndrome = to_sparse_indices(syndrome);
    let mut flips: Vec<u64> = flips.into_iter().collect();
    flips.sort_unstable();
    syndrome == flips
}

pub fn assert_parity_factor(decoding_hypergraph: &DecodingHypergraph, parity_factor: &ParityFactor, syndrome: &BitVector) {
    if !is_parity_factor(decoding_hypergraph, parity_factor, syndrome) {
        panic!(
            "the provided parity factor does not match the syndrome: parity factor {parity_factor:?}, syndrome {syndrome:?}"
        );
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn single_edge_graph() -> DecodingHypergraph {
        DecodingHypergraph {
            vertex_num: 1,
            hyperedges: vec![crate::decoder::blackbox_decoder::Hyperedge {
                vertices: vec![0],
                probability: 0.1,
            }],
        }
    }

    #[test]
    fn parity_factor_rejects_invalid_and_duplicate_edges() {
        let hypergraph = single_edge_graph();
        let syndrome = crate::misc::bit_vector::from_sparse_indices(1, &[0]);

        assert!(is_parity_factor(&hypergraph, &ParityFactor { subgraph: vec![0] }, &syndrome));
        assert!(!is_parity_factor(&hypergraph, &ParityFactor { subgraph: vec![1] }, &syndrome));
        assert!(!is_parity_factor(
            &hypergraph,
            &ParityFactor { subgraph: vec![0, 0] },
            &syndrome
        ));
    }
}