qec_code/
sparse_gf2.rs

1use crate::error::{QecError, Result};
2
3#[derive(Debug, Clone, PartialEq, Eq)]
4pub struct SparseGf2Matrix {
5    num_rows: usize,
6    num_cols: usize,
7    rows: Vec<Vec<usize>>,
8}
9
10impl SparseGf2Matrix {
11    pub fn new(num_rows: usize, num_cols: usize, rows: Vec<Vec<usize>>) -> Result<Self> {
12        if rows.len() != num_rows {
13            return Err(QecError::SparseGf2RowCountMismatch {
14                expected: num_rows,
15                actual: rows.len(),
16            });
17        }
18
19        let rows = rows
20            .into_iter()
21            .enumerate()
22            .map(|(row_index, row)| canonicalize_row(num_cols, row_index, row))
23            .collect::<Result<Vec<_>>>()?;
24
25        Ok(Self {
26            num_rows,
27            num_cols,
28            rows,
29        })
30    }
31
32    pub fn identity(size: usize) -> Result<Self> {
33        identity(size)
34    }
35
36    pub fn transpose(&self) -> Result<Self> {
37        transpose(self)
38    }
39
40    pub fn hconcat(&self, rhs: &Self) -> Result<Self> {
41        hconcat(self, rhs)
42    }
43
44    pub fn kron(&self, rhs: &Self) -> Result<Self> {
45        kron(self, rhs)
46    }
47
48    pub fn num_rows(&self) -> usize {
49        self.num_rows
50    }
51
52    pub fn num_cols(&self) -> usize {
53        self.num_cols
54    }
55
56    pub fn rows(&self) -> &[Vec<usize>] {
57        &self.rows
58    }
59}
60
61pub fn identity(size: usize) -> Result<SparseGf2Matrix> {
62    let mut rows = Vec::new();
63    rows.try_reserve_exact(size)
64        .map_err(|_| QecError::SparseGf2DimensionOverflow {
65            operation: "identity",
66        })?;
67    for index in 0..size {
68        rows.push(vec![index]);
69    }
70    SparseGf2Matrix::new(size, size, rows)
71}
72
73pub fn transpose(matrix: &SparseGf2Matrix) -> Result<SparseGf2Matrix> {
74    let mut rows = Vec::new();
75    rows.try_reserve_exact(matrix.num_cols)
76        .map_err(|_| QecError::SparseGf2DimensionOverflow {
77            operation: "transpose",
78        })?;
79    rows.resize_with(matrix.num_cols, Vec::new);
80
81    for (row_index, row) in matrix.rows.iter().enumerate() {
82        for &support in row {
83            rows[support].push(row_index);
84        }
85    }
86
87    SparseGf2Matrix::new(matrix.num_cols, matrix.num_rows, rows)
88}
89
90pub fn hconcat(left: &SparseGf2Matrix, right: &SparseGf2Matrix) -> Result<SparseGf2Matrix> {
91    if left.num_rows != right.num_rows {
92        return Err(QecError::SparseGf2HorizontalRowMismatch {
93            left_rows: left.num_rows,
94            right_rows: right.num_rows,
95        });
96    }
97
98    let num_cols =
99        left.num_cols
100            .checked_add(right.num_cols)
101            .ok_or(QecError::SparseGf2DimensionOverflow {
102                operation: "hconcat",
103            })?;
104
105    let mut rows = Vec::new();
106    rows.try_reserve_exact(left.num_rows)
107        .map_err(|_| QecError::SparseGf2DimensionOverflow {
108            operation: "hconcat",
109        })?;
110
111    for (left_row, right_row) in left.rows.iter().zip(&right.rows) {
112        let mut row = Vec::new();
113        row.try_reserve_exact(left_row.len().saturating_add(right_row.len()))
114            .map_err(|_| QecError::SparseGf2DimensionOverflow {
115                operation: "hconcat",
116            })?;
117        row.extend(left_row.iter().copied());
118        for &support in right_row {
119            row.push(left.num_cols.checked_add(support).ok_or(
120                QecError::SparseGf2DimensionOverflow {
121                    operation: "hconcat",
122                },
123            )?);
124        }
125        rows.push(row);
126    }
127
128    SparseGf2Matrix::new(left.num_rows, num_cols, rows)
129}
130
131pub fn kron(left: &SparseGf2Matrix, right: &SparseGf2Matrix) -> Result<SparseGf2Matrix> {
132    let num_rows = left
133        .num_rows
134        .checked_mul(right.num_rows)
135        .ok_or(QecError::SparseGf2DimensionOverflow { operation: "kron" })?;
136    let num_cols = left
137        .num_cols
138        .checked_mul(right.num_cols)
139        .ok_or(QecError::SparseGf2DimensionOverflow { operation: "kron" })?;
140
141    let mut rows = Vec::new();
142    rows.try_reserve_exact(num_rows)
143        .map_err(|_| QecError::SparseGf2DimensionOverflow { operation: "kron" })?;
144
145    for left_row in &left.rows {
146        for right_row in &right.rows {
147            let mut row = Vec::new();
148            for &left_support in left_row {
149                let block_start = left_support
150                    .checked_mul(right.num_cols)
151                    .ok_or(QecError::SparseGf2DimensionOverflow { operation: "kron" })?;
152                for &right_support in right_row {
153                    row.push(
154                        block_start
155                            .checked_add(right_support)
156                            .ok_or(QecError::SparseGf2DimensionOverflow { operation: "kron" })?,
157                    );
158                }
159            }
160            rows.push(row);
161        }
162    }
163
164    SparseGf2Matrix::new(num_rows, num_cols, rows)
165}
166
167fn canonicalize_row(num_cols: usize, row_index: usize, mut row: Vec<usize>) -> Result<Vec<usize>> {
168    for &support in &row {
169        if support >= num_cols {
170            return Err(QecError::SparseGf2SupportOutOfRange {
171                row: row_index,
172                support,
173                num_cols,
174            });
175        }
176    }
177
178    row.sort_unstable();
179
180    let mut canonical = Vec::new();
181    let mut index = 0;
182    while index < row.len() {
183        let support = row[index];
184        let mut keep = false;
185        while index < row.len() && row[index] == support {
186            keep = !keep;
187            index += 1;
188        }
189        if keep {
190            canonical.push(support);
191        }
192    }
193
194    Ok(canonical)
195}
qec_code/sparse_gf2.rs

qec_code/
sparse_gf2.rs
