1use std::collections::BTreeMap;
2use std::sync::LazyLock;
3
4use serde::{Deserialize, Serialize};
5use serde_json::{Map, Value};
6use sha2::{Digest, Sha256};
7
8use crate::binary::try_binary_rank;
9use crate::codes::built_in_css::{
10 BuiltInCssCodeSpec, BuiltInCssFamily, BuiltInCssParams, built_in_css_checks,
11 parse_built_in_css_code_spec,
12};
13use crate::codes::color_666::{COLOR_666_CONSTRUCTION_ID, color_666_sparse_checks};
14pub use crate::codes::color_666::{Color666FamilySpec, Color666Layout};
15pub use crate::codes::coprime_bb::CoprimeBivariateBicycleSpec;
16use crate::codes::coprime_bb::{
17 COPRIME_BB_CONSTRUCTION_ID, coprime_bb_known_distances, coprime_bb_sparse_checks,
18};
19use crate::codes::directional::{
20 DirectionalConnectivity, DirectionalCssSpec, build_directional_css_checks,
21};
22pub use crate::codes::generalized_bicycle::GeneralizedBicycleSpec;
23use crate::codes::generalized_bicycle::{
24 GENERALIZED_BICYCLE_CONSTRUCTION_ID, generalized_bicycle_known_distances,
25 generalized_bicycle_sparse_checks,
26};
27use crate::codes::la_cross::{
28 LA_CROSS_CONSTRUCTION_ID, la_cross_classical_check, la_cross_known_distances,
29};
30pub use crate::codes::la_cross::{LaCrossBoundary, LaCrossSpec};
31use crate::codes::quantum_tanner::{
32 QuantumTannerSpec, quantum_tanner_css_checks, quantum_tanner_spec_from_json_str,
33};
34use crate::codes::random_hgp::{
35 RandomHgpClassicalSample, RandomHgpSpec, random_hgp_spec_from_json_str,
36 sample_random_hgp_classical_matrices, sampled_random_hgp_to_hgp_spec,
37};
38use crate::codes::random_two_block::{
39 RandomTwoBlockSpec, random_two_block_css_checks, random_two_block_spec_from_json_str,
40};
41use crate::codes::toric_3d::{Toric3dSpec, toric_3d_css_checks};
42use crate::css::SparseRowsMatrix;
43use crate::error::{QecError, Result};
44use crate::finite_group::{FiniteGroupSpec, GroupAlgebraElement};
45use crate::lifted_product::lifted_product_binary_checks;
46use crate::sparse_gf2::SparseGf2Matrix;
47
48pub const CSS_CONSTRUCTION_SCHEMA_VERSION: u64 = 1;
49
50pub const DOCUMENTED_NON_FAMILY_CONSTRUCTION_IDS: &[&str] = &[
51 "hypergraph_product",
52 "legacy_built_in",
53 "steane",
54 "bb72",
55 "apm_kasai",
56 "bb",
57 "repetition_x",
58 "repetition_z",
59 "surface_rotated",
60 "toric",
61];
62
63#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
64#[serde(rename_all = "snake_case")]
65pub enum RequestedFamilyId {
66 Directional,
67 QuantumTanner,
68 GeneralizedBicycle,
69 LaCross,
70 RandomHgp,
71 LiftedProduct,
72 #[serde(rename = "hyperbolic_5_5")]
73 Hyperbolic55,
74 CoprimeBb,
75 #[serde(rename = "toric_3d")]
76 Toric3d,
77 #[serde(rename = "color_666")]
78 Color666,
79 Surface,
80 ShorLike,
81 RandomTwoBlock,
82 PerturbedHgp,
83}
84
85impl RequestedFamilyId {
86 pub const ALL: [Self; 14] = [
87 Self::Directional,
88 Self::QuantumTanner,
89 Self::GeneralizedBicycle,
90 Self::LaCross,
91 Self::RandomHgp,
92 Self::LiftedProduct,
93 Self::Hyperbolic55,
94 Self::CoprimeBb,
95 Self::Toric3d,
96 Self::Color666,
97 Self::Surface,
98 Self::ShorLike,
99 Self::RandomTwoBlock,
100 Self::PerturbedHgp,
101 ];
102
103 pub const fn as_str(self) -> &'static str {
104 match self {
105 Self::Directional => "directional",
106 Self::QuantumTanner => "quantum_tanner",
107 Self::GeneralizedBicycle => "generalized_bicycle",
108 Self::LaCross => "la_cross",
109 Self::RandomHgp => "random_hgp",
110 Self::LiftedProduct => "lifted_product",
111 Self::Hyperbolic55 => "hyperbolic_5_5",
112 Self::CoprimeBb => "coprime_bb",
113 Self::Toric3d => "toric_3d",
114 Self::Color666 => "color_666",
115 Self::Surface => "surface",
116 Self::ShorLike => "shor_like",
117 Self::RandomTwoBlock => "random_two_block",
118 Self::PerturbedHgp => "perturbed_hgp",
119 }
120 }
121}
122
123#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
124#[serde(rename_all = "snake_case")]
125pub enum SurfaceLayout {
126 Rotated,
127 Unrotated,
128}
129
130impl SurfaceLayout {
131 pub const fn as_str(self) -> &'static str {
132 match self {
133 Self::Rotated => "rotated",
134 Self::Unrotated => "unrotated",
135 }
136 }
137}
138
139#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
140pub struct SurfaceSpec {
141 pub layout: SurfaceLayout,
142 pub row_distance: usize,
143 pub column_distance: usize,
144}
145
146impl SurfaceSpec {
147 pub const fn rotated_square(distance: usize) -> Self {
148 Self {
149 layout: SurfaceLayout::Rotated,
150 row_distance: distance,
151 column_distance: distance,
152 }
153 }
154}
155
156#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
157pub struct SurfaceFamilySpec {
158 pub distance: usize,
159}
160
161#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
162pub struct ShorLikeSpec {
163 pub outer_blocks: usize,
164 pub inner_block: usize,
165}
166
167#[derive(Debug, Clone, PartialEq, Eq)]
168pub enum CssFamilySpec {
169 Directional(DirectionalCssSpec),
170 QuantumTanner(QuantumTannerSpec),
171 GeneralizedBicycle(GeneralizedBicycleSpec),
172 LaCross(LaCrossSpec),
173 RandomHgp(RandomHgpSpec),
174 LiftedProduct(LiftedProductSpec),
175 CoprimeBb(CoprimeBivariateBicycleSpec),
176 Toric3d(Toric3dSpec),
177 Color666(Color666FamilySpec),
178 Surface(SurfaceFamilySpec),
179 ShorLike(ShorLikeSpec),
180 RandomTwoBlock(RandomTwoBlockSpec),
181}
182
183impl CssFamilySpec {
184 pub const fn callable_requested_family_ids() -> &'static [RequestedFamilyId] {
185 &[
186 RequestedFamilyId::Directional,
187 RequestedFamilyId::QuantumTanner,
188 RequestedFamilyId::GeneralizedBicycle,
189 RequestedFamilyId::LaCross,
190 RequestedFamilyId::RandomHgp,
191 RequestedFamilyId::LiftedProduct,
192 RequestedFamilyId::CoprimeBb,
193 RequestedFamilyId::Toric3d,
194 RequestedFamilyId::Color666,
195 RequestedFamilyId::Surface,
196 RequestedFamilyId::ShorLike,
197 RequestedFamilyId::RandomTwoBlock,
198 ]
199 }
200}
201
202#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
203pub struct CssClassicalCheckSpec {
204 pub num_cols: usize,
205 pub rows: Vec<Vec<usize>>,
206}
207
208pub static CLASSICAL_IDENTITY_2: LazyLock<CssClassicalCheckSpec> =
209 LazyLock::new(|| CssClassicalCheckSpec {
210 num_cols: 2,
211 rows: vec![vec![0], vec![1]],
212 });
213
214#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
215pub struct HypergraphProductSpec {
216 pub left: CssClassicalCheckSpec,
217 pub right: CssClassicalCheckSpec,
218}
219
220#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
221pub struct FiniteGroupTableSpec {
222 pub order: usize,
223 pub identity: usize,
224 pub multiplication_table: Vec<Vec<usize>>,
225}
226
227#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
228pub struct GroupAlgebraElementSpec {
229 pub support: Vec<usize>,
230}
231
232#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
233pub struct GroupAlgebraProtographSpec {
234 pub rows: Vec<Vec<GroupAlgebraElementSpec>>,
235}
236
237#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
238pub struct LiftedProductSpec {
239 pub group: FiniteGroupTableSpec,
240 pub left: GroupAlgebraProtographSpec,
241 pub right: GroupAlgebraProtographSpec,
242}
243
244#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
245pub struct LegacyBuiltInCssSpec {
246 pub code_id: String,
247}
248
249#[derive(Debug, Clone, PartialEq, Eq)]
250pub enum CssConstructionSpec {
251 Family(CssFamilySpec),
252 Surface(SurfaceSpec),
253 HypergraphProduct(HypergraphProductSpec),
254 LiftedProduct(LiftedProductSpec),
255 LegacyBuiltIn(LegacyBuiltInCssSpec),
256}
257
258impl From<CssFamilySpec> for CssConstructionSpec {
259 fn from(value: CssFamilySpec) -> Self {
260 Self::Family(value)
261 }
262}
263
264impl From<SurfaceSpec> for CssConstructionSpec {
265 fn from(value: SurfaceSpec) -> Self {
266 Self::Surface(value)
267 }
268}
269
270impl CssConstructionSpec {
271 pub const fn documented_non_family_construction_ids() -> &'static [&'static str] {
272 DOCUMENTED_NON_FAMILY_CONSTRUCTION_IDS
273 }
274
275 pub fn from_inline(input: &str) -> Result<Self> {
276 let parsed = parse_built_in_css_code_spec(input)?;
277 if let BuiltInCssCodeSpec::Family {
278 family: BuiltInCssFamily::SurfaceRotated,
279 params: BuiltInCssParams::Distance { distance },
280 } = parsed
281 {
282 return Ok(CssFamilySpec::Surface(SurfaceFamilySpec { distance }).into());
283 }
284 if let BuiltInCssCodeSpec::Family {
285 family: BuiltInCssFamily::Color666,
286 params: BuiltInCssParams::Distance { distance },
287 } = parsed
288 {
289 return Ok(CssFamilySpec::Color666(Color666FamilySpec {
290 distance,
291 layout: Color666Layout::Triangular,
292 })
293 .into());
294 }
295
296 if let BuiltInCssCodeSpec::Family {
297 family: BuiltInCssFamily::Toric3d,
298 params: BuiltInCssParams::Toric3d(spec),
299 } = parsed
300 {
301 return Ok(CssFamilySpec::Toric3d(spec).into());
302 }
303
304 Ok(Self::LegacyBuiltIn(LegacyBuiltInCssSpec {
305 code_id: input.to_owned(),
306 }))
307 }
308}
309
310#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
311pub struct CssChecks {
312 pub h_x: Vec<Vec<usize>>,
313 pub h_z: Vec<Vec<usize>>,
314}
315
316#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
317pub struct CssCodeStats {
318 pub n: usize,
319 pub m_x: usize,
320 pub m_z: usize,
321 pub rank_x: usize,
322 pub rank_z: usize,
323 pub k: usize,
324 #[serde(skip_serializing_if = "Option::is_none")]
325 pub d_x: Option<usize>,
326 #[serde(skip_serializing_if = "Option::is_none")]
327 pub d_z: Option<usize>,
328}
329
330#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
331pub struct CssConstructionProvenance {
332 pub adapter: String,
333 pub source: String,
334 pub normalized_input_digest: String,
335}
336
337#[derive(Debug, Clone, PartialEq, Serialize)]
338pub struct CssConstructionResult {
339 pub schema_version: u64,
340 pub construction_id: String,
341 pub requested_family_id: Option<RequestedFamilyId>,
342 pub normalized_parameters: BTreeMap<String, Value>,
343 pub checks: CssChecks,
344 pub stats: CssCodeStats,
345 pub provenance: CssConstructionProvenance,
346}
347
348pub fn construct_css(spec: CssConstructionSpec) -> Result<CssConstructionResult> {
349 match spec {
350 CssConstructionSpec::Family(CssFamilySpec::Surface(spec)) => construct_legacy_surface(spec),
351 CssConstructionSpec::Family(CssFamilySpec::QuantumTanner(spec)) => {
352 let checks = quantum_tanner_css_checks(&spec)?;
353 let parameters = quantum_tanner_normalized_parameters(&spec);
354 construction_result(
355 "quantum_tanner",
356 Some(RequestedFamilyId::QuantumTanner),
357 parameters,
358 checks.num_cols,
359 checks.hx,
360 checks.hz,
361 "quantum_tanner",
362 "CssFamilySpec::QuantumTanner",
363 None,
364 )
365 }
366 CssConstructionSpec::Family(CssFamilySpec::GeneralizedBicycle(spec)) => {
367 let checks = generalized_bicycle_sparse_checks(&spec)?;
368 let normalized = checks.normalized_spec;
369 let mut parameters = BTreeMap::new();
370 parameters.insert("order".to_owned(), Value::from(normalized.order));
371 parameters.insert(
372 "a_exponents".to_owned(),
373 serde_json::to_value(&normalized.a_exponents).expect("serializable exponents"),
374 );
375 parameters.insert(
376 "b_exponents".to_owned(),
377 serde_json::to_value(&normalized.b_exponents).expect("serializable exponents"),
378 );
379 let known_distances = generalized_bicycle_known_distances(&normalized);
380 construction_result(
381 GENERALIZED_BICYCLE_CONSTRUCTION_ID,
382 Some(RequestedFamilyId::GeneralizedBicycle),
383 parameters,
384 checks.num_cols,
385 checks.h_x,
386 checks.h_z,
387 GENERALIZED_BICYCLE_CONSTRUCTION_ID,
388 "CssFamilySpec::GeneralizedBicycle",
389 known_distances,
390 )
391 }
392 CssConstructionSpec::Family(CssFamilySpec::LaCross(spec)) => construct_la_cross(spec),
393 CssConstructionSpec::Family(CssFamilySpec::CoprimeBb(spec)) => {
394 let checks = coprime_bb_sparse_checks(&spec)?;
395 let normalized = checks.normalized_spec;
396 let mut parameters = BTreeMap::new();
397 parameters.insert("l".to_owned(), Value::from(normalized.l));
398 parameters.insert("m".to_owned(), Value::from(normalized.m));
399 parameters.insert(
400 "cyclic_order".to_owned(),
401 Value::from(normalized.l * normalized.m),
402 );
403 parameters.insert("pi".to_owned(), Value::from("xy"));
404 parameters.insert(
405 "a_exponents".to_owned(),
406 serde_json::to_value(&normalized.a_exponents).unwrap(),
407 );
408 parameters.insert(
409 "b_exponents".to_owned(),
410 serde_json::to_value(&normalized.b_exponents).unwrap(),
411 );
412 let known_distances = coprime_bb_known_distances(&normalized);
413 construction_result(
414 COPRIME_BB_CONSTRUCTION_ID,
415 Some(RequestedFamilyId::CoprimeBb),
416 parameters,
417 checks.num_cols,
418 checks.h_x,
419 checks.h_z,
420 "coprime_bb",
421 "CssFamilySpec::CoprimeBb",
422 known_distances,
423 )
424 }
425 CssConstructionSpec::Family(CssFamilySpec::Toric3d(spec)) => {
426 let checks = toric_3d_css_checks(spec)?;
427 let mut parameters = BTreeMap::new();
428 parameters.insert("lx".to_owned(), Value::from(spec.lx));
429 parameters.insert("ly".to_owned(), Value::from(spec.ly));
430 parameters.insert("lz".to_owned(), Value::from(spec.lz));
431 construction_result(
432 "toric_3d",
433 Some(RequestedFamilyId::Toric3d),
434 parameters,
435 checks.num_cols,
436 checks.hx,
437 checks.hz,
438 "toric_3d_chain_complex",
439 "CssFamilySpec::Toric3d",
440 Some((checks.distances.d_x, checks.distances.d_z)),
441 )
442 }
443 CssConstructionSpec::Family(CssFamilySpec::RandomTwoBlock(spec)) => {
444 let checks = random_two_block_css_checks(&spec)?;
445 let parameters = random_two_block_normalized_parameters(&spec, &checks);
446 construction_result(
447 "random_two_block",
448 Some(RequestedFamilyId::RandomTwoBlock),
449 parameters,
450 checks.num_cols,
451 checks.h_x,
452 checks.h_z,
453 "random_two_block",
454 "CssFamilySpec::RandomTwoBlock",
455 None,
456 )
457 }
458 CssConstructionSpec::Family(CssFamilySpec::RandomHgp(spec)) => {
459 let samples = sample_random_hgp_classical_matrices(&spec)?;
460 let hgp = sampled_random_hgp_to_hgp_spec(&samples);
461 construct_hypergraph_product_from_parts(
462 hgp,
463 "random_hgp",
464 Some(RequestedFamilyId::RandomHgp),
465 random_hgp_normalized_parameters(&samples),
466 "random_hgp",
467 "CssFamilySpec::RandomHgp",
468 )
469 }
470 CssConstructionSpec::Family(CssFamilySpec::LiftedProduct(spec)) => {
471 construct_lifted_product(spec, "CssFamilySpec::LiftedProduct")
472 }
473 CssConstructionSpec::Family(CssFamilySpec::Directional(spec)) => {
474 let checks = build_directional_css_checks(&spec)?;
475 let parameters = directional_normalized_parameters(&spec, &checks);
476 construction_result(
477 checks.code_id,
478 Some(RequestedFamilyId::Directional),
479 parameters,
480 checks.num_cols,
481 checks.hx,
482 checks.hz,
483 "directional",
484 "CssFamilySpec::Directional",
485 directional_known_distances(&spec, &checks.normalized_route),
486 )
487 }
488 CssConstructionSpec::Family(CssFamilySpec::Color666(spec)) => {
489 let checks = color_666_sparse_checks(&spec)?;
490 let mut parameters = BTreeMap::new();
491 parameters.insert("distance".to_owned(), Value::from(spec.distance));
492 parameters.insert("layout".to_owned(), Value::from(spec.layout.as_str()));
493 construction_result(
494 COLOR_666_CONSTRUCTION_ID,
495 Some(RequestedFamilyId::Color666),
496 parameters,
497 checks.num_cols,
498 checks.rows.clone(),
499 checks.rows,
500 COLOR_666_CONSTRUCTION_ID,
501 "CssFamilySpec::Color666",
502 Some((spec.distance, spec.distance)),
503 )
504 }
505 CssConstructionSpec::Family(CssFamilySpec::ShorLike(spec)) => construct_shor_like(spec),
506 CssConstructionSpec::Surface(spec) => construct_surface(spec),
507 CssConstructionSpec::HypergraphProduct(spec) => construct_hypergraph_product(spec),
508 CssConstructionSpec::LiftedProduct(spec) => {
509 construct_lifted_product(spec, "CssConstructionSpec::LiftedProduct")
510 }
511 CssConstructionSpec::LegacyBuiltIn(spec) => {
512 if let Some(distance) = legacy_surface_distance_from_code_id(&spec.code_id) {
513 preflight_legacy_surface_overflow(distance)?;
514 }
515
516 let checks = built_in_css_checks(&spec.code_id)?;
517 let mut parameters = BTreeMap::new();
518 parameters.insert("code_id".to_owned(), Value::from(spec.code_id));
519 construction_result(
520 checks.code_id,
521 None,
522 parameters,
523 checks.num_cols,
524 checks.hx,
525 checks.hz,
526 "built_in_css",
527 "CssConstructionSpec::LegacyBuiltIn",
528 None,
529 )
530 }
531 }
532}
533
534fn construct_la_cross(spec: LaCrossSpec) -> Result<CssConstructionResult> {
535 let generated = la_cross_classical_check(&spec)?;
536 let hgp = construct_hypergraph_product(HypergraphProductSpec {
537 left: generated.check.clone(),
538 right: generated.check.clone(),
539 })?;
540 let mut parameters = BTreeMap::new();
541 parameters.insert(
542 "seed_length".to_owned(),
543 Value::from(generated.spec.seed_length),
544 );
545 parameters.insert("reach".to_owned(), Value::from(generated.spec.reach));
546 parameters.insert(
547 "boundary".to_owned(),
548 Value::from(generated.spec.boundary.as_str()),
549 );
550 parameters.insert(
551 "classical_check".to_owned(),
552 serde_json::to_value(&generated.check).expect("serializable classical check"),
553 );
554 let known_distances = la_cross_known_distances(&generated.spec);
555
556 construction_result(
557 LA_CROSS_CONSTRUCTION_ID,
558 Some(RequestedFamilyId::LaCross),
559 parameters,
560 hgp.stats.n,
561 hgp.checks.h_x,
562 hgp.checks.h_z,
563 LA_CROSS_CONSTRUCTION_ID,
564 "CssFamilySpec::LaCross",
565 known_distances,
566 )
567}
568
569fn construct_shor_like(spec: ShorLikeSpec) -> Result<CssConstructionResult> {
570 validate_shor_like_spec(&spec)?;
571 let n = spec
572 .outer_blocks
573 .checked_mul(spec.inner_block)
574 .ok_or_else(|| QecError::InvalidCssConstruction {
575 construction: "shor_like".to_owned(),
576 reason: "shor_like dimension overflow during data qubit count".to_owned(),
577 })?;
578 let (h_x, h_z) = shor_like_supports(spec.outer_blocks, spec.inner_block);
579 let mut parameters = BTreeMap::new();
580 parameters.insert("inner_block".to_owned(), Value::from(spec.inner_block));
581 parameters.insert("outer_blocks".to_owned(), Value::from(spec.outer_blocks));
582 construction_result(
583 "shor_like",
584 Some(RequestedFamilyId::ShorLike),
585 parameters,
586 n,
587 h_x,
588 h_z,
589 "shor_like",
590 "CssFamilySpec::ShorLike",
591 Some((spec.inner_block, spec.outer_blocks)),
592 )
593}
594
595fn validate_shor_like_spec(spec: &ShorLikeSpec) -> Result<()> {
596 for (parameter, value) in [
597 ("outer_blocks", spec.outer_blocks),
598 ("inner_block", spec.inner_block),
599 ] {
600 if value < 2 {
601 return Err(QecError::InvalidCssConstruction {
602 construction: "shor_like".to_owned(),
603 reason: format!("{parameter} must be at least 2, got {value}"),
604 });
605 }
606 }
607 Ok(())
608}
609
610fn shor_like_supports(
611 outer_blocks: usize,
612 inner_block: usize,
613) -> (Vec<Vec<usize>>, Vec<Vec<usize>>) {
614 let mut h_x = Vec::new();
615 for outer_block in 0..outer_blocks - 1 {
616 let first_base = outer_block * inner_block;
617 let second_base = (outer_block + 1) * inner_block;
618 let mut row = Vec::new();
619 for offset in 0..inner_block {
620 row.push(first_base + offset);
621 }
622 for offset in 0..inner_block {
623 row.push(second_base + offset);
624 }
625 h_x.push(row);
626 }
627
628 let mut h_z = Vec::new();
629 for outer_block in 0..outer_blocks {
630 let base = outer_block * inner_block;
631 for inner_index in 0..inner_block - 1 {
632 let first = base + inner_index;
633 h_z.push(vec![first, first + 1]);
634 }
635 }
636 (h_x, h_z)
637}
638
639fn directional_normalized_parameters(
640 spec: &DirectionalCssSpec,
641 checks: &crate::codes::directional::DirectionalCssChecks,
642) -> BTreeMap<String, Value> {
643 let mut parameters = BTreeMap::new();
644 parameters.insert(
645 "torus".to_owned(),
646 serde_json::to_value(&spec.torus).expect("serializable directional torus"),
647 );
648 parameters.insert("route".to_owned(), Value::from(spec.route.clone()));
649 parameters.insert(
650 "normalized_route".to_owned(),
651 Value::from(checks.normalized_route.clone()),
652 );
653 parameters.insert(
654 "route_support".to_owned(),
655 serde_json::to_value(&checks.route_support)
656 .expect("serializable directional route support"),
657 );
658 parameters.insert(
659 "layout".to_owned(),
660 serde_json::to_value(&spec.layout).expect("serializable directional layout"),
661 );
662 parameters.insert(
663 "connectivity".to_owned(),
664 serde_json::to_value(spec.connectivity).expect("serializable directional connectivity"),
665 );
666 parameters
667}
668
669fn directional_known_distances(
670 spec: &DirectionalCssSpec,
671 normalized_route: &str,
672) -> Option<(usize, usize)> {
673 match (
674 spec.torus.period_x,
675 spec.torus.period_y,
676 spec.torus.vertical_period_x_shift,
677 normalized_route,
678 spec.connectivity,
679 ) {
680 (8, 6, 4, "NE2N", DirectionalConnectivity::Square) => Some((3, 3)),
681 (18, 4, 0, "NE3N", DirectionalConnectivity::Hex) => Some((4, 4)),
682 _ => None,
683 }
684}
685
686fn legacy_surface_distance_from_code_id(code_id: &str) -> Option<usize> {
687 match parse_built_in_css_code_spec(code_id).ok()? {
688 BuiltInCssCodeSpec::Family {
689 family: BuiltInCssFamily::SurfaceRotated,
690 params: BuiltInCssParams::Distance { distance },
691 } => Some(distance),
692 _ => None,
693 }
694}
695
696fn construct_legacy_surface(spec: SurfaceFamilySpec) -> Result<CssConstructionResult> {
697 preflight_legacy_surface_overflow(spec.distance)?;
698
699 let checks = built_in_css_checks(&format!("surface_rotated:d={}", spec.distance))?;
700 let mut parameters = BTreeMap::new();
701 parameters.insert("distance".to_owned(), Value::from(spec.distance));
702 construction_result(
703 checks.code_id,
704 Some(RequestedFamilyId::Surface),
705 parameters,
706 checks.num_cols,
707 checks.hx,
708 checks.hz,
709 "built_in_css",
710 "CssFamilySpec::Surface",
711 Some((spec.distance, spec.distance)),
712 )
713}
714
715fn construct_surface(spec: SurfaceSpec) -> Result<CssConstructionResult> {
716 validate_surface_spec(&spec)?;
717 let (n, h_x, h_z, construction_id) = match spec.layout {
718 SurfaceLayout::Rotated => {
719 let n = spec
720 .row_distance
721 .checked_mul(spec.column_distance)
722 .ok_or_else(|| surface_overflow("data qubit count"))?;
723 let (h_x, h_z) = rotated_surface_supports(spec.row_distance, spec.column_distance);
724 (n, h_x, h_z, "surface_rotated")
725 }
726 SurfaceLayout::Unrotated => {
727 let n = unrotated_surface_num_data_qubits(spec.row_distance, spec.column_distance)?;
728 let (h_x, h_z) = unrotated_surface_supports(spec.row_distance, spec.column_distance)?;
729 (n, h_x, h_z, "surface_unrotated")
730 }
731 };
732 let mut parameters = BTreeMap::new();
733 parameters.insert("layout".to_owned(), Value::from(spec.layout.as_str()));
734 parameters.insert("row_distance".to_owned(), Value::from(spec.row_distance));
735 parameters.insert(
736 "column_distance".to_owned(),
737 Value::from(spec.column_distance),
738 );
739 construction_result(
740 construction_id,
741 Some(RequestedFamilyId::Surface),
742 parameters,
743 n,
744 h_x,
745 h_z,
746 "surface",
747 "CssConstructionSpec::Surface",
748 Some((spec.column_distance, spec.row_distance)),
749 )
750}
751
752fn validate_surface_spec(spec: &SurfaceSpec) -> Result<()> {
753 validate_surface_distance("row_distance", spec.row_distance)?;
754 validate_surface_distance("column_distance", spec.column_distance)?;
755
756 if matches!(spec.layout, SurfaceLayout::Rotated)
757 && (spec.row_distance > isize::MAX as usize / 2
758 || spec.column_distance > isize::MAX as usize / 2)
759 {
760 return Err(surface_overflow("rotated coordinate arithmetic"));
761 }
762
763 Ok(())
764}
765
766fn validate_surface_distance(parameter: &'static str, value: usize) -> Result<()> {
767 if value < 2 {
768 return Err(QecError::InvalidCssConstruction {
769 construction: "surface".to_owned(),
770 reason: format!("{parameter} must be at least 2, got {value}"),
771 });
772 }
773 Ok(())
774}
775
776fn preflight_legacy_surface_overflow(distance: usize) -> Result<()> {
777 distance
778 .checked_mul(distance)
779 .ok_or_else(|| surface_overflow("data qubit count"))?;
780 if distance > isize::MAX as usize / 2 {
781 return Err(surface_overflow("rotated coordinate arithmetic"));
782 }
783 Ok(())
784}
785
786fn surface_overflow(operation: &'static str) -> QecError {
787 QecError::InvalidCssConstruction {
788 construction: "surface".to_owned(),
789 reason: format!("surface dimension overflow during {operation}"),
790 }
791}
792
793fn rotated_surface_supports(
794 row_distance: usize,
795 column_distance: usize,
796) -> (Vec<Vec<usize>>, Vec<Vec<usize>>) {
797 let mut h_x = Vec::new();
798 let mut h_z = Vec::new();
799
800 for ax in 0..=row_distance {
801 for ay in 0..=column_distance {
802 let on_row_boundary = ax == 0 || ax == row_distance;
803 let on_column_boundary = ay == 0 || ay == column_distance;
804 let parity = (ax % 2) != (ay % 2);
805 if on_row_boundary && parity {
806 continue;
807 }
808 if on_column_boundary && !parity {
809 continue;
810 }
811
812 let support = rotated_surface_measure_support(row_distance, column_distance, ax, ay);
813 if support.is_empty() {
814 continue;
815 }
816
817 if parity {
818 h_x.push(support);
819 } else {
820 h_z.push(support);
821 }
822 }
823 }
824
825 (h_x, h_z)
826}
827
828fn rotated_surface_measure_support(
829 row_distance: usize,
830 column_distance: usize,
831 ax: usize,
832 ay: usize,
833) -> Vec<usize> {
834 let mut support = Vec::new();
835 let mx = (2 * ax) as isize;
836 let my = (2 * ay) as isize;
837
838 for (dx, dy) in [(1isize, 1isize), (1, -1), (-1, 1), (-1, -1)] {
839 let x = mx + dx;
840 let y = my + dy;
841 if x >= 1
842 && x <= (2 * row_distance - 1) as isize
843 && y >= 1
844 && y <= (2 * column_distance - 1) as isize
845 && x % 2 == 1
846 && y % 2 == 1
847 {
848 let qx = ((x - 1) / 2) as usize;
849 let qy = ((y - 1) / 2) as usize;
850 if qx < row_distance && qy < column_distance {
851 support.push(qx * column_distance + qy);
852 }
853 }
854 }
855
856 support.sort_unstable();
857 support.dedup();
858 support
859}
860
861fn unrotated_surface_num_data_qubits(row_distance: usize, column_distance: usize) -> Result<usize> {
862 let grid_rows = checked_surface_grid_extent(row_distance, "row grid extent")?;
863 let grid_columns = checked_surface_grid_extent(column_distance, "column grid extent")?;
864 grid_rows
865 .checked_mul(grid_columns)
866 .and_then(|count| count.checked_add(1))
867 .map(|count| count / 2)
868 .ok_or_else(|| surface_overflow("data qubit count"))
869}
870
871fn checked_surface_grid_extent(distance: usize, operation: &'static str) -> Result<usize> {
872 distance
873 .checked_mul(2)
874 .and_then(|extent| extent.checked_sub(1))
875 .ok_or_else(|| surface_overflow(operation))
876}
877
878fn unrotated_surface_data_indices(
879 grid_rows: usize,
880 grid_columns: usize,
881) -> Result<Vec<Vec<Option<usize>>>> {
882 let mut data_indices = Vec::with_capacity(grid_rows);
883 let mut next_index = 0usize;
884 for row in 0..grid_rows {
885 let mut indices = Vec::with_capacity(grid_columns);
886 for column in 0..grid_columns {
887 if (row % 2) == (column % 2) {
888 indices.push(Some(next_index));
889 next_index = next_index
890 .checked_add(1)
891 .ok_or_else(|| surface_overflow("data qubit count"))?;
892 } else {
893 indices.push(None);
894 }
895 }
896 data_indices.push(indices);
897 }
898 Ok(data_indices)
899}
900
901fn unrotated_surface_supports(
902 row_distance: usize,
903 column_distance: usize,
904) -> Result<(Vec<Vec<usize>>, Vec<Vec<usize>>)> {
905 let grid_rows = checked_surface_grid_extent(row_distance, "row grid extent")?;
906 let grid_columns = checked_surface_grid_extent(column_distance, "column grid extent")?;
907 let data_indices = unrotated_surface_data_indices(grid_rows, grid_columns)?;
908 let mut h_x = Vec::with_capacity(
909 row_distance
910 .checked_sub(1)
911 .and_then(|rows| rows.checked_mul(column_distance))
912 .ok_or_else(|| surface_overflow("X-check count"))?,
913 );
914 let mut h_z = Vec::with_capacity(
915 column_distance
916 .checked_sub(1)
917 .and_then(|columns| row_distance.checked_mul(columns))
918 .ok_or_else(|| surface_overflow("Z-check count"))?,
919 );
920
921 for row in (1..grid_rows).step_by(2) {
922 for column in (0..grid_columns).step_by(2) {
923 h_x.push(unrotated_surface_check_support(
924 grid_rows,
925 grid_columns,
926 &data_indices,
927 row,
928 column,
929 ));
930 }
931 }
932 for row in (0..grid_rows).step_by(2) {
933 for column in (1..grid_columns).step_by(2) {
934 h_z.push(unrotated_surface_check_support(
935 grid_rows,
936 grid_columns,
937 &data_indices,
938 row,
939 column,
940 ));
941 }
942 }
943
944 Ok((h_x, h_z))
945}
946
947fn unrotated_surface_check_support(
948 grid_rows: usize,
949 grid_columns: usize,
950 data_indices: &[Vec<Option<usize>>],
951 row: usize,
952 column: usize,
953) -> Vec<usize> {
954 let mut support = Vec::with_capacity(4);
955 for (neighbor_row, neighbor_column) in [
956 (row.checked_sub(1), Some(column)),
957 (Some(row), column.checked_sub(1)),
958 (Some(row), column.checked_add(1)),
959 (row.checked_add(1), Some(column)),
960 ] {
961 if let (Some(neighbor_row), Some(neighbor_column)) = (neighbor_row, neighbor_column)
962 && neighbor_row < grid_rows
963 && neighbor_column < grid_columns
964 && let Some(index) = data_indices[neighbor_row][neighbor_column]
965 {
966 support.push(index);
967 }
968 }
969 support
970}
971
972fn quantum_tanner_normalized_parameters(spec: &QuantumTannerSpec) -> BTreeMap<String, Value> {
973 let mut base_group = BTreeMap::new();
974 base_group.insert(
975 "name".to_owned(),
976 spec.base_group
977 .name
978 .as_ref()
979 .map_or(Value::Null, |value| Value::from(value.clone())),
980 );
981 base_group.insert(
982 "element_order".to_owned(),
983 spec.base_group
984 .element_order
985 .as_ref()
986 .map_or(Value::Null, |value| Value::from(value.clone())),
987 );
988 base_group.insert("order".to_owned(), Value::from(spec.base_group.order));
989 base_group.insert("identity".to_owned(), Value::from(spec.base_group.identity));
990 base_group.insert(
991 "multiplication_table".to_owned(),
992 serde_json::to_value(&spec.base_group.multiplication_table).expect("serializable table"),
993 );
994
995 let mut local_codes = BTreeMap::new();
996 local_codes.insert(
997 "matrix_role".to_owned(),
998 Value::from(spec.local_codes.matrix_role.clone()),
999 );
1000 local_codes.insert(
1001 "field".to_owned(),
1002 Value::from(spec.local_codes.field.clone()),
1003 );
1004 local_codes.insert(
1005 "h_a".to_owned(),
1006 serde_json::to_value(&spec.local_codes.h_a).expect("serializable h_a"),
1007 );
1008 local_codes.insert(
1009 "h_b".to_owned(),
1010 serde_json::to_value(&spec.local_codes.h_b).expect("serializable h_b"),
1011 );
1012 local_codes.insert(
1013 "g_a".to_owned(),
1014 serde_json::to_value(&spec.local_codes.g_a).expect("serializable g_a"),
1015 );
1016 local_codes.insert(
1017 "g_b".to_owned(),
1018 serde_json::to_value(&spec.local_codes.g_b).expect("serializable g_b"),
1019 );
1020
1021 let mut parameters = BTreeMap::new();
1022 parameters.insert(
1023 "construction_mode".to_owned(),
1024 Value::from(spec.construction_mode.as_str()),
1025 );
1026 parameters.insert(
1027 "base_group".to_owned(),
1028 serde_json::to_value(base_group).expect("serializable base_group"),
1029 );
1030 parameters.insert(
1031 "a_generator_indices".to_owned(),
1032 serde_json::to_value(&spec.a_generator_indices).expect("serializable a generators"),
1033 );
1034 parameters.insert(
1035 "b_generator_indices".to_owned(),
1036 serde_json::to_value(&spec.b_generator_indices).expect("serializable b generators"),
1037 );
1038 parameters.insert(
1039 "local_codes".to_owned(),
1040 serde_json::to_value(local_codes).expect("serializable local_codes"),
1041 );
1042 parameters
1043}
1044
1045fn random_two_block_normalized_parameters(
1046 spec: &RandomTwoBlockSpec,
1047 checks: &crate::codes::random_two_block::RandomTwoBlockCssChecks,
1048) -> BTreeMap<String, Value> {
1049 let mut group = BTreeMap::new();
1050 group.insert("order".to_owned(), Value::from(spec.group.order()));
1051 group.insert("identity".to_owned(), Value::from(spec.group.identity()));
1052 group.insert(
1053 "multiplication_table".to_owned(),
1054 serde_json::to_value(spec.group.multiplication_table())
1055 .expect("serializable random two-block group table"),
1056 );
1057
1058 let mut parameters = BTreeMap::new();
1059 parameters.insert(
1060 "group".to_owned(),
1061 serde_json::to_value(group).expect("serializable random two-block group"),
1062 );
1063 parameters.insert(
1064 "group_digest".to_owned(),
1065 Value::from(checks.metadata.group_digest.clone()),
1066 );
1067 parameters.insert("seed".to_owned(), Value::from(checks.metadata.seed));
1068 parameters.insert(
1069 "support_a_weight".to_owned(),
1070 Value::from(checks.metadata.support_a_weight),
1071 );
1072 parameters.insert(
1073 "support_b_weight".to_owned(),
1074 Value::from(checks.metadata.support_b_weight),
1075 );
1076 parameters.insert(
1077 "algorithm_version".to_owned(),
1078 Value::from(checks.metadata.algorithm_version),
1079 );
1080 parameters.insert(
1081 "support_a".to_owned(),
1082 serde_json::to_value(&checks.support_a).expect("serializable support A"),
1083 );
1084 parameters.insert(
1085 "support_b".to_owned(),
1086 serde_json::to_value(&checks.support_b).expect("serializable support B"),
1087 );
1088 parameters
1089}
1090
1091fn random_hgp_normalized_parameters(
1092 samples: &crate::codes::random_hgp::RandomHgpClassicalSamples,
1093) -> BTreeMap<String, Value> {
1094 let mut parameters = BTreeMap::new();
1095 parameters.insert(
1096 "left".to_owned(),
1097 random_hgp_classical_parameters(&samples.left),
1098 );
1099 parameters.insert(
1100 "right".to_owned(),
1101 random_hgp_classical_parameters(&samples.right),
1102 );
1103 parameters
1104}
1105
1106fn random_hgp_classical_parameters(sample: &RandomHgpClassicalSample) -> Value {
1107 serde_json::json!({
1108 "classical_spec": sample.spec,
1109 "rows": sample.rows,
1110 "sampler_version": sample.spec.algorithm_version,
1111 })
1112}
1113
1114pub fn parse_css_construction_json(input: &str) -> Result<CssConstructionSpec> {
1115 let value: Value = serde_json::from_str(input)
1116 .map_err(|error| QecError::InvalidCssConstructionJson(error.to_string()))?;
1117 let object = value.as_object().ok_or_else(|| {
1118 QecError::InvalidCssConstructionJson(
1119 "construction request must be a JSON object".to_owned(),
1120 )
1121 })?;
1122 let version = required_u64(object, "schema_version")?;
1123 if version != CSS_CONSTRUCTION_SCHEMA_VERSION {
1124 return Err(QecError::UnsupportedCssConstructionSchemaVersion { version });
1125 }
1126 let construction = required_string(object, "construction")?;
1127 match construction {
1128 "surface" => surface_construction_from_json(object, construction),
1129 "generalized_bicycle" => Ok(CssFamilySpec::GeneralizedBicycle(GeneralizedBicycleSpec {
1130 order: required_usize(object, "order", construction)?,
1131 a_exponents: required_usize_array(object, "a_exponents", construction)?,
1132 b_exponents: required_usize_array(object, "b_exponents", construction)?,
1133 })
1134 .into()),
1135 "coprime_bb" => Ok(CssFamilySpec::CoprimeBb(CoprimeBivariateBicycleSpec {
1136 l: required_usize(object, "l", construction)?,
1137 m: required_usize(object, "m", construction)?,
1138 a_exponents: required_usize_array(object, "a_exponents", construction)?,
1139 b_exponents: required_usize_array(object, "b_exponents", construction)?,
1140 })
1141 .into()),
1142 "color_666" => {
1143 let layout = optional_string(object, "layout")?
1144 .map(Color666Layout::parse)
1145 .transpose()?
1146 .unwrap_or(Color666Layout::Triangular);
1147 Ok(CssFamilySpec::Color666(Color666FamilySpec {
1148 distance: required_usize(object, "distance", construction)?,
1149 layout,
1150 })
1151 .into())
1152 }
1153 "shor_like" => {
1154 let spec = ShorLikeSpec {
1155 outer_blocks: required_usize(object, "outer_blocks", construction)?,
1156 inner_block: required_usize(object, "inner_block", construction)?,
1157 };
1158 validate_shor_like_spec(&spec)?;
1159 Ok(CssFamilySpec::ShorLike(spec).into())
1160 }
1161 "quantum_tanner" => {
1162 let spec_value = object.get("spec").unwrap_or(&value);
1163 let mut spec_object = spec_value.as_object().cloned().ok_or_else(|| {
1164 QecError::InvalidCssConstruction {
1165 construction: construction.to_owned(),
1166 reason: "spec must be a JSON object".to_owned(),
1167 }
1168 })?;
1169 spec_object.remove("schema_version");
1170 spec_object.remove("construction");
1171 let spec_json = serde_json::to_string(&spec_object)
1172 .expect("JSON object serialization should not fail");
1173 Ok(CssFamilySpec::QuantumTanner(quantum_tanner_spec_from_json_str(&spec_json)?).into())
1174 }
1175 "toric_3d" => {
1176 let spec = Toric3dSpec {
1177 lx: required_usize(object, "lx", construction)?,
1178 ly: required_usize(object, "ly", construction)?,
1179 lz: required_usize(object, "lz", construction)?,
1180 };
1181 toric_3d_css_checks(spec)?;
1182 Ok(CssFamilySpec::Toric3d(spec).into())
1183 }
1184 "la_cross" => {
1185 let spec = LaCrossSpec {
1186 seed_length: required_usize(object, "seed_length", construction)?,
1187 reach: required_usize(object, "reach", construction)?,
1188 boundary: LaCrossBoundary::parse(required_string(object, "boundary")?)?,
1189 };
1190 la_cross_classical_check(&spec)?;
1191 Ok(CssFamilySpec::LaCross(spec).into())
1192 }
1193 "random_two_block" => {
1194 Ok(CssFamilySpec::RandomTwoBlock(random_two_block_spec_from_json_str(input)?).into())
1195 }
1196 "random_hgp" => Ok(CssFamilySpec::RandomHgp(random_hgp_spec_from_json_str(input)?).into()),
1197 "directional" => directional_construction_from_json(object, construction),
1198 "hypergraph_product" => Ok(CssConstructionSpec::HypergraphProduct(
1199 serde_json::from_value(value.clone()).map_err(|error| {
1200 QecError::InvalidCssConstruction {
1201 construction: construction.to_owned(),
1202 reason: error.to_string(),
1203 }
1204 })?,
1205 )),
1206 "lifted_product" => Ok(CssFamilySpec::LiftedProduct(
1207 serde_json::from_value(value.clone()).map_err(|error| {
1208 QecError::InvalidCssConstruction {
1209 construction: construction.to_owned(),
1210 reason: error.to_string(),
1211 }
1212 })?,
1213 )
1214 .into()),
1215 "legacy_built_in" => Ok(CssConstructionSpec::LegacyBuiltIn(LegacyBuiltInCssSpec {
1216 code_id: required_string(object, "code_id")?.to_owned(),
1217 })),
1218 unknown => Err(QecError::UnknownCssConstruction {
1219 construction: unknown.to_owned(),
1220 }),
1221 }
1222}
1223
1224fn directional_construction_from_json(
1225 object: &Map<String, Value>,
1226 construction: &str,
1227) -> Result<CssConstructionSpec> {
1228 let spec_value = if let Some(spec_value) = object.get("spec") {
1229 for key in object.keys() {
1230 if !matches!(key.as_str(), "schema_version" | "construction" | "spec") {
1231 return Err(QecError::InvalidCssConstruction {
1232 construction: construction.to_owned(),
1233 reason: format!("unknown directional construction field {key:?}"),
1234 });
1235 }
1236 }
1237 spec_value.clone()
1238 } else {
1239 let mut spec_object = object.clone();
1240 spec_object.remove("schema_version");
1241 spec_object.remove("construction");
1242 Value::Object(spec_object)
1243 };
1244 let spec =
1245 serde_json::from_value(spec_value).map_err(|error| QecError::InvalidCssConstruction {
1246 construction: construction.to_owned(),
1247 reason: error.to_string(),
1248 })?;
1249 Ok(CssFamilySpec::Directional(spec).into())
1250}
1251
1252pub fn verify_css_orthogonality(n: usize, h_x: &[Vec<usize>], h_z: &[Vec<usize>]) -> Result<()> {
1253 let h_x = canonical_sparse_rows(n, h_x.to_vec())?;
1254 let h_z = canonical_sparse_rows(n, h_z.to_vec())?;
1255 if h_x.iter().all(|x_row| {
1256 h_z.iter().all(|z_row| {
1257 let mut x_index = 0;
1258 let mut z_index = 0;
1259 let mut parity = false;
1260 while x_index < x_row.len() && z_index < z_row.len() {
1261 match x_row[x_index].cmp(&z_row[z_index]) {
1262 std::cmp::Ordering::Less => x_index += 1,
1263 std::cmp::Ordering::Greater => z_index += 1,
1264 std::cmp::Ordering::Equal => {
1265 parity = !parity;
1266 x_index += 1;
1267 z_index += 1;
1268 }
1269 }
1270 }
1271 !parity
1272 })
1273 }) {
1274 Ok(())
1275 } else {
1276 Err(QecError::InvalidCssOrthogonality)
1277 }
1278}
1279
1280fn construct_lifted_product(
1281 spec: LiftedProductSpec,
1282 provenance_source: &str,
1283) -> Result<CssConstructionResult> {
1284 let group = FiniteGroupSpec::new(
1285 spec.group.order,
1286 spec.group.identity,
1287 spec.group.multiplication_table,
1288 )?;
1289 let left = group_algebra_protograph_matrix(&group, spec.left)?;
1290 let right = group_algebra_protograph_matrix(&group, spec.right)?;
1291 let checks = lifted_product_binary_checks(&group, &left, &right)?;
1292
1293 let mut parameters = BTreeMap::new();
1294 parameters.insert(
1295 "group".to_owned(),
1296 serde_json::json!({
1297 "order": group.order(),
1298 "identity": group.identity(),
1299 "multiplication_table": group.multiplication_table(),
1300 }),
1301 );
1302 parameters.insert(
1303 "left".to_owned(),
1304 serde_json::to_value(group_algebra_protograph_spec(&left))
1305 .expect("serializable lifted-product protograph"),
1306 );
1307 parameters.insert(
1308 "right".to_owned(),
1309 serde_json::to_value(group_algebra_protograph_spec(&right))
1310 .expect("serializable lifted-product protograph"),
1311 );
1312 let known_distances = is_canonical_c3_fixture(&group, &left)
1313 .then_some((3, 3))
1314 .filter(|_| is_canonical_c3_fixture(&group, &right));
1315 construction_result(
1316 "lifted_product",
1317 Some(RequestedFamilyId::LiftedProduct),
1318 parameters,
1319 checks.num_cols,
1320 checks.h_x,
1321 checks.h_z,
1322 "lifted_product",
1323 provenance_source,
1324 known_distances,
1325 )
1326}
1327
1328fn group_algebra_protograph_matrix(
1329 group: &FiniteGroupSpec,
1330 spec: GroupAlgebraProtographSpec,
1331) -> Result<Vec<Vec<GroupAlgebraElement>>> {
1332 spec.rows
1333 .into_iter()
1334 .map(|row| {
1335 row.into_iter()
1336 .map(|entry| GroupAlgebraElement::new(group, entry.support))
1337 .collect()
1338 })
1339 .collect()
1340}
1341
1342fn group_algebra_protograph_spec(
1343 matrix: &[Vec<GroupAlgebraElement>],
1344) -> GroupAlgebraProtographSpec {
1345 GroupAlgebraProtographSpec {
1346 rows: matrix
1347 .iter()
1348 .map(|row| {
1349 row.iter()
1350 .map(|entry| GroupAlgebraElementSpec {
1351 support: entry.support().to_vec(),
1352 })
1353 .collect()
1354 })
1355 .collect(),
1356 }
1357}
1358
1359fn is_canonical_c3_fixture(group: &FiniteGroupSpec, matrix: &[Vec<GroupAlgebraElement>]) -> bool {
1360 group.order() == 3
1361 && group.identity() == 0
1362 && group.multiplication_table() == [vec![0, 1, 2], vec![1, 2, 0], vec![2, 0, 1]]
1363 && matrix_supports(matrix)
1364 == vec![
1365 vec![vec![1, 2], vec![0], vec![]],
1366 vec![vec![], vec![0, 1], vec![1]],
1367 ]
1368}
1369
1370fn matrix_supports(matrix: &[Vec<GroupAlgebraElement>]) -> Vec<Vec<Vec<usize>>> {
1371 matrix
1372 .iter()
1373 .map(|row| {
1374 row.iter()
1375 .map(|element| element.support().to_vec())
1376 .collect()
1377 })
1378 .collect()
1379}
1380
1381fn construct_hypergraph_product(spec: HypergraphProductSpec) -> Result<CssConstructionResult> {
1382 let parameters = normalized_hypergraph_product_parameters(&spec)?;
1383 construct_hypergraph_product_from_parts(
1384 spec,
1385 "hypergraph_product",
1386 None,
1387 parameters,
1388 "hypergraph_product",
1389 "CssConstructionSpec::HypergraphProduct",
1390 )
1391}
1392
1393fn construct_hypergraph_product_from_parts(
1394 spec: HypergraphProductSpec,
1395 construction_id: &'static str,
1396 requested_family_id: Option<RequestedFamilyId>,
1397 normalized_parameters: BTreeMap<String, Value>,
1398 adapter: &'static str,
1399 source: &'static str,
1400) -> Result<CssConstructionResult> {
1401 let HypergraphProductSpec {
1402 left: left_spec,
1403 right: right_spec,
1404 } = spec;
1405 let left = classical_check_matrix(left_spec)?;
1406 let right = classical_check_matrix(right_spec)?;
1407
1408 let left_identity_rows = SparseGf2Matrix::identity(left.num_rows())?;
1409 let left_identity_cols = SparseGf2Matrix::identity(left.num_cols())?;
1410 let right_identity_rows = SparseGf2Matrix::identity(right.num_rows())?;
1411 let right_identity_cols = SparseGf2Matrix::identity(right.num_cols())?;
1412 let left_transpose = left.transpose()?;
1413 let right_transpose = right.transpose()?;
1414
1415 let h_x = left
1416 .kron(&right_identity_cols)?
1417 .hconcat(&left_identity_rows.kron(&right_transpose)?)?;
1418 let h_z = left_identity_cols
1419 .kron(&right)?
1420 .hconcat(&left_transpose.kron(&right_identity_rows)?)?;
1421 debug_assert_eq!(h_x.num_cols(), h_z.num_cols());
1422
1423 construction_result(
1424 construction_id,
1425 requested_family_id,
1426 normalized_parameters,
1427 h_x.num_cols(),
1428 h_x.rows().to_vec(),
1429 h_z.rows().to_vec(),
1430 adapter,
1431 source,
1432 None,
1433 )
1434}
1435
1436fn normalized_hypergraph_product_parameters(
1437 spec: &HypergraphProductSpec,
1438) -> Result<BTreeMap<String, Value>> {
1439 let left = classical_check_matrix(spec.left.clone())?;
1440 let right = classical_check_matrix(spec.right.clone())?;
1441 let mut parameters = BTreeMap::new();
1442 parameters.insert(
1443 "left".to_owned(),
1444 serde_json::to_value(CssClassicalCheckSpec {
1445 num_cols: left.num_cols(),
1446 rows: left.rows().to_vec(),
1447 })
1448 .expect("serializable spec"),
1449 );
1450 parameters.insert(
1451 "right".to_owned(),
1452 serde_json::to_value(CssClassicalCheckSpec {
1453 num_cols: right.num_cols(),
1454 rows: right.rows().to_vec(),
1455 })
1456 .expect("serializable spec"),
1457 );
1458 Ok(parameters)
1459}
1460
1461fn classical_check_matrix(spec: CssClassicalCheckSpec) -> Result<SparseGf2Matrix> {
1462 for (row_index, row) in spec.rows.iter().enumerate() {
1463 let mut supports = std::collections::BTreeSet::new();
1464 for &support in row {
1465 if !supports.insert(support) {
1466 return Err(QecError::DuplicateSparseRowSupport {
1467 row: row_index,
1468 support,
1469 });
1470 }
1471 }
1472 }
1473 SparseGf2Matrix::new(spec.rows.len(), spec.num_cols, spec.rows)
1474}
1475
1476fn construction_result(
1477 construction_id: impl Into<String>,
1478 requested_family_id: Option<RequestedFamilyId>,
1479 normalized_parameters: BTreeMap<String, Value>,
1480 n: usize,
1481 h_x: Vec<Vec<usize>>,
1482 h_z: Vec<Vec<usize>>,
1483 adapter: impl Into<String>,
1484 source: impl Into<String>,
1485 known_distances: Option<(usize, usize)>,
1486) -> Result<CssConstructionResult> {
1487 let construction_id = construction_id.into();
1488 let adapter = adapter.into();
1489 let source = source.into();
1490 let normalized_input_digest = normalized_input_digest(
1491 &construction_id,
1492 requested_family_id,
1493 &normalized_parameters,
1494 );
1495 let h_x = canonical_sparse_rows(n, h_x)?;
1496 let h_z = canonical_sparse_rows(n, h_z)?;
1497 verify_css_orthogonality(n, &h_x, &h_z)?;
1498 let rank_x = try_binary_rank(&dense_rows(n, &h_x))?;
1499 let rank_z = try_binary_rank(&dense_rows(n, &h_z))?;
1500 let (d_x, d_z) = known_distances
1501 .map(|(d_x, d_z)| (Some(d_x), Some(d_z)))
1502 .unwrap_or((None, None));
1503 let stats = CssCodeStats {
1504 n,
1505 m_x: h_x.len(),
1506 m_z: h_z.len(),
1507 rank_x,
1508 rank_z,
1509 k: n.saturating_sub(rank_x + rank_z),
1510 d_x,
1511 d_z,
1512 };
1513 Ok(CssConstructionResult {
1514 schema_version: CSS_CONSTRUCTION_SCHEMA_VERSION,
1515 construction_id,
1516 requested_family_id,
1517 normalized_parameters,
1518 checks: CssChecks { h_x, h_z },
1519 stats,
1520 provenance: CssConstructionProvenance {
1521 adapter,
1522 source,
1523 normalized_input_digest,
1524 },
1525 })
1526}
1527
1528fn normalized_input_digest(
1529 construction_id: &str,
1530 requested_family_id: Option<RequestedFamilyId>,
1531 normalized_parameters: &BTreeMap<String, Value>,
1532) -> String {
1533 let payload = serde_json::json!({
1534 "schema_version": CSS_CONSTRUCTION_SCHEMA_VERSION,
1535 "construction_id": construction_id,
1536 "requested_family_id": requested_family_id,
1537 "normalized_parameters": normalized_parameters,
1538 });
1539 let json = serde_json::to_vec(&payload).expect("normalized construction input is serializable");
1540 format!("sha256:{}", lower_hex(&Sha256::digest(json)))
1541}
1542
1543fn lower_hex(bytes: impl AsRef<[u8]>) -> String {
1544 const HEX: &[u8; 16] = b"0123456789abcdef";
1545 let bytes = bytes.as_ref();
1546 let mut output = String::with_capacity(bytes.len() * 2);
1547 for &byte in bytes {
1548 output.push(HEX[(byte >> 4) as usize] as char);
1549 output.push(HEX[(byte & 0x0f) as usize] as char);
1550 }
1551 output
1552}
1553
1554fn canonical_sparse_rows(n: usize, mut rows: Vec<Vec<usize>>) -> Result<Vec<Vec<usize>>> {
1555 SparseRowsMatrix::new(n, rows.clone())?;
1556 for row in &mut rows {
1557 row.sort_unstable();
1558 }
1559 Ok(rows)
1560}
1561
1562fn dense_rows(n: usize, rows: &[Vec<usize>]) -> Vec<Vec<u8>> {
1563 rows.iter()
1564 .map(|row| {
1565 let mut dense = vec![0; n];
1566 for &column in row {
1567 dense[column] = 1;
1568 }
1569 dense
1570 })
1571 .collect()
1572}
1573
1574fn surface_construction_from_json(
1575 object: &Map<String, Value>,
1576 construction: &str,
1577) -> Result<CssConstructionSpec> {
1578 let has_legacy_distance = object.contains_key("distance");
1579 let has_layout_aware_fields = object.contains_key("layout")
1580 || object.contains_key("row_distance")
1581 || object.contains_key("column_distance");
1582 if has_legacy_distance && has_layout_aware_fields {
1583 return Err(QecError::InvalidCssConstruction {
1584 construction: construction.to_owned(),
1585 reason: "conflicting legacy distance and layout-aware surface parameters".to_owned(),
1586 });
1587 }
1588 if has_legacy_distance {
1589 return Ok(CssFamilySpec::Surface(SurfaceFamilySpec {
1590 distance: required_usize(object, "distance", construction)?,
1591 })
1592 .into());
1593 }
1594 if !has_layout_aware_fields {
1595 return Err(QecError::InvalidCssConstruction {
1596 construction: construction.to_owned(),
1597 reason: "missing or invalid distance".to_owned(),
1598 });
1599 }
1600
1601 let layout = match required_string(object, "layout")? {
1602 "rotated" => SurfaceLayout::Rotated,
1603 "unrotated" => SurfaceLayout::Unrotated,
1604 value => {
1605 return Err(QecError::InvalidCssConstruction {
1606 construction: construction.to_owned(),
1607 reason: format!("unknown surface layout {value}"),
1608 });
1609 }
1610 };
1611 Ok(SurfaceSpec {
1612 layout,
1613 row_distance: required_usize(object, "row_distance", construction)?,
1614 column_distance: required_usize(object, "column_distance", construction)?,
1615 }
1616 .into())
1617}
1618
1619fn required_string<'a>(object: &'a Map<String, Value>, field: &str) -> Result<&'a str> {
1620 object
1621 .get(field)
1622 .and_then(Value::as_str)
1623 .ok_or_else(|| QecError::InvalidCssConstructionJson(format!("missing or invalid {field}")))
1624}
1625
1626fn optional_string<'a>(object: &'a Map<String, Value>, field: &str) -> Result<Option<&'a str>> {
1627 match object.get(field) {
1628 None => Ok(None),
1629 Some(Value::String(value)) => Ok(Some(value)),
1630 Some(_) => Err(QecError::InvalidCssConstructionJson(format!(
1631 "missing or invalid {field}"
1632 ))),
1633 }
1634}
1635
1636fn required_u64(object: &Map<String, Value>, field: &str) -> Result<u64> {
1637 object
1638 .get(field)
1639 .and_then(Value::as_u64)
1640 .ok_or_else(|| QecError::InvalidCssConstructionJson(format!("missing or invalid {field}")))
1641}
1642
1643fn required_usize(object: &Map<String, Value>, field: &str, construction: &str) -> Result<usize> {
1644 let value = object.get(field).and_then(Value::as_u64).ok_or_else(|| {
1645 QecError::InvalidCssConstruction {
1646 construction: construction.to_owned(),
1647 reason: format!("missing or invalid {field}"),
1648 }
1649 })?;
1650 usize::try_from(value).map_err(|_| QecError::InvalidCssConstruction {
1651 construction: construction.to_owned(),
1652 reason: format!("{field} is outside usize range"),
1653 })
1654}
1655
1656fn required_usize_array(
1657 object: &Map<String, Value>,
1658 field: &str,
1659 construction: &str,
1660) -> Result<Vec<usize>> {
1661 let values = object.get(field).and_then(Value::as_array).ok_or_else(|| {
1662 QecError::InvalidCssConstruction {
1663 construction: construction.to_owned(),
1664 reason: format!("missing or invalid {field}"),
1665 }
1666 })?;
1667 values
1668 .iter()
1669 .enumerate()
1670 .map(|(index, value)| {
1671 let value = value
1672 .as_u64()
1673 .ok_or_else(|| QecError::InvalidCssConstruction {
1674 construction: construction.to_owned(),
1675 reason: format!("{field}[{index}] must be a nonnegative integer"),
1676 })?;
1677 json_u64_to_usize_array_entry(value, field, index, construction)
1678 })
1679 .collect()
1680}
1681
1682#[cfg(target_pointer_width = "64")]
1683fn json_u64_to_usize_array_entry(
1684 value: u64,
1685 _field: &str,
1686 _index: usize,
1687 _construction: &str,
1688) -> Result<usize> {
1689 Ok(value as usize)
1690}
1691
1692#[cfg(not(target_pointer_width = "64"))]
1693fn json_u64_to_usize_array_entry(
1694 value: u64,
1695 field: &str,
1696 index: usize,
1697 construction: &str,
1698) -> Result<usize> {
1699 usize::try_from(value).map_err(|_| QecError::InvalidCssConstruction {
1700 construction: construction.to_owned(),
1701 reason: format!("{field}[{index}] is outside usize range"),
1702 })
1703}