1use serde::Serialize;
2
3use crate::error::{QecError, Result};
4use crate::sparse_gf2::SparseGf2Matrix;
5
6pub const MAX_FINITE_GROUP_ORDER: usize = 256;
8
9#[derive(Debug, Clone, PartialEq, Eq)]
10pub struct FiniteGroupSpec {
11 order: usize,
12 identity: usize,
13 multiplication_table: Vec<Vec<usize>>,
14 inverse_table: Vec<usize>,
15}
16
17#[derive(Debug, Clone, PartialEq, Eq)]
18pub struct GroupAlgebraElement {
19 group_order: usize,
20 support: Vec<usize>,
21}
22
23#[derive(Debug, Clone, Copy, PartialEq, Eq)]
24pub struct LeftRegularLift;
25
26#[derive(Debug, Clone, Copy, PartialEq, Eq)]
27pub struct RightRegularLift;
28
29impl FiniteGroupSpec {
30 pub fn new(
31 order: usize,
32 identity: usize,
33 multiplication_table: Vec<Vec<usize>>,
34 ) -> Result<Self> {
35 if order > MAX_FINITE_GROUP_ORDER {
36 return Err(QecError::GroupOrderLimitExceeded {
37 order,
38 max_order: MAX_FINITE_GROUP_ORDER,
39 });
40 }
41 if order == 0 {
42 return Err(QecError::InvalidFiniteGroupTable {
43 reason: "order must be positive".to_owned(),
44 });
45 }
46 if identity >= order {
47 return Err(QecError::InvalidFiniteGroupTable {
48 reason: format!("identity {identity} is out of range for order {order}"),
49 });
50 }
51
52 validate_group_table_shape(order, &multiplication_table)?;
53 find_unique_table_identity(order, identity, &multiplication_table)?;
54 let inverse_table = build_inverse_table(order, identity, &multiplication_table)?;
55 validate_associativity(order, &multiplication_table)?;
56
57 Ok(Self {
58 order,
59 identity,
60 multiplication_table,
61 inverse_table,
62 })
63 }
64
65 pub fn order(&self) -> usize {
66 self.order
67 }
68
69 pub fn identity(&self) -> usize {
70 self.identity
71 }
72
73 pub fn multiplication_table(&self) -> &[Vec<usize>] {
74 &self.multiplication_table
75 }
76
77 pub fn inverse_table(&self) -> &[usize] {
78 &self.inverse_table
79 }
80
81 pub fn multiply(&self, left: usize, right: usize) -> Result<usize> {
82 validate_group_element(self.order, left)?;
83 validate_group_element(self.order, right)?;
84 Ok(self.multiplication_table[left][right])
85 }
86
87 pub fn inverse(&self, element: usize) -> Result<usize> {
88 validate_group_element(self.order, element)?;
89 Ok(self.inverse_table[element])
90 }
91
92 pub fn to_json_string(&self) -> String {
93 #[derive(Serialize)]
94 struct GroupJson<'a> {
95 order: usize,
96 identity: usize,
97 multiplication_table: &'a [Vec<usize>],
98 }
99
100 serde_json::to_string(&GroupJson {
101 order: self.order,
102 identity: self.identity,
103 multiplication_table: &self.multiplication_table,
104 })
105 .expect("finite-group JSON serialization cannot fail")
106 }
107}
108
109impl GroupAlgebraElement {
110 pub fn new(group: &FiniteGroupSpec, support: Vec<usize>) -> Result<Self> {
111 Ok(Self {
112 group_order: group.order,
113 support: canonicalize_support(group.order, support)?,
114 })
115 }
116
117 pub fn group_order(&self) -> usize {
118 self.group_order
119 }
120
121 pub fn support(&self) -> &[usize] {
122 &self.support
123 }
124
125 pub fn to_json_string(&self) -> String {
126 #[derive(Serialize)]
127 struct GroupAlgebraElementJson<'a> {
128 group_order: usize,
129 support: &'a [usize],
130 }
131
132 serde_json::to_string(&GroupAlgebraElementJson {
133 group_order: self.group_order,
134 support: &self.support,
135 })
136 .expect("group-algebra JSON serialization cannot fail")
137 }
138}
139
140impl LeftRegularLift {
141 pub fn checked_output_shape(
142 &self,
143 group: &FiniteGroupSpec,
144 matrix_rows: usize,
145 matrix_cols: usize,
146 ) -> Result<(usize, usize)> {
147 regular_lift_shape(group, matrix_rows, matrix_cols)
148 }
149
150 pub fn lift(
151 &self,
152 group: &FiniteGroupSpec,
153 matrix: &[Vec<GroupAlgebraElement>],
154 ) -> Result<SparseGf2Matrix> {
155 regular_lift(group, matrix, left_action)
156 }
157}
158
159impl RightRegularLift {
160 pub fn checked_output_shape(
161 &self,
162 group: &FiniteGroupSpec,
163 matrix_rows: usize,
164 matrix_cols: usize,
165 ) -> Result<(usize, usize)> {
166 regular_lift_shape(group, matrix_rows, matrix_cols)
167 }
168
169 pub fn lift(
170 &self,
171 group: &FiniteGroupSpec,
172 matrix: &[Vec<GroupAlgebraElement>],
173 ) -> Result<SparseGf2Matrix> {
174 regular_lift(group, matrix, right_action)
175 }
176}
177
178pub fn left_regular_lift(
179 group: &FiniteGroupSpec,
180 matrix: &[Vec<GroupAlgebraElement>],
181) -> Result<SparseGf2Matrix> {
182 LeftRegularLift.lift(group, matrix)
183}
184
185pub fn right_regular_lift(
186 group: &FiniteGroupSpec,
187 matrix: &[Vec<GroupAlgebraElement>],
188) -> Result<SparseGf2Matrix> {
189 RightRegularLift.lift(group, matrix)
190}
191
192fn validate_group_table_shape(order: usize, multiplication_table: &[Vec<usize>]) -> Result<()> {
193 if multiplication_table.len() != order {
194 return Err(QecError::InvalidFiniteGroupTable {
195 reason: format!("expected {order} rows, got {}", multiplication_table.len()),
196 });
197 }
198
199 for (row_index, row) in multiplication_table.iter().enumerate() {
200 if row.len() != order {
201 return Err(QecError::InvalidFiniteGroupTable {
202 reason: format!("row {row_index} has width {}; expected {order}", row.len()),
203 });
204 }
205 for (column_index, &entry) in row.iter().enumerate() {
206 if entry >= order {
207 return Err(QecError::InvalidFiniteGroupTable {
208 reason: format!(
209 "entry at row {row_index}, column {column_index} is {entry}; expected < {order}"
210 ),
211 });
212 }
213 }
214 }
215 Ok(())
216}
217
218fn find_unique_table_identity(
219 order: usize,
220 declared_identity: usize,
221 multiplication_table: &[Vec<usize>],
222) -> Result<()> {
223 let identities = (0..order)
224 .filter(|&candidate| {
225 (0..order).all(|element| {
226 multiplication_table[candidate][element] == element
227 && multiplication_table[element][candidate] == element
228 })
229 })
230 .collect::<Vec<_>>();
231
232 match identities.as_slice() {
233 [identity] if *identity == declared_identity => Ok(()),
234 [identity] => Err(QecError::InvalidFiniteGroupTable {
235 reason: format!(
236 "declared identity {declared_identity} does not match table identity {identity}"
237 ),
238 }),
239 [] => Err(QecError::InvalidFiniteGroupTable {
240 reason: "table has no two-sided identity".to_owned(),
241 }),
242 _ => Err(QecError::InvalidFiniteGroupTable {
243 reason: "table has multiple two-sided identities".to_owned(),
244 }),
245 }
246}
247
248fn build_inverse_table(
249 order: usize,
250 identity: usize,
251 multiplication_table: &[Vec<usize>],
252) -> Result<Vec<usize>> {
253 let mut inverse_table = Vec::new();
254 inverse_table
255 .try_reserve_exact(order)
256 .map_err(|_| QecError::InvalidFiniteGroupTable {
257 reason: "could not allocate inverse table".to_owned(),
258 })?;
259
260 for element in 0..order {
261 let inverses = (0..order)
262 .filter(|&candidate| {
263 multiplication_table[element][candidate] == identity
264 && multiplication_table[candidate][element] == identity
265 })
266 .collect::<Vec<_>>();
267 match inverses.as_slice() {
268 [inverse] => inverse_table.push(*inverse),
269 [] => {
270 return Err(QecError::InvalidFiniteGroupTable {
271 reason: format!("element {element} has no two-sided inverse"),
272 });
273 }
274 _ => {
275 return Err(QecError::InvalidFiniteGroupTable {
276 reason: format!("element {element} has multiple two-sided inverses"),
277 });
278 }
279 }
280 }
281 Ok(inverse_table)
282}
283
284fn validate_associativity(order: usize, multiplication_table: &[Vec<usize>]) -> Result<()> {
285 for left in 0..order {
286 for middle in 0..order {
287 for right in 0..order {
288 let left_associated =
289 multiplication_table[multiplication_table[left][middle]][right];
290 let right_associated =
291 multiplication_table[left][multiplication_table[middle][right]];
292 if left_associated != right_associated {
293 return Err(QecError::InvalidFiniteGroupTable {
294 reason: format!(
295 "associativity failed for ({left} * {middle}) * {right} = {left_associated}, {left} * ({middle} * {right}) = {right_associated}"
296 ),
297 });
298 }
299 }
300 }
301 }
302 Ok(())
303}
304
305fn validate_group_element(order: usize, element: usize) -> Result<()> {
306 if element >= order {
307 return Err(QecError::InvalidFiniteGroupElement { element, order });
308 }
309 Ok(())
310}
311
312fn canonicalize_support(order: usize, mut support: Vec<usize>) -> Result<Vec<usize>> {
313 for &element in &support {
314 if element >= order {
315 return Err(QecError::InvalidGroupAlgebraElementSupport {
316 support: element,
317 order,
318 });
319 }
320 }
321
322 support.sort_unstable();
323 let mut canonical = Vec::new();
324 let mut index = 0;
325 while index < support.len() {
326 let element = support[index];
327 let mut keep = false;
328 while index < support.len() && support[index] == element {
329 keep = !keep;
330 index += 1;
331 }
332 if keep {
333 canonical.push(element);
334 }
335 }
336 Ok(canonical)
337}
338
339fn regular_lift(
340 group: &FiniteGroupSpec,
341 matrix: &[Vec<GroupAlgebraElement>],
342 action: fn(&FiniteGroupSpec, usize, usize) -> Result<usize>,
343) -> Result<SparseGf2Matrix> {
344 let matrix_rows = matrix.len();
345 let matrix_cols = matrix.first().map_or(0, Vec::len);
346 for row in matrix {
347 if row.len() != matrix_cols {
348 return Err(QecError::GroupAlgebraMatrixRowWidthMismatch {
349 expected: matrix_cols,
350 actual: row.len(),
351 });
352 }
353 for element in row {
354 if element.group_order != group.order {
355 return Err(QecError::GroupAlgebraOrderMismatch {
356 expected: group.order,
357 actual: element.group_order,
358 });
359 }
360 }
361 }
362
363 let (num_rows, num_cols) = regular_lift_shape(group, matrix_rows, matrix_cols)?;
364 let mut rows = Vec::new();
365 rows.try_reserve_exact(num_rows)
366 .map_err(|_| QecError::GroupAlgebraDimensionOverflow {
367 operation: "regular lift rows",
368 })?;
369
370 for row in matrix {
371 for x in 0..group.order {
372 let mut output_row = Vec::new();
373 for (matrix_col, element) in row.iter().enumerate() {
374 let block_start = matrix_col.checked_mul(group.order).ok_or(
375 QecError::GroupAlgebraDimensionOverflow {
376 operation: "regular lift column index",
377 },
378 )?;
379 for &support in &element.support {
380 let acted = action(group, support, x)?;
381 output_row.push(block_start.checked_add(acted).ok_or(
382 QecError::GroupAlgebraDimensionOverflow {
383 operation: "regular lift column index",
384 },
385 )?);
386 }
387 }
388 rows.push(output_row);
389 }
390 }
391
392 SparseGf2Matrix::new(num_rows, num_cols, rows)
393}
394
395fn regular_lift_shape(
396 group: &FiniteGroupSpec,
397 matrix_rows: usize,
398 matrix_cols: usize,
399) -> Result<(usize, usize)> {
400 let num_rows =
401 matrix_rows
402 .checked_mul(group.order)
403 .ok_or(QecError::GroupAlgebraDimensionOverflow {
404 operation: "regular lift shape",
405 })?;
406 let num_cols =
407 matrix_cols
408 .checked_mul(group.order)
409 .ok_or(QecError::GroupAlgebraDimensionOverflow {
410 operation: "regular lift shape",
411 })?;
412 Ok((num_rows, num_cols))
413}
414
415fn left_action(group: &FiniteGroupSpec, element: usize, x: usize) -> Result<usize> {
416 group.multiply(group.inverse(element)?, x)
417}
418
419fn right_action(group: &FiniteGroupSpec, element: usize, x: usize) -> Result<usize> {
420 group.multiply(x, element)
421}