1use crate::Pauli;
9use thiserror::Error;
10
11#[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 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#[derive(Debug, Clone, PartialEq, Eq)]
39pub struct PhasedPauli {
40 support: Pauli,
41 phase: Phase,
42}
43
44impl PhasedPauli {
45 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 pub fn into_support(self) -> Pauli {
71 self.support
72 }
73
74 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 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#[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#[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#[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 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 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 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 Ok(ValidatedLogicalBasis {
392 logical_x,
393 logical_z,
394 })
395 }
396}
397
398#[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}