Skip to main content

qec_code/
phased_pauli.rs

1//! Exact Pauli phases, signed stabilizers, and caller-supplied logical bases.
2//!
3//! An operator is `i^phase X^x Z^z`, with qubits in the same order as [`Pauli`].
4//! Thus `Y = i XZ`: support `(x, z) = (1, 1)` with phase [`Phase::PlusI`].
5//! The support-only [`Pauli`] remains unchanged; adding or discarding a phase
6//! always requires an explicit method call.
7
8use crate::Pauli;
9use thiserror::Error;
10
11/// The scalar multiplying an ordered `X^x Z^z` Pauli product.
12#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
13#[repr(u8)]
14pub enum Phase {
15    PlusOne = 0,
16    PlusI = 1,
17    MinusOne = 2,
18    MinusI = 3,
19}
20
21impl Phase {
22    pub fn exponent(self) -> u8 {
23        self as u8
24    }
25
26    /// Convert an exponent of `i`, reduced modulo four.
27    pub fn from_exponent(exponent: u8) -> Self {
28        match exponent % 4 {
29            0 => Self::PlusOne,
30            1 => Self::PlusI,
31            2 => Self::MinusOne,
32            _ => Self::MinusI,
33        }
34    }
35}
36
37/// A phase-aware Pauli operator. Equality includes the scalar phase.
38#[derive(Debug, Clone, PartialEq, Eq)]
39pub struct PhasedPauli {
40    support: Pauli,
41    phase: Phase,
42}
43
44impl PhasedPauli {
45    /// Attach an explicit phase to a support-only Pauli.
46    pub fn new(support: Pauli, phase: Phase) -> Self {
47        Self { support, phase }
48    }
49
50    pub fn identity(n: usize) -> Self {
51        Self::new(
52            Pauli::from_xz_bits(vec![0; n], vec![0; n]).expect("zero bits are valid"),
53            Phase::PlusOne,
54        )
55    }
56
57    pub fn support(&self) -> &Pauli {
58        &self.support
59    }
60
61    pub fn phase(&self) -> Phase {
62        self.phase
63    }
64
65    pub fn n(&self) -> usize {
66        self.support.n()
67    }
68
69    /// Return the X/Z support, explicitly discarding the scalar phase.
70    pub fn into_support(self) -> Pauli {
71        self.support
72    }
73
74    /// Exact ordered product, including the sign from moving the right X past the left Z.
75    pub fn multiply(&self, rhs: &Self) -> Result<Self, PhaseAlgebraError> {
76        if self.n() != rhs.n() {
77            return Err(PhaseAlgebraError::WidthMismatch {
78                expected: self.n(),
79                actual: rhs.n(),
80            });
81        }
82        let crossing_parity = self
83            .support
84            .z_bits()
85            .iter()
86            .zip(rhs.support.x_bits())
87            .fold(0u8, |parity, (&z, &x)| parity ^ (z & x));
88        let phase = Phase::from_exponent(
89            self.phase.exponent() + rhs.phase.exponent() + 2 * crossing_parity,
90        );
91        let x = self
92            .support
93            .x_bits()
94            .iter()
95            .zip(rhs.support.x_bits())
96            .map(|(&left, &right)| left ^ right)
97            .collect();
98        let z = self
99            .support
100            .z_bits()
101            .iter()
102            .zip(rhs.support.z_bits())
103            .map(|(&left, &right)| left ^ right)
104            .collect();
105        Ok(Self::new(
106            Pauli::from_xz_bits(x, z).expect("XOR of valid bits is valid"),
107            phase,
108        ))
109    }
110
111    /// The adjoint is also the inverse, since every Pauli is unitary.
112    pub fn adjoint(&self) -> Self {
113        let xz_parity = self
114            .support
115            .x_bits()
116            .iter()
117            .zip(self.support.z_bits())
118            .fold(0u8, |parity, (&x, &z)| parity ^ (x & z));
119        let exponent = (4 - self.phase.exponent() + 2 * xz_parity) % 4;
120        Self::new(self.support.clone(), Phase::from_exponent(exponent))
121    }
122
123    pub fn inverse(&self) -> Self {
124        self.adjoint()
125    }
126
127    pub fn is_hermitian(&self) -> bool {
128        self == &self.adjoint()
129    }
130
131    pub fn commutes_with(&self, other: &Self) -> Result<bool, PhaseAlgebraError> {
132        if self.n() != other.n() {
133            return Err(PhaseAlgebraError::WidthMismatch {
134                expected: self.n(),
135                actual: other.n(),
136            });
137        }
138        Ok(self.support.commutes_with(&other.support))
139    }
140}
141
142/// Validation and query errors for the phase-aware API.
143#[derive(Debug, Clone, PartialEq, Eq, Error)]
144pub enum PhaseAlgebraError {
145    #[error("Pauli width mismatch: expected {expected}, got {actual}")]
146    WidthMismatch { expected: usize, actual: usize },
147    #[error("stabilizer generator {index} has width {actual}, expected {expected}")]
148    GeneratorWidth {
149        index: usize,
150        expected: usize,
151        actual: usize,
152    },
153    #[error("stabilizer generator {index} is not Hermitian")]
154    NonHermitianGenerator { index: usize },
155    #[error("stabilizer generators {left} and {right} do not commute")]
156    NonCommutingGenerators { left: usize, right: usize },
157    #[error("stabilizer generator {index} contradicts the preceding generators (-I)")]
158    ContradictoryGenerator { index: usize },
159    #[error("expected {expected} logical X/Z pairs, got {x_count} X and {z_count} Z operators")]
160    LogicalCount {
161        expected: usize,
162        x_count: usize,
163        z_count: usize,
164    },
165    #[error("logical {kind}[{index}] has width {actual}, expected {expected}")]
166    LogicalWidth {
167        kind: &'static str,
168        index: usize,
169        expected: usize,
170        actual: usize,
171    },
172    #[error("logical {kind}[{index}] is not Hermitian")]
173    NonHermitianLogical { kind: &'static str, index: usize },
174    #[error("logical {kind}[{index}] does not commute with stabilizer generator {generator}")]
175    NonCentralizingLogical {
176        kind: &'static str,
177        index: usize,
178        generator: usize,
179    },
180    #[error(
181        "logical {left_kind}[{left_index}] and {right_kind}[{right_index}] have the wrong commutation relation: expected anticommutation = {expected_anticommutation}"
182    )]
183    LogicalCommutation {
184        left_kind: &'static str,
185        left_index: usize,
186        right_kind: &'static str,
187        right_index: usize,
188        expected_anticommutation: bool,
189    },
190    #[error("generator witness index {index} is out of range for {count} generators")]
191    WitnessIndex { index: usize, count: usize },
192}
193
194/// Original generator indices, in the order supplied to [`SignedStabilizerGroup::new`].
195/// Each index occurs at most once and indices are sorted ascending.
196#[derive(Debug, Clone, PartialEq, Eq)]
197pub struct GeneratorProductWitness {
198    generator_indices: Vec<usize>,
199}
200
201impl GeneratorProductWitness {
202    pub fn generator_indices(&self) -> &[usize] {
203        &self.generator_indices
204    }
205}
206
207#[derive(Debug, Clone)]
208struct BasisRow {
209    pivot: usize,
210    operator: PhasedPauli,
211    witness: Vec<usize>,
212}
213
214/// A validated abelian stabilizer group, including generator signs.
215///
216/// The original generators, including consistent redundant ones, retain their
217/// input order. A reduced basis is stored for repeated membership queries.
218#[derive(Debug, Clone)]
219pub struct SignedStabilizerGroup {
220    n: usize,
221    generators: Vec<PhasedPauli>,
222    basis: Vec<BasisRow>,
223}
224
225impl SignedStabilizerGroup {
226    pub fn new(n: usize, generators: Vec<PhasedPauli>) -> Result<Self, PhaseAlgebraError> {
227        let mut basis: Vec<BasisRow> = Vec::new();
228        for (index, generator) in generators.iter().enumerate() {
229            if generator.n() != n {
230                return Err(PhaseAlgebraError::GeneratorWidth {
231                    index,
232                    expected: n,
233                    actual: generator.n(),
234                });
235            }
236            if !generator.is_hermitian() {
237                return Err(PhaseAlgebraError::NonHermitianGenerator { index });
238            }
239            for (left, preceding) in generators[..index].iter().enumerate() {
240                if !generator.commutes_with(preceding)? {
241                    return Err(PhaseAlgebraError::NonCommutingGenerators { left, right: index });
242                }
243            }
244
245            let mut residual = generator.clone();
246            let mut witness = vec![index];
247            for row in &basis {
248                if bit_at(&residual, row.pivot) != 0 {
249                    residual = residual.multiply(&row.operator)?;
250                    witness = symmetric_difference(&witness, &row.witness);
251                }
252            }
253            if let Some(pivot) = first_set_bit(&residual) {
254                let position = basis.partition_point(|row| row.pivot < pivot);
255                basis.insert(
256                    position,
257                    BasisRow {
258                        pivot,
259                        operator: residual,
260                        witness,
261                    },
262                );
263            } else if residual.phase() != Phase::PlusOne {
264                return Err(PhaseAlgebraError::ContradictoryGenerator { index });
265            }
266        }
267        Ok(Self {
268            n,
269            generators,
270            basis,
271        })
272    }
273
274    pub fn n(&self) -> usize {
275        self.n
276    }
277
278    pub fn rank(&self) -> usize {
279        self.basis.len()
280    }
281
282    pub fn num_logical_qubits(&self) -> usize {
283        self.n - self.rank()
284    }
285
286    pub fn generators(&self) -> &[PhasedPauli] {
287        &self.generators
288    }
289
290    /// Return a recomputable witness for exact signed membership.
291    pub fn contains_with_witness(
292        &self,
293        target: &PhasedPauli,
294    ) -> Result<Option<GeneratorProductWitness>, PhaseAlgebraError> {
295        if target.n() != self.n {
296            return Err(PhaseAlgebraError::WidthMismatch {
297                expected: self.n,
298                actual: target.n(),
299            });
300        }
301        let mut residual = target.clone();
302        let mut witness = Vec::new();
303        for row in &self.basis {
304            if bit_at(&residual, row.pivot) != 0 {
305                residual = residual.multiply(&row.operator)?;
306                witness = symmetric_difference(&witness, &row.witness);
307            }
308        }
309        if first_set_bit(&residual).is_none() && residual.phase() == Phase::PlusOne {
310            Ok(Some(GeneratorProductWitness {
311                generator_indices: witness,
312            }))
313        } else {
314            Ok(None)
315        }
316    }
317
318    /// Multiply original generators in the given order; useful to verify a witness.
319    pub fn product_from_indices(
320        &self,
321        indices: &[usize],
322    ) -> Result<PhasedPauli, PhaseAlgebraError> {
323        let mut product = PhasedPauli::identity(self.n);
324        for &index in indices {
325            let generator = self
326                .generators
327                .get(index)
328                .ok_or(PhaseAlgebraError::WitnessIndex {
329                    index,
330                    count: self.generators.len(),
331                })?;
332            product = product.multiply(generator)?;
333        }
334        Ok(product)
335    }
336
337    /// Validate and retain the exact ordered logical representatives and signs.
338    pub fn validate_logical_basis(
339        &self,
340        logical_x: Vec<PhasedPauli>,
341        logical_z: Vec<PhasedPauli>,
342    ) -> Result<ValidatedLogicalBasis, PhaseAlgebraError> {
343        let k = self.num_logical_qubits();
344        if logical_x.len() != k || logical_z.len() != k {
345            return Err(PhaseAlgebraError::LogicalCount {
346                expected: k,
347                x_count: logical_x.len(),
348                z_count: logical_z.len(),
349            });
350        }
351        for (kind, operators) in [("X", &logical_x), ("Z", &logical_z)] {
352            for (index, operator) in operators.iter().enumerate() {
353                if operator.n() != self.n {
354                    return Err(PhaseAlgebraError::LogicalWidth {
355                        kind,
356                        index,
357                        expected: self.n,
358                        actual: operator.n(),
359                    });
360                }
361                if !operator.is_hermitian() {
362                    return Err(PhaseAlgebraError::NonHermitianLogical { kind, index });
363                }
364                for (generator, stabilizer) in self.generators.iter().enumerate() {
365                    if !operator.commutes_with(stabilizer)? {
366                        return Err(PhaseAlgebraError::NonCentralizingLogical {
367                            kind,
368                            index,
369                            generator,
370                        });
371                    }
372                }
373            }
374        }
375
376        for i in 0..k {
377            for j in (i + 1)..k {
378                check_commutation("X", i, &logical_x[i], "X", j, &logical_x[j], false)?;
379                check_commutation("Z", i, &logical_z[i], "Z", j, &logical_z[j], false)?;
380            }
381            for j in 0..k {
382                check_commutation("X", i, &logical_x[i], "Z", j, &logical_z[j], i == j)?;
383            }
384        }
385
386        // Canonical commutation and exactly k pairs imply independence modulo
387        // stabilizers: a product in the stabilizer group commutes with every
388        // logical, so pairing it with each X/Z forces every logical exponent
389        // to vanish. There are 2k such independent quotient representatives.
390
391        Ok(ValidatedLogicalBasis {
392            logical_x,
393            logical_z,
394        })
395    }
396}
397
398/// A logical basis validated against a signed stabilizer group.
399#[derive(Debug, Clone, PartialEq, Eq)]
400pub struct ValidatedLogicalBasis {
401    logical_x: Vec<PhasedPauli>,
402    logical_z: Vec<PhasedPauli>,
403}
404
405impl ValidatedLogicalBasis {
406    pub fn k(&self) -> usize {
407        self.logical_x.len()
408    }
409
410    pub fn logical_x(&self) -> &[PhasedPauli] {
411        &self.logical_x
412    }
413
414    pub fn logical_z(&self) -> &[PhasedPauli] {
415        &self.logical_z
416    }
417}
418
419fn check_commutation(
420    left_kind: &'static str,
421    left_index: usize,
422    left: &PhasedPauli,
423    right_kind: &'static str,
424    right_index: usize,
425    right: &PhasedPauli,
426    expected_anticommutation: bool,
427) -> Result<(), PhaseAlgebraError> {
428    if left.commutes_with(right)? == expected_anticommutation {
429        return Err(PhaseAlgebraError::LogicalCommutation {
430            left_kind,
431            left_index,
432            right_kind,
433            right_index,
434            expected_anticommutation,
435        });
436    }
437    Ok(())
438}
439
440fn bit_at(operator: &PhasedPauli, column: usize) -> u8 {
441    let n = operator.n();
442    if column < n {
443        operator.support().x_bits()[column]
444    } else {
445        operator.support().z_bits()[column - n]
446    }
447}
448
449fn first_set_bit(operator: &PhasedPauli) -> Option<usize> {
450    operator
451        .support()
452        .x_bits()
453        .iter()
454        .chain(operator.support().z_bits())
455        .position(|&bit| bit != 0)
456}
457
458fn symmetric_difference(left: &[usize], right: &[usize]) -> Vec<usize> {
459    let mut result = Vec::with_capacity(left.len() + right.len());
460    let (mut i, mut j) = (0, 0);
461    while i < left.len() && j < right.len() {
462        match left[i].cmp(&right[j]) {
463            std::cmp::Ordering::Less => {
464                result.push(left[i]);
465                i += 1;
466            }
467            std::cmp::Ordering::Greater => {
468                result.push(right[j]);
469                j += 1;
470            }
471            std::cmp::Ordering::Equal => {
472                i += 1;
473                j += 1;
474            }
475        }
476    }
477    result.extend_from_slice(&left[i..]);
478    result.extend_from_slice(&right[j..]);
479    result
480}