1use serde::{Deserialize, Serialize};
2
3use crate::codes::generalized_bicycle::{
4 generalized_bicycle_known_distances, generalized_bicycle_sparse_checks, GeneralizedBicycleSpec,
5};
6use crate::error::{QecError, Result};
7
8pub const COPRIME_BB_CONSTRUCTION_ID: &str = "coprime_bb";
9
10#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
11pub struct CoprimeBivariateBicycleSpec {
12 pub l: usize,
13 pub m: usize,
14 pub a_exponents: Vec<usize>,
15 pub b_exponents: Vec<usize>,
16}
17
18#[derive(Debug, Clone, PartialEq, Eq)]
19pub struct CoprimeBivariateBicycleSparseChecks {
20 pub num_cols: usize,
21 pub h_x: Vec<Vec<usize>>,
22 pub h_z: Vec<Vec<usize>>,
23 pub normalized_spec: CoprimeBivariateBicycleSpec,
24}
25
26pub fn coprime_pi_power_index(l: usize, m: usize, exponent: usize) -> Result<(usize, usize)> {
27 let normalized = normalize_periods(l, m)?;
28 if exponent >= normalized.cyclic_order {
29 return Err(invalid(format!(
30 "pi exponent {exponent} is out of range for cyclic order {}",
31 normalized.cyclic_order
32 )));
33 }
34 Ok((exponent % l, exponent % m))
35}
36
37pub fn coprime_bb_sparse_checks(
38 spec: &CoprimeBivariateBicycleSpec,
39) -> Result<CoprimeBivariateBicycleSparseChecks> {
40 let normalized_spec = normalize_spec(spec)?;
41 let generalized_checks = generalized_bicycle_sparse_checks(&GeneralizedBicycleSpec {
42 order: normalized_spec.l * normalized_spec.m,
43 a_exponents: normalized_spec.a_exponents.clone(),
44 b_exponents: normalized_spec.b_exponents.clone(),
45 })?;
46
47 Ok(CoprimeBivariateBicycleSparseChecks {
48 num_cols: generalized_checks.num_cols,
49 h_x: generalized_checks.h_x,
50 h_z: generalized_checks.h_z,
51 normalized_spec,
52 })
53}
54
55pub fn coprime_bb_known_distances(spec: &CoprimeBivariateBicycleSpec) -> Option<(usize, usize)> {
56 let normalized = normalize_spec(spec).ok()?;
57 generalized_bicycle_known_distances(&GeneralizedBicycleSpec {
58 order: normalized.l * normalized.m,
59 a_exponents: normalized.a_exponents.clone(),
60 b_exponents: normalized.b_exponents.clone(),
61 })
62 .or_else(|| {
63 (normalized.l == 3
64 && normalized.m == 5
65 && normalized.a_exponents == [0, 1, 2]
66 && normalized.b_exponents == [0, 2, 7])
67 .then_some((6, 6))
68 })
69}
70
71#[derive(Debug, Clone, Copy)]
72struct NormalizedPeriods {
73 cyclic_order: usize,
74}
75
76fn normalize_spec(spec: &CoprimeBivariateBicycleSpec) -> Result<CoprimeBivariateBicycleSpec> {
77 let normalized_periods = normalize_periods(spec.l, spec.m)?;
78 Ok(CoprimeBivariateBicycleSpec {
79 l: spec.l,
80 m: spec.m,
81 a_exponents: normalize_exponents(
82 "a_exponents",
83 normalized_periods.cyclic_order,
84 &spec.a_exponents,
85 )?,
86 b_exponents: normalize_exponents(
87 "b_exponents",
88 normalized_periods.cyclic_order,
89 &spec.b_exponents,
90 )?,
91 })
92}
93
94fn normalize_periods(l: usize, m: usize) -> Result<NormalizedPeriods> {
95 if l == 0 {
96 return Err(invalid("l must be nonzero"));
97 }
98 if m == 0 {
99 return Err(invalid("m must be nonzero"));
100 }
101 if gcd(l, m) != 1 {
102 return Err(invalid(format!("periods l={l} and m={m} must be coprime")));
103 }
104 let cyclic_order = l
105 .checked_mul(m)
106 .ok_or_else(|| invalid(format!("cyclic order l={l} * m={m} overflows usize")))?;
107
108 Ok(NormalizedPeriods { cyclic_order })
109}
110
111fn normalize_exponents(
112 parameter: &'static str,
113 cyclic_order: usize,
114 exponents: &[usize],
115) -> Result<Vec<usize>> {
116 if exponents.is_empty() {
117 return Err(invalid(format!("{parameter} must not be empty")));
118 }
119
120 let mut normalized = Vec::with_capacity(exponents.len());
121 for &exponent in exponents {
122 if exponent >= cyclic_order {
123 return Err(invalid(format!(
124 "{parameter} exponent {exponent} is out of range for cyclic order {cyclic_order}"
125 )));
126 }
127 normalized.push(exponent);
128 }
129 normalized.sort_unstable();
130
131 for window in normalized.windows(2) {
132 if window[0] == window[1] {
133 return Err(invalid(format!(
134 "{parameter} contains duplicate exponent {}",
135 window[0]
136 )));
137 }
138 }
139
140 Ok(normalized)
141}
142
143fn gcd(mut left: usize, mut right: usize) -> usize {
144 while right != 0 {
145 (left, right) = (right, left % right);
146 }
147 left
148}
149
150fn invalid(reason: impl Into<String>) -> QecError {
151 QecError::InvalidCssConstruction {
152 construction: COPRIME_BB_CONSTRUCTION_ID.to_owned(),
153 reason: reason.into(),
154 }
155}
156
157#[cfg(test)]
158mod tests {
159 use super::*;
160
161 fn fixture_spec() -> CoprimeBivariateBicycleSpec {
162 CoprimeBivariateBicycleSpec {
163 l: 3,
164 m: 5,
165 a_exponents: vec![0, 1, 2],
166 b_exponents: vec![0, 2, 7],
167 }
168 }
169
170 #[test]
171 fn pi_power_index_uses_coprime_period_coordinates() {
172 assert_eq!(coprime_pi_power_index(3, 5, 7).unwrap(), (1, 2));
173 }
174
175 #[test]
176 fn l3_m5_fixture_row_zero_matches_pi_lowering() {
177 let checks = coprime_bb_sparse_checks(&fixture_spec()).unwrap();
178
179 assert_eq!(checks.num_cols, 30);
180 assert_eq!(checks.h_x[0], vec![0, 1, 2, 15, 17, 22]);
181 assert_eq!(checks.h_z[0], vec![0, 8, 13, 15, 28, 29]);
182 assert_eq!(checks.normalized_spec.l, 3);
183 assert_eq!(checks.normalized_spec.m, 5);
184 assert_eq!(checks.normalized_spec.a_exponents, vec![0, 1, 2]);
185 assert_eq!(checks.normalized_spec.b_exponents, vec![0, 2, 7]);
186 }
187
188 #[test]
189 fn known_distances_normalizes_reordered_fixture_exponents() {
190 assert_eq!(
191 coprime_bb_known_distances(&CoprimeBivariateBicycleSpec {
192 l: 3,
193 m: 5,
194 a_exponents: vec![2, 0, 1],
195 b_exponents: vec![7, 0, 2],
196 }),
197 Some((6, 6))
198 );
199 }
200
201 #[test]
202 fn rejects_non_coprime_periods() {
203 let error = coprime_bb_sparse_checks(&CoprimeBivariateBicycleSpec {
204 l: 3,
205 m: 6,
206 a_exponents: vec![0],
207 b_exponents: vec![0],
208 })
209 .unwrap_err();
210
211 assert!(matches!(
212 error,
213 QecError::InvalidCssConstruction { construction, reason }
214 if construction == COPRIME_BB_CONSTRUCTION_ID
215 && reason == "periods l=3 and m=6 must be coprime"
216 ));
217 }
218}