qec_code/
lifted_product.rs

1use crate::error::{QecError, Result};
2use crate::finite_group::{
3    FiniteGroupSpec, GroupAlgebraElement, left_regular_lift, right_regular_lift,
4};
5
6/// Maximum number of group-algebra cells in either ring-level lifted-product
7/// check matrix. This bounds CLI input amplification before dense ring rows are
8/// materialized.
9pub const MAX_LIFTED_PRODUCT_RING_CELLS: usize = 1_000_000;
10
11/// Maximum dense binary cells in either lifted CSS check matrix.
12///
13/// The common CSS construction contract verifies orthogonality and ranks after
14/// construction. Those paths use pairwise sparse row intersections and dense
15/// rank matrices, so the lifted-product constructor must bound the post-lift
16/// matrices before materializing them.
17pub const MAX_LIFTED_PRODUCT_BINARY_CELLS: usize = 10_000_000;
18
19/// Maximum row pairs considered by the common CSS orthogonality check.
20pub const MAX_LIFTED_PRODUCT_ORTHOGONALITY_ROW_PAIRS: usize = 10_000_000;
21
22/// Ring-level lifted-product matrix shape before regular binary lifting.
23#[derive(Debug, Clone, Copy, PartialEq, Eq)]
24pub struct LiftedProductRingShape {
25    pub h_x_rows: usize,
26    pub h_z_rows: usize,
27    pub num_cols: usize,
28}
29
30/// Ring-level lifted-product checks over the group algebra.
31///
32/// `h_x` has `shape.h_x_rows` rows and `shape.num_cols` columns; `h_z` has
33/// `shape.h_z_rows` rows and the same columns. Transposed protograph blocks
34/// use group inversion on every support element.
35#[derive(Debug, Clone, PartialEq, Eq)]
36pub struct LiftedProductRingChecks {
37    pub shape: LiftedProductRingShape,
38    pub h_x: Vec<Vec<GroupAlgebraElement>>,
39    pub h_z: Vec<Vec<GroupAlgebraElement>>,
40}
41
42/// Binary CSS checks after applying regular group lifts.
43#[derive(Debug, Clone, PartialEq, Eq)]
44pub struct LiftedProductBinaryChecks {
45    pub num_cols: usize,
46    pub h_x: Vec<Vec<usize>>,
47    pub h_z: Vec<Vec<usize>>,
48}
49
50/// Return the ring-level shape, rejecting overflow and oversized dense ring
51/// materializations.
52pub fn checked_lifted_product_ring_shape(
53    left_rows: usize,
54    left_cols: usize,
55    right_rows: usize,
56    right_cols: usize,
57) -> Result<LiftedProductRingShape> {
58    let h_x_rows = left_rows.checked_mul(right_cols).ok_or(ring_overflow())?;
59    let h_z_rows = left_cols.checked_mul(right_rows).ok_or(ring_overflow())?;
60    let left_block_cols = left_cols.checked_mul(right_cols).ok_or(ring_overflow())?;
61    let right_block_cols = left_rows.checked_mul(right_rows).ok_or(ring_overflow())?;
62    let num_cols = left_block_cols
63        .checked_add(right_block_cols)
64        .ok_or(ring_overflow())?;
65    check_ring_cell_limit(h_x_rows, num_cols)?;
66    check_ring_cell_limit(h_z_rows, num_cols)?;
67    Ok(LiftedProductRingShape {
68        h_x_rows,
69        h_z_rows,
70        num_cols,
71    })
72}
73
74/// Return the ring-level shape and also preflight the post-lift binary shape.
75pub fn checked_lifted_product_binary_shape(
76    group: &FiniteGroupSpec,
77    left_rows: usize,
78    left_cols: usize,
79    right_rows: usize,
80    right_cols: usize,
81) -> Result<LiftedProductRingShape> {
82    let shape = checked_lifted_product_ring_shape(left_rows, left_cols, right_rows, right_cols)?;
83    let binary_h_x_rows = checked_binary_dimension(shape.h_x_rows, group.order())?;
84    let binary_h_z_rows = checked_binary_dimension(shape.h_z_rows, group.order())?;
85    let binary_cols = checked_binary_dimension(shape.num_cols, group.order())?;
86    check_binary_cell_limit("H_X", binary_h_x_rows, binary_cols)?;
87    check_binary_cell_limit("H_Z", binary_h_z_rows, binary_cols)?;
88    check_binary_row_pair_limit(binary_h_x_rows, binary_h_z_rows)?;
89    Ok(shape)
90}
91
92/// Build ring-level lifted-product checks.
93pub fn lifted_product_ring_checks(
94    group: &FiniteGroupSpec,
95    left: &[Vec<GroupAlgebraElement>],
96    right: &[Vec<GroupAlgebraElement>],
97) -> Result<LiftedProductRingChecks> {
98    let (left_rows, left_cols) = group_algebra_matrix_shape(left)?;
99    let (right_rows, right_cols) = group_algebra_matrix_shape(right)?;
100    validate_group_orders(group, left)?;
101    validate_group_orders(group, right)?;
102    let shape = checked_lifted_product_ring_shape(left_rows, left_cols, right_rows, right_cols)?;
103
104    let h_x = hconcat(
105        &matrix_kron_identity(group, left, right_cols)?,
106        &identity_kron_matrix(group, left_rows, &inverse_transpose(group, right)?)?,
107    )?;
108    let h_z = hconcat(
109        &identity_kron_matrix(group, left_cols, right)?,
110        &matrix_kron_identity(group, &inverse_transpose(group, left)?, right_rows)?,
111    )?;
112    debug_assert_eq!(h_x.len(), shape.h_x_rows);
113    debug_assert_eq!(h_z.len(), shape.h_z_rows);
114    debug_assert!(h_x.iter().all(|row| row.len() == shape.num_cols));
115    debug_assert!(h_z.iter().all(|row| row.len() == shape.num_cols));
116    Ok(LiftedProductRingChecks { shape, h_x, h_z })
117}
118
119/// Build binary CSS checks using commuting left/right regular actions.
120///
121/// Ring-level rows are ordered as the Kronecker constructors emit them: for
122/// `A kron I_q`, rows are `(a_row, q_index)` and columns are
123/// `(a_col, q_index)` with the left index major; for `I_p kron B`, rows are
124/// `(p_index, b_row)` and columns are `(p_index, b_col)`. The binary lift then
125/// expands every ring column into a contiguous `|G|` basis block.
126///
127/// For support element `g` and basis row `x`, the left action places a 1 at
128/// `g^-1 x`, while the right action places a 1 at `x g`. The binary CSS check
129/// order is:
130///
131/// - `H_X = [left_lift(A kron I), right_lift(I kron B^T)]`
132/// - `H_Z = [right_lift(I kron inverse_entries(B)), left_lift(inverse_transpose(A) kron I)]`
133///
134/// This fixes the left qubit block before the right qubit block and makes the
135/// extra involutions explicit for callers comparing ring and binary outputs.
136pub fn lifted_product_binary_checks(
137    group: &FiniteGroupSpec,
138    left: &[Vec<GroupAlgebraElement>],
139    right: &[Vec<GroupAlgebraElement>],
140) -> Result<LiftedProductBinaryChecks> {
141    let (left_rows, left_cols) = group_algebra_matrix_shape(left)?;
142    let (right_rows, right_cols) = group_algebra_matrix_shape(right)?;
143    validate_group_orders(group, left)?;
144    validate_group_orders(group, right)?;
145    let shape =
146        checked_lifted_product_binary_shape(group, left_rows, left_cols, right_rows, right_cols)?;
147
148    let h_x_left = matrix_kron_identity(group, left, right_cols)?;
149    let h_x_right = identity_kron_matrix(group, left_rows, &transpose_without_inversion(right)?)?;
150    let h_z_left = identity_kron_matrix(group, left_cols, &invert_entries(group, right)?)?;
151    let h_z_right = matrix_kron_identity(group, &inverse_transpose(group, left)?, right_rows)?;
152
153    let h_x =
154        left_regular_lift(group, &h_x_left)?.hconcat(&right_regular_lift(group, &h_x_right)?)?;
155    let h_z =
156        right_regular_lift(group, &h_z_left)?.hconcat(&left_regular_lift(group, &h_z_right)?)?;
157    debug_assert_eq!(h_x.num_cols(), h_z.num_cols());
158    debug_assert_eq!(h_x.num_rows(), shape.h_x_rows * group.order());
159    debug_assert_eq!(h_z.num_rows(), shape.h_z_rows * group.order());
160    Ok(LiftedProductBinaryChecks {
161        num_cols: h_x.num_cols(),
162        h_x: h_x.rows().to_vec(),
163        h_z: h_z.rows().to_vec(),
164    })
165}
166
167fn ring_overflow() -> QecError {
168    QecError::GroupAlgebraDimensionOverflow {
169        operation: "lifted product ring shape",
170    }
171}
172
173fn binary_overflow() -> QecError {
174    QecError::GroupAlgebraDimensionOverflow {
175        operation: "lifted product binary shape",
176    }
177}
178
179fn checked_binary_dimension(value: usize, group_order: usize) -> Result<usize> {
180    value.checked_mul(group_order).ok_or(binary_overflow())
181}
182
183fn check_ring_cell_limit(rows: usize, num_cols: usize) -> Result<()> {
184    let cell_count = rows.checked_mul(num_cols).ok_or(ring_overflow())?;
185    if cell_count > MAX_LIFTED_PRODUCT_RING_CELLS {
186        return Err(QecError::InvalidCssConstruction {
187            construction: "lifted_product".to_owned(),
188            reason: format!(
189                "ring cell count {cell_count} exceeds maximum supported {MAX_LIFTED_PRODUCT_RING_CELLS}"
190            ),
191        });
192    }
193    Ok(())
194}
195
196fn check_binary_cell_limit(matrix_name: &str, rows: usize, num_cols: usize) -> Result<()> {
197    let cell_count = rows.checked_mul(num_cols).ok_or(binary_overflow())?;
198    if cell_count > MAX_LIFTED_PRODUCT_BINARY_CELLS {
199        return Err(QecError::InvalidCssConstruction {
200            construction: "lifted_product".to_owned(),
201            reason: format!(
202                "binary {matrix_name} cell count {cell_count} exceeds maximum supported {MAX_LIFTED_PRODUCT_BINARY_CELLS}"
203            ),
204        });
205    }
206    Ok(())
207}
208
209fn check_binary_row_pair_limit(h_x_rows: usize, h_z_rows: usize) -> Result<()> {
210    let row_pairs = h_x_rows.checked_mul(h_z_rows).ok_or(binary_overflow())?;
211    if row_pairs > MAX_LIFTED_PRODUCT_ORTHOGONALITY_ROW_PAIRS {
212        return Err(QecError::InvalidCssConstruction {
213            construction: "lifted_product".to_owned(),
214            reason: format!(
215                "binary orthogonality row-pair count {row_pairs} exceeds maximum supported {MAX_LIFTED_PRODUCT_ORTHOGONALITY_ROW_PAIRS}"
216            ),
217        });
218    }
219    Ok(())
220}
221
222fn group_algebra_matrix_shape(matrix: &[Vec<GroupAlgebraElement>]) -> Result<(usize, usize)> {
223    let Some(first_row) = matrix.first() else {
224        return Err(invalid_protograph("must contain at least one row"));
225    };
226    if first_row.is_empty() {
227        return Err(invalid_protograph("must contain at least one column"));
228    }
229    for row in matrix {
230        if row.len() != first_row.len() {
231            return Err(QecError::GroupAlgebraMatrixRowWidthMismatch {
232                expected: first_row.len(),
233                actual: row.len(),
234            });
235        }
236    }
237    Ok((matrix.len(), first_row.len()))
238}
239
240fn validate_group_orders(
241    group: &FiniteGroupSpec,
242    matrix: &[Vec<GroupAlgebraElement>],
243) -> Result<()> {
244    for row in matrix {
245        for element in row {
246            if element.group_order() != group.order() {
247                return Err(QecError::GroupAlgebraOrderMismatch {
248                    expected: group.order(),
249                    actual: element.group_order(),
250                });
251            }
252        }
253    }
254    Ok(())
255}
256
257fn invalid_protograph(reason: &str) -> QecError {
258    QecError::InvalidCssConstruction {
259        construction: "lifted_product".to_owned(),
260        reason: reason.to_owned(),
261    }
262}
263
264fn inverse_transpose(
265    group: &FiniteGroupSpec,
266    matrix: &[Vec<GroupAlgebraElement>],
267) -> Result<Vec<Vec<GroupAlgebraElement>>> {
268    let rows = matrix.len();
269    let cols = matrix[0].len();
270    let mut output = Vec::with_capacity(cols);
271    for col in 0..cols {
272        let mut row = Vec::with_capacity(rows);
273        for source_row in matrix {
274            let support = source_row[col]
275                .support()
276                .iter()
277                .map(|&element| group.inverse(element))
278                .collect::<Result<Vec<_>>>()?;
279            row.push(GroupAlgebraElement::new(group, support)?);
280        }
281        output.push(row);
282    }
283    Ok(output)
284}
285
286fn transpose_without_inversion(
287    matrix: &[Vec<GroupAlgebraElement>],
288) -> Result<Vec<Vec<GroupAlgebraElement>>> {
289    let rows = matrix.len();
290    let cols = matrix[0].len();
291    let mut output = Vec::with_capacity(cols);
292    for col in 0..cols {
293        let mut row = Vec::with_capacity(rows);
294        for source_row in matrix {
295            row.push(source_row[col].clone());
296        }
297        output.push(row);
298    }
299    Ok(output)
300}
301
302fn invert_entries(
303    group: &FiniteGroupSpec,
304    matrix: &[Vec<GroupAlgebraElement>],
305) -> Result<Vec<Vec<GroupAlgebraElement>>> {
306    matrix
307        .iter()
308        .map(|row| {
309            row.iter()
310                .map(|entry| {
311                    let support = entry
312                        .support()
313                        .iter()
314                        .map(|&element| group.inverse(element))
315                        .collect::<Result<Vec<_>>>()?;
316                    GroupAlgebraElement::new(group, support)
317                })
318                .collect()
319        })
320        .collect()
321}
322
323fn matrix_kron_identity(
324    group: &FiniteGroupSpec,
325    matrix: &[Vec<GroupAlgebraElement>],
326    identity_size: usize,
327) -> Result<Vec<Vec<GroupAlgebraElement>>> {
328    let zero = GroupAlgebraElement::new(group, Vec::new())?;
329    let mut output = Vec::with_capacity(matrix.len() * identity_size);
330    for source_row in matrix {
331        for diagonal in 0..identity_size {
332            let mut row = Vec::with_capacity(source_row.len() * identity_size);
333            for element in source_row {
334                for column in 0..identity_size {
335                    row.push(if column == diagonal {
336                        element.clone()
337                    } else {
338                        zero.clone()
339                    });
340                }
341            }
342            output.push(row);
343        }
344    }
345    Ok(output)
346}
347
348fn identity_kron_matrix(
349    group: &FiniteGroupSpec,
350    identity_size: usize,
351    matrix: &[Vec<GroupAlgebraElement>],
352) -> Result<Vec<Vec<GroupAlgebraElement>>> {
353    let zero = GroupAlgebraElement::new(group, Vec::new())?;
354    let matrix_cols = matrix[0].len();
355    let mut output = Vec::with_capacity(identity_size * matrix.len());
356    for diagonal in 0..identity_size {
357        for source_row in matrix {
358            let mut row = Vec::with_capacity(identity_size * matrix_cols);
359            for block in 0..identity_size {
360                if block == diagonal {
361                    row.extend(source_row.iter().cloned());
362                } else {
363                    row.extend(std::iter::repeat_n(zero.clone(), matrix_cols));
364                }
365            }
366            output.push(row);
367        }
368    }
369    Ok(output)
370}
371
372fn hconcat(
373    left: &[Vec<GroupAlgebraElement>],
374    right: &[Vec<GroupAlgebraElement>],
375) -> Result<Vec<Vec<GroupAlgebraElement>>> {
376    if left.len() != right.len() {
377        return Err(invalid_protograph("internal lifted-product row mismatch"));
378    }
379    Ok(left
380        .iter()
381        .zip(right)
382        .map(|(left_row, right_row)| {
383            let mut row = left_row.clone();
384            row.extend(right_row.iter().cloned());
385            row
386        })
387        .collect())
388}
qec_code/lifted_product.rs

qec_code/
lifted_product.rs
