qec_code/codes/
generalized_bicycle.rs

1use serde::{Deserialize, Serialize};
2
3use crate::error::{QecError, Result};
4use crate::sparse_gf2::SparseGf2Matrix;
5
6pub const GENERALIZED_BICYCLE_CONSTRUCTION_ID: &str = "generalized_bicycle";
7
8#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
9pub struct GeneralizedBicycleSpec {
10    pub order: usize,
11    pub a_exponents: Vec<usize>,
12    pub b_exponents: Vec<usize>,
13}
14
15#[derive(Debug, Clone, PartialEq, Eq)]
16pub struct GeneralizedBicycleSparseChecks {
17    pub num_cols: usize,
18    pub h_x: Vec<Vec<usize>>,
19    pub h_z: Vec<Vec<usize>>,
20    pub normalized_spec: GeneralizedBicycleSpec,
21}
22
23pub fn generalized_bicycle_sparse_checks(
24    spec: &GeneralizedBicycleSpec,
25) -> Result<GeneralizedBicycleSparseChecks> {
26    let normalized_spec = normalize_spec(spec)?;
27    let a = cyclic_circulant(normalized_spec.order, &normalized_spec.a_exponents)?;
28    let b = cyclic_circulant(normalized_spec.order, &normalized_spec.b_exponents)?;
29    let h_x = a.hconcat(&b)?;
30    let h_z = b.transpose()?.hconcat(&a.transpose()?)?;
31
32    Ok(GeneralizedBicycleSparseChecks {
33        num_cols: h_x.num_cols(),
34        h_x: h_x.rows().to_vec(),
35        h_z: h_z.rows().to_vec(),
36        normalized_spec,
37    })
38}
39
40pub fn generalized_bicycle_known_distances(
41    spec: &GeneralizedBicycleSpec,
42) -> Option<(usize, usize)> {
43    (spec.order == 5 && spec.a_exponents == [0, 1] && spec.b_exponents == [0, 2]).then_some((3, 3))
44}
45
46fn normalize_spec(spec: &GeneralizedBicycleSpec) -> Result<GeneralizedBicycleSpec> {
47    if spec.order == 0 {
48        return Err(invalid("order must be nonzero"));
49    }
50    Ok(GeneralizedBicycleSpec {
51        order: spec.order,
52        a_exponents: normalize_exponents("a_exponents", spec.order, &spec.a_exponents)?,
53        b_exponents: normalize_exponents("b_exponents", spec.order, &spec.b_exponents)?,
54    })
55}
56
57fn normalize_exponents(
58    parameter: &'static str,
59    order: usize,
60    exponents: &[usize],
61) -> Result<Vec<usize>> {
62    if exponents.is_empty() {
63        return Err(invalid(format!("{parameter} must not be empty")));
64    }
65
66    let mut normalized = Vec::with_capacity(exponents.len());
67    for &exponent in exponents {
68        if exponent >= order {
69            return Err(invalid(format!(
70                "{parameter} exponent {exponent} is out of range for order {order}"
71            )));
72        }
73        normalized.push(exponent);
74    }
75    normalized.sort_unstable();
76
77    for window in normalized.windows(2) {
78        if window[0] == window[1] {
79            return Err(invalid(format!(
80                "{parameter} contains duplicate exponent {}",
81                window[0]
82            )));
83        }
84    }
85
86    Ok(normalized)
87}
88
89fn cyclic_circulant(order: usize, exponents: &[usize]) -> Result<SparseGf2Matrix> {
90    let mut rows = Vec::with_capacity(order);
91    for row in 0..order {
92        rows.push(
93            exponents
94                .iter()
95                .map(|&exponent| periodic_add(row, exponent, order))
96                .collect(),
97        );
98    }
99    SparseGf2Matrix::new(order, order, rows)
100}
101
102fn periodic_add(value: usize, shift: usize, period: usize) -> usize {
103    if shift == 0 {
104        value
105    } else if value >= period - shift {
106        value - (period - shift)
107    } else {
108        value + shift
109    }
110}
111
112fn invalid(reason: impl Into<String>) -> QecError {
113    QecError::InvalidCssConstruction {
114        construction: GENERALIZED_BICYCLE_CONSTRUCTION_ID.to_owned(),
115        reason: reason.into(),
116    }
117}
118
119#[cfg(test)]
120mod tests {
121    use super::*;
122
123    #[test]
124    fn order5_rows_match_issue_fixture() {
125        let checks = generalized_bicycle_sparse_checks(&GeneralizedBicycleSpec {
126            order: 5,
127            a_exponents: vec![0, 1],
128            b_exponents: vec![0, 2],
129        })
130        .unwrap();
131
132        assert_eq!(checks.num_cols, 10);
133        assert_eq!(
134            checks.h_x,
135            vec![
136                vec![0, 1, 5, 7],
137                vec![1, 2, 6, 8],
138                vec![2, 3, 7, 9],
139                vec![3, 4, 5, 8],
140                vec![0, 4, 6, 9],
141            ]
142        );
143        assert_eq!(
144            checks.h_z,
145            vec![
146                vec![0, 3, 5, 9],
147                vec![1, 4, 5, 6],
148                vec![0, 2, 6, 7],
149                vec![1, 3, 7, 8],
150                vec![2, 4, 8, 9],
151            ]
152        );
153    }
154}
qec_code/codes/generalized_bicycle.rs

qec_code/codes/
generalized_bicycle.rs
