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 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#[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 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}