Skip to main content

faultscope_core/
stabilizer.rs

1use crate::pauli::{
2    coeff_bit, multiply_concrete_rows, solve_row_span, sparse_symplectic_product_bits,
3    support_to_words, symplectic_product_bits, xz_to_pauli, DensePauliRef, SparsePauli,
4};
5use crate::{Expr, NpError, NpResult};
6
7#[derive(Clone, Debug, PartialEq, Eq)]
8pub struct PauliFrame {
9    x: Vec<u8>,
10    z: Vec<u8>,
11}
12
13impl PauliFrame {
14    pub fn new(x: Vec<u8>, z: Vec<u8>) -> NpResult<Self> {
15        DensePauliRef::new(&x, &z, x.len())?;
16        Ok(Self { x, z })
17    }
18
19    pub fn zero(n_qubits: usize) -> Self {
20        Self {
21            x: vec![0; n_qubits],
22            z: vec![0; n_qubits],
23        }
24    }
25
26    pub fn n_qubits(&self) -> usize {
27        self.x.len()
28    }
29
30    pub fn x_bits(&self) -> &[u8] {
31        &self.x
32    }
33
34    pub fn z_bits(&self) -> &[u8] {
35        &self.z
36    }
37
38    pub fn apply_pauli(&mut self, qubit: usize, pauli: &str) -> NpResult<()> {
39        let qubits = [qubit];
40        let target = SparsePauli::new(self.n_qubits(), &qubits, pauli, "PauliFrame.apply_pauli")?;
41        self.apply_sparse_impl(target);
42        Ok(())
43    }
44
45    pub fn apply_pauli_string(&mut self, qubits: &[usize], pauli: &str) -> NpResult<()> {
46        let target = SparsePauli::new(
47            self.n_qubits(),
48            qubits,
49            pauli,
50            "PauliFrame.apply_pauli_string",
51        )?;
52        self.apply_sparse_impl(target);
53        Ok(())
54    }
55
56    pub fn apply_h(&mut self, qubit: usize) -> NpResult<()> {
57        crate::model::validate_qubit_index(self.n_qubits(), qubit, "PauliFrame.apply_h")?;
58        self.apply_h_impl(qubit);
59        Ok(())
60    }
61
62    pub fn apply_s(&mut self, qubit: usize) -> NpResult<()> {
63        crate::model::validate_qubit_index(self.n_qubits(), qubit, "PauliFrame.apply_s")?;
64        self.apply_s_impl(qubit);
65        Ok(())
66    }
67
68    pub fn apply_s_dag(&mut self, qubit: usize) -> NpResult<()> {
69        crate::model::validate_qubit_index(self.n_qubits(), qubit, "PauliFrame.apply_s_dag")?;
70        self.apply_s_impl(qubit);
71        Ok(())
72    }
73
74    pub fn apply_cx(&mut self, control: usize, target: usize) -> NpResult<()> {
75        crate::model::validate_qubit_pair(self.n_qubits(), control, target, "PauliFrame.apply_cx")?;
76        self.apply_cx_impl(control, target);
77        Ok(())
78    }
79
80    pub fn apply_cz(&mut self, left: usize, right: usize) -> NpResult<()> {
81        crate::model::validate_qubit_pair(self.n_qubits(), left, right, "PauliFrame.apply_cz")?;
82        self.apply_cz_impl(left, right);
83        Ok(())
84    }
85
86    pub fn apply_swap(&mut self, left: usize, right: usize) -> NpResult<()> {
87        crate::model::validate_qubit_pair(self.n_qubits(), left, right, "PauliFrame.apply_swap")?;
88        self.apply_swap_impl(left, right);
89        Ok(())
90    }
91
92    pub fn reset(&mut self, qubit: usize) -> NpResult<()> {
93        crate::model::validate_qubit_index(self.n_qubits(), qubit, "PauliFrame.reset")?;
94        self.x[qubit] = 0;
95        self.z[qubit] = 0;
96        Ok(())
97    }
98
99    pub fn measurement_flip(&self, qubits: &[usize], pauli: &str) -> NpResult<bool> {
100        let target = SparsePauli::new(
101            self.n_qubits(),
102            qubits,
103            pauli,
104            "PauliFrame.measurement_flip",
105        )?;
106        Ok(sparse_symplectic_product_bits(&self.x, &self.z, target) != 0)
107    }
108
109    pub fn pauli_on(&self, qubits: &[usize]) -> NpResult<String> {
110        crate::model::validate_qubit_targets(self.n_qubits(), qubits, "PauliFrame.pauli_on")?;
111        Ok(qubits
112            .iter()
113            .map(|qubit| xz_to_pauli(self.x[*qubit], self.z[*qubit]))
114            .collect())
115    }
116
117    fn apply_sparse_impl(&mut self, target: SparsePauli<'_>) {
118        for (qubit, x, z) in target.entries() {
119            self.x[qubit] ^= x;
120            self.z[qubit] ^= z;
121        }
122    }
123
124    fn apply_h_impl(&mut self, qubit: usize) {
125        std::mem::swap(&mut self.x[qubit], &mut self.z[qubit]);
126    }
127
128    fn apply_s_impl(&mut self, qubit: usize) {
129        self.z[qubit] ^= self.x[qubit];
130    }
131
132    fn apply_cx_impl(&mut self, control: usize, target: usize) {
133        self.x[target] ^= self.x[control];
134        self.z[control] ^= self.z[target];
135    }
136
137    fn apply_cz_impl(&mut self, left: usize, right: usize) {
138        self.apply_h_impl(right);
139        self.apply_cx_impl(left, right);
140        self.apply_h_impl(right);
141    }
142
143    fn apply_swap_impl(&mut self, left: usize, right: usize) {
144        self.apply_cx_impl(left, right);
145        self.apply_cx_impl(right, left);
146        self.apply_cx_impl(left, right);
147    }
148}
149
150#[derive(Clone, Debug, PartialEq, Eq)]
151pub struct ConcreteStabilizer {
152    x: Vec<Vec<u8>>,
153    z: Vec<Vec<u8>>,
154    sign: Vec<bool>,
155}
156
157impl ConcreteStabilizer {
158    pub fn zero(n_qubits: usize) -> Self {
159        let x = vec![vec![0; n_qubits]; n_qubits];
160        let mut z = vec![vec![0; n_qubits]; n_qubits];
161        for (qubit, row) in z.iter_mut().enumerate().take(n_qubits) {
162            row[qubit] = 1;
163        }
164        Self {
165            x,
166            z,
167            sign: vec![false; n_qubits],
168        }
169    }
170
171    pub fn n_qubits(&self) -> usize {
172        self.x.len()
173    }
174
175    pub fn x_rows(&self) -> &[Vec<u8>] {
176        &self.x
177    }
178
179    pub fn z_rows(&self) -> &[Vec<u8>] {
180        &self.z
181    }
182
183    pub fn sign_bits(&self) -> &[bool] {
184        &self.sign
185    }
186
187    pub fn apply_h(&mut self, qubit: usize) -> NpResult<()> {
188        crate::model::validate_qubit_index(self.n_qubits(), qubit, "ConcreteStabilizer.apply_h")?;
189        self.apply_h_impl(qubit);
190        Ok(())
191    }
192
193    pub(crate) fn apply_h_impl(&mut self, qubit: usize) {
194        for row in 0..self.n_qubits() {
195            let old_x = self.x[row][qubit];
196            let old_z = self.z[row][qubit];
197            if old_x != 0 && old_z != 0 {
198                self.sign[row] ^= true;
199            }
200            self.x[row][qubit] = old_z;
201            self.z[row][qubit] = old_x;
202        }
203    }
204
205    pub fn apply_s(&mut self, qubit: usize) -> NpResult<()> {
206        crate::model::validate_qubit_index(self.n_qubits(), qubit, "ConcreteStabilizer.apply_s")?;
207        self.apply_s_impl(qubit);
208        Ok(())
209    }
210
211    pub(crate) fn apply_s_impl(&mut self, qubit: usize) {
212        for row in 0..self.n_qubits() {
213            let old_x = self.x[row][qubit];
214            let old_z = self.z[row][qubit];
215            if old_x != 0 && old_z != 0 {
216                self.sign[row] ^= true;
217            }
218            self.z[row][qubit] = old_z ^ old_x;
219        }
220    }
221
222    pub fn apply_s_dag(&mut self, qubit: usize) -> NpResult<()> {
223        crate::model::validate_qubit_index(
224            self.n_qubits(),
225            qubit,
226            "ConcreteStabilizer.apply_s_dag",
227        )?;
228        self.apply_s_dag_impl(qubit);
229        Ok(())
230    }
231
232    pub(crate) fn apply_s_dag_impl(&mut self, qubit: usize) {
233        for row in 0..self.n_qubits() {
234            let old_x = self.x[row][qubit];
235            let old_z = self.z[row][qubit];
236            if old_x != 0 && old_z == 0 {
237                self.sign[row] ^= true;
238            }
239            self.z[row][qubit] = old_z ^ old_x;
240        }
241    }
242
243    pub fn apply_cx(&mut self, control: usize, target: usize) -> NpResult<()> {
244        crate::model::validate_qubit_pair(
245            self.n_qubits(),
246            control,
247            target,
248            "ConcreteStabilizer.apply_cx",
249        )?;
250        self.apply_cx_impl(control, target);
251        Ok(())
252    }
253
254    pub(crate) fn apply_cx_impl(&mut self, control: usize, target: usize) {
255        for row in 0..self.n_qubits() {
256            let x_c = self.x[row][control];
257            let z_c = self.z[row][control];
258            let x_t = self.x[row][target];
259            let z_t = self.z[row][target];
260            if (x_c & z_t & (x_t ^ z_c ^ 1)) != 0 {
261                self.sign[row] ^= true;
262            }
263            self.x[row][target] ^= x_c;
264            self.z[row][control] ^= z_t;
265        }
266    }
267
268    pub fn apply_cz(&mut self, left: usize, right: usize) -> NpResult<()> {
269        crate::model::validate_qubit_pair(
270            self.n_qubits(),
271            left,
272            right,
273            "ConcreteStabilizer.apply_cz",
274        )?;
275        self.apply_cz_impl(left, right);
276        Ok(())
277    }
278
279    pub(crate) fn apply_cz_impl(&mut self, left: usize, right: usize) {
280        self.apply_h_impl(right);
281        self.apply_cx_impl(left, right);
282        self.apply_h_impl(right);
283    }
284
285    pub fn apply_swap(&mut self, left: usize, right: usize) -> NpResult<()> {
286        crate::model::validate_qubit_pair(
287            self.n_qubits(),
288            left,
289            right,
290            "ConcreteStabilizer.apply_swap",
291        )?;
292        self.apply_swap_impl(left, right);
293        Ok(())
294    }
295
296    pub(crate) fn apply_swap_impl(&mut self, left: usize, right: usize) {
297        debug_assert_ne!(left, right);
298        self.apply_cx_impl(left, right);
299        self.apply_cx_impl(right, left);
300        self.apply_cx_impl(left, right);
301    }
302
303    pub fn apply_pauli(&mut self, qubit: usize, pauli: &str) -> NpResult<()> {
304        let qubits = [qubit];
305        let target = SparsePauli::new(
306            self.n_qubits(),
307            &qubits,
308            pauli,
309            "ConcreteStabilizer.apply_pauli",
310        )?;
311        self.apply_sparse_pauli_impl(target);
312        Ok(())
313    }
314
315    pub fn apply_pauli_string(&mut self, x: &[u8], z: &[u8]) -> NpResult<()> {
316        let target = DensePauliRef::new(x, z, self.n_qubits())?;
317        self.apply_dense_pauli_impl(target);
318        Ok(())
319    }
320
321    fn apply_dense_pauli_impl(&mut self, target: DensePauliRef<'_>) {
322        for row in 0..self.n_qubits() {
323            if symplectic_product_bits(&self.x[row], &self.z[row], target.x(), target.z()) != 0 {
324                self.sign[row] ^= true;
325            }
326        }
327    }
328
329    pub(crate) fn apply_sparse_pauli_string(
330        &mut self,
331        qubits: &[usize],
332        pauli: &str,
333    ) -> NpResult<()> {
334        let target = SparsePauli::new(self.n_qubits(), qubits, pauli, "stabilizer Pauli")?;
335        self.apply_sparse_pauli_impl(target);
336        Ok(())
337    }
338
339    /// Apply one validated sparse Pauli event to this state and its frame.
340    ///
341    /// Both objects are checked before either is mutated, so an error leaves
342    /// the state and frame unchanged.
343    pub fn apply_pauli_event(
344        &mut self,
345        frame: &mut PauliFrame,
346        qubits: &[usize],
347        pauli: &str,
348    ) -> NpResult<()> {
349        if self.n_qubits() != frame.n_qubits() {
350            return Err(NpError::new(format!(
351                "stabilizer state and Pauli frame must have the same width, got state={} and frame={}",
352                self.n_qubits(),
353                frame.n_qubits()
354            )));
355        }
356        let target = SparsePauli::new(self.n_qubits(), qubits, pauli, "stabilizer Pauli event")?;
357        self.apply_sparse_pauli_impl(target);
358        frame.apply_sparse_impl(target);
359        Ok(())
360    }
361
362    fn apply_sparse_pauli_impl(&mut self, target: SparsePauli<'_>) {
363        for row in 0..self.n_qubits() {
364            if sparse_symplectic_product_bits(&self.x[row], &self.z[row], target) != 0 {
365                self.sign[row] ^= true;
366            }
367        }
368    }
369
370    pub fn is_deterministic_pauli(&self, x: &[u8], z: &[u8]) -> NpResult<bool> {
371        let target = DensePauliRef::new(x, z, self.n_qubits())?;
372        Ok(self.is_deterministic_impl(target))
373    }
374
375    fn is_deterministic_impl(&self, target: DensePauliRef<'_>) -> bool {
376        (0..self.n_qubits()).all(|row| {
377            symplectic_product_bits(&self.x[row], &self.z[row], target.x(), target.z()) == 0
378        })
379    }
380
381    pub(crate) fn is_deterministic_sparse_pauli(
382        &self,
383        qubits: &[usize],
384        pauli: &str,
385    ) -> NpResult<bool> {
386        let target = SparsePauli::new(self.n_qubits(), qubits, pauli, "stabilizer Pauli")?;
387        Ok(self.is_deterministic_sparse_impl(target))
388    }
389
390    fn is_deterministic_sparse_impl(&self, target: SparsePauli<'_>) -> bool {
391        if target.entries().all(|(_, x, z)| x == 0 && z == 1) {
392            for row in 0..self.n_qubits() {
393                let mut acc = 0;
394                for (qubit, _, _) in target.entries() {
395                    acc ^= self.x[row][qubit];
396                }
397                if (acc & 1) != 0 {
398                    return false;
399                }
400            }
401            return true;
402        }
403        if target.entries().all(|(_, x, z)| x == 1 && z == 0) {
404            for row in 0..self.n_qubits() {
405                let mut acc = 0;
406                for (qubit, _, _) in target.entries() {
407                    acc ^= self.z[row][qubit];
408                }
409                if (acc & 1) != 0 {
410                    return false;
411                }
412            }
413            return true;
414        }
415        if target.entries().all(|(_, x, z)| x == 1 && z == 1) {
416            for row in 0..self.n_qubits() {
417                let mut acc = 0;
418                for (qubit, _, _) in target.entries() {
419                    acc ^= self.x[row][qubit] ^ self.z[row][qubit];
420                }
421                if (acc & 1) != 0 {
422                    return false;
423                }
424            }
425            return true;
426        }
427        for row in 0..self.n_qubits() {
428            let mut acc = 0;
429            for (qubit, x, z) in target.entries() {
430                acc ^= (self.x[row][qubit] & z) ^ (self.z[row][qubit] & x);
431            }
432            if (acc & 1) != 0 {
433                return false;
434            }
435        }
436        true
437    }
438
439    pub fn deterministic_measurement_bit(&self, x: &[u8], z: &[u8]) -> NpResult<bool> {
440        let target = DensePauliRef::new(x, z, self.n_qubits())?;
441        if !self.is_deterministic_impl(target) {
442            return Err(NpError::new(
443                "Pauli measurement is random for this stabilizer state",
444            ));
445        }
446        self.deterministic_measurement_bit_impl(target)
447    }
448
449    fn deterministic_measurement_bit_impl(&self, target: DensePauliRef<'_>) -> NpResult<bool> {
450        let rows: Vec<Vec<u64>> = (0..self.n_qubits())
451            .map(|row| support_to_words(&self.x[row], &self.z[row]))
452            .collect();
453        let target_words = support_to_words(target.x(), target.z());
454        let coeff = solve_row_span(&rows, &target_words, self.n_qubits())
455            .ok_or_else(|| NpError::new("commuting Pauli was not in the stabilizer span"))?;
456
457        let mut selected_any = false;
458        let mut acc_x = vec![0; self.n_qubits()];
459        let mut acc_z = vec![0; self.n_qubits()];
460        let mut acc_sign = false;
461        for row in 0..self.n_qubits() {
462            if !coeff_bit(&coeff, row) {
463                continue;
464            }
465            if !selected_any {
466                acc_x = self.x[row].clone();
467                acc_z = self.z[row].clone();
468                acc_sign = self.sign[row];
469                selected_any = true;
470            } else {
471                let (new_x, new_z, new_sign) = multiply_concrete_rows(
472                    &acc_x,
473                    &acc_z,
474                    acc_sign,
475                    &self.x[row],
476                    &self.z[row],
477                    self.sign[row],
478                )?;
479                acc_x = new_x;
480                acc_z = new_z;
481                acc_sign = new_sign;
482            }
483        }
484        Ok(selected_any && acc_sign)
485    }
486
487    pub fn measure_pauli_with<E, F>(&mut self, x: &[u8], z: &[u8], random_bit: F) -> Result<bool, E>
488    where
489        E: From<NpError>,
490        F: FnOnce() -> Result<bool, E>,
491    {
492        let target = DensePauliRef::new(x, z, self.n_qubits()).map_err(E::from)?;
493        if self.is_deterministic_impl(target) {
494            return self
495                .deterministic_measurement_bit_impl(target)
496                .map_err(E::from);
497        }
498        let outcome = random_bit()?;
499        self.measure_pauli_with_outcome_impl(target, outcome)
500            .map_err(E::from)
501    }
502
503    fn measure_pauli_with_outcome_impl(
504        &mut self,
505        target: DensePauliRef<'_>,
506        outcome: bool,
507    ) -> NpResult<bool> {
508        let anti: Vec<usize> = (0..self.n_qubits())
509            .filter(|row| {
510                symplectic_product_bits(&self.x[*row], &self.z[*row], target.x(), target.z()) != 0
511            })
512            .collect();
513        if anti.is_empty() {
514            return self.deterministic_measurement_bit_impl(target);
515        }
516
517        let pivot = anti[0];
518        let old_x = self.x[pivot].clone();
519        let old_z = self.z[pivot].clone();
520        let old_sign = self.sign[pivot];
521        for row in anti.into_iter().skip(1) {
522            let (new_x, new_z, new_sign) = multiply_concrete_rows(
523                &self.x[row],
524                &self.z[row],
525                self.sign[row],
526                &old_x,
527                &old_z,
528                old_sign,
529            )?;
530            self.x[row] = new_x;
531            self.z[row] = new_z;
532            self.sign[row] = new_sign;
533        }
534        self.x[pivot] = target.x().to_vec();
535        self.z[pivot] = target.z().to_vec();
536        self.sign[pivot] = outcome;
537        Ok(outcome)
538    }
539
540    pub fn reset_prepare(&mut self, qubit: usize, basis: &str) -> NpResult<()> {
541        crate::model::validate_qubit_index(
542            self.n_qubits(),
543            qubit,
544            "ConcreteStabilizer.reset_prepare",
545        )?;
546        self.reset_prepare_impl(qubit, basis)
547    }
548
549    pub(crate) fn reset_prepare_impl(&mut self, qubit: usize, basis: &str) -> NpResult<()> {
550        let (target_x, target_z, correction_x, correction_z) = match basis {
551            "Z" => (0, 1, 1, 0),
552            "X" => (1, 0, 0, 1),
553            "Y" => (1, 1, 1, 0),
554            _ => return Err(NpError::new(format!("unsupported reset basis {basis:?}"))),
555        };
556        debug_assert!(qubit < self.n_qubits());
557        let mut x = vec![0; self.n_qubits()];
558        let mut z = vec![0; self.n_qubits()];
559        x[qubit] = target_x;
560        z[qubit] = target_z;
561        let dense = DensePauliRef::from_validated(&x, &z);
562        if self.is_deterministic_impl(dense) {
563            let bit = self.deterministic_measurement_bit_impl(dense)?;
564            if bit {
565                self.apply_single_pauli_impl(qubit, correction_x, correction_z);
566            }
567        } else {
568            self.measure_pauli_with_outcome_impl(dense, false)?;
569        }
570        Ok(())
571    }
572
573    fn apply_single_pauli_impl(&mut self, qubit: usize, x: u8, z: u8) {
574        debug_assert!(qubit < self.n_qubits());
575        debug_assert!(x <= 1 && z <= 1);
576        for row in 0..self.n_qubits() {
577            if ((self.x[row][qubit] & z) ^ (self.z[row][qubit] & x)) != 0 {
578                self.sign[row] ^= true;
579            }
580        }
581    }
582}
583
584/// Compiler-only symbolic Aaronson-Gottesman tableau.
585///
586/// Rows ``0..n`` are destabilizers and rows ``n..2n`` are stabilizers. Pauli
587/// supports are packed into u64 words. Keeping the dual destabilizer basis lets
588/// deterministic measurements recover their stabilizer coefficients directly,
589/// instead of rebuilding and eliminating a dense row span for every result.
590#[derive(Clone)]
591pub(crate) struct SymbolicStabilizer {
592    n_qubits: usize,
593    words: usize,
594    row_words: usize,
595    x: Vec<u64>,
596    z: Vec<u64>,
597    x_columns: Vec<u64>,
598    z_columns: Vec<u64>,
599    rows_valid: bool,
600    sign: Vec<Expr>,
601    random_source_count: usize,
602    row_scratch: Vec<u64>,
603    support_scratch_x: Vec<u64>,
604    support_scratch_z: Vec<u64>,
605}
606
607impl SymbolicStabilizer {
608    pub(crate) fn zero(n_qubits: usize) -> Self {
609        let words = n_qubits.div_ceil(64);
610        let mut x = vec![0; n_qubits * 2 * words];
611        let mut z = vec![0; n_qubits * 2 * words];
612        for qubit in 0..n_qubits {
613            toggle_flat_row_bit(&mut x, words, qubit, qubit);
614            toggle_flat_row_bit(&mut z, words, n_qubits + qubit, qubit);
615        }
616        let row_words = (n_qubits * 2).div_ceil(64);
617        let mut x_columns = vec![0; n_qubits * row_words];
618        let mut z_columns = vec![0; n_qubits * row_words];
619        for qubit in 0..n_qubits {
620            toggle_flat_column_bit(&mut x_columns, row_words, qubit, qubit);
621            toggle_flat_column_bit(&mut z_columns, row_words, qubit, n_qubits + qubit);
622        }
623        Self {
624            n_qubits,
625            words,
626            row_words,
627            x,
628            z,
629            x_columns,
630            z_columns,
631            rows_valid: true,
632            sign: vec![Expr::default(); n_qubits * 2],
633            random_source_count: 0,
634            row_scratch: vec![0; row_words],
635            support_scratch_x: vec![0; words],
636            support_scratch_z: vec![0; words],
637        }
638    }
639
640    pub(crate) fn random_source_count(&self) -> usize {
641        self.random_source_count
642    }
643
644    pub(crate) fn n_qubits(&self) -> usize {
645        self.n_qubits
646    }
647
648    fn row_start(&self, row: usize) -> usize {
649        row * self.words
650    }
651
652    fn x_row(&self, row: usize) -> &[u64] {
653        let start = self.row_start(row);
654        &self.x[start..start + self.words]
655    }
656
657    fn z_row(&self, row: usize) -> &[u64] {
658        let start = self.row_start(row);
659        &self.z[start..start + self.words]
660    }
661
662    fn column_start(&self, qubit: usize) -> usize {
663        qubit * self.row_words
664    }
665
666    #[cfg(test)]
667    fn x_column(&self, qubit: usize) -> &[u64] {
668        let start = self.column_start(qubit);
669        &self.x_columns[start..start + self.row_words]
670    }
671
672    #[cfg(test)]
673    fn z_column(&self, qubit: usize) -> &[u64] {
674        let start = self.column_start(qubit);
675        &self.z_columns[start..start + self.row_words]
676    }
677
678    fn synchronize_rows(&mut self) {
679        if self.rows_valid {
680            return;
681        }
682        self.x.fill(0);
683        self.z.fill(0);
684        for qubit_block in 0..self.words {
685            let first_qubit = qubit_block * 64;
686            let block_qubits = (self.n_qubits - first_qubit).min(64);
687            for local_qubit in 0..block_qubits {
688                let qubit = first_qubit + local_qubit;
689                let column_start = self.column_start(qubit);
690                for row_word in 0..self.row_words {
691                    let mut x_rows = self.x_columns[column_start + row_word];
692                    while x_rows != 0 {
693                        let row_bit = x_rows.trailing_zeros() as usize;
694                        let row = row_word * 64 + row_bit;
695                        if row < self.n_qubits * 2 {
696                            self.x[row * self.words + qubit_block] |= 1u64 << local_qubit;
697                        }
698                        x_rows &= x_rows - 1;
699                    }
700                    let mut z_rows = self.z_columns[column_start + row_word];
701                    while z_rows != 0 {
702                        let row_bit = z_rows.trailing_zeros() as usize;
703                        let row = row_word * 64 + row_bit;
704                        if row < self.n_qubits * 2 {
705                            self.z[row * self.words + qubit_block] |= 1u64 << local_qubit;
706                        }
707                        z_rows &= z_rows - 1;
708                    }
709                }
710            }
711        }
712        self.rows_valid = true;
713    }
714
715    pub(crate) fn affine_template(&self) -> Self {
716        let mut template = self.clone();
717        template.sign = (0..self.sign.len()).map(Expr::random).collect();
718        template.random_source_count = self.sign.len();
719        template
720    }
721
722    pub(crate) fn support_equals(&self, other: &Self) -> bool {
723        self.n_qubits == other.n_qubits
724            && self.x_columns == other.x_columns
725            && self.z_columns == other.z_columns
726    }
727
728    pub(crate) fn signs(&self) -> &[Expr] {
729        &self.sign
730    }
731
732    pub(crate) fn replace_affine_state(&mut self, signs: Vec<Expr>, random_source_count: usize) {
733        self.sign = signs;
734        self.random_source_count = random_source_count;
735    }
736
737    pub(crate) fn replace_with_affine_template(
738        &mut self,
739        mut template: Self,
740        signs: Vec<Expr>,
741        random_source_count: usize,
742    ) {
743        template.sign = signs;
744        template.random_source_count = random_source_count;
745        *self = template;
746    }
747
748    pub(crate) fn apply_h(&mut self, qubit: usize) {
749        let start = self.column_start(qubit);
750        for word_index in 0..self.row_words {
751            let index = start + word_index;
752            let old_x = self.x_columns[index];
753            let old_z = self.z_columns[index];
754            for_each_set_bit_in_word(word_index, old_x & old_z, |row| {
755                self.sign[row].toggle_constant()
756            });
757            self.x_columns[index] = old_z;
758            self.z_columns[index] = old_x;
759        }
760        self.rows_valid = false;
761    }
762
763    pub(crate) fn apply_s(&mut self, qubit: usize) {
764        let start = self.column_start(qubit);
765        for word_index in 0..self.row_words {
766            let index = start + word_index;
767            let x_rows = self.x_columns[index];
768            let z_rows = self.z_columns[index];
769            for_each_set_bit_in_word(word_index, x_rows & z_rows, |row| {
770                self.sign[row].toggle_constant()
771            });
772            self.z_columns[index] = z_rows ^ x_rows;
773        }
774        self.rows_valid = false;
775    }
776
777    pub(crate) fn apply_s_dag(&mut self, qubit: usize) {
778        let start = self.column_start(qubit);
779        for word_index in 0..self.row_words {
780            let index = start + word_index;
781            let x_rows = self.x_columns[index];
782            let z_rows = self.z_columns[index];
783            for_each_set_bit_in_word(word_index, x_rows & !z_rows, |row| {
784                self.sign[row].toggle_constant()
785            });
786            self.z_columns[index] = z_rows ^ x_rows;
787        }
788        self.rows_valid = false;
789    }
790
791    pub(crate) fn apply_cx(&mut self, control: usize, target: usize) {
792        let control_start = self.column_start(control);
793        let target_start = self.column_start(target);
794        for word_index in 0..self.row_words {
795            let control_index = control_start + word_index;
796            let target_index = target_start + word_index;
797            let x_c = self.x_columns[control_index];
798            let z_c = self.z_columns[control_index];
799            let x_t = self.x_columns[target_index];
800            let z_t = self.z_columns[target_index];
801            let sign_rows = x_c & z_t & !(x_t ^ z_c);
802            for_each_set_bit_in_word(word_index, sign_rows, |row| {
803                self.sign[row].toggle_constant()
804            });
805            if control == target {
806                self.x_columns[target_index] = 0;
807                self.z_columns[control_index] = 0;
808            } else {
809                self.x_columns[target_index] = x_t ^ x_c;
810                self.z_columns[control_index] = z_c ^ z_t;
811            }
812        }
813        self.rows_valid = false;
814    }
815
816    pub(crate) fn apply_cz(&mut self, left: usize, right: usize) {
817        if left == right {
818            self.apply_h(right);
819            self.apply_cx(left, right);
820            self.apply_h(right);
821            return;
822        }
823        let left_start = self.column_start(left);
824        let right_start = self.column_start(right);
825        for word_index in 0..self.row_words {
826            let left_index = left_start + word_index;
827            let right_index = right_start + word_index;
828            let x_l = self.x_columns[left_index];
829            let z_l = self.z_columns[left_index];
830            let x_r = self.x_columns[right_index];
831            let z_r = self.z_columns[right_index];
832            let sign_rows = x_l & x_r & (z_l ^ z_r);
833            for_each_set_bit_in_word(word_index, sign_rows, |row| {
834                self.sign[row].toggle_constant()
835            });
836            self.z_columns[left_index] = z_l ^ x_r;
837            self.z_columns[right_index] = z_r ^ x_l;
838        }
839        self.rows_valid = false;
840    }
841
842    pub(crate) fn apply_swap(&mut self, left: usize, right: usize) {
843        if left == right {
844            return;
845        }
846        let left_start = self.column_start(left);
847        let right_start = self.column_start(right);
848        for word_index in 0..self.row_words {
849            self.x_columns
850                .swap(left_start + word_index, right_start + word_index);
851            self.z_columns
852                .swap(left_start + word_index, right_start + word_index);
853        }
854        self.rows_valid = false;
855    }
856
857    /*
858     * Gate updates above keep only the contiguous column-major tableau current.
859     * Row-major support is rebuilt once, in 64-qubit blocks, before the next
860     * measurement that needs row products.
861     */
862
863    pub(crate) fn apply_sparse_pauli_string(
864        &mut self,
865        qubits: &[usize],
866        pauli: &str,
867    ) -> NpResult<()> {
868        let target = SparsePackedPauli::new(self.n_qubits, qubits, pauli)?;
869        let rows = target.anticommuting_rows(&self.x_columns, &self.z_columns, self.row_words);
870        self.toggle_sign_constants(&rows);
871        Ok(())
872    }
873
874    pub(crate) fn apply_single_pauli_string_expr(
875        &mut self,
876        qubit: usize,
877        pauli: &str,
878        expr: &Expr,
879    ) -> NpResult<()> {
880        let (x, z) = single_pauli_bits(qubit, self.n_qubits, pauli)?;
881        let column_start = self.column_start(qubit);
882        for word_index in 0..self.row_words {
883            let rows = (if x {
884                self.z_columns[column_start + word_index]
885            } else {
886                0
887            }) ^ (if z {
888                self.x_columns[column_start + word_index]
889            } else {
890                0
891            });
892            for_each_set_bit_in_word(word_index, rows, |row| self.sign[row].xor_assign(expr));
893        }
894        Ok(())
895    }
896
897    pub(crate) fn measure_single_pauli_expr(
898        &mut self,
899        qubit: usize,
900        pauli: &str,
901    ) -> NpResult<Expr> {
902        let (x, z) = single_pauli_bits(qubit, self.n_qubits, pauli)?;
903        let mut anticommuting_rows = std::mem::take(&mut self.row_scratch);
904        let column_start = self.column_start(qubit);
905        for (word_index, rows) in anticommuting_rows.iter_mut().enumerate() {
906            *rows = (if x {
907                self.z_columns[column_start + word_index]
908            } else {
909                0
910            }) ^ (if z {
911                self.x_columns[column_start + word_index]
912            } else {
913                0
914            });
915        }
916        self.synchronize_rows();
917        let pivot = first_set_bit_from(&anticommuting_rows, self.n_qubits);
918        let result = match pivot {
919            Some(pivot) => {
920                self.measure_random_single_pauli(pivot, qubit, x, z, &anticommuting_rows)
921            }
922            None => self.combine_stabilizers_selected_by(|destabilizer| {
923                packed_bit(&anticommuting_rows, destabilizer)
924            }),
925        };
926        self.row_scratch = anticommuting_rows;
927        result
928    }
929
930    pub(crate) fn measure_sparse_pauli_expr(
931        &mut self,
932        qubits: &[usize],
933        pauli: &str,
934    ) -> NpResult<Expr> {
935        let target = SparsePackedPauli::new(self.n_qubits, qubits, pauli)?;
936        let anticommuting_rows =
937            target.anticommuting_rows(&self.x_columns, &self.z_columns, self.row_words);
938        self.synchronize_rows();
939        let pivot = first_set_bit_from(&anticommuting_rows, self.n_qubits);
940        match pivot {
941            Some(pivot) => self.measure_random_sparse_pauli(pivot, target, &anticommuting_rows),
942            None => self.combine_stabilizers_selected_by(|destabilizer| {
943                packed_bit(&anticommuting_rows, destabilizer)
944            }),
945        }
946    }
947
948    fn measure_random_sparse_pauli(
949        &mut self,
950        pivot: usize,
951        target: SparsePackedPauli,
952        anticommuting_rows: &[u64],
953    ) -> NpResult<Expr> {
954        self.measure_random_pauli_with_support(
955            pivot,
956            anticommuting_rows,
957            Some((target.x, target.z)),
958            None,
959        )
960    }
961
962    fn measure_random_single_pauli(
963        &mut self,
964        pivot: usize,
965        qubit: usize,
966        x: bool,
967        z: bool,
968        anticommuting_rows: &[u64],
969    ) -> NpResult<Expr> {
970        self.measure_random_pauli_with_support(pivot, anticommuting_rows, None, Some((qubit, x, z)))
971    }
972
973    fn measure_random_pauli_with_support(
974        &mut self,
975        pivot: usize,
976        anticommuting_rows: &[u64],
977        target: Option<(Vec<u64>, Vec<u64>)>,
978        single_target: Option<(usize, bool, bool)>,
979    ) -> NpResult<Expr> {
980        let paired_destabilizer = pivot - self.n_qubits;
981        let mut pivot_x = std::mem::take(&mut self.support_scratch_x);
982        let mut pivot_z = std::mem::take(&mut self.support_scratch_z);
983        pivot_x.clone_from_slice(self.x_row(pivot));
984        pivot_z.clone_from_slice(self.z_row(pivot));
985        let pivot_sign = self.sign[pivot].clone();
986        let rowsum_result = for_each_set_bit_result(anticommuting_rows, |row| {
987            if row != pivot && row != paired_destabilizer {
988                self.rowsum_row_only(row, &pivot_x, &pivot_z, &pivot_sign)?;
989            }
990            Ok(())
991        });
992        if let Err(error) = rowsum_result {
993            self.support_scratch_x = pivot_x;
994            self.support_scratch_z = pivot_z;
995            return Err(error);
996        }
997        self.apply_rowsum_columns_batch(
998            anticommuting_rows,
999            pivot,
1000            paired_destabilizer,
1001            &pivot_x,
1002            &pivot_z,
1003        );
1004
1005        self.replace_row_support(paired_destabilizer, &pivot_x, &pivot_z);
1006        self.sign[paired_destabilizer] = pivot_sign;
1007        let source = self.random_source_count;
1008        self.random_source_count += 1;
1009        let outcome = Expr::random(source);
1010        if let Some((target_x, target_z)) = target {
1011            self.replace_row_support(pivot, &target_x, &target_z);
1012        } else if let Some((qubit, x, z)) = single_target {
1013            self.replace_row_support_single(pivot, qubit, x, z);
1014        }
1015        self.sign[pivot] = outcome.clone();
1016        self.support_scratch_x = pivot_x;
1017        self.support_scratch_z = pivot_z;
1018        Ok(outcome)
1019    }
1020
1021    fn combine_stabilizers_selected_by<F>(&mut self, mut selected: F) -> NpResult<Expr>
1022    where
1023        F: FnMut(usize) -> bool,
1024    {
1025        let mut acc_x = std::mem::take(&mut self.support_scratch_x);
1026        let mut acc_z = std::mem::take(&mut self.support_scratch_z);
1027        acc_x.fill(0);
1028        acc_z.fill(0);
1029        let mut acc_sign = Expr::default();
1030        let mut result = Ok(());
1031        for destabilizer in 0..self.n_qubits {
1032            if selected(destabilizer) {
1033                let stabilizer = self.n_qubits + destabilizer;
1034                let start = self.row_start(stabilizer);
1035                result = packed_rowsum(
1036                    &mut acc_x,
1037                    &mut acc_z,
1038                    &mut acc_sign,
1039                    &self.x[start..start + self.words],
1040                    &self.z[start..start + self.words],
1041                    &self.sign[stabilizer],
1042                );
1043                if result.is_err() {
1044                    break;
1045                }
1046            }
1047        }
1048        self.support_scratch_x = acc_x;
1049        self.support_scratch_z = acc_z;
1050        result.map(|_| acc_sign)
1051    }
1052
1053    fn toggle_sign_constants(&mut self, rows: &[u64]) {
1054        for_each_set_bit(rows, |row| self.sign[row].toggle_constant());
1055    }
1056
1057    fn rowsum_row_only(
1058        &mut self,
1059        target: usize,
1060        source_x: &[u64],
1061        source_z: &[u64],
1062        source_sign: &Expr,
1063    ) -> NpResult<()> {
1064        let start = self.row_start(target);
1065        packed_rowsum(
1066            &mut self.x[start..start + self.words],
1067            &mut self.z[start..start + self.words],
1068            &mut self.sign[target],
1069            source_x,
1070            source_z,
1071            source_sign,
1072        )
1073    }
1074
1075    fn apply_rowsum_columns_batch(
1076        &mut self,
1077        anticommuting_rows: &[u64],
1078        pivot: usize,
1079        paired_destabilizer: usize,
1080        source_x: &[u64],
1081        source_z: &[u64],
1082    ) {
1083        let update_word = |word_index: usize| {
1084            let mut rows = anticommuting_rows[word_index];
1085            if pivot / 64 == word_index {
1086                rows &= !(1u64 << (pivot % 64));
1087            }
1088            if paired_destabilizer / 64 == word_index {
1089                rows &= !(1u64 << (paired_destabilizer % 64));
1090            }
1091            rows
1092        };
1093        for_each_set_bit(source_x, |qubit| {
1094            let column_start = qubit * self.row_words;
1095            for word_index in 0..self.row_words {
1096                self.x_columns[column_start + word_index] ^= update_word(word_index);
1097            }
1098        });
1099        for_each_set_bit(source_z, |qubit| {
1100            let column_start = qubit * self.row_words;
1101            for word_index in 0..self.row_words {
1102                self.z_columns[column_start + word_index] ^= update_word(word_index);
1103            }
1104        });
1105    }
1106
1107    fn replace_row_support(&mut self, row: usize, new_x: &[u64], new_z: &[u64]) {
1108        let start = self.row_start(row);
1109        for word_index in 0..self.words {
1110            let index = start + word_index;
1111            let changed_x = self.x[index] ^ new_x[word_index];
1112            let changed_z = self.z[index] ^ new_z[word_index];
1113            for_each_set_bit_in_word(word_index, changed_x, |qubit| {
1114                toggle_flat_column_bit(&mut self.x_columns, self.row_words, qubit, row)
1115            });
1116            for_each_set_bit_in_word(word_index, changed_z, |qubit| {
1117                toggle_flat_column_bit(&mut self.z_columns, self.row_words, qubit, row)
1118            });
1119            self.x[index] = new_x[word_index];
1120            self.z[index] = new_z[word_index];
1121        }
1122    }
1123
1124    fn replace_row_support_single(&mut self, row: usize, qubit: usize, x: bool, z: bool) {
1125        let target_word = qubit / 64;
1126        let target_bit = 1u64 << (qubit % 64);
1127        let start = self.row_start(row);
1128        for word_index in 0..self.words {
1129            let new_x = if x && word_index == target_word {
1130                target_bit
1131            } else {
1132                0
1133            };
1134            let new_z = if z && word_index == target_word {
1135                target_bit
1136            } else {
1137                0
1138            };
1139            let index = start + word_index;
1140            let changed_x = self.x[index] ^ new_x;
1141            let changed_z = self.z[index] ^ new_z;
1142            for_each_set_bit_in_word(word_index, changed_x, |changed_qubit| {
1143                toggle_flat_column_bit(&mut self.x_columns, self.row_words, changed_qubit, row)
1144            });
1145            for_each_set_bit_in_word(word_index, changed_z, |changed_qubit| {
1146                toggle_flat_column_bit(&mut self.z_columns, self.row_words, changed_qubit, row)
1147            });
1148            self.x[index] = new_x;
1149            self.z[index] = new_z;
1150        }
1151    }
1152}
1153
1154struct SparsePackedPauli {
1155    entries: Vec<(usize, bool, bool)>,
1156    x: Vec<u64>,
1157    z: Vec<u64>,
1158}
1159
1160fn single_pauli_bits(qubit: usize, n_qubits: usize, pauli: &str) -> NpResult<(bool, bool)> {
1161    if qubit >= n_qubits {
1162        return Err(NpError::new(format!(
1163            "qubit {qubit} is out of range for {n_qubits} qubits"
1164        )));
1165    }
1166    match pauli.as_bytes() {
1167        [b'X'] => Ok((true, false)),
1168        [b'Y'] => Ok((true, true)),
1169        [b'Z'] => Ok((false, true)),
1170        _ => Err(NpError::new(format!(
1171            "unsupported single-qubit Pauli {pauli:?}"
1172        ))),
1173    }
1174}
1175
1176fn toggle_flat_row_bit(matrix: &mut [u64], words: usize, row: usize, bit: usize) {
1177    matrix[row * words + bit / 64] ^= 1u64 << (bit % 64);
1178}
1179
1180fn toggle_flat_column_bit(matrix: &mut [u64], row_words: usize, column: usize, row: usize) {
1181    matrix[column * row_words + row / 64] ^= 1u64 << (row % 64);
1182}
1183
1184fn xor_words_in_place(target: &mut [u64], source: &[u64]) {
1185    debug_assert_eq!(target.len(), source.len(), "word counts must match");
1186    for (target, source) in target.iter_mut().zip(source) {
1187        *target ^= source;
1188    }
1189}
1190
1191fn for_each_set_bit(words: &[u64], mut function: impl FnMut(usize)) {
1192    for (word_index, word) in words.iter().copied().enumerate() {
1193        let mut remaining = word;
1194        while remaining != 0 {
1195            let bit = remaining.trailing_zeros() as usize;
1196            function(word_index * 64 + bit);
1197            remaining &= remaining - 1;
1198        }
1199    }
1200}
1201
1202fn for_each_set_bit_in_word(word_index: usize, mut word: u64, mut function: impl FnMut(usize)) {
1203    while word != 0 {
1204        let bit = word.trailing_zeros() as usize;
1205        function(word_index * 64 + bit);
1206        word &= word - 1;
1207    }
1208}
1209
1210fn for_each_set_bit_result(
1211    words: &[u64],
1212    mut function: impl FnMut(usize) -> NpResult<()>,
1213) -> NpResult<()> {
1214    for (word_index, word) in words.iter().copied().enumerate() {
1215        let mut remaining = word;
1216        while remaining != 0 {
1217            let bit = remaining.trailing_zeros() as usize;
1218            function(word_index * 64 + bit)?;
1219            remaining &= remaining - 1;
1220        }
1221    }
1222    Ok(())
1223}
1224
1225fn first_set_bit_from(words: &[u64], start: usize) -> Option<usize> {
1226    let mut word_index = start / 64;
1227    if word_index >= words.len() {
1228        return None;
1229    }
1230    let mut word = words[word_index] & (!0u64 << (start % 64));
1231    loop {
1232        if word != 0 {
1233            return Some(word_index * 64 + word.trailing_zeros() as usize);
1234        }
1235        word_index += 1;
1236        if word_index >= words.len() {
1237            return None;
1238        }
1239        word = words[word_index];
1240    }
1241}
1242
1243impl SparsePackedPauli {
1244    fn new(n_qubits: usize, qubits: &[usize], pauli: &str) -> NpResult<Self> {
1245        let target = SparsePauli::new(n_qubits, qubits, pauli, "stabilizer Pauli")?;
1246        let words = n_qubits.div_ceil(64);
1247        let mut entries = Vec::with_capacity(target.len());
1248        let mut x = vec![0; words];
1249        let mut z = vec![0; words];
1250        for (qubit, local_x, local_z) in target.entries() {
1251            let local_x = local_x != 0;
1252            let local_z = local_z != 0;
1253            entries.push((qubit, local_x, local_z));
1254            if local_x {
1255                toggle_packed_bit(&mut x, qubit);
1256            }
1257            if local_z {
1258                toggle_packed_bit(&mut z, qubit);
1259            }
1260        }
1261        Ok(Self { entries, x, z })
1262    }
1263
1264    fn anticommuting_rows(
1265        &self,
1266        x_columns: &[u64],
1267        z_columns: &[u64],
1268        row_words: usize,
1269    ) -> Vec<u64> {
1270        let mut rows = vec![0; row_words];
1271        for (qubit, x, z) in &self.entries {
1272            let start = qubit * row_words;
1273            if *z {
1274                xor_words_in_place(&mut rows, &x_columns[start..start + row_words]);
1275            }
1276            if *x {
1277                xor_words_in_place(&mut rows, &z_columns[start..start + row_words]);
1278            }
1279        }
1280        rows
1281    }
1282}
1283
1284fn packed_bit(words: &[u64], qubit: usize) -> bool {
1285    ((words[qubit / 64] >> (qubit % 64)) & 1) != 0
1286}
1287
1288fn toggle_packed_bit(words: &mut [u64], qubit: usize) {
1289    words[qubit / 64] ^= 1u64 << (qubit % 64);
1290}
1291
1292fn packed_rowsum(
1293    target_x: &mut [u64],
1294    target_z: &mut [u64],
1295    target_sign: &mut Expr,
1296    source_x: &[u64],
1297    source_z: &[u64],
1298    source_sign: &Expr,
1299) -> NpResult<()> {
1300    debug_assert_eq!(target_x.len(), target_z.len(), "word counts must match");
1301    debug_assert_eq!(target_x.len(), source_x.len(), "word counts must match");
1302    debug_assert_eq!(target_x.len(), source_z.len(), "word counts must match");
1303    let mut phase = 0u32;
1304    for (((target_x_word, target_z_word), source_x_word), source_z_word) in target_x
1305        .iter_mut()
1306        .zip(target_z.iter_mut())
1307        .zip(source_x)
1308        .zip(source_z)
1309    {
1310        let tx = *target_x_word;
1311        let tz = *target_z_word;
1312        let sx = *source_x_word;
1313        let sz = *source_z_word;
1314        let plus = (tx & !tz & sx & sz).count_ones()
1315            + (tx & tz & !sx & sz).count_ones()
1316            + (!tx & tz & sx & !sz).count_ones();
1317        let minus = (tx & tz & sx & !sz).count_ones()
1318            + (!tx & tz & sx & sz).count_ones()
1319            + (tx & !tz & !sx & sz).count_ones();
1320        phase = (phase + plus + 3 * minus) & 3;
1321        *target_x_word = tx ^ sx;
1322        *target_z_word = tz ^ sz;
1323    }
1324    target_sign.xor_assign(source_sign);
1325    match phase {
1326        0 => Ok(()),
1327        2 => {
1328            target_sign.toggle_constant();
1329            Ok(())
1330        }
1331        _ => Err(NpError::new(
1332            "product of symbolic tableau rows produced a non-Hermitian phase",
1333        )),
1334    }
1335}
1336
1337#[cfg(test)]
1338mod tests {
1339    use super::*;
1340    use crate::pauli::sparse_pauli_to_xz;
1341
1342    struct DenseSymbolicReference {
1343        x: Vec<Vec<u8>>,
1344        z: Vec<Vec<u8>>,
1345        sign: Vec<Expr>,
1346        random_source_count: usize,
1347    }
1348
1349    impl DenseSymbolicReference {
1350        fn zero(n_qubits: usize) -> Self {
1351            let x = vec![vec![0; n_qubits]; n_qubits];
1352            let mut z = vec![vec![0; n_qubits]; n_qubits];
1353            for (qubit, row) in z.iter_mut().enumerate() {
1354                row[qubit] = 1;
1355            }
1356            Self {
1357                x,
1358                z,
1359                sign: vec![Expr::default(); n_qubits],
1360                random_source_count: 0,
1361            }
1362        }
1363
1364        fn n_qubits(&self) -> usize {
1365            self.x.len()
1366        }
1367
1368        fn apply_h(&mut self, qubit: usize) {
1369            for row in 0..self.n_qubits() {
1370                let old_x = self.x[row][qubit];
1371                let old_z = self.z[row][qubit];
1372                if old_x != 0 && old_z != 0 {
1373                    self.sign[row].toggle_constant();
1374                }
1375                self.x[row][qubit] = old_z;
1376                self.z[row][qubit] = old_x;
1377            }
1378        }
1379
1380        fn apply_s(&mut self, qubit: usize) {
1381            for row in 0..self.n_qubits() {
1382                let old_x = self.x[row][qubit];
1383                let old_z = self.z[row][qubit];
1384                if old_x != 0 && old_z != 0 {
1385                    self.sign[row].toggle_constant();
1386                }
1387                self.z[row][qubit] = old_z ^ old_x;
1388            }
1389        }
1390
1391        fn apply_s_dag(&mut self, qubit: usize) {
1392            for row in 0..self.n_qubits() {
1393                let old_x = self.x[row][qubit];
1394                let old_z = self.z[row][qubit];
1395                if old_x != 0 && old_z == 0 {
1396                    self.sign[row].toggle_constant();
1397                }
1398                self.z[row][qubit] = old_z ^ old_x;
1399            }
1400        }
1401
1402        fn apply_cx(&mut self, control: usize, target: usize) {
1403            for row in 0..self.n_qubits() {
1404                let x_c = self.x[row][control];
1405                let z_c = self.z[row][control];
1406                let x_t = self.x[row][target];
1407                let z_t = self.z[row][target];
1408                if (x_c & z_t & (x_t ^ z_c ^ 1)) != 0 {
1409                    self.sign[row].toggle_constant();
1410                }
1411                self.x[row][target] ^= x_c;
1412                self.z[row][control] ^= z_t;
1413            }
1414        }
1415
1416        fn apply_cz(&mut self, left: usize, right: usize) {
1417            self.apply_h(right);
1418            self.apply_cx(left, right);
1419            self.apply_h(right);
1420        }
1421
1422        fn apply_swap(&mut self, left: usize, right: usize) {
1423            self.apply_cx(left, right);
1424            self.apply_cx(right, left);
1425            self.apply_cx(left, right);
1426        }
1427
1428        fn apply_sparse_pauli_expr(&mut self, qubits: &[usize], pauli: &str, expr: &Expr) {
1429            let (x, z) = sparse_pauli_to_xz(self.n_qubits(), qubits, pauli).unwrap();
1430            for row in 0..self.n_qubits() {
1431                if symplectic_product_bits(&self.x[row], &self.z[row], &x, &z) != 0 {
1432                    self.sign[row].xor_assign(expr);
1433                }
1434            }
1435        }
1436
1437        fn measure_sparse(&mut self, qubits: &[usize], pauli: &str) -> Expr {
1438            let (x, z) = sparse_pauli_to_xz(self.n_qubits(), qubits, pauli).unwrap();
1439            self.measure(&x, &z)
1440        }
1441
1442        fn measure(&mut self, x: &[u8], z: &[u8]) -> Expr {
1443            let anti: Vec<usize> = (0..self.n_qubits())
1444                .filter(|row| symplectic_product_bits(&self.x[*row], &self.z[*row], x, z) != 0)
1445                .collect();
1446            if anti.is_empty() {
1447                return self.deterministic_measurement(x, z);
1448            }
1449
1450            let source = self.random_source_count;
1451            self.random_source_count += 1;
1452            let outcome = Expr::random(source);
1453            let pivot = anti[0];
1454            let old_x = self.x[pivot].clone();
1455            let old_z = self.z[pivot].clone();
1456            let old_sign = self.sign[pivot].clone();
1457            for row in anti.into_iter().skip(1) {
1458                let (new_x, new_z, new_sign) = crate::pauli::multiply_symbolic_rows(
1459                    &self.x[row],
1460                    &self.z[row],
1461                    &self.sign[row],
1462                    &old_x,
1463                    &old_z,
1464                    &old_sign,
1465                )
1466                .unwrap();
1467                self.x[row] = new_x;
1468                self.z[row] = new_z;
1469                self.sign[row] = new_sign;
1470            }
1471            self.x[pivot] = x.to_vec();
1472            self.z[pivot] = z.to_vec();
1473            self.sign[pivot] = outcome.clone();
1474            outcome
1475        }
1476
1477        fn deterministic_measurement(&self, x: &[u8], z: &[u8]) -> Expr {
1478            let rows: Vec<Vec<u64>> = (0..self.n_qubits())
1479                .map(|row| support_to_words(&self.x[row], &self.z[row]))
1480                .collect();
1481            let target = support_to_words(x, z);
1482            let coeff = solve_row_span(&rows, &target, self.n_qubits()).unwrap();
1483            let mut acc_x = vec![0; self.n_qubits()];
1484            let mut acc_z = vec![0; self.n_qubits()];
1485            let mut acc_sign = Expr::default();
1486            for row in 0..self.n_qubits() {
1487                if coeff_bit(&coeff, row) {
1488                    (acc_x, acc_z, acc_sign) = crate::pauli::multiply_symbolic_rows(
1489                        &acc_x,
1490                        &acc_z,
1491                        &acc_sign,
1492                        &self.x[row],
1493                        &self.z[row],
1494                        &self.sign[row],
1495                    )
1496                    .unwrap();
1497                }
1498            }
1499            acc_sign
1500        }
1501    }
1502
1503    fn assert_matches_dense_reference(packed: &SymbolicStabilizer, dense: &DenseSymbolicReference) {
1504        assert_eq!(packed.n_qubits, dense.n_qubits());
1505        assert_eq!(packed.random_source_count, dense.random_source_count);
1506        for row in 0..dense.n_qubits() {
1507            let packed_row = packed.n_qubits + row;
1508            for qubit in 0..dense.n_qubits() {
1509                assert_eq!(
1510                    packed_bit(packed.x_column(qubit), packed_row),
1511                    dense.x[row][qubit] != 0,
1512                    "x row {row}, qubit {qubit}"
1513                );
1514                assert_eq!(
1515                    packed_bit(packed.z_column(qubit), packed_row),
1516                    dense.z[row][qubit] != 0,
1517                    "z row {row}, qubit {qubit}"
1518                );
1519            }
1520            assert_eq!(packed.sign[packed_row], dense.sign[row], "sign row {row}");
1521        }
1522    }
1523
1524    fn assert_symbolic_states_equal(left: &SymbolicStabilizer, right: &SymbolicStabilizer) {
1525        assert_eq!(left.n_qubits, right.n_qubits);
1526        assert_eq!(left.x, right.x);
1527        assert_eq!(left.z, right.z);
1528        assert_eq!(left.x_columns, right.x_columns);
1529        assert_eq!(left.z_columns, right.z_columns);
1530        assert_eq!(left.rows_valid, right.rows_valid);
1531        assert_eq!(left.sign, right.sign);
1532        assert_eq!(left.random_source_count, right.random_source_count);
1533    }
1534
1535    type TwoQubitPauliConjugation = (&'static str, &'static str, bool);
1536
1537    const CX_PAULI_CONJUGATIONS: [TwoQubitPauliConjugation; 16] = [
1538        ("II", "II", false),
1539        ("IX", "IX", false),
1540        ("IY", "ZY", false),
1541        ("IZ", "ZZ", false),
1542        ("XI", "XX", false),
1543        ("XX", "XI", false),
1544        ("XY", "YZ", false),
1545        ("XZ", "YY", true),
1546        ("YI", "YX", false),
1547        ("YX", "YI", false),
1548        ("YY", "XZ", true),
1549        ("YZ", "XY", false),
1550        ("ZI", "ZI", false),
1551        ("ZX", "ZX", false),
1552        ("ZY", "IY", false),
1553        ("ZZ", "IZ", false),
1554    ];
1555
1556    const CZ_PAULI_CONJUGATIONS: [TwoQubitPauliConjugation; 16] = [
1557        ("II", "II", false),
1558        ("IX", "ZX", false),
1559        ("IY", "ZY", false),
1560        ("IZ", "IZ", false),
1561        ("XI", "XZ", false),
1562        ("XX", "YY", false),
1563        ("XY", "YX", true),
1564        ("XZ", "XI", false),
1565        ("YI", "YZ", false),
1566        ("YX", "XY", true),
1567        ("YY", "XX", false),
1568        ("YZ", "YI", false),
1569        ("ZI", "ZI", false),
1570        ("ZX", "IX", false),
1571        ("ZY", "IY", false),
1572        ("ZZ", "ZZ", false),
1573    ];
1574
1575    fn set_symbolic_row_support(state: &mut SymbolicStabilizer, row: usize, x: &[u8], z: &[u8]) {
1576        let word_index = row / 64;
1577        let row_mask = 1u64 << (row % 64);
1578        for (qubit, (&x_bit, &z_bit)) in x.iter().zip(z).enumerate() {
1579            let index = state.column_start(qubit) + word_index;
1580            if x_bit == 0 {
1581                state.x_columns[index] &= !row_mask;
1582            } else {
1583                state.x_columns[index] |= row_mask;
1584            }
1585            if z_bit == 0 {
1586                state.z_columns[index] &= !row_mask;
1587            } else {
1588                state.z_columns[index] |= row_mask;
1589            }
1590        }
1591        state.sign[row] = Expr::default();
1592    }
1593
1594    fn assert_two_qubit_pauli_conjugations(
1595        gate_name: &str,
1596        truth_table: &[TwoQubitPauliConjugation],
1597        apply_concrete: fn(&mut ConcreteStabilizer, usize, usize),
1598        apply_symbolic: fn(&mut SymbolicStabilizer, usize, usize),
1599        apply_dense: fn(&mut DenseSymbolicReference, usize, usize),
1600    ) {
1601        for &(input, expected_output, expected_negative) in truth_table {
1602            let (input_x, input_z) = sparse_pauli_to_xz(2, &[0, 1], input).unwrap();
1603            let (expected_x, expected_z) = sparse_pauli_to_xz(2, &[0, 1], expected_output).unwrap();
1604
1605            let mut concrete = ConcreteStabilizer {
1606                x: vec![input_x.clone(), vec![0; 2]],
1607                z: vec![input_z.clone(), vec![0; 2]],
1608                sign: vec![false; 2],
1609            };
1610            apply_concrete(&mut concrete, 0, 1);
1611            assert_eq!(
1612                concrete.x[0], expected_x,
1613                "{gate_name} concrete x support for {input}"
1614            );
1615            assert_eq!(
1616                concrete.z[0], expected_z,
1617                "{gate_name} concrete z support for {input}"
1618            );
1619            assert!(
1620                concrete.sign[0] == expected_negative,
1621                "{gate_name} concrete sign for {input}"
1622            );
1623
1624            let mut symbolic = SymbolicStabilizer::zero(2);
1625            let symbolic_row = symbolic.n_qubits;
1626            set_symbolic_row_support(&mut symbolic, symbolic_row, &input_x, &input_z);
1627            apply_symbolic(&mut symbolic, 0, 1);
1628            for (qubit, (&expected_x_bit, &expected_z_bit)) in
1629                expected_x.iter().zip(&expected_z).enumerate()
1630            {
1631                assert_eq!(
1632                    u8::from(packed_bit(symbolic.x_column(qubit), symbolic_row)),
1633                    expected_x_bit,
1634                    "{gate_name} symbolic x support for {input}, qubit {qubit}"
1635                );
1636                assert_eq!(
1637                    u8::from(packed_bit(symbolic.z_column(qubit), symbolic_row)),
1638                    expected_z_bit,
1639                    "{gate_name} symbolic z support for {input}, qubit {qubit}"
1640                );
1641            }
1642            assert_eq!(
1643                symbolic.sign[symbolic_row],
1644                Expr::constant(expected_negative),
1645                "{gate_name} symbolic sign for {input}"
1646            );
1647
1648            let mut dense = DenseSymbolicReference {
1649                x: vec![input_x, vec![0; 2]],
1650                z: vec![input_z, vec![0; 2]],
1651                sign: vec![Expr::default(); 2],
1652                random_source_count: 0,
1653            };
1654            apply_dense(&mut dense, 0, 1);
1655            assert_eq!(
1656                dense.x[0], expected_x,
1657                "{gate_name} dense x support for {input}"
1658            );
1659            assert_eq!(
1660                dense.z[0], expected_z,
1661                "{gate_name} dense z support for {input}"
1662            );
1663            assert_eq!(
1664                dense.sign[0],
1665                Expr::constant(expected_negative),
1666                "{gate_name} dense sign for {input}"
1667            );
1668        }
1669    }
1670
1671    #[test]
1672    fn cx_matches_two_qubit_pauli_conjugation_truth_table() {
1673        assert_two_qubit_pauli_conjugations(
1674            "CX",
1675            &CX_PAULI_CONJUGATIONS,
1676            ConcreteStabilizer::apply_cx_impl,
1677            SymbolicStabilizer::apply_cx,
1678            DenseSymbolicReference::apply_cx,
1679        );
1680    }
1681
1682    #[test]
1683    fn cz_matches_two_qubit_pauli_conjugation_truth_table() {
1684        assert_two_qubit_pauli_conjugations(
1685            "CZ",
1686            &CZ_PAULI_CONJUGATIONS,
1687            ConcreteStabilizer::apply_cz_impl,
1688            SymbolicStabilizer::apply_cz,
1689            DenseSymbolicReference::apply_cz,
1690        );
1691    }
1692
1693    #[test]
1694    fn reset_prepares_zero_state() {
1695        let mut state = ConcreteStabilizer::zero(1);
1696        let (x, z) = sparse_pauli_to_xz(1, &[0], "Z").unwrap();
1697
1698        state.reset_prepare(0, "Z").unwrap();
1699
1700        assert!(state.is_deterministic_pauli(&x, &z).unwrap());
1701        assert!(!state.deterministic_measurement_bit(&x, &z).unwrap());
1702    }
1703
1704    #[test]
1705    fn dense_pauli_methods_reject_before_rng_or_mutation() {
1706        let mut state = ConcreteStabilizer::zero(2);
1707        let before = state.clone();
1708        let mut rng_calls = 0;
1709
1710        assert!(state.apply_pauli_string(&[1], &[0]).is_err());
1711        assert!(state.is_deterministic_pauli(&[1], &[0]).is_err());
1712        assert!(state.deterministic_measurement_bit(&[1], &[0]).is_err());
1713        assert!(state
1714            .deterministic_measurement_bit(&[1, 0], &[0, 0])
1715            .is_err());
1716        let measured: NpResult<bool> = state.measure_pauli_with(&[1], &[0], || {
1717            rng_calls += 1;
1718            Ok(false)
1719        });
1720        assert!(measured.is_err());
1721        assert!(state.apply_pauli_string(&[2, 0], &[0, 0]).is_err());
1722
1723        assert_eq!(rng_calls, 0);
1724        assert_eq!(state, before);
1725        assert!(state.x_rows().iter().all(|row| row.len() == 2));
1726        assert!(state.z_rows().iter().all(|row| row.len() == 2));
1727    }
1728
1729    #[test]
1730    fn public_gate_methods_reject_invalid_targets() {
1731        let mut state = ConcreteStabilizer::zero(2);
1732        let before = state.clone();
1733
1734        assert!(state.apply_h(2).is_err());
1735        assert!(state.apply_cx(0, 0).is_err());
1736        assert!(state.apply_swap(0, 2).is_err());
1737        assert_eq!(state, before);
1738    }
1739
1740    #[test]
1741    fn pauli_frame_validates_construction_and_targets() {
1742        assert!(PauliFrame::new(vec![1], vec![0, 0]).is_err());
1743        assert!(PauliFrame::new(vec![2], vec![0]).is_err());
1744
1745        let mut frame = PauliFrame::new(vec![1], vec![0]).unwrap();
1746        let before = frame.clone();
1747        assert!(frame.apply_pauli_string(&[0, 0], "XZ").is_err());
1748        assert!(frame.measurement_flip(&[1], "Z").is_err());
1749        assert_eq!(frame, before);
1750    }
1751
1752    #[test]
1753    fn pauli_event_validates_state_and_frame_before_mutation() {
1754        let mut state = ConcreteStabilizer::zero(2);
1755        let mut short_frame = PauliFrame::zero(1);
1756        let state_before = state.clone();
1757        let frame_before = short_frame.clone();
1758
1759        assert!(state
1760            .apply_pauli_event(&mut short_frame, &[1], "X")
1761            .is_err());
1762        assert_eq!(state, state_before);
1763        assert_eq!(short_frame, frame_before);
1764
1765        let mut frame = PauliFrame::zero(2);
1766        let state_before = state.clone();
1767        let frame_before = frame.clone();
1768        assert!(state.apply_pauli_event(&mut frame, &[0, 0], "XZ").is_err());
1769        assert_eq!(state, state_before);
1770        assert_eq!(frame, frame_before);
1771
1772        state.apply_pauli_event(&mut frame, &[0, 1], "XZ").unwrap();
1773        let mut expected_state = ConcreteStabilizer::zero(2);
1774        expected_state.apply_pauli_string(&[1, 0], &[0, 1]).unwrap();
1775        assert_eq!(state, expected_state);
1776        assert_eq!(frame.pauli_on(&[0, 1]).unwrap(), "XZ");
1777    }
1778
1779    #[test]
1780    fn pauli_frame_sparse_work_is_independent_of_frame_width() {
1781        let mut frame = PauliFrame::zero(10_000);
1782        frame
1783            .apply_pauli_string(&[1, 127, 4_095, 9_999], "XYZX")
1784            .unwrap();
1785
1786        assert_eq!(frame.pauli_on(&[1, 127, 4_095, 9_999]).unwrap(), "XYZX");
1787        assert!(frame.measurement_flip(&[1], "Z").unwrap());
1788    }
1789
1790    #[test]
1791    #[cfg(debug_assertions)]
1792    fn packed_rowsum_debug_asserts_mismatched_widths_before_mutation() {
1793        let mut target_x = vec![1];
1794        let mut target_z = vec![0, 0];
1795        let mut target_sign = Expr::constant(true);
1796        let before = (target_x.clone(), target_z.clone(), target_sign.clone());
1797
1798        let result = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
1799            let _ = packed_rowsum(
1800                &mut target_x,
1801                &mut target_z,
1802                &mut target_sign,
1803                &[0],
1804                &[0],
1805                &Expr::default(),
1806            );
1807        }));
1808
1809        assert!(result.is_err());
1810        assert_eq!((target_x, target_z, target_sign), before);
1811    }
1812
1813    #[test]
1814    fn frame_pauli_flips_measurement_when_anticommuting() {
1815        let mut frame = PauliFrame::new(vec![1], vec![0]).unwrap();
1816
1817        assert!(frame.measurement_flip(&[0], "Z").unwrap());
1818
1819        frame.apply_h(0).unwrap();
1820
1821        assert!(!frame.measurement_flip(&[0], "Z").unwrap());
1822    }
1823
1824    #[test]
1825    fn concrete_sparse_pauli_path_matches_dense_path() {
1826        for (qubits, pauli) in [
1827            (vec![0], "X"),
1828            (vec![1], "Y"),
1829            (vec![2], "Z"),
1830            (vec![0, 2], "XZ"),
1831        ] {
1832            let mut sparse = ConcreteStabilizer::zero(3);
1833            let mut dense = ConcreteStabilizer::zero(3);
1834            sparse.apply_h(0).unwrap();
1835            dense.apply_h(0).unwrap();
1836            sparse.apply_cx(0, 1).unwrap();
1837            dense.apply_cx(0, 1).unwrap();
1838            let (x, z) = sparse_pauli_to_xz(3, &qubits, pauli).unwrap();
1839
1840            sparse.apply_sparse_pauli_string(&qubits, pauli).unwrap();
1841            dense.apply_pauli_string(&x, &z).unwrap();
1842
1843            assert_eq!(sparse, dense);
1844        }
1845    }
1846
1847    #[test]
1848    fn symbolic_measurement_tracks_random_sources() {
1849        let mut state = SymbolicStabilizer::zero(1);
1850        let expr = state.measure_sparse_pauli_expr(&[0], "X").unwrap();
1851
1852        assert_eq!(expr.terms(), &[0]);
1853        assert_eq!(state.random_source_count(), 1);
1854    }
1855
1856    #[test]
1857    fn single_qubit_measurement_fast_path_matches_sparse_path() {
1858        for prepared_with_h in [false, true] {
1859            for basis in ["X", "Y", "Z"] {
1860                let mut initial = SymbolicStabilizer::zero(2);
1861                if prepared_with_h {
1862                    initial.apply_h(0);
1863                    initial.apply_cx(0, 1);
1864                }
1865                let mut direct = initial.clone();
1866                let mut sparse = initial;
1867
1868                let direct_ideal = direct.measure_single_pauli_expr(0, basis).unwrap();
1869                let sparse_ideal = sparse.measure_sparse_pauli_expr(&[0], basis).unwrap();
1870
1871                assert_eq!(direct_ideal, sparse_ideal, "basis {basis}");
1872                assert_symbolic_states_equal(&direct, &sparse);
1873            }
1874        }
1875    }
1876
1877    #[test]
1878    fn packed_symbolic_tableau_matches_dense_reference_gate_by_gate() {
1879        let mut packed = SymbolicStabilizer::zero(3);
1880        let mut dense = DenseSymbolicReference::zero(3);
1881
1882        packed.apply_h(0);
1883        dense.apply_h(0);
1884        assert_matches_dense_reference(&packed, &dense);
1885        packed.apply_s(0);
1886        dense.apply_s(0);
1887        assert_matches_dense_reference(&packed, &dense);
1888        packed.apply_s_dag(0);
1889        dense.apply_s_dag(0);
1890        assert_matches_dense_reference(&packed, &dense);
1891        packed.apply_cx(0, 1);
1892        dense.apply_cx(0, 1);
1893        assert_matches_dense_reference(&packed, &dense);
1894        packed.apply_cz(1, 2);
1895        dense.apply_cz(1, 2);
1896        assert_matches_dense_reference(&packed, &dense);
1897        packed.apply_swap(0, 2);
1898        dense.apply_swap(0, 2);
1899        assert_matches_dense_reference(&packed, &dense);
1900
1901        for (qubit, pauli) in [(0, "X"), (1, "Y"), (2, "Z")] {
1902            packed
1903                .apply_single_pauli_string_expr(qubit, pauli, &Expr::constant(true))
1904                .unwrap();
1905            dense.apply_sparse_pauli_expr(&[qubit], pauli, &Expr::constant(true));
1906            assert_matches_dense_reference(&packed, &dense);
1907        }
1908    }
1909
1910    #[test]
1911    fn packed_symbolic_measurements_and_reset_match_dense_reference() {
1912        let mut packed = SymbolicStabilizer::zero(3);
1913        let mut dense = DenseSymbolicReference::zero(3);
1914        packed.apply_h(0);
1915        dense.apply_h(0);
1916
1917        let packed_random = packed.measure_sparse_pauli_expr(&[0], "Z").unwrap();
1918        let dense_random = dense.measure_sparse(&[0], "Z");
1919        assert_eq!(packed_random, dense_random);
1920        assert_matches_dense_reference(&packed, &dense);
1921
1922        packed
1923            .apply_single_pauli_string_expr(0, "X", &packed_random)
1924            .unwrap();
1925        dense.apply_sparse_pauli_expr(&[0], "X", &dense_random);
1926        assert_matches_dense_reference(&packed, &dense);
1927        let packed_reset_result = packed.measure_sparse_pauli_expr(&[0], "Z").unwrap();
1928        let dense_reset_result = dense.measure_sparse(&[0], "Z");
1929        assert_eq!(packed_reset_result, dense_reset_result);
1930        assert_eq!(packed_reset_result, Expr::constant(false));
1931
1932        packed.apply_h(1);
1933        dense.apply_h(1);
1934        let packed_mpp = packed.measure_sparse_pauli_expr(&[1, 2], "XX").unwrap();
1935        let dense_mpp = dense.measure_sparse(&[1, 2], "XX");
1936        assert_eq!(packed_mpp, dense_mpp);
1937        assert_matches_dense_reference(&packed, &dense);
1938        assert_eq!(
1939            packed.measure_sparse_pauli_expr(&[1, 2], "XX").unwrap(),
1940            dense.measure_sparse(&[1, 2], "XX")
1941        );
1942        assert_matches_dense_reference(&packed, &dense);
1943    }
1944}