qec_code/
binary_chain_complex.rs

1use crate::error::{QecError, Result};
2use crate::sparse_gf2::SparseGf2Matrix;
3use std::collections::BTreeSet;
4
5#[derive(Debug, Clone, PartialEq, Eq)]
6pub struct BinaryBoundaryMap {
7    domain_dimension: usize,
8    codomain_dimension: usize,
9    matrix: SparseGf2Matrix,
10}
11
12impl BinaryBoundaryMap {
13    pub fn new(
14        domain_dimension: usize,
15        codomain_dimension: usize,
16        matrix: SparseGf2Matrix,
17    ) -> Result<Self> {
18        if codomain_dimension.checked_add(1) != Some(domain_dimension) {
19            return Err(QecError::InvalidBoundaryMapDimensions {
20                domain_dimension,
21                codomain_dimension,
22            });
23        }
24
25        Ok(Self {
26            domain_dimension,
27            codomain_dimension,
28            matrix,
29        })
30    }
31
32    pub fn domain_dimension(&self) -> usize {
33        self.domain_dimension
34    }
35
36    pub fn codomain_dimension(&self) -> usize {
37        self.codomain_dimension
38    }
39
40    pub fn matrix(&self) -> &SparseGf2Matrix {
41        &self.matrix
42    }
43
44    pub fn num_domain_cells(&self) -> usize {
45        self.matrix.num_cols()
46    }
47
48    pub fn num_codomain_cells(&self) -> usize {
49        self.matrix.num_rows()
50    }
51}
52
53#[derive(Debug, Clone, PartialEq, Eq)]
54pub struct BinaryChainComplex {
55    boundaries: Vec<BinaryBoundaryMap>,
56}
57
58impl BinaryChainComplex {
59    pub fn new(mut boundaries: Vec<BinaryBoundaryMap>) -> Result<Self> {
60        boundaries.sort_by_key(BinaryBoundaryMap::domain_dimension);
61
62        for pair in boundaries.windows(2) {
63            if pair[0].domain_dimension == pair[1].domain_dimension {
64                return Err(QecError::DuplicateBoundaryMapDimension {
65                    domain_dimension: pair[0].domain_dimension,
66                });
67            }
68        }
69
70        for pair in boundaries.windows(2) {
71            let lower = &pair[0];
72            let upper = &pair[1];
73            if lower.domain_dimension == upper.codomain_dimension {
74                verify_zero_composition(lower, upper)?;
75            }
76        }
77
78        Ok(Self { boundaries })
79    }
80
81    pub fn boundaries(&self) -> &[BinaryBoundaryMap] {
82        &self.boundaries
83    }
84
85    pub fn boundary_map(&self, domain_dimension: usize) -> Option<&BinaryBoundaryMap> {
86        self.boundaries
87            .binary_search_by_key(&domain_dimension, BinaryBoundaryMap::domain_dimension)
88            .ok()
89            .map(|index| &self.boundaries[index])
90    }
91
92    pub fn boundary(&self, domain_dimension: usize) -> Option<&SparseGf2Matrix> {
93        self.boundary_map(domain_dimension)
94            .map(BinaryBoundaryMap::matrix)
95    }
96
97    pub fn css_view(&self, qubit_dimension: usize) -> Result<HomologicalCssView> {
98        let hx = self
99            .boundary(qubit_dimension)
100            .ok_or(QecError::MissingBoundaryMap {
101                domain_dimension: qubit_dimension,
102            })?
103            .clone();
104        let upper_dimension =
105            qubit_dimension
106                .checked_add(1)
107                .ok_or(QecError::MissingBoundaryMap {
108                    domain_dimension: qubit_dimension,
109                })?;
110        let hz = self
111            .boundary(upper_dimension)
112            .ok_or(QecError::MissingBoundaryMap {
113                domain_dimension: upper_dimension,
114            })?
115            .transpose()?;
116
117        Ok(HomologicalCssView {
118            qubit_dimension,
119            hx,
120            hz,
121        })
122    }
123}
124
125#[derive(Debug, Clone, PartialEq, Eq)]
126pub struct HomologicalCssView {
127    qubit_dimension: usize,
128    hx: SparseGf2Matrix,
129    hz: SparseGf2Matrix,
130}
131
132impl HomologicalCssView {
133    pub fn qubit_dimension(&self) -> usize {
134        self.qubit_dimension
135    }
136
137    pub fn hx(&self) -> &SparseGf2Matrix {
138        &self.hx
139    }
140
141    pub fn hz(&self) -> &SparseGf2Matrix {
142        &self.hz
143    }
144
145    pub fn num_qubits(&self) -> usize {
146        self.hx.num_cols()
147    }
148
149    pub fn num_x_checks(&self) -> usize {
150        self.hx.num_rows()
151    }
152
153    pub fn num_z_checks(&self) -> usize {
154        self.hz.num_rows()
155    }
156}
157
158fn verify_zero_composition(lower: &BinaryBoundaryMap, upper: &BinaryBoundaryMap) -> Result<()> {
159    if lower.matrix.num_cols() != upper.matrix.num_rows() {
160        return Err(QecError::BoundaryCompositionDimensionMismatch {
161            lower_dimension: lower.domain_dimension,
162            upper_dimension: upper.domain_dimension,
163            lower_domain_cells: lower.matrix.num_cols(),
164            upper_codomain_cells: upper.matrix.num_rows(),
165        });
166    }
167
168    for (row_index, lower_row) in lower.matrix.rows().iter().enumerate() {
169        let support = compose_row_support(lower_row, upper.matrix.rows());
170        if !support.is_empty() {
171            return Err(QecError::NonzeroBoundaryComposition {
172                lower_dimension: lower.domain_dimension,
173                upper_dimension: upper.domain_dimension,
174                row: row_index,
175                support,
176            });
177        }
178    }
179
180    Ok(())
181}
182
183fn compose_row_support(lower_row: &[usize], upper_rows: &[Vec<usize>]) -> Vec<usize> {
184    let mut support = BTreeSet::new();
185    for &intermediate_cell in lower_row {
186        for &upper_support in &upper_rows[intermediate_cell] {
187            if !support.insert(upper_support) {
188                support.remove(&upper_support);
189            }
190        }
191    }
192    support.into_iter().collect()
193}
qec_code/binary_chain_complex.rs

qec_code/
binary_chain_complex.rs
