1use std::collections::{BTreeMap, BTreeSet};
2
3use serde::Deserialize;
4
5use crate::css::{CssCode, SparseRowsMatrix};
6use crate::error::{QecError, Result};
7use crate::gf2;
8
9pub const LR_CAYLEY_NO_COVER_V1: &str = "lr_cayley_no_cover_v1";
10
11#[derive(Debug, Clone, PartialEq, Eq)]
12pub struct QuantumTannerSpec {
13 pub construction_mode: QuantumTannerConstructionMode,
14 pub base_group: ExplicitFiniteGroup,
15 pub a_generator_indices: Vec<usize>,
16 pub b_generator_indices: Vec<usize>,
17 pub local_codes: QuantumTannerLocalCodes,
18}
19
20#[derive(Debug, Clone, Copy, PartialEq, Eq)]
21pub enum QuantumTannerConstructionMode {
22 LeftRightCayleyNoCoverV1,
23}
24
25impl QuantumTannerConstructionMode {
26 pub fn as_str(self) -> &'static str {
27 match self {
28 Self::LeftRightCayleyNoCoverV1 => LR_CAYLEY_NO_COVER_V1,
29 }
30 }
31}
32
33#[derive(Debug, Clone, PartialEq, Eq)]
34pub struct ExplicitFiniteGroup {
35 pub name: Option<String>,
36 pub element_order: Option<String>,
37 pub order: usize,
38 pub identity: usize,
39 pub multiplication_table: Vec<Vec<usize>>,
40}
41
42#[derive(Debug, Clone, PartialEq, Eq)]
43pub struct QuantumTannerLocalCodes {
44 pub matrix_role: String,
45 pub field: String,
46 pub h_a: Vec<Vec<u8>>,
47 pub h_b: Vec<Vec<u8>>,
48 pub g_a: Option<Vec<Vec<u8>>>,
49 pub g_b: Option<Vec<Vec<u8>>>,
50}
51
52#[derive(Debug, Clone, PartialEq, Eq)]
53pub struct QuantumTannerLocalBinaryCode {
54 pub width: usize,
55 pub generator_rows: Vec<Vec<u8>>,
56 pub dual_rows: Vec<Vec<u8>>,
57}
58
59#[derive(Debug, Clone, PartialEq, Eq)]
60pub struct QuantumTannerLocalCodeTensorDual {
61 pub code_a: QuantumTannerLocalBinaryCode,
62 pub code_b: QuantumTannerLocalBinaryCode,
63 pub x_sector_rows: Vec<Vec<u8>>,
64 pub z_sector_rows: Vec<Vec<u8>>,
65}
66
67#[derive(Debug, Clone, PartialEq, Eq)]
68pub struct QuantumTannerCayleyComplex {
69 pub faces: Vec<QuantumTannerCayleyFace>,
70 pub oriented_faces: Vec<QuantumTannerOrientedFace>,
71 pub x_incidence: Vec<QuantumTannerLocalIncidence>,
72 pub z_incidence: Vec<QuantumTannerLocalIncidence>,
73}
74
75#[derive(Debug, Clone, Copy, PartialEq, Eq)]
76pub struct QuantumTannerCayleyFace {
77 pub id: usize,
78 pub vertices: [usize; 4],
79}
80
81#[derive(Debug, Clone, Copy, PartialEq, Eq)]
82pub struct QuantumTannerOrientedFace {
83 pub root_vertex: usize,
84 pub a_index: usize,
85 pub b_index: usize,
86 pub a_generator: usize,
87 pub b_generator: usize,
88 pub vertices: [usize; 4],
89 pub face_id: usize,
90}
91
92#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
93pub struct QuantumTannerLocalIncidence {
94 pub source_vertex: usize,
95 pub a_index: usize,
96 pub b_index: usize,
97 pub a_generator: usize,
98 pub b_generator: usize,
99 pub face_id: usize,
100}
101
102#[derive(Debug, Clone, PartialEq, Eq)]
103pub struct QuantumTannerCssChecks {
104 pub num_cols: usize,
105 pub hx: Vec<Vec<usize>>,
106 pub hz: Vec<Vec<usize>>,
107}
108
109#[derive(Debug, Clone, PartialEq, Eq)]
110pub struct ValidatedFiniteGroup {
111 identity: usize,
112 multiplication_table: Vec<Vec<usize>>,
113 inverse_table: Vec<usize>,
114 a_generators: Vec<usize>,
115 b_generators: Vec<usize>,
116}
117
118impl ValidatedFiniteGroup {
119 pub fn order(&self) -> usize {
120 self.multiplication_table.len()
121 }
122
123 pub fn identity(&self) -> usize {
124 self.identity
125 }
126
127 pub fn multiply(&self, left: usize, right: usize) -> Result<usize> {
128 self.validate_element(left)?;
129 self.validate_element(right)?;
130 Ok(self.multiplication_table[left][right])
131 }
132
133 pub fn inv(&self, element: usize) -> Result<usize> {
134 self.validate_element(element)?;
135 Ok(self.inverse_table[element])
136 }
137
138 pub fn a_generators(&self) -> &[usize] {
139 &self.a_generators
140 }
141
142 pub fn b_generators(&self) -> &[usize] {
143 &self.b_generators
144 }
145
146 pub fn a_generator(&self, index: usize) -> Option<usize> {
147 self.a_generators.get(index).copied()
148 }
149
150 pub fn b_generator(&self, index: usize) -> Option<usize> {
151 self.b_generators.get(index).copied()
152 }
153
154 fn validate_element(&self, element: usize) -> Result<()> {
155 let order = self.order();
156 if element < order {
157 Ok(())
158 } else {
159 Err(QecError::InvalidQuantumTannerGroupElement { element, order })
160 }
161 }
162}
163
164pub fn validate_quantum_tanner_group_table(
170 spec: &QuantumTannerSpec,
171) -> Result<ValidatedFiniteGroup> {
172 let group = &spec.base_group;
173 validate_group_table_shape(group.order, group.identity, &group.multiplication_table)?;
174 let identity = find_unique_table_identity(group.order, &group.multiplication_table)?;
175 if identity != group.identity {
176 return Err(QecError::InvalidQuantumTannerGroupTable {
177 reason: format!(
178 "declared identity {} does not match table identity {identity}",
179 group.identity
180 ),
181 });
182 }
183 let inverse_table = build_inverse_table(&group.multiplication_table, identity)?;
184 validate_associativity(&group.multiplication_table)?;
185 validate_generator_indices("A", &spec.a_generator_indices, group.order)?;
186 validate_generator_indices("B", &spec.b_generator_indices, group.order)?;
187
188 Ok(ValidatedFiniteGroup {
189 identity,
190 multiplication_table: group.multiplication_table.clone(),
191 inverse_table,
192 a_generators: spec.a_generator_indices.clone(),
193 b_generators: spec.b_generator_indices.clone(),
194 })
195}
196
197#[derive(Debug, Deserialize)]
198struct QuantumTannerSpecJson {
199 construction_mode: String,
200 base_group: ExplicitFiniteGroupJson,
201 a_generator_indices: Vec<usize>,
202 b_generator_indices: Vec<usize>,
203 local_codes: QuantumTannerLocalCodesJson,
204}
205
206#[derive(Debug, Deserialize)]
207struct ExplicitFiniteGroupJson {
208 name: Option<String>,
209 element_order: Option<String>,
210 order: usize,
211 identity: usize,
212 multiplication_table: Vec<Vec<usize>>,
213}
214
215#[derive(Debug, Deserialize)]
216struct QuantumTannerLocalCodesJson {
217 matrix_role: String,
218 field: String,
219 h_a: Vec<Vec<u8>>,
220 h_b: Vec<Vec<u8>>,
221 #[serde(default)]
222 g_a: Option<Vec<Vec<u8>>>,
223 #[serde(default)]
224 g_b: Option<Vec<Vec<u8>>>,
225}
226
227pub fn quantum_tanner_spec_from_json_str(input: &str) -> Result<QuantumTannerSpec> {
235 let parsed: QuantumTannerSpecJson = serde_json::from_str(input)
236 .map_err(|error| QecError::InvalidQuantumTannerSpecJson(error.to_string()))?;
237
238 let construction_mode = parse_construction_mode(&parsed.construction_mode)?;
239 validate_group_table(
240 parsed.base_group.order,
241 parsed.base_group.identity,
242 &parsed.base_group.multiplication_table,
243 )?;
244 let local_codes = parse_local_codes(
245 parsed.local_codes,
246 parsed.a_generator_indices.len(),
247 parsed.b_generator_indices.len(),
248 )?;
249
250 Ok(QuantumTannerSpec {
251 construction_mode,
252 base_group: ExplicitFiniteGroup {
253 name: parsed.base_group.name,
254 element_order: parsed.base_group.element_order,
255 order: parsed.base_group.order,
256 identity: parsed.base_group.identity,
257 multiplication_table: parsed.base_group.multiplication_table,
258 },
259 a_generator_indices: parsed.a_generator_indices,
260 b_generator_indices: parsed.b_generator_indices,
261 local_codes,
262 })
263}
264
265pub fn quantum_tanner_local_code_tensor_dual(
266 spec: &QuantumTannerSpec,
267) -> Result<QuantumTannerLocalCodeTensorDual> {
268 let code_a = build_local_binary_code(
269 "code_a",
270 &spec.local_codes.h_a,
271 spec.local_codes.g_a.as_deref(),
272 spec.a_generator_indices.len(),
273 )?;
274 let code_b = build_local_binary_code(
275 "code_b",
276 &spec.local_codes.h_b,
277 spec.local_codes.g_b.as_deref(),
278 spec.b_generator_indices.len(),
279 )?;
280 let x_sector_rows = tensor_product_rows(&code_a.generator_rows, &code_b.generator_rows);
281 let z_sector_rows = tensor_product_rows(&code_a.dual_rows, &code_b.dual_rows);
282
283 Ok(QuantumTannerLocalCodeTensorDual {
284 code_a,
285 code_b,
286 x_sector_rows,
287 z_sector_rows,
288 })
289}
290
291pub fn enumerate_quantum_tanner_cayley_faces(
292 construction_mode: QuantumTannerConstructionMode,
293 group: &ValidatedFiniteGroup,
294) -> Result<QuantumTannerCayleyComplex> {
295 match construction_mode {
296 QuantumTannerConstructionMode::LeftRightCayleyNoCoverV1 => {}
297 }
298
299 validate_construction_generators("A", group.a_generators(), group)?;
300 validate_construction_generators("B", group.b_generators(), group)?;
301
302 let mut face_keys = BTreeSet::new();
303 let mut pending_oriented = Vec::new();
304 for root_vertex in 0..group.order() {
305 for (a_index, &a_generator) in group.a_generators().iter().enumerate() {
306 for (b_index, &b_generator) in group.b_generators().iter().enumerate() {
307 let vertices =
308 oriented_face_vertices(group, root_vertex, a_generator, b_generator)?;
309 face_keys.insert(vertices);
310 pending_oriented.push((
311 root_vertex,
312 a_index,
313 b_index,
314 a_generator,
315 b_generator,
316 vertices,
317 ));
318 }
319 }
320 }
321
322 let faces = face_keys
323 .iter()
324 .enumerate()
325 .map(|(id, &vertices)| QuantumTannerCayleyFace { id, vertices })
326 .collect::<Vec<_>>();
327 let face_ids = faces
328 .iter()
329 .map(|face| (face.vertices, face.id))
330 .collect::<BTreeMap<_, _>>();
331
332 let inverse_a_indices = inverse_generator_indices(group.a_generators(), group)?;
333 let mut oriented_faces = Vec::with_capacity(pending_oriented.len());
334 let mut x_incidence = Vec::with_capacity(pending_oriented.len());
335 let mut z_incidence = Vec::with_capacity(pending_oriented.len());
336
337 for (root_vertex, a_index, b_index, a_generator, b_generator, vertices) in pending_oriented {
338 let face_id = face_ids[&vertices];
339 oriented_faces.push(QuantumTannerOrientedFace {
340 root_vertex,
341 a_index,
342 b_index,
343 a_generator,
344 b_generator,
345 vertices,
346 face_id,
347 });
348 x_incidence.push(QuantumTannerLocalIncidence {
349 source_vertex: root_vertex,
350 a_index,
351 b_index,
352 a_generator,
353 b_generator,
354 face_id,
355 });
356
357 let z_source_vertex = group.multiply(a_generator, root_vertex)?;
358 let z_a_generator = group.inv(a_generator)?;
359 let z_a_index = inverse_a_indices[&a_generator];
360 z_incidence.push(QuantumTannerLocalIncidence {
361 source_vertex: z_source_vertex,
362 a_index: z_a_index,
363 b_index,
364 a_generator: z_a_generator,
365 b_generator,
366 face_id,
367 });
368 }
369
370 x_incidence.sort();
371 z_incidence.sort();
372
373 Ok(QuantumTannerCayleyComplex {
374 faces,
375 oriented_faces,
376 x_incidence,
377 z_incidence,
378 })
379}
380
381pub fn quantum_tanner_css_checks(spec: &QuantumTannerSpec) -> Result<QuantumTannerCssChecks> {
382 let group = validate_quantum_tanner_group_table(spec)?;
383 let complex = enumerate_quantum_tanner_cayley_faces(spec.construction_mode, &group)?;
384 let local = quantum_tanner_local_code_tensor_dual(spec)?;
385 quantum_tanner_css_checks_from_validated_parts(spec, &group, &complex, &local)
386}
387
388pub fn quantum_tanner_css_checks_from_validated_parts(
389 spec: &QuantumTannerSpec,
390 group: &ValidatedFiniteGroup,
391 complex: &QuantumTannerCayleyComplex,
392 local: &QuantumTannerLocalCodeTensorDual,
393) -> Result<QuantumTannerCssChecks> {
394 match spec.construction_mode {
395 QuantumTannerConstructionMode::LeftRightCayleyNoCoverV1 => {}
396 }
397
398 if spec.a_generator_indices.as_slice() != group.a_generators() {
399 return Err(css_construction_error(
400 "spec A generator indices do not match validated group",
401 ));
402 }
403 if spec.b_generator_indices.as_slice() != group.b_generators() {
404 return Err(css_construction_error(
405 "spec B generator indices do not match validated group",
406 ));
407 }
408
409 let a_width = group.a_generators().len();
410 let b_width = group.b_generators().len();
411 if local.code_a.width != a_width {
412 return Err(css_construction_error(format!(
413 "local code A width {} does not match |A| {a_width}",
414 local.code_a.width
415 )));
416 }
417 if local.code_b.width != b_width {
418 return Err(css_construction_error(format!(
419 "local code B width {} does not match |B| {b_width}",
420 local.code_b.width
421 )));
422 }
423
424 let local_width = a_width.checked_mul(b_width).ok_or_else(|| {
425 css_construction_error(format!(
426 "local coordinate width overflow for |A|={a_width}, |B|={b_width}"
427 ))
428 })?;
429 validate_local_tensor_rows("X", &local.x_sector_rows, local_width)?;
430 validate_local_tensor_rows("Z", &local.z_sector_rows, local_width)?;
431
432 let num_cols = complex.faces.len();
433 let (x_source_vertices, z_source_vertices) = quantum_tanner_source_vertex_partitions(group)?;
434 let hx = sparse_rows_from_local_incidence(
435 "X",
436 group,
437 &local.x_sector_rows,
438 &complex.x_incidence,
439 &x_source_vertices,
440 num_cols,
441 )?;
442 let hz = sparse_rows_from_local_incidence(
443 "Z",
444 group,
445 &local.z_sector_rows,
446 &complex.z_incidence,
447 &z_source_vertices,
448 num_cols,
449 )?;
450
451 let hx_matrix = SparseRowsMatrix::new(num_cols, hx.clone())?;
452 let hz_matrix = SparseRowsMatrix::new(num_cols, hz.clone())?;
453 CssCode::from_hx_hz(hx_matrix.to_dense_rows(), hz_matrix.to_dense_rows())?;
454
455 Ok(QuantumTannerCssChecks { num_cols, hx, hz })
456}
457
458fn sparse_rows_from_local_incidence(
459 sector: &'static str,
460 group: &ValidatedFiniteGroup,
461 local_rows: &[Vec<u8>],
462 incidence: &[QuantumTannerLocalIncidence],
463 source_vertices: &[usize],
464 num_cols: usize,
465) -> Result<Vec<Vec<usize>>> {
466 let mut rows = Vec::with_capacity(source_vertices.len() * local_rows.len());
467 for &source_vertex in source_vertices {
468 let local_faces =
469 local_incidence_grid_for_source(sector, group, incidence, source_vertex, num_cols)?;
470 for local_row in local_rows {
471 let mut support = BTreeSet::new();
472 for (coordinate, &bit) in local_row.iter().enumerate() {
473 if bit == 0 {
474 continue;
475 }
476 let face_id = local_faces[coordinate].ok_or_else(|| {
477 css_construction_error(format!(
478 "{sector} incidence source {source_vertex} is missing local coordinate {coordinate}"
479 ))
480 })?;
481 if !support.insert(face_id) {
482 support.remove(&face_id);
483 }
484 }
485 rows.push(support.into_iter().collect());
486 }
487 }
488 Ok(rows)
489}
490
491fn quantum_tanner_source_vertex_partitions(
492 group: &ValidatedFiniteGroup,
493) -> Result<(Vec<usize>, Vec<usize>)> {
494 let mut colors: Vec<Option<u8>> = vec![None; group.order()];
495 for start in 0..group.order() {
496 if colors[start].is_some() {
497 continue;
498 }
499 colors[start] = Some(0);
500 let mut queue = std::collections::VecDeque::from([start]);
501 while let Some(vertex) = queue.pop_front() {
502 let color = colors[vertex].expect("queued vertices are colored");
503 for neighbor in quantum_tanner_cayley_neighbors(group, vertex)? {
504 match colors[neighbor] {
505 Some(neighbor_color) if neighbor_color == color => {
506 return Err(css_construction_error(format!(
507 "Cayley graph is not bipartite: adjacent vertices {vertex} and {neighbor} have the same source color"
508 )));
509 }
510 Some(_) => {}
511 None => {
512 colors[neighbor] = Some(color ^ 1);
513 queue.push_back(neighbor);
514 }
515 }
516 }
517 }
518 }
519
520 let mut x_source_vertices = Vec::new();
521 let mut z_source_vertices = Vec::new();
522 for (vertex, color) in colors.into_iter().enumerate() {
523 match color {
524 Some(0) => x_source_vertices.push(vertex),
525 Some(1) => z_source_vertices.push(vertex),
526 _ => unreachable!("all vertices are colored"),
527 }
528 }
529 Ok((x_source_vertices, z_source_vertices))
530}
531
532fn quantum_tanner_cayley_neighbors(
533 group: &ValidatedFiniteGroup,
534 vertex: usize,
535) -> Result<Vec<usize>> {
536 let mut neighbors = Vec::with_capacity(group.a_generators().len() + group.b_generators().len());
537 for &a_generator in group.a_generators() {
538 neighbors.push(group.multiply(a_generator, vertex)?);
539 }
540 for &b_generator in group.b_generators() {
541 neighbors.push(group.multiply(vertex, b_generator)?);
542 }
543 Ok(neighbors)
544}
545
546fn local_incidence_grid_for_source(
547 sector: &'static str,
548 group: &ValidatedFiniteGroup,
549 incidence: &[QuantumTannerLocalIncidence],
550 source_vertex: usize,
551 num_cols: usize,
552) -> Result<Vec<Option<usize>>> {
553 let b_width = group.b_generators().len();
554 let local_width = group.a_generators().len() * b_width;
555 let mut local_faces = vec![None; local_width];
556 for record in incidence
557 .iter()
558 .filter(|record| record.source_vertex == source_vertex)
559 {
560 if record.face_id >= num_cols {
561 return Err(css_construction_error(format!(
562 "{sector} incidence source {source_vertex} references face {} outside 0..{num_cols}",
563 record.face_id
564 )));
565 }
566 let Some(expected_a) = group.a_generator(record.a_index) else {
567 return Err(css_construction_error(format!(
568 "{sector} incidence source {source_vertex} has out-of-range A coordinate {}",
569 record.a_index
570 )));
571 };
572 if record.a_generator != expected_a {
573 return Err(css_construction_error(format!(
574 "{sector} incidence source {source_vertex} A coordinate {} uses generator {}, expected {expected_a}",
575 record.a_index, record.a_generator
576 )));
577 }
578 let Some(expected_b) = group.b_generator(record.b_index) else {
579 return Err(css_construction_error(format!(
580 "{sector} incidence source {source_vertex} has out-of-range B coordinate {}",
581 record.b_index
582 )));
583 };
584 if record.b_generator != expected_b {
585 return Err(css_construction_error(format!(
586 "{sector} incidence source {source_vertex} B coordinate {} uses generator {}, expected {expected_b}",
587 record.b_index, record.b_generator
588 )));
589 }
590
591 let coordinate = record.a_index * b_width + record.b_index;
592 if local_faces[coordinate].replace(record.face_id).is_some() {
593 return Err(css_construction_error(format!(
594 "{sector} incidence source {source_vertex} has duplicate local coordinate {coordinate}"
595 )));
596 }
597 }
598
599 for (coordinate, face_id) in local_faces.iter().enumerate() {
600 if face_id.is_none() {
601 return Err(css_construction_error(format!(
602 "{sector} incidence source {source_vertex} is missing local coordinate {coordinate}"
603 )));
604 }
605 }
606
607 Ok(local_faces)
608}
609
610fn validate_local_tensor_rows(
611 sector: &'static str,
612 rows: &[Vec<u8>],
613 expected_width: usize,
614) -> Result<()> {
615 for (row_index, row) in rows.iter().enumerate() {
616 if row.len() != expected_width {
617 return Err(css_construction_error(format!(
618 "{sector} local tensor row {row_index} has width {}, expected {expected_width}",
619 row.len()
620 )));
621 }
622 for (col_index, &bit) in row.iter().enumerate() {
623 if bit > 1 {
624 return Err(css_construction_error(format!(
625 "{sector} local tensor row {row_index}, column {col_index} is {bit}, expected 0 or 1"
626 )));
627 }
628 }
629 }
630 Ok(())
631}
632
633fn parse_construction_mode(input: &str) -> Result<QuantumTannerConstructionMode> {
634 match input {
635 LR_CAYLEY_NO_COVER_V1 => Ok(QuantumTannerConstructionMode::LeftRightCayleyNoCoverV1),
636 mode => Err(QecError::UnsupportedQuantumTannerConstructionMode {
637 mode: mode.to_owned(),
638 }),
639 }
640}
641
642fn validate_group_table(order: usize, identity: usize, table: &[Vec<usize>]) -> Result<()> {
643 validate_group_table_shape(order, identity, table)?;
644 if identity != 0 {
645 return Err(QecError::InvalidQuantumTannerGroupTable {
646 reason: format!("identity must be 0 in v1, got {identity}"),
647 });
648 }
649
650 Ok(())
651}
652
653fn validate_construction_generators(
654 set: &'static str,
655 generators: &[usize],
656 group: &ValidatedFiniteGroup,
657) -> Result<()> {
658 if generators.is_empty() {
659 return Err(QecError::InvalidQuantumTannerGeneratorSet {
660 set,
661 reason: "generator set must be nonempty".to_owned(),
662 });
663 }
664
665 let mut seen = BTreeSet::new();
666 for (index, &generator) in generators.iter().enumerate() {
667 if !seen.insert(generator) {
668 return Err(QecError::InvalidQuantumTannerGeneratorSet {
669 set,
670 reason: format!("duplicate generator {generator} at coordinate {index}"),
671 });
672 }
673 }
674
675 for &generator in generators {
676 let inverse = group.inv(generator)?;
677 if !seen.contains(&inverse) {
678 return Err(QecError::InvalidQuantumTannerGeneratorSet {
679 set,
680 reason: format!("generator {generator} is missing inverse {inverse}"),
681 });
682 }
683 }
684
685 Ok(())
686}
687
688fn oriented_face_vertices(
689 group: &ValidatedFiniteGroup,
690 root: usize,
691 a: usize,
692 b: usize,
693) -> Result<[usize; 4]> {
694 let ag = group.multiply(a, root)?;
695 let gb = group.multiply(root, b)?;
696 let agb = group.multiply(ag, b)?;
697 let mut vertices = [root, ag, gb, agb];
698 vertices.sort_unstable();
699 if vertices.windows(2).any(|pair| pair[0] == pair[1]) {
700 return Err(QecError::DegenerateQuantumTannerFace {
701 root,
702 a,
703 b,
704 vertices: vertices.to_vec(),
705 });
706 }
707 Ok(vertices)
708}
709
710fn inverse_generator_indices(
711 generators: &[usize],
712 group: &ValidatedFiniteGroup,
713) -> Result<BTreeMap<usize, usize>> {
714 let generator_indices = generators
715 .iter()
716 .enumerate()
717 .map(|(index, &generator)| (generator, index))
718 .collect::<BTreeMap<_, _>>();
719 generators
720 .iter()
721 .map(|&generator| {
722 let inverse = group.inv(generator)?;
723 Ok((generator, generator_indices[&inverse]))
724 })
725 .collect()
726}
727
728fn parse_local_codes(
729 local_codes: QuantumTannerLocalCodesJson,
730 a_width: usize,
731 b_width: usize,
732) -> Result<QuantumTannerLocalCodes> {
733 if local_codes.matrix_role != "parity_check" {
734 return Err(QecError::InvalidQuantumTannerLocalCodeMatrix {
735 matrix: "local_codes",
736 reason: format!(
737 "matrix_role must be parity_check, got {}",
738 local_codes.matrix_role
739 ),
740 });
741 }
742 if local_codes.field != "GF(2)" {
743 return Err(QecError::InvalidQuantumTannerLocalCodeMatrix {
744 matrix: "local_codes",
745 reason: format!("field must be GF(2), got {}", local_codes.field),
746 });
747 }
748
749 validate_binary_matrix_width("h_a", &local_codes.h_a, a_width)?;
750 validate_binary_matrix_width("h_b", &local_codes.h_b, b_width)?;
751 validate_optional_generator_rows(
752 "code_a",
753 "g_a",
754 &local_codes.h_a,
755 local_codes.g_a.as_deref(),
756 a_width,
757 )?;
758 validate_optional_generator_rows(
759 "code_b",
760 "g_b",
761 &local_codes.h_b,
762 local_codes.g_b.as_deref(),
763 b_width,
764 )?;
765
766 Ok(QuantumTannerLocalCodes {
767 matrix_role: local_codes.matrix_role,
768 field: local_codes.field,
769 h_a: local_codes.h_a,
770 h_b: local_codes.h_b,
771 g_a: local_codes.g_a,
772 g_b: local_codes.g_b,
773 })
774}
775
776fn validate_group_table_shape(order: usize, identity: usize, table: &[Vec<usize>]) -> Result<()> {
777 if order == 0 {
778 return Err(QecError::InvalidQuantumTannerGroupTable {
779 reason: "order must be positive".to_owned(),
780 });
781 }
782 if identity >= order {
783 return Err(QecError::InvalidQuantumTannerGroupTable {
784 reason: format!("identity {identity} is out of range for order {order}"),
785 });
786 }
787 if table.len() != order {
788 return Err(QecError::InvalidQuantumTannerGroupTable {
789 reason: format!("expected {order} rows, got {}", table.len()),
790 });
791 }
792
793 for (row_index, row) in table.iter().enumerate() {
794 if row.len() != order {
795 return Err(QecError::InvalidQuantumTannerGroupTable {
796 reason: format!("row {row_index} has width {}, expected {order}", row.len()),
797 });
798 }
799 for (col_index, &entry) in row.iter().enumerate() {
800 if entry >= order {
801 return Err(QecError::InvalidQuantumTannerGroupTable {
802 reason: format!(
803 "entry at row {row_index}, column {col_index} is {entry}, expected < {order}"
804 ),
805 });
806 }
807 }
808 }
809
810 Ok(())
811}
812
813fn find_unique_table_identity(order: usize, table: &[Vec<usize>]) -> Result<usize> {
814 let candidates = (0..order)
815 .filter(|&candidate| {
816 (0..order).all(|element| {
817 table[candidate][element] == element && table[element][candidate] == element
818 })
819 })
820 .collect::<Vec<_>>();
821
822 match candidates.as_slice() {
823 [identity] => Ok(*identity),
824 [] => Err(QecError::InvalidQuantumTannerGroupTable {
825 reason: "expected exactly one two-sided identity, found none".to_owned(),
826 }),
827 many => Err(QecError::InvalidQuantumTannerGroupTable {
828 reason: format!("expected exactly one two-sided identity, found {many:?}"),
829 }),
830 }
831}
832
833fn build_inverse_table(table: &[Vec<usize>], identity: usize) -> Result<Vec<usize>> {
834 let order = table.len();
835 let mut inverse_table = Vec::with_capacity(order);
836 for element in 0..order {
837 let candidates = (0..order)
838 .filter(|&candidate| {
839 table[element][candidate] == identity && table[candidate][element] == identity
840 })
841 .collect::<Vec<_>>();
842 match candidates.as_slice() {
843 [inverse] => inverse_table.push(*inverse),
844 [] => {
845 return Err(QecError::InvalidQuantumTannerGroupTable {
846 reason: format!(
847 "element {element} has no two-sided inverse under identity {identity}"
848 ),
849 });
850 }
851 many => {
852 return Err(QecError::InvalidQuantumTannerGroupTable {
853 reason: format!(
854 "element {element} has multiple two-sided inverses under identity {identity}: {many:?}"
855 ),
856 });
857 }
858 }
859 }
860 Ok(inverse_table)
861}
862
863fn validate_associativity(table: &[Vec<usize>]) -> Result<()> {
864 let order = table.len();
865 for a in 0..order {
866 for b in 0..order {
867 for c in 0..order {
868 let left = table[table[a][b]][c];
869 let right = table[a][table[b][c]];
870 if left != right {
871 return Err(QecError::InvalidQuantumTannerGroupTable {
872 reason: format!(
873 "associativity failed for ({a}, {b}, {c}): ({a} * {b}) * {c} = {left}, but {a} * ({b} * {c}) = {right}"
874 ),
875 });
876 }
877 }
878 }
879 }
880 Ok(())
881}
882
883fn validate_generator_indices(set: &'static str, generators: &[usize], order: usize) -> Result<()> {
884 for (index, &element) in generators.iter().enumerate() {
885 if element >= order {
886 return Err(QecError::InvalidQuantumTannerGeneratorIndex {
887 set,
888 index,
889 element,
890 order,
891 });
892 }
893 }
894 Ok(())
895}
896
897fn validate_binary_matrix_width(
898 matrix: &'static str,
899 rows: &[Vec<u8>],
900 expected_width: usize,
901) -> Result<()> {
902 for (row_index, row) in rows.iter().enumerate() {
903 if row.len() != expected_width {
904 return Err(QecError::InvalidQuantumTannerLocalCodeMatrix {
905 matrix,
906 reason: format!(
907 "row {row_index} has width {}, expected {expected_width}",
908 row.len()
909 ),
910 });
911 }
912 for (col_index, &entry) in row.iter().enumerate() {
913 if entry > 1 {
914 return Err(QecError::InvalidQuantumTannerLocalCodeMatrix {
915 matrix,
916 reason: format!(
917 "entry at row {row_index}, column {col_index} is {entry}, expected 0 or 1"
918 ),
919 });
920 }
921 }
922 }
923
924 Ok(())
925}
926
927fn build_local_binary_code(
928 code: &'static str,
929 check_rows: &[Vec<u8>],
930 supplied_generator_rows: Option<&[Vec<u8>]>,
931 width: usize,
932) -> Result<QuantumTannerLocalBinaryCode> {
933 validate_binary_matrix_width(code, check_rows, width)?;
934 let dual_rows = gf2::try_select_independent_rows(check_rows)
935 .map_err(|error| local_code_error(code, error.to_string()))?;
936 let generator_rows = match supplied_generator_rows {
937 Some(rows) => validate_generator_rows(code, "generator", check_rows, rows, width)?,
938 None => gf2::try_nullspace_basis_with_width(check_rows, width)
939 .map_err(|error| local_code_error(code, error.to_string()))?,
940 };
941
942 Ok(QuantumTannerLocalBinaryCode {
943 width,
944 generator_rows,
945 dual_rows,
946 })
947}
948
949fn validate_optional_generator_rows(
950 code: &'static str,
951 matrix: &'static str,
952 check_rows: &[Vec<u8>],
953 generator_rows: Option<&[Vec<u8>]>,
954 width: usize,
955) -> Result<()> {
956 let Some(generator_rows) = generator_rows else {
957 return Ok(());
958 };
959 validate_generator_rows(code, matrix, check_rows, generator_rows, width)?;
960 Ok(())
961}
962
963fn validate_generator_rows(
964 code: &'static str,
965 matrix: &'static str,
966 check_rows: &[Vec<u8>],
967 generator_rows: &[Vec<u8>],
968 width: usize,
969) -> Result<Vec<Vec<u8>>> {
970 validate_binary_matrix_width(matrix, generator_rows, width)?;
971 for (check_index, check_row) in check_rows.iter().enumerate() {
972 for (generator_index, generator_row) in generator_rows.iter().enumerate() {
973 if dot_mod2(check_row, generator_row) != 0 {
974 return Err(local_code_error(
975 code,
976 format!(
977 "{matrix} row {generator_index} is not orthogonal to check row {check_index}"
978 ),
979 ));
980 }
981 }
982 }
983
984 let check_rank =
985 gf2::try_rank(check_rows).map_err(|error| local_code_error(code, error.to_string()))?;
986 let expected_generator_rank = width - check_rank;
987 let generator_basis = gf2::try_select_independent_rows(generator_rows)
988 .map_err(|error| local_code_error(code, error.to_string()))?;
989 if generator_basis.len() != expected_generator_rank {
990 return Err(local_code_error(
991 code,
992 format!(
993 "{matrix} rank is {}, expected {expected_generator_rank}",
994 generator_basis.len()
995 ),
996 ));
997 }
998
999 Ok(generator_basis)
1000}
1001
1002fn dot_mod2(lhs: &[u8], rhs: &[u8]) -> u8 {
1003 lhs.iter()
1004 .zip(rhs)
1005 .fold(0, |parity, (&left, &right)| parity ^ (left & right))
1006}
1007
1008fn tensor_product_rows(lhs: &[Vec<u8>], rhs: &[Vec<u8>]) -> Vec<Vec<u8>> {
1009 lhs.iter()
1010 .flat_map(|left| {
1011 rhs.iter().map(move |right| {
1012 left.iter()
1013 .flat_map(|&left_bit| right.iter().map(move |&right_bit| left_bit & right_bit))
1014 .collect::<Vec<_>>()
1015 })
1016 })
1017 .collect()
1018}
1019
1020fn local_code_error(matrix: &'static str, reason: String) -> QecError {
1021 QecError::InvalidQuantumTannerLocalCodeMatrix { matrix, reason }
1022}
1023
1024fn css_construction_error(reason: impl Into<String>) -> QecError {
1025 QecError::InvalidQuantumTannerCssConstruction {
1026 reason: reason.into(),
1027 }
1028}