1#![cfg_attr(feature = "unstable_simd", feature(portable_simd))]
3#![expect(clippy::too_many_arguments, clippy::type_complexity)]
4use rand::rngs::StdRng;
5use rand::{RngExt, SeedableRng};
6use std::fmt;
7#[cfg(feature = "unstable_simd")]
8use std::simd::Simd;
9#[cfg(feature = "unstable_simd")]
10use std::simd::num::SimdUint;
11#[cfg(feature = "unstable_simd")]
12use tk_pg_bitpacked::{
13 apply_enum_tqe_simd, apply_half_pi_gate_simd, simd_h_gate, simd_x_gate, simd_xx_gate,
14 simd_xy_gate, simd_xz_gate, simd_y_gate, simd_yy_gate, simd_yz_gate, simd_z_gate, simd_zz_gate,
15};
16use tk_pg_bitpacked::{
17 apply_enum_tqe_slice, apply_half_pi_gate_slice, paulis_to_u64s, slice_h_gate, slice_x_gate,
18 slice_xx_gate, slice_xy_gate, slice_xz_gate, slice_y_gate, slice_yy_gate, slice_yz_gate,
19 slice_z_gate, slice_zz_gate, u64s_to_paulis,
20};
21use tk_pg_core::Pauli;
22
23mod converter;
24
25const MT_THRESH: usize = 500;
28
29type TqeGateFn = fn(&mut [u64], &mut [u64], &mut [u64], &mut [u64], &mut [u64]);
32type PauliGateFn = fn(&[u64], &[u64], &mut [u64]);
33type ApplyEnumTqeFn = fn(&mut [u64], &mut [u64], &mut [u64], &mut [u64], &mut [u64], Pauli, Pauli);
34type ApplyHalfPiFn = fn(&mut [u64], &mut [u64], &mut [u64], Pauli, bool);
35type StringMulFn = fn(&mut [u64], &mut [u64], &[u64], &[u64]) -> u8;
36type CountYFn = fn(&[u64], &[u64]) -> u64;
37
38fn get_two_mut<T>(v: &mut [T], i: usize, j: usize) -> (&mut T, &mut T) {
50 let (a, b) = if i < j {
51 let (left, right) = v.split_at_mut(j);
52 (&mut left[i], &mut right[0])
53 } else {
54 let (left, right) = v.split_at_mut(i);
55 (&mut right[0], &mut left[j])
56 };
57 (a, b)
58}
59
60fn check_distinct_qubits(q0: usize, q1: usize) {
62 if q0 == q1 {
63 panic!("Expected two distinct qubit indices, but both q0 and q1 are {q0}");
64 }
65}
66
67fn string_mul(
83 lhs_z_bits: &mut [u64],
84 lhs_x_bits: &mut [u64],
85 rhs_z_bits: &[u64],
86 rhs_x_bits: &[u64],
87) -> u8 {
88 let len = lhs_z_bits.len();
89 let mut n_anti_commute_sites: u64 = 0;
90 let mut n_anti_cyclic_sites: u64 = 0;
91 for idx in 0..len {
92 let lhs_z_word = lhs_z_bits[idx];
93 let lhs_x_word = lhs_x_bits[idx];
94 let rhs_z_word = rhs_z_bits[idx];
95 let rhs_x_word = rhs_x_bits[idx];
96 lhs_z_bits[idx] ^= rhs_z_word;
97 lhs_x_bits[idx] ^= rhs_x_word;
98 let lhs_z_rhs_x_word = lhs_z_word & rhs_x_word;
99 let rhs_z_lhs_x_word = rhs_z_word & lhs_x_word;
100 let anti_commute_word = lhs_z_rhs_x_word ^ rhs_z_lhs_x_word;
101 let anti_cyclic_word = (rhs_z_lhs_x_word & !lhs_z_word & !rhs_x_word)
102 | (lhs_z_rhs_x_word & (lhs_x_word ^ rhs_z_word));
103 n_anti_commute_sites += anti_commute_word.count_ones() as u64;
104 n_anti_cyclic_sites += anti_cyclic_word.count_ones() as u64;
105 }
106 ((n_anti_commute_sites as i64 - 2 * n_anti_cyclic_sites as i64).rem_euclid(4)) as u8
107}
108
109fn count_y(input_z_bits: &[u64], input_x_bits: &[u64]) -> u64 {
111 let len = input_z_bits.len();
112 let mut n_ys = 0;
113 for idx in 0..len {
114 n_ys += (input_z_bits[idx] & input_x_bits[idx]).count_ones() as u64;
115 }
116 n_ys
117}
118
119#[cfg(feature = "unstable_simd")]
121fn simd_string_mul<const N: usize>(
122 lhs_z_bits: &mut [u64],
123 lhs_x_bits: &mut [u64],
124 rhs_z_bits: &[u64],
125 rhs_x_bits: &[u64],
126) -> u8 {
127 let len = lhs_z_bits.len();
128 let chunks = len / N;
129 let mut n_anti_commute_sites: u64 = 0;
130 let mut n_anti_cyclic_sites: u64 = 0;
131 for i in 0..chunks {
132 let lhs_z_chunk = &mut lhs_z_bits[i * N..(i + 1) * N];
133 let lhs_x_chunk = &mut lhs_x_bits[i * N..(i + 1) * N];
134 let rhs_z_chunk = &rhs_z_bits[i * N..(i + 1) * N];
135 let rhs_x_chunk = &rhs_x_bits[i * N..(i + 1) * N];
136 let lhs_z_simd = Simd::<u64, N>::from_slice(lhs_z_chunk);
137 let lhs_x_simd = Simd::<u64, N>::from_slice(lhs_x_chunk);
138 let rhs_z_simd = Simd::<u64, N>::from_slice(rhs_z_chunk);
139 let rhs_x_simd = Simd::<u64, N>::from_slice(rhs_x_chunk);
140 let result_z_simd = lhs_z_simd ^ rhs_z_simd;
141 let result_x_simd = lhs_x_simd ^ rhs_x_simd;
142 result_z_simd.copy_to_slice(lhs_z_chunk);
143 result_x_simd.copy_to_slice(lhs_x_chunk);
144 let lhs_z_rhs_x_simd = lhs_z_simd & rhs_x_simd;
145 let rhs_z_lhs_x_simd = rhs_z_simd & lhs_x_simd;
146 let anti_commute_simd = lhs_z_rhs_x_simd ^ rhs_z_lhs_x_simd;
147 let anti_cyclic_simd = (rhs_z_lhs_x_simd & !lhs_z_simd & !rhs_x_simd)
148 | (lhs_z_rhs_x_simd & (lhs_x_simd ^ rhs_z_simd));
149 n_anti_commute_sites += anti_commute_simd.count_ones().reduce_sum();
150 n_anti_cyclic_sites += anti_cyclic_simd.count_ones().reduce_sum();
151 }
152 let start = chunks * N;
154 for idx in start..len {
155 let lhs_z_word = lhs_z_bits[idx];
156 let lhs_x_word = lhs_x_bits[idx];
157 let rhs_z_word = rhs_z_bits[idx];
158 let rhs_x_word = rhs_x_bits[idx];
159 lhs_z_bits[idx] ^= rhs_z_word;
160 lhs_x_bits[idx] ^= rhs_x_word;
161 let lhs_z_rhs_x_word = lhs_z_word & rhs_x_word;
162 let rhs_z_lhs_x_word = rhs_z_word & lhs_x_word;
163 let anti_commute_word = lhs_z_rhs_x_word ^ rhs_z_lhs_x_word;
164 let anti_cyclic_word = (rhs_z_lhs_x_word & !lhs_z_word & !rhs_x_word)
165 | (lhs_z_rhs_x_word & (lhs_x_word ^ rhs_z_word));
166 n_anti_commute_sites += anti_commute_word.count_ones() as u64;
167 n_anti_cyclic_sites += anti_cyclic_word.count_ones() as u64;
168 }
169 ((n_anti_commute_sites as i64 - 2 * n_anti_cyclic_sites as i64).rem_euclid(4)) as u8
170}
171
172#[cfg(feature = "unstable_simd")]
174fn simd_count_y<const N: usize>(input_z_bits: &[u64], input_x_bits: &[u64]) -> u64 {
175 let len = input_z_bits.len();
176 let chunks = len / N;
177
178 let mut n_ys = 0;
179 for i in 0..chunks {
180 let z_chunk = &input_z_bits[i * N..(i + 1) * N];
181 let x_chunk = &input_x_bits[i * N..(i + 1) * N];
182 let z_simd = Simd::<u64, N>::from_slice(z_chunk);
183 let x_simd = Simd::<u64, N>::from_slice(x_chunk);
184 n_ys += (z_simd & x_simd).count_ones().reduce_sum();
185 }
186 let start = chunks * N;
188 for idx in start..len {
189 let input_z_word = input_z_bits[idx];
190 let input_x_word = input_x_bits[idx];
191 n_ys += (input_z_word & input_x_word).count_ones() as u64;
192 }
193 n_ys
194}
195
196#[derive(Clone, Debug, PartialEq, Eq)]
220pub struct Tableau {
221 qubit_slices_z_bits: Vec<Vec<u64>>,
222 qubit_slices_x_bits: Vec<Vec<u64>>,
223 sign_bits: Vec<u64>,
224 n_qubits: usize,
225}
226
227impl fmt::Display for Tableau {
228 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
229 for i in 0..self.n_qubits {
230 let paulis = u64s_to_paulis(
231 &self.qubit_slices_z_bits[i],
232 &self.qubit_slices_x_bits[i],
233 self.n_qubits * 2,
234 );
235 for p in paulis {
236 write!(f, "{p} ")?;
237 }
238 writeln!(f)?;
239 }
240 let total_sign_bits = 2 * self.n_qubits;
241 let mut bits_printed = 0;
242 for s in &self.sign_bits {
243 for i in 0..64 {
244 if bits_printed == total_sign_bits {
245 break;
246 }
247 let bit = (s >> i) & 1;
248 write!(f, "{} ", if bit == 1 { '-' } else { '+' })?;
249 bits_printed += 1;
250 }
251 if bits_printed == total_sign_bits {
252 break;
253 }
254 }
255 writeln!(f)
256 }
257}
258
259impl Tableau {
260 pub fn get_n_qubits(&self) -> usize {
262 self.n_qubits
263 }
264 pub fn qubit_slices_z_bits(&self) -> &Vec<Vec<u64>> {
266 &self.qubit_slices_z_bits
267 }
268 pub fn qubit_slices_x_bits(&self) -> &Vec<Vec<u64>> {
270 &self.qubit_slices_x_bits
271 }
272 pub fn get_sign_bits(&self) -> &Vec<u64> {
274 &self.sign_bits
275 }
276
277 pub fn split_qubit_slices_mut(
283 &mut self,
284 q0: usize,
285 q1: usize,
286 ) -> (
287 &mut Vec<u64>,
288 &mut Vec<u64>,
289 &mut Vec<u64>,
290 &mut Vec<u64>,
291 &mut Vec<u64>,
292 ) {
293 check_distinct_qubits(q0, q1);
294 let (q0_slice_z_bits, q1_slice_z_bits) = get_two_mut(&mut self.qubit_slices_z_bits, q0, q1);
295 let (q0_slice_x_bits, q1_slice_x_bits) = get_two_mut(&mut self.qubit_slices_x_bits, q0, q1);
296 (
297 q0_slice_z_bits,
298 q1_slice_z_bits,
299 q0_slice_x_bits,
300 q1_slice_x_bits,
301 &mut self.sign_bits,
302 )
303 }
304
305 fn postcompose_tqe_with(
307 &mut self,
308 g0: Pauli,
309 g1: Pauli,
310 q0: usize,
311 q1: usize,
312 xx_gate: TqeGateFn,
313 xy_gate: TqeGateFn,
314 xz_gate: TqeGateFn,
315 yy_gate: TqeGateFn,
316 yz_gate: TqeGateFn,
317 zz_gate: TqeGateFn,
318 ) {
319 let (q0_slice_z_bits, q1_slice_z_bits) = get_two_mut(&mut self.qubit_slices_z_bits, q0, q1);
320 let (q0_slice_x_bits, q1_slice_x_bits) = get_two_mut(&mut self.qubit_slices_x_bits, q0, q1);
321 match (g0, g1) {
322 (Pauli::X, Pauli::X) => xx_gate(
323 q0_slice_z_bits,
324 q0_slice_x_bits,
325 q1_slice_z_bits,
326 q1_slice_x_bits,
327 &mut self.sign_bits,
328 ),
329 (Pauli::X, Pauli::Y) => xy_gate(
330 q0_slice_z_bits,
331 q0_slice_x_bits,
332 q1_slice_z_bits,
333 q1_slice_x_bits,
334 &mut self.sign_bits,
335 ),
336 (Pauli::X, Pauli::Z) => xz_gate(
337 q0_slice_z_bits,
338 q0_slice_x_bits,
339 q1_slice_z_bits,
340 q1_slice_x_bits,
341 &mut self.sign_bits,
342 ),
343 (Pauli::Y, Pauli::X) => xy_gate(
344 q1_slice_z_bits,
345 q1_slice_x_bits,
346 q0_slice_z_bits,
347 q0_slice_x_bits,
348 &mut self.sign_bits,
349 ),
350 (Pauli::Y, Pauli::Y) => yy_gate(
351 q0_slice_z_bits,
352 q0_slice_x_bits,
353 q1_slice_z_bits,
354 q1_slice_x_bits,
355 &mut self.sign_bits,
356 ),
357 (Pauli::Y, Pauli::Z) => yz_gate(
358 q0_slice_z_bits,
359 q0_slice_x_bits,
360 q1_slice_z_bits,
361 q1_slice_x_bits,
362 &mut self.sign_bits,
363 ),
364 (Pauli::Z, Pauli::X) => xz_gate(
365 q1_slice_z_bits,
366 q1_slice_x_bits,
367 q0_slice_z_bits,
368 q0_slice_x_bits,
369 &mut self.sign_bits,
370 ),
371 (Pauli::Z, Pauli::Y) => yz_gate(
372 q1_slice_z_bits,
373 q1_slice_x_bits,
374 q0_slice_z_bits,
375 q0_slice_x_bits,
376 &mut self.sign_bits,
377 ),
378 (Pauli::Z, Pauli::Z) => zz_gate(
379 q0_slice_z_bits,
380 q0_slice_x_bits,
381 q1_slice_z_bits,
382 q1_slice_x_bits,
383 &mut self.sign_bits,
384 ),
385 _ => panic!("Unexpected TQE gate!"),
386 }
387 }
388
389 fn precompose_tqe_with(
391 &mut self,
392 g0: Pauli,
393 g1: Pauli,
394 q0: usize,
395 q1: usize,
396 string_mul: StringMulFn,
397 ) {
398 let (g0, g1, q0, q1) = {
399 if g0 <= g1 {
400 (g0, g1, q0, q1)
401 } else {
402 (g1, g0, q1, q0)
403 }
404 };
405 let z0_img_idx = 2 * q0;
406 let x0_img_idx = 2 * q0 + 1;
407 let z1_img_idx = 2 * q1;
408 let x1_img_idx = 2 * q1 + 1;
409 let (mut z0_img_z_bits, mut z0_img_x_bits, z0_img_sign_bit) = self.packed_image(z0_img_idx);
410 let (mut x0_img_z_bits, mut x0_img_x_bits, x0_img_sign_bit) = self.packed_image(x0_img_idx);
411 let (mut z1_img_z_bits, mut z1_img_x_bits, z1_img_sign_bit) = self.packed_image(z1_img_idx);
412 let (mut x1_img_z_bits, mut x1_img_x_bits, x1_img_sign_bit) = self.packed_image(x1_img_idx);
413
414 match (g0, g1) {
415 (Pauli::X, Pauli::X) => {
416 let phase = string_mul(
418 &mut z0_img_z_bits,
419 &mut z0_img_x_bits,
420 &x1_img_z_bits,
421 &x1_img_x_bits,
422 );
423 self.set_packed_image(
424 z0_img_idx,
425 &z0_img_z_bits,
426 &z0_img_x_bits,
427 z0_img_sign_bit ^ x1_img_sign_bit ^ (phase == 2),
428 );
429 let phase = string_mul(
431 &mut z1_img_z_bits,
432 &mut z1_img_x_bits,
433 &x0_img_z_bits,
434 &x0_img_x_bits,
435 );
436 self.set_packed_image(
437 z1_img_idx,
438 &z1_img_z_bits,
439 &z1_img_x_bits,
440 z1_img_sign_bit ^ x0_img_sign_bit ^ (phase == 2),
441 );
442 }
443 (Pauli::X, Pauli::Y) => {
444 let mut phase = string_mul(
446 &mut z0_img_z_bits,
447 &mut z0_img_x_bits,
448 &x1_img_z_bits,
449 &x1_img_x_bits,
450 );
451 phase += string_mul(
452 &mut z0_img_z_bits,
453 &mut z0_img_x_bits,
454 &z1_img_z_bits,
455 &z1_img_x_bits,
456 );
457 phase = (phase + 1) % 4;
458 self.set_packed_image(
459 z0_img_idx,
460 &z0_img_z_bits,
461 &z0_img_x_bits,
462 z0_img_sign_bit ^ z1_img_sign_bit ^ x1_img_sign_bit ^ (phase == 2),
463 );
464 let phase = string_mul(
466 &mut z1_img_z_bits,
467 &mut z1_img_x_bits,
468 &x0_img_z_bits,
469 &x0_img_x_bits,
470 );
471 self.set_packed_image(
472 z1_img_idx,
473 &z1_img_z_bits,
474 &z1_img_x_bits,
475 z1_img_sign_bit ^ x0_img_sign_bit ^ (phase == 2),
476 );
477 let phase = string_mul(
479 &mut x1_img_z_bits,
480 &mut x1_img_x_bits,
481 &x0_img_z_bits,
482 &x0_img_x_bits,
483 );
484 self.set_packed_image(
485 x1_img_idx,
486 &x1_img_z_bits,
487 &x1_img_x_bits,
488 x1_img_sign_bit ^ x0_img_sign_bit ^ (phase == 2),
489 );
490 }
491 (Pauli::X, Pauli::Z) => {
492 let phase = string_mul(
494 &mut z0_img_z_bits,
495 &mut z0_img_x_bits,
496 &z1_img_z_bits,
497 &z1_img_x_bits,
498 );
499 self.set_packed_image(
500 z0_img_idx,
501 &z0_img_z_bits,
502 &z0_img_x_bits,
503 z0_img_sign_bit ^ z1_img_sign_bit ^ (phase == 2),
504 );
505 let phase = string_mul(
507 &mut x1_img_z_bits,
508 &mut x1_img_x_bits,
509 &x0_img_z_bits,
510 &x0_img_x_bits,
511 );
512 self.set_packed_image(
513 x1_img_idx,
514 &x1_img_z_bits,
515 &x1_img_x_bits,
516 x0_img_sign_bit ^ x1_img_sign_bit ^ (phase == 2),
517 );
518 }
519 (Pauli::Y, Pauli::Y) => {
520 let z0_img_phase = (z0_img_sign_bit as u8) << 1;
522 let x0_img_phase = (x0_img_sign_bit as u8) << 1;
523 let z1_img_phase = (z1_img_sign_bit as u8) << 1;
524 let x1_img_phase = (x1_img_sign_bit as u8) << 1;
525 let mut y1_img_z_bits = x1_img_z_bits;
527 let mut y1_img_x_bits = x1_img_x_bits;
528 let y1_img_phase = string_mul(
529 &mut y1_img_z_bits,
530 &mut y1_img_x_bits,
531 &z1_img_z_bits,
532 &z1_img_x_bits,
533 ) + 1
534 + z1_img_phase
535 + x1_img_phase;
536 let z0_img_phase_new = (string_mul(
538 &mut z0_img_z_bits,
539 &mut z0_img_x_bits,
540 &y1_img_z_bits,
541 &y1_img_x_bits,
542 ) + z0_img_phase
543 + y1_img_phase)
544 % 4;
545 self.set_packed_image(
546 z0_img_idx,
547 &z0_img_z_bits,
548 &z0_img_x_bits,
549 z0_img_phase_new == 2,
550 );
551 let x0_img_phase_new = (string_mul(
553 &mut x0_img_z_bits,
554 &mut x0_img_x_bits,
555 &y1_img_z_bits,
556 &y1_img_x_bits,
557 ) + x0_img_phase
558 + y1_img_phase)
559 % 4;
560 self.set_packed_image(
561 x0_img_idx,
562 &x0_img_z_bits,
563 &x0_img_x_bits,
564 x0_img_phase_new == 2,
565 );
566 let mut y0_img_z_bits = x0_img_z_bits;
568 let mut y0_img_x_bits = x0_img_x_bits;
569 let y0_img_phase = string_mul(
570 &mut y0_img_z_bits,
571 &mut y0_img_x_bits,
572 &z0_img_z_bits,
573 &z0_img_x_bits,
574 ) + z0_img_phase_new
575 + x0_img_phase_new
576 + 1;
577 let z1_img_phase_new = (string_mul(
579 &mut z1_img_z_bits,
580 &mut z1_img_x_bits,
581 &y0_img_z_bits,
582 &y0_img_x_bits,
583 ) + z1_img_phase
584 + y0_img_phase)
585 % 4;
586 self.set_packed_image(
587 z1_img_idx,
588 &z1_img_z_bits,
589 &z1_img_x_bits,
590 z1_img_phase_new == 2,
591 );
592 let mut x1_img_z_bits = y1_img_z_bits;
594 let mut x1_img_x_bits = y1_img_x_bits;
595 let x1_img_phase_new = (string_mul(
596 &mut x1_img_z_bits,
597 &mut x1_img_x_bits,
598 &z1_img_z_bits,
599 &z1_img_x_bits,
600 ) + y1_img_phase
601 + z1_img_phase_new
602 + 3)
603 % 4;
604 self.set_packed_image(
605 x1_img_idx,
606 &x1_img_z_bits,
607 &x1_img_x_bits,
608 x1_img_phase_new == 2,
609 );
610 }
611 (Pauli::Y, Pauli::Z) => {
612 let mut phase = string_mul(
614 &mut x1_img_z_bits,
615 &mut x1_img_x_bits,
616 &x0_img_z_bits,
617 &x0_img_x_bits,
618 );
619 phase += string_mul(
620 &mut x1_img_z_bits,
621 &mut x1_img_x_bits,
622 &z0_img_z_bits,
623 &z0_img_x_bits,
624 );
625 phase = (phase + 1) % 4;
626 self.set_packed_image(
627 x1_img_idx,
628 &x1_img_z_bits,
629 &x1_img_x_bits,
630 x1_img_sign_bit ^ z0_img_sign_bit ^ x0_img_sign_bit ^ (phase == 2),
631 );
632 let phase = string_mul(
634 &mut z0_img_z_bits,
635 &mut z0_img_x_bits,
636 &z1_img_z_bits,
637 &z1_img_x_bits,
638 );
639 self.set_packed_image(
640 z0_img_idx,
641 &z0_img_z_bits,
642 &z0_img_x_bits,
643 z0_img_sign_bit ^ z1_img_sign_bit ^ (phase == 2),
644 );
645 let phase = string_mul(
647 &mut x0_img_z_bits,
648 &mut x0_img_x_bits,
649 &z1_img_z_bits,
650 &z1_img_x_bits,
651 );
652 self.set_packed_image(
653 x0_img_idx,
654 &x0_img_z_bits,
655 &x0_img_x_bits,
656 x0_img_sign_bit ^ z1_img_sign_bit ^ (phase == 2),
657 );
658 }
659 (Pauli::Z, Pauli::Z) => {
660 let phase = string_mul(
662 &mut x0_img_z_bits,
663 &mut x0_img_x_bits,
664 &z1_img_z_bits,
665 &z1_img_x_bits,
666 );
667 self.set_packed_image(
668 x0_img_idx,
669 &x0_img_z_bits,
670 &x0_img_x_bits,
671 x0_img_sign_bit ^ z1_img_sign_bit ^ (phase == 2),
672 );
673 let phase = string_mul(
675 &mut x1_img_z_bits,
676 &mut x1_img_x_bits,
677 &z0_img_z_bits,
678 &z0_img_x_bits,
679 );
680 self.set_packed_image(
681 x1_img_idx,
682 &x1_img_z_bits,
683 &x1_img_x_bits,
684 x1_img_sign_bit ^ z0_img_sign_bit ^ (phase == 2),
685 );
686 }
687 _ => panic!("Unexpected TQE gate!"),
688 }
689 }
690
691 fn precompose_half_pi_with(
693 &mut self,
694 axis: Pauli,
695 q: usize,
696 dagger: bool,
697 string_mul: StringMulFn,
698 ) {
699 let z_img_idx = 2 * q;
700 let x_img_idx = 2 * q + 1;
701 let (mut z_img_z_bits, mut z_img_x_bits, z_img_sign_bit) = self.packed_image(z_img_idx);
702 let (mut x_img_z_bits, mut x_img_x_bits, x_img_sign_bit) = self.packed_image(x_img_idx);
703 match axis {
704 Pauli::X => {
705 let mut phase = string_mul(
709 &mut z_img_z_bits,
710 &mut z_img_x_bits,
711 &x_img_z_bits,
712 &x_img_x_bits,
713 );
714 phase = (phase + 1) % 4;
716 self.set_packed_image(
717 z_img_idx,
718 &z_img_z_bits,
719 &z_img_x_bits,
720 z_img_sign_bit ^ x_img_sign_bit ^ (phase == 2) ^ dagger,
721 );
722 }
723 Pauli::Y => {
724 self.set_packed_image(
728 z_img_idx,
729 &x_img_z_bits,
730 &x_img_x_bits,
731 x_img_sign_bit ^ dagger,
732 );
733 self.set_packed_image(
734 x_img_idx,
735 &z_img_z_bits,
736 &z_img_x_bits,
737 !z_img_sign_bit ^ dagger,
738 );
739 }
740 Pauli::Z => {
741 let mut phase = string_mul(
745 &mut x_img_z_bits,
746 &mut x_img_x_bits,
747 &z_img_z_bits,
748 &z_img_x_bits,
749 );
750 phase = (phase + 1) % 4;
752 self.set_packed_image(
753 x_img_idx,
754 &x_img_z_bits,
755 &x_img_x_bits,
756 z_img_sign_bit ^ x_img_sign_bit ^ (phase == 2) ^ dagger,
757 );
758 }
759 _ => panic!("Unexpected rotation axis!"),
760 }
761 }
762
763 fn postcompose_half_pi_with(
765 &mut self,
766 axis: Pauli,
767 q: usize,
768 dagger: bool,
769 apply_half_pi: ApplyHalfPiFn,
770 ) {
771 apply_half_pi(
772 &mut self.qubit_slices_z_bits[q],
773 &mut self.qubit_slices_x_bits[q],
774 &mut self.sign_bits,
775 axis,
776 dagger,
777 );
778 }
779
780 fn postcompose_pauli_with(
782 &mut self,
783 pauli: Pauli,
784 q: usize,
785 x_gate: PauliGateFn,
786 y_gate: PauliGateFn,
787 z_gate: PauliGateFn,
788 ) {
789 match pauli {
790 Pauli::X => x_gate(
791 &self.qubit_slices_z_bits[q],
792 &self.qubit_slices_x_bits[q],
793 &mut self.sign_bits,
794 ),
795 Pauli::Y => y_gate(
796 &self.qubit_slices_z_bits[q],
797 &self.qubit_slices_x_bits[q],
798 &mut self.sign_bits,
799 ),
800 Pauli::Z => z_gate(
801 &self.qubit_slices_z_bits[q],
802 &self.qubit_slices_x_bits[q],
803 &mut self.sign_bits,
804 ),
805 _ => panic!("Unexpected basis gate!"),
806 }
807 }
808
809 fn postcompose_pauli_gadget_with(
811 &mut self,
812 pauli_z_bits: &[u64],
813 pauli_x_bits: &[u64],
814 half_pis: u8,
815 apply_enum_tqe: ApplyEnumTqeFn,
816 apply_half_pi: ApplyHalfPiFn,
817 x_gate: PauliGateFn,
818 y_gate: PauliGateFn,
819 z_gate: PauliGateFn,
820 ) {
821 let half_pis = half_pis % 4;
822 if half_pis == 0 {
823 return;
824 }
825 if half_pis == 2 {
826 for q in 0..self.n_qubits {
827 let word_idx = q / 64;
828 let bit_offset = q % 64;
829 let pauli_z_bit = (pauli_z_bits[word_idx] >> bit_offset) & 1;
830 let pauli_x_bit = (pauli_x_bits[word_idx] >> bit_offset) & 1;
831 if pauli_z_bit == 1 && pauli_x_bit == 1 {
832 y_gate(
833 &self.qubit_slices_z_bits[q],
834 &self.qubit_slices_x_bits[q],
835 &mut self.sign_bits,
836 );
837 } else if pauli_z_bit == 1 && pauli_x_bit == 0 {
838 z_gate(
839 &self.qubit_slices_z_bits[q],
840 &self.qubit_slices_x_bits[q],
841 &mut self.sign_bits,
842 );
843 } else if pauli_z_bit == 0 && pauli_x_bit == 1 {
844 x_gate(
845 &self.qubit_slices_z_bits[q],
846 &self.qubit_slices_x_bits[q],
847 &mut self.sign_bits,
848 );
849 }
850 }
851 return;
852 }
853 let (a, pa) = {
856 let mut result = None;
857 for (input_word_idx, (input_z_word, input_x_word)) in
858 pauli_z_bits.iter().zip(pauli_x_bits).enumerate()
859 {
860 let occupied_bits = input_z_word | input_x_word;
861 let input_bit_offset = occupied_bits.trailing_zeros();
862 if input_bit_offset < 64 {
863 let q = input_word_idx * 64 + input_bit_offset as usize;
864 let pauli_z_bit = (input_z_word >> input_bit_offset) & 1;
865 let pauli_x_bit = (input_x_word >> input_bit_offset) & 1;
866 let pauli = match (pauli_z_bit, pauli_x_bit) {
867 (0, 1) => Pauli::X,
868 (1, 0) => Pauli::Z,
869 (1, 1) => Pauli::Y,
870 _ => panic!("Shouldn't be"),
871 };
872 result = Some((q, pauli));
873 break;
874 }
875 }
876 result.expect("No non-identity Pauli found in the string")
877 };
878 let ga = match pa {
879 Pauli::X => Pauli::Z,
880 Pauli::Z => Pauli::X,
881 Pauli::Y => Pauli::Z,
882 _ => panic!("Shouldn't be"),
883 };
884
885 let mut tqe_gates = Vec::new();
887
888 for b in (a + 1)..self.n_qubits {
890 let word_idx = b / 64;
891 let bit_offset = b % 64;
892 let pauli_z_bit = (pauli_z_bits[word_idx] >> bit_offset) & 1;
893 let pauli_x_bit = (pauli_x_bits[word_idx] >> bit_offset) & 1;
894 let gb = match (pauli_z_bit, pauli_x_bit) {
896 (0, 1) => Pauli::X,
897 (1, 0) => Pauli::Z,
898 (1, 1) => Pauli::Y,
899 _ => continue,
900 };
901
902 tqe_gates.push((a, b, ga, gb));
904
905 let (a_slice_z_bits, b_slice_z_bits) = get_two_mut(&mut self.qubit_slices_z_bits, a, b);
906 let (a_slice_x_bits, b_slice_x_bits) = get_two_mut(&mut self.qubit_slices_x_bits, a, b);
907 apply_enum_tqe(
908 a_slice_z_bits,
909 a_slice_x_bits,
910 b_slice_z_bits,
911 b_slice_x_bits,
912 &mut self.sign_bits,
913 ga,
914 gb,
915 );
916 }
917
918 self.postcompose_half_pi_with(pa, a, half_pis == 3, apply_half_pi);
920 for (qa, qb, ga_rev, gb_rev) in tqe_gates.iter().rev() {
922 let (qa_slice_z_bits, qb_slice_z_bits) =
923 get_two_mut(&mut self.qubit_slices_z_bits, *qa, *qb);
924 let (qa_slice_x_bits, qb_slice_x_bits) =
925 get_two_mut(&mut self.qubit_slices_x_bits, *qa, *qb);
926 apply_enum_tqe(
927 qa_slice_z_bits,
928 qa_slice_x_bits,
929 qb_slice_z_bits,
930 qb_slice_x_bits,
931 &mut self.sign_bits,
932 *ga_rev,
933 *gb_rev,
934 );
935 }
936 }
937
938 fn apply_to_pauli_with(
940 &self,
941 pauli_z_bits: &[u64],
942 pauli_x_bits: &[u64],
943 string_mul: StringMulFn,
944 count_y: CountYFn,
945 ) -> (Vec<u64>, Vec<u64>, bool) {
946 let mut phase: u64 = 0;
947 let mut result_sign_flip = false;
948 let mut result_z_bits = vec![0u64; pauli_z_bits.len()];
949 let mut result_x_bits = vec![0u64; pauli_x_bits.len()];
950 'outer: for (input_word_idx, input_x_word) in pauli_x_bits.iter().enumerate() {
951 let mut remaining_bits = *input_x_word;
952 for _ in 0..input_x_word.count_ones() {
953 let input_bit_offset = remaining_bits.trailing_zeros() as usize;
954 let q = input_word_idx * 64 + input_bit_offset;
955 if q == self.n_qubits {
956 break 'outer;
957 }
958 let (x_img_z_bits, x_img_x_bits, x_img_sign_bit) = self.packed_image(2 * q + 1);
959 result_sign_flip ^= x_img_sign_bit;
960 phase += string_mul(
961 &mut result_z_bits,
962 &mut result_x_bits,
963 &x_img_z_bits,
964 &x_img_x_bits,
965 ) as u64;
966 remaining_bits &= remaining_bits - 1;
967 }
968 }
969 'outer: for (input_word_idx, input_z_word) in pauli_z_bits.iter().enumerate() {
970 let mut remaining_bits = *input_z_word;
971 for _ in 0..input_z_word.count_ones() {
972 let input_bit_offset = remaining_bits.trailing_zeros() as usize;
973 let q = input_word_idx * 64 + input_bit_offset;
974 if q == self.n_qubits {
975 break 'outer;
976 }
977 let (z_img_z_bits, z_img_x_bits, z_img_sign_bit) = self.packed_image(2 * q);
978 result_sign_flip ^= z_img_sign_bit;
979 phase += string_mul(
980 &mut result_z_bits,
981 &mut result_x_bits,
982 &z_img_z_bits,
983 &z_img_x_bits,
984 ) as u64;
985 remaining_bits &= remaining_bits - 1;
986 }
987 }
988 let n_ys = count_y(pauli_z_bits, pauli_x_bits);
990 (
991 result_z_bits,
992 result_x_bits,
993 result_sign_flip ^ ((phase + n_ys) % 4 == 2),
994 )
995 }
996
997 fn apply_to_pauli_mt_with(
1000 &self,
1001 pauli_z_bits: &[u64],
1002 pauli_x_bits: &[u64],
1003 string_mul: StringMulFn,
1004 count_y: CountYFn,
1005 ) -> (Vec<u64>, Vec<u64>, bool) {
1006 let mut x_img_phase: u64 = 0;
1007 let mut x_img_sign_flip = false;
1008 let mut z_img_phase: u64 = 0;
1009 let mut z_img_sign_flip = false;
1010 let mut n_ys: u64 = 0;
1011 let mut x_img_product_z_bits = vec![0u64; pauli_z_bits.len()];
1012 let mut x_img_product_x_bits = vec![0u64; pauli_x_bits.len()];
1013 let mut z_img_product_z_bits = vec![0u64; pauli_z_bits.len()];
1014 let mut z_img_product_x_bits = vec![0u64; pauli_x_bits.len()];
1015 rayon::scope(|s| {
1016 s.spawn(|_| {
1017 'outer: for (input_word_idx, input_x_word) in pauli_x_bits.iter().enumerate() {
1018 let mut remaining_bits = *input_x_word;
1019 for _ in 0..input_x_word.count_ones() {
1020 let input_bit_offset = remaining_bits.trailing_zeros() as usize;
1021 let q = input_word_idx * 64 + input_bit_offset;
1022 if q == self.n_qubits {
1023 break 'outer;
1024 }
1025 let (x_img_z_bits, x_img_x_bits, x_img_sign_bit) =
1026 self.packed_image(2 * q + 1);
1027 x_img_sign_flip ^= x_img_sign_bit;
1028 x_img_phase += string_mul(
1029 &mut x_img_product_z_bits,
1030 &mut x_img_product_x_bits,
1031 &x_img_z_bits,
1032 &x_img_x_bits,
1033 ) as u64;
1034 remaining_bits &= remaining_bits - 1;
1035 }
1036 }
1037 });
1038 s.spawn(|_| {
1039 'outer: for (input_word_idx, input_z_word) in pauli_z_bits.iter().enumerate() {
1040 let mut remaining_bits = *input_z_word;
1041 for _ in 0..input_z_word.count_ones() {
1042 let input_bit_offset = remaining_bits.trailing_zeros() as usize;
1043 let q = input_word_idx * 64 + input_bit_offset;
1044 if q == self.n_qubits {
1045 break 'outer;
1046 }
1047 let (z_img_z_bits, z_img_x_bits, z_img_sign_bit) = self.packed_image(2 * q);
1048 z_img_sign_flip ^= z_img_sign_bit;
1049 z_img_phase += string_mul(
1050 &mut z_img_product_z_bits,
1051 &mut z_img_product_x_bits,
1052 &z_img_z_bits,
1053 &z_img_x_bits,
1054 ) as u64;
1055 remaining_bits &= remaining_bits - 1;
1056 }
1057 }
1058 });
1059 s.spawn(|_| {
1060 n_ys = count_y(pauli_z_bits, pauli_x_bits);
1061 });
1062 });
1063 let phase = string_mul(
1064 &mut x_img_product_z_bits,
1065 &mut x_img_product_x_bits,
1066 &z_img_product_z_bits,
1067 &z_img_product_x_bits,
1068 ) as u64;
1069 (
1071 x_img_product_z_bits,
1072 x_img_product_x_bits,
1073 x_img_sign_flip
1074 ^ z_img_sign_flip
1075 ^ ((x_img_phase + z_img_phase + phase + n_ys) % 4 == 2),
1076 )
1077 }
1078
1079 fn invert_with<F, G>(&self, apply_fn: F, apply_mt_fn: G) -> Tableau
1081 where
1082 F: Fn(&Tableau, &[u64], &[u64]) -> (Vec<u64>, Vec<u64>, bool) + Copy,
1083 G: Fn(&Tableau, &[u64], &[u64]) -> (Vec<u64>, Vec<u64>, bool) + Copy,
1084 {
1085 let n_images = self.n_qubits * 2;
1086 let slice_word_len = n_images.div_ceil(64);
1087 let mut inv_slices_z_bits: Vec<Vec<u64>> = Vec::with_capacity(self.n_qubits);
1088 let mut inv_slices_x_bits: Vec<Vec<u64>> = Vec::with_capacity(self.n_qubits);
1089 for input_q in 0..self.n_qubits {
1091 let img_word_idx = (2 * input_q) / 64;
1092 let z_img_bit_offset = (2 * input_q) % 64;
1093 let x_img_bit_offset = z_img_bit_offset + 1;
1094 let mut inv_slice_z_bits: Vec<u64> = Vec::with_capacity(slice_word_len);
1095 let mut inv_slice_x_bits: Vec<u64> = Vec::with_capacity(slice_word_len);
1096 let mut inv_slice_z_word: u64 = 0;
1097 let mut inv_slice_x_word: u64 = 0;
1098 let mut bits_filled = 0;
1099
1100 for output_q in 0..self.n_qubits {
1101 let slice_z_word = self.qubit_slices_z_bits[output_q][img_word_idx];
1102 let slice_x_word = self.qubit_slices_x_bits[output_q][img_word_idx];
1103 let z_img_z_bit = (slice_z_word >> z_img_bit_offset) & 0b1;
1104 let x_img_z_bit = (slice_z_word >> x_img_bit_offset) & 0b1;
1105 let z_img_x_bit = (slice_x_word >> z_img_bit_offset) & 0b1;
1106 let x_img_x_bit = (slice_x_word >> x_img_bit_offset) & 0b1;
1107
1108 inv_slice_x_word |= z_img_x_bit << bits_filled;
1109 inv_slice_x_word |= z_img_z_bit << (bits_filled + 1);
1110
1111 inv_slice_z_word |= x_img_x_bit << bits_filled;
1112 inv_slice_z_word |= x_img_z_bit << (bits_filled + 1);
1113 bits_filled += 2;
1114 if bits_filled == 64 {
1115 inv_slice_z_bits.push(inv_slice_z_word);
1116 inv_slice_x_bits.push(inv_slice_x_word);
1117 inv_slice_z_word = 0;
1118 inv_slice_x_word = 0;
1119 bits_filled = 0;
1120 }
1121 }
1122 if bits_filled > 0 {
1123 inv_slice_z_bits.push(inv_slice_z_word);
1124 inv_slice_x_bits.push(inv_slice_x_word);
1125 }
1126 inv_slices_z_bits.push(inv_slice_z_bits);
1127 inv_slices_x_bits.push(inv_slice_x_bits);
1128 }
1129 let mut tab_inv = Self {
1130 qubit_slices_z_bits: inv_slices_z_bits,
1131 qubit_slices_x_bits: inv_slices_x_bits,
1132 sign_bits: vec![0; self.sign_bits.len()],
1133 n_qubits: self.n_qubits,
1134 };
1135
1136 for q in 0..self.n_qubits {
1138 let (z_img_z_bits, z_img_x_bits, _) = tab_inv.packed_image(2 * q);
1139 let (x_img_z_bits, x_img_x_bits, _) = tab_inv.packed_image(2 * q + 1);
1140 let (z_img_sign_bit, x_img_sign_bit) = if self.n_qubits >= MT_THRESH {
1141 let (_, _, z_img_sign_bit) = apply_mt_fn(self, &z_img_z_bits, &z_img_x_bits);
1142 let (_, _, x_img_sign_bit) = apply_mt_fn(self, &x_img_z_bits, &x_img_x_bits);
1143 (z_img_sign_bit, x_img_sign_bit)
1144 } else {
1145 let (_, _, z_img_sign_bit) = apply_fn(self, &z_img_z_bits, &z_img_x_bits);
1146 let (_, _, x_img_sign_bit) = apply_fn(self, &x_img_z_bits, &x_img_x_bits);
1147 (z_img_sign_bit, x_img_sign_bit)
1148 };
1149 tab_inv.set_sign_bit(2 * q, z_img_sign_bit);
1150 tab_inv.set_sign_bit(2 * q + 1, x_img_sign_bit);
1151 }
1152
1153 tab_inv
1154 }
1155
1156 fn compose_with<F, G>(&mut self, other: &Tableau, apply_fn: F, apply_mt_fn: G)
1158 where
1159 F: Fn(&Tableau, &[u64], &[u64]) -> (Vec<u64>, Vec<u64>, bool) + Copy,
1160 G: Fn(&Tableau, &[u64], &[u64]) -> (Vec<u64>, Vec<u64>, bool) + Copy,
1161 {
1162 if self.n_qubits != other.n_qubits {
1163 panic!("Cannot compose tableaux with different numbers of qubits");
1164 }
1165 for q in 0..self.n_qubits {
1166 let z_img_idx = 2 * q;
1167 let x_img_idx = 2 * q + 1;
1168 let (mut z_img_z_bits, mut z_img_x_bits, z_img_sign_bit) = self.packed_image(z_img_idx);
1169 let (mut x_img_z_bits, mut x_img_x_bits, x_img_sign_bit) = self.packed_image(x_img_idx);
1170 let (z_img_z_bits_new, z_img_x_bits_new, z_img_sign_bit_new) =
1171 if self.n_qubits >= MT_THRESH {
1172 apply_mt_fn(other, &mut z_img_z_bits, &mut z_img_x_bits)
1173 } else {
1174 apply_fn(other, &mut z_img_z_bits, &mut z_img_x_bits)
1175 };
1176 let (x_img_z_bits_new, x_img_x_bits_new, x_img_sign_bit_new) =
1177 if self.n_qubits >= MT_THRESH {
1178 apply_mt_fn(other, &mut x_img_z_bits, &mut x_img_x_bits)
1179 } else {
1180 apply_fn(other, &mut x_img_z_bits, &mut x_img_x_bits)
1181 };
1182
1183 self.set_packed_image(
1184 z_img_idx,
1185 &z_img_z_bits_new,
1186 &z_img_x_bits_new,
1187 z_img_sign_bit_new ^ z_img_sign_bit,
1188 );
1189 self.set_packed_image(
1190 x_img_idx,
1191 &x_img_z_bits_new,
1192 &x_img_x_bits_new,
1193 x_img_sign_bit_new ^ x_img_sign_bit,
1194 );
1195 }
1196 }
1197
1198 pub fn from_packed_qubit_slices(
1212 qubit_slices_z_bits: Vec<Vec<u64>>,
1213 qubit_slices_x_bits: Vec<Vec<u64>>,
1214 sign_bits: Vec<u64>,
1215 n_qubits: usize,
1216 ) -> Self {
1217 Self {
1218 qubit_slices_z_bits,
1219 qubit_slices_x_bits,
1220 sign_bits,
1221 n_qubits,
1222 }
1223 }
1224
1225 pub fn eye(n_qubits: usize) -> Self {
1227 let n_images = n_qubits * 2;
1228 let mut qubit_slices_z_bits = Vec::with_capacity(n_qubits);
1229 let mut qubit_slices_x_bits = Vec::with_capacity(n_qubits);
1230 for q in 0..n_qubits {
1231 let mut paulis = vec![Pauli::I; n_images];
1232 paulis[2 * q] = Pauli::Z;
1233 paulis[2 * q + 1] = Pauli::X;
1234 let (slice_z_bits, slice_x_bits) = paulis_to_u64s(&paulis);
1235 qubit_slices_z_bits.push(slice_z_bits);
1236 qubit_slices_x_bits.push(slice_x_bits);
1237 }
1238 let n_words = n_images.div_ceil(64);
1239 Self {
1240 qubit_slices_z_bits,
1241 qubit_slices_x_bits,
1242 sign_bits: vec![0; n_words],
1243 n_qubits,
1244 }
1245 }
1246
1247 pub fn random(n_qubits: usize, seed: u32, n_half_pi: u32, n_tqe: u32) -> Self {
1250 let mut tableau = Tableau::eye(n_qubits);
1251 let mut rng = StdRng::seed_from_u64(seed as u64);
1252
1253 for _ in 0..n_half_pi {
1255 let axis = match rng.random_range(0..3) {
1256 0 => Pauli::X,
1257 1 => Pauli::Y,
1258 _ => Pauli::Z,
1259 };
1260 let q = rng.random_range(0..n_qubits);
1261 tableau.postcompose_half_pi(axis, q, false);
1262 }
1263 if n_qubits == 1 {
1265 return tableau;
1266 }
1267 for i in 0..n_qubits - 1 {
1269 let g0 = match rng.random_range(0..3) {
1270 0 => Pauli::X,
1271 1 => Pauli::Y,
1272 _ => Pauli::Z,
1273 };
1274 let g1 = match rng.random_range(0..3) {
1275 0 => Pauli::X,
1276 1 => Pauli::Y,
1277 _ => Pauli::Z,
1278 };
1279 tableau.postcompose_tqe(g0, g1, i, i + 1);
1280 }
1281 for _ in 0..n_tqe {
1282 let q0 = rng.random_range(0..n_qubits);
1283 let mut q1 = rng.random_range(0..n_qubits - 1);
1284 if q1 >= q0 {
1285 q1 += 1;
1286 }
1287 let g0 = match rng.random_range(0..3) {
1288 0 => Pauli::X,
1289 1 => Pauli::Y,
1290 _ => Pauli::Z,
1291 };
1292 let g1 = match rng.random_range(0..3) {
1293 0 => Pauli::X,
1294 1 => Pauli::Y,
1295 _ => Pauli::Z,
1296 };
1297 tableau.postcompose_tqe(g0, g1, q0, q1);
1298 }
1299 tableau
1300 }
1301
1302 fn packed_image(&self, img_idx: usize) -> (Vec<u64>, Vec<u64>, bool) {
1305 let img_word_idx = img_idx / 64;
1306 let img_bit_offset = img_idx % 64;
1307 let n_words = self.n_qubits.div_ceil(64);
1308 let mut img_z_word = 0;
1309 let mut img_x_word = 0;
1310 let mut bits_filled = 0;
1311 let mut img_z_bits = Vec::with_capacity(n_words);
1312 let mut img_x_bits = Vec::with_capacity(n_words);
1313
1314 for output_q in 0..self.n_qubits {
1315 let img_z_bit =
1316 (self.qubit_slices_z_bits[output_q][img_word_idx] >> img_bit_offset) & 1;
1317 let img_x_bit =
1318 (self.qubit_slices_x_bits[output_q][img_word_idx] >> img_bit_offset) & 1;
1319 img_z_word |= img_z_bit << bits_filled;
1320 img_x_word |= img_x_bit << bits_filled;
1321 bits_filled += 1;
1322 if bits_filled == 64 {
1323 img_z_bits.push(img_z_word);
1324 img_x_bits.push(img_x_word);
1325 bits_filled = 0;
1326 img_z_word = 0;
1327 img_x_word = 0;
1328 }
1329 }
1330 if bits_filled > 0 {
1331 img_z_bits.push(img_z_word);
1332 img_x_bits.push(img_x_word);
1333 }
1334 (
1335 img_z_bits,
1336 img_x_bits,
1337 (self.sign_bits[img_word_idx] >> img_bit_offset & 1 == 1),
1338 )
1339 }
1340
1341 fn set_packed_image(
1343 &mut self,
1344 img_idx: usize,
1345 img_z_bits: &[u64],
1346 img_x_bits: &[u64],
1347 img_sign_bit: bool,
1348 ) {
1349 let img_word_idx = img_idx / 64;
1350 let img_bit_offset = img_idx % 64;
1351 for output_q in 0..self.n_qubits {
1352 let output_word_idx = output_q / 64;
1353 let output_bit_offset = output_q % 64;
1354 let img_z_bit = (img_z_bits[output_word_idx] >> output_bit_offset) & 1;
1355 let img_x_bit = (img_x_bits[output_word_idx] >> output_bit_offset) & 1;
1356 self.qubit_slices_z_bits[output_q][img_word_idx] &= !(1 << img_bit_offset);
1357 self.qubit_slices_z_bits[output_q][img_word_idx] |= img_z_bit << img_bit_offset;
1358 self.qubit_slices_x_bits[output_q][img_word_idx] &= !(1 << img_bit_offset);
1359 self.qubit_slices_x_bits[output_q][img_word_idx] |= img_x_bit << img_bit_offset;
1360 }
1361 if img_sign_bit {
1362 self.sign_bits[img_word_idx] |= 1 << img_bit_offset;
1363 } else {
1364 self.sign_bits[img_word_idx] &= !(1 << img_bit_offset);
1365 }
1366 }
1367 fn flip_sign(&mut self, img_idx: usize) {
1369 let img_word_idx = img_idx / 64;
1370 let img_bit_offset = img_idx % 64;
1371 self.sign_bits[img_word_idx] ^= 1 << img_bit_offset;
1372 }
1373 fn set_sign_bit(&mut self, img_idx: usize, img_sign_bit: bool) {
1375 let img_word_idx = img_idx / 64;
1376 let img_bit_offset = img_idx % 64;
1377 if img_sign_bit {
1378 self.sign_bits[img_word_idx] |= 1 << img_bit_offset;
1379 } else {
1380 self.sign_bits[img_word_idx] &= !(1 << img_bit_offset);
1381 }
1382 }
1383
1384 pub fn postcompose_tqe(&mut self, g0: Pauli, g1: Pauli, q0: usize, q1: usize) {
1399 check_distinct_qubits(q0, q1);
1400 self.postcompose_tqe_with(
1401 g0,
1402 g1,
1403 q0,
1404 q1,
1405 slice_xx_gate,
1406 slice_xy_gate,
1407 slice_xz_gate,
1408 slice_yy_gate,
1409 slice_yz_gate,
1410 slice_zz_gate,
1411 );
1412 }
1413
1414 pub fn precompose_tqe(&mut self, g0: Pauli, g1: Pauli, q0: usize, q1: usize) {
1429 check_distinct_qubits(q0, q1);
1430 self.precompose_tqe_with(g0, g1, q0, q1, string_mul);
1431 }
1432
1433 pub fn precompose_half_pi(&mut self, axis: Pauli, q: usize, dagger: bool) {
1445 self.precompose_half_pi_with(axis, q, dagger, string_mul);
1446 }
1447
1448 pub fn precompose_pauli(&mut self, p: Pauli, q: usize) {
1459 let z_img_idx = 2 * q;
1460 let x_img_idx = 2 * q + 1;
1461 match p {
1462 Pauli::X => {
1463 self.flip_sign(z_img_idx);
1464 }
1465 Pauli::Y => {
1466 self.flip_sign(z_img_idx);
1467 self.flip_sign(x_img_idx);
1468 }
1469 Pauli::Z => {
1470 self.flip_sign(x_img_idx);
1471 }
1472 _ => panic!("Unexpected Pauli!"),
1473 }
1474 }
1475
1476 pub fn precompose_swap(&mut self, q0: usize, q1: usize) {
1484 let (z0_img_z_bits, z0_img_x_bits, z0_img_sign_bit) = self.packed_image(2 * q0);
1485 let (z1_img_z_bits, z1_img_x_bits, z1_img_sign_bit) = self.packed_image(2 * q1);
1486 let (x0_img_z_bits, x0_img_x_bits, x0_img_sign_bit) = self.packed_image(2 * q0 + 1);
1487 let (x1_img_z_bits, x1_img_x_bits, x1_img_sign_bit) = self.packed_image(2 * q1 + 1);
1488 self.set_packed_image(2 * q0, &z1_img_z_bits, &z1_img_x_bits, z1_img_sign_bit);
1489 self.set_packed_image(2 * q1, &z0_img_z_bits, &z0_img_x_bits, z0_img_sign_bit);
1490 self.set_packed_image(2 * q0 + 1, &x1_img_z_bits, &x1_img_x_bits, x1_img_sign_bit);
1491 self.set_packed_image(2 * q1 + 1, &x0_img_z_bits, &x0_img_x_bits, x0_img_sign_bit);
1492 }
1493
1494 pub fn postcompose_swap(&mut self, q0: usize, q1: usize) {
1502 self.qubit_slices_z_bits.swap(q0, q1);
1503 self.qubit_slices_x_bits.swap(q0, q1);
1504 }
1505
1506 pub fn postcompose_half_pi(&mut self, axis: Pauli, q: usize, dagger: bool) {
1515 self.postcompose_half_pi_with(axis, q, dagger, apply_half_pi_gate_slice);
1516 }
1517
1518 pub fn precompose_h(&mut self, q: usize) {
1525 let z_img_idx = 2 * q;
1526 let x_img_idx = 2 * q + 1;
1527 let (z_img_z_bits, z_img_x_bits, z_img_sign_bit) = self.packed_image(z_img_idx);
1528 let (x_img_z_bits, x_img_x_bits, x_img_sign_bit) = self.packed_image(x_img_idx);
1529 self.set_packed_image(z_img_idx, &x_img_z_bits, &x_img_x_bits, x_img_sign_bit);
1530 self.set_packed_image(x_img_idx, &z_img_z_bits, &z_img_x_bits, z_img_sign_bit);
1531 }
1532
1533 pub fn postcompose_h(&mut self, q: usize) {
1540 slice_h_gate(
1541 &mut self.qubit_slices_z_bits[q],
1542 &mut self.qubit_slices_x_bits[q],
1543 &mut self.sign_bits,
1544 );
1545 }
1546
1547 pub fn postcompose_pauli_gadget(
1561 &mut self,
1562 pauli_z_bits: &[u64],
1563 pauli_x_bits: &[u64],
1564 half_pis: u8,
1565 ) {
1566 self.postcompose_pauli_gadget_with(
1567 pauli_z_bits,
1568 pauli_x_bits,
1569 half_pis,
1570 apply_enum_tqe_slice,
1571 apply_half_pi_gate_slice,
1572 slice_x_gate,
1573 slice_y_gate,
1574 slice_z_gate,
1575 );
1576 }
1577
1578 pub fn apply_to_pauli(
1593 &self,
1594 pauli_z_bits: &[u64],
1595 pauli_x_bits: &[u64],
1596 ) -> (Vec<u64>, Vec<u64>, bool) {
1597 self.apply_to_pauli_with(pauli_z_bits, pauli_x_bits, string_mul, count_y)
1598 }
1599
1600 pub fn apply_to_pauli_mt(
1604 &self,
1605 pauli_z_bits: &[u64],
1606 pauli_x_bits: &[u64],
1607 ) -> (Vec<u64>, Vec<u64>, bool) {
1608 self.apply_to_pauli_mt_with(pauli_z_bits, pauli_x_bits, string_mul, count_y)
1609 }
1610
1611 pub fn invert(&self) -> Tableau {
1614 self.invert_with(Tableau::apply_to_pauli, Tableau::apply_to_pauli_mt)
1615 }
1616
1617 pub fn compose(&mut self, other: &Tableau) {
1621 self.compose_with(other, Tableau::apply_to_pauli, Tableau::apply_to_pauli_mt);
1622 }
1623
1624 pub fn postcompose_pauli(&mut self, pauli: Pauli, q: usize) {
1630 self.postcompose_pauli_with(pauli, q, slice_x_gate, slice_y_gate, slice_z_gate);
1631 }
1632
1633 pub fn x_image(&self, input_qubit: usize) -> (Vec<Pauli>, bool) {
1635 let (x_img_z_bits, x_img_x_bits, x_img_sign_bit) = self.packed_image(2 * input_qubit + 1);
1636 (
1637 u64s_to_paulis(&x_img_z_bits, &x_img_x_bits, self.n_qubits),
1638 x_img_sign_bit,
1639 )
1640 }
1641
1642 pub fn z_image(&self, input_qubit: usize) -> (Vec<Pauli>, bool) {
1644 let (z_img_z_bits, z_img_x_bits, z_img_sign_bit) = self.packed_image(2 * input_qubit);
1645 (
1646 u64s_to_paulis(&z_img_z_bits, &z_img_x_bits, self.n_qubits),
1647 z_img_sign_bit,
1648 )
1649 }
1650}
1651
1652#[cfg(feature = "unstable_simd")]
1654pub trait SimdTableau {
1655 fn postcompose_tqe_simd<const N: usize>(&mut self, g0: Pauli, g1: Pauli, q0: usize, q1: usize);
1661 fn precompose_tqe_simd<const N: usize>(&mut self, g0: Pauli, g1: Pauli, q0: usize, q1: usize);
1667 fn precompose_half_pi_simd<const N: usize>(&mut self, axis: Pauli, q: usize, dagger: bool);
1673 fn postcompose_half_pi_simd<const N: usize>(&mut self, axis: Pauli, q: usize, dagger: bool);
1675 fn postcompose_pauli_gadget_simd<const N: usize>(
1681 &mut self,
1682 pauli_z_bits: &[u64],
1683 pauli_x_bits: &[u64],
1684 half_pis: u8,
1685 );
1686 fn apply_to_pauli_simd<const N: usize>(
1688 &self,
1689 pauli_z_bits: &[u64],
1690 pauli_x_bits: &[u64],
1691 ) -> (Vec<u64>, Vec<u64>, bool);
1692 fn apply_to_pauli_mt_simd<const N: usize>(
1697 &self,
1698 pauli_z_bits: &[u64],
1699 pauli_x_bits: &[u64],
1700 ) -> (Vec<u64>, Vec<u64>, bool);
1701 fn invert_simd<const N: usize>(&self) -> Tableau;
1703 fn compose_simd<const N: usize>(&mut self, other: &Tableau);
1705 fn postcompose_pauli_simd<const N: usize>(&mut self, pauli: Pauli, q: usize);
1711
1712 fn postcompose_h_simd<const N: usize>(&mut self, q: usize);
1714}
1715
1716#[cfg(feature = "unstable_simd")]
1717impl SimdTableau for Tableau {
1718 fn postcompose_tqe_simd<const N: usize>(&mut self, g0: Pauli, g1: Pauli, q0: usize, q1: usize) {
1719 check_distinct_qubits(q0, q1);
1720 self.postcompose_tqe_with(
1721 g0,
1722 g1,
1723 q0,
1724 q1,
1725 simd_xx_gate::<N>,
1726 simd_xy_gate::<N>,
1727 simd_xz_gate::<N>,
1728 simd_yy_gate::<N>,
1729 simd_yz_gate::<N>,
1730 simd_zz_gate::<N>,
1731 );
1732 }
1733
1734 fn precompose_tqe_simd<const N: usize>(&mut self, g0: Pauli, g1: Pauli, q0: usize, q1: usize) {
1735 check_distinct_qubits(q0, q1);
1736 self.precompose_tqe_with(g0, g1, q0, q1, simd_string_mul::<N>);
1737 }
1738
1739 fn precompose_half_pi_simd<const N: usize>(&mut self, axis: Pauli, q: usize, dagger: bool) {
1740 self.precompose_half_pi_with(axis, q, dagger, simd_string_mul::<N>);
1741 }
1742
1743 fn postcompose_half_pi_simd<const N: usize>(&mut self, axis: Pauli, q: usize, dagger: bool) {
1744 self.postcompose_half_pi_with(axis, q, dagger, apply_half_pi_gate_simd::<N>);
1745 }
1746
1747 fn postcompose_pauli_gadget_simd<const N: usize>(
1748 &mut self,
1749 pauli_z_bits: &[u64],
1750 pauli_x_bits: &[u64],
1751 half_pis: u8,
1752 ) {
1753 self.postcompose_pauli_gadget_with(
1754 pauli_z_bits,
1755 pauli_x_bits,
1756 half_pis,
1757 apply_enum_tqe_simd::<N>,
1758 apply_half_pi_gate_simd::<N>,
1759 simd_x_gate::<N>,
1760 simd_y_gate::<N>,
1761 simd_z_gate::<N>,
1762 );
1763 }
1764
1765 fn apply_to_pauli_simd<const N: usize>(
1766 &self,
1767 pauli_z_bits: &[u64],
1768 pauli_x_bits: &[u64],
1769 ) -> (Vec<u64>, Vec<u64>, bool) {
1770 self.apply_to_pauli_with(
1771 pauli_z_bits,
1772 pauli_x_bits,
1773 simd_string_mul::<N>,
1774 simd_count_y::<N>,
1775 )
1776 }
1777
1778 fn apply_to_pauli_mt_simd<const N: usize>(
1779 &self,
1780 pauli_z_bits: &[u64],
1781 pauli_x_bits: &[u64],
1782 ) -> (Vec<u64>, Vec<u64>, bool) {
1783 self.apply_to_pauli_mt_with(
1784 pauli_z_bits,
1785 pauli_x_bits,
1786 simd_string_mul::<N>,
1787 simd_count_y::<N>,
1788 )
1789 }
1790
1791 fn invert_simd<const N: usize>(&self) -> Tableau {
1792 self.invert_with(
1793 SimdTableau::apply_to_pauli_simd::<N>,
1794 SimdTableau::apply_to_pauli_mt_simd::<N>,
1795 )
1796 }
1797
1798 fn compose_simd<const N: usize>(&mut self, other: &Tableau) {
1799 self.compose_with(
1800 other,
1801 SimdTableau::apply_to_pauli_simd::<N>,
1802 SimdTableau::apply_to_pauli_mt_simd::<N>,
1803 );
1804 }
1805
1806 fn postcompose_pauli_simd<const N: usize>(&mut self, pauli: Pauli, q: usize) {
1807 self.postcompose_pauli_with(
1808 pauli,
1809 q,
1810 simd_x_gate::<N>,
1811 simd_y_gate::<N>,
1812 simd_z_gate::<N>,
1813 );
1814 }
1815
1816 fn postcompose_h_simd<const N: usize>(&mut self, q: usize) {
1817 simd_h_gate::<N>(
1818 &mut self.qubit_slices_z_bits[q],
1819 &mut self.qubit_slices_x_bits[q],
1820 &mut self.sign_bits,
1821 );
1822 }
1823}
1824
1825#[cfg(test)]
1826mod tests {
1827 use super::*;
1828 #[cfg(feature = "unstable_simd")]
1829 use crate::SimdTableau;
1830 use rand::RngExt;
1831 #[cfg(feature = "unstable_simd")]
1832 use tk_pg_bitpacked::apply_enum_tqe_simd;
1833 use tk_pg_bitpacked::apply_enum_tqe_slice;
1834
1835 fn random_tqes(
1836 n_qubits: usize,
1837 k: usize,
1838 rng: &mut StdRng,
1839 ) -> Vec<(Pauli, Pauli, usize, usize)> {
1840 (0..k)
1841 .map(|_| {
1842 let q0 = rng.random_range(0..n_qubits);
1843 let mut q1 = rng.random_range(0..n_qubits - 1);
1844 if q1 >= q0 {
1845 q1 += 1;
1846 }
1847 let g0 = match rng.random_range(0..3) {
1848 0 => Pauli::X,
1849 1 => Pauli::Y,
1850 _ => Pauli::Z,
1851 };
1852 let g1 = match rng.random_range(0..3) {
1853 0 => Pauli::X,
1854 1 => Pauli::Y,
1855 _ => Pauli::Z,
1856 };
1857 (g0, g1, q0, q1)
1858 })
1859 .collect()
1860 }
1861 fn random_half_pi_rotations(
1862 n_qubits: usize,
1863 k: usize,
1864 rng: &mut StdRng,
1865 ) -> Vec<(Pauli, usize)> {
1866 (0..k)
1867 .map(|_| {
1868 let q = rng.random_range(0..n_qubits);
1869 let axis = match rng.random_range(0..3) {
1870 0 => Pauli::X,
1871 1 => Pauli::Y,
1872 _ => Pauli::Z,
1873 };
1874 (axis, q)
1875 })
1876 .collect()
1877 }
1878
1879 fn tableau_invert_roundtrip_body(
1882 invert: impl Fn(&Tableau) -> Tableau,
1883 compose: impl Fn(&mut Tableau, &Tableau),
1884 ) {
1885 for n_qubits in [5, 70] {
1886 for seed in 0..10 {
1887 let tab = Tableau::random(n_qubits, seed, 100, 100);
1888 let tab_inv = invert(&tab);
1889 assert_eq!(invert(&tab_inv), tab);
1890
1891 let mut tab_then_inv = tab.clone();
1892 compose(&mut tab_then_inv, &tab_inv);
1893 assert_eq!(tab_then_inv, Tableau::eye(n_qubits));
1894
1895 let mut inv_then_tab = tab_inv;
1896 compose(&mut inv_then_tab, &tab);
1897 assert_eq!(inv_then_tab, Tableau::eye(n_qubits));
1898 }
1899 }
1900 }
1901
1902 #[test]
1903 fn test_tableau_invert_roundtrip() {
1904 tableau_invert_roundtrip_body(Tableau::invert, Tableau::compose);
1905 }
1906
1907 #[cfg(feature = "unstable_simd")]
1908 #[test]
1909 fn test_tableau_invert_roundtrip_simd() {
1910 tableau_invert_roundtrip_body(Tableau::invert_simd::<64>, Tableau::compose_simd::<64>);
1911 }
1912
1913 fn tqe_precompose_postcompose_body(
1916 precompose: impl Fn(&mut Tableau, Pauli, Pauli, usize, usize),
1917 postcompose: impl Fn(&mut Tableau, Pauli, Pauli, usize, usize),
1918 ) {
1919 let mut rng = StdRng::seed_from_u64(0);
1920 for (n_qubits, n_tqes) in [(5, 100), (100, 1000)] {
1921 let mut tab = Tableau::eye(n_qubits);
1922 let mut tab2 = Tableau::eye(n_qubits);
1923 let gates = random_tqes(n_qubits, n_tqes, &mut rng);
1924 for &(g0, g1, q0, q1) in gates.iter() {
1925 precompose(&mut tab, g0, g1, q0, q1);
1926 }
1927 for &(g0, g1, q0, q1) in gates.iter().rev() {
1928 postcompose(&mut tab2, g0, g1, q0, q1);
1929 }
1930 assert_eq!(tab, tab2);
1931 }
1932 }
1933
1934 #[test]
1935 fn test_tqe_precompose_postcompose_matches() {
1936 tqe_precompose_postcompose_body(Tableau::precompose_tqe, Tableau::postcompose_tqe);
1937 }
1938
1939 #[cfg(feature = "unstable_simd")]
1940 #[test]
1941 fn test_tqe_simd_precompose_postcompose_matches() {
1942 tqe_precompose_postcompose_body(
1943 Tableau::precompose_tqe_simd::<64>,
1944 Tableau::postcompose_tqe_simd::<64>,
1945 );
1946 }
1947
1948 fn half_pi_precompose_postcompose_body(
1952 precompose: impl Fn(&mut Tableau, Pauli, usize, bool),
1953 postcompose: impl Fn(&mut Tableau, Pauli, usize, bool),
1954 ) {
1955 let mut rng = StdRng::seed_from_u64(0);
1956 for (n_qubits, n_gates) in [(5, 100), (100, 1000)] {
1957 let gates = random_half_pi_rotations(n_qubits, n_gates, &mut rng);
1958 for dagger in [false, true] {
1959 let mut tab = Tableau::eye(n_qubits);
1960 let mut tab2 = Tableau::eye(n_qubits);
1961 for &(axis, q) in gates.iter() {
1962 precompose(&mut tab, axis, q, dagger);
1963 }
1964 for &(axis, q) in gates.iter().rev() {
1965 postcompose(&mut tab2, axis, q, dagger);
1966 }
1967 assert_eq!(tab, tab2);
1968 }
1969 }
1970 }
1971
1972 #[test]
1973 fn test_half_pi_precompose_postcompose_matches() {
1974 half_pi_precompose_postcompose_body(
1975 Tableau::precompose_half_pi,
1976 Tableau::postcompose_half_pi,
1977 );
1978 }
1979
1980 #[cfg(feature = "unstable_simd")]
1981 #[test]
1982 fn test_half_pi_simd_precompose_postcompose_matches() {
1983 half_pi_precompose_postcompose_body(
1984 Tableau::precompose_half_pi_simd::<64>,
1985 Tableau::postcompose_half_pi_simd::<64>,
1986 );
1987 }
1988
1989 fn compose_body(
1991 precompose_half_pi: impl Fn(&mut Tableau, Pauli, usize, bool),
1992 precompose_tqe: impl Fn(&mut Tableau, Pauli, Pauli, usize, usize),
1993 compose: impl Fn(&mut Tableau, &Tableau),
1994 ) {
1995 let mut rng = StdRng::seed_from_u64(0);
1996
1997 for (n_qubits, n_tqes, n_half_pi) in [(5, 100, 100), (100, 1000, 1000)] {
1998 let mut sqc_gates = random_half_pi_rotations(n_qubits, n_half_pi, &mut rng);
1999 let mut tqes = random_tqes(n_qubits, n_tqes, &mut rng);
2000 let sqc_gates2 = sqc_gates.split_off(50);
2001 let tqes2 = tqes.split_off(50);
2002 let mut tab1 = Tableau::eye(n_qubits);
2003 let mut tab2 = Tableau::eye(n_qubits);
2004 let mut tab3 = Tableau::eye(n_qubits);
2005 for &(axis, q) in sqc_gates.iter() {
2006 precompose_half_pi(&mut tab1, axis, q, false);
2007 precompose_half_pi(&mut tab3, axis, q, false);
2008 }
2009 for &(g0, g1, q0, q1) in tqes.iter() {
2010 precompose_tqe(&mut tab1, g0, g1, q0, q1);
2011 precompose_tqe(&mut tab3, g0, g1, q0, q1);
2012 }
2013 for &(axis, q) in sqc_gates2.iter() {
2014 precompose_half_pi(&mut tab2, axis, q, false);
2015 precompose_half_pi(&mut tab3, axis, q, false);
2016 }
2017 for &(g0, g1, q0, q1) in tqes2.iter() {
2018 precompose_tqe(&mut tab2, g0, g1, q0, q1);
2019 precompose_tqe(&mut tab3, g0, g1, q0, q1);
2020 }
2021 compose(&mut tab2, &tab1);
2022 assert_eq!(tab2, tab3);
2023 }
2024 }
2025
2026 #[test]
2027 fn test_compose() {
2028 compose_body(
2029 Tableau::precompose_half_pi,
2030 Tableau::precompose_tqe,
2031 Tableau::compose,
2032 );
2033 }
2034
2035 #[cfg(feature = "unstable_simd")]
2036 #[test]
2037 fn test_compose_simd() {
2038 compose_body(
2039 Tableau::precompose_half_pi_simd::<64>,
2040 Tableau::precompose_tqe_simd::<64>,
2041 Tableau::compose_simd::<64>,
2042 );
2043 }
2044
2045 #[test]
2046 #[should_panic(expected = "Cannot compose tableaux with different numbers of qubits")]
2047 fn test_compose_rejects_larger_right_tableau() {
2048 Tableau::eye(2).compose(&Tableau::eye(3));
2049 }
2050
2051 #[test]
2052 #[should_panic(expected = "Cannot compose tableaux with different numbers of qubits")]
2053 fn test_compose_rejects_smaller_right_tableau() {
2054 Tableau::eye(3).compose(&Tableau::eye(2));
2055 }
2056
2057 fn gadget_body(
2067 apply_enum_tqe: impl Fn(
2068 &mut [u64],
2069 &mut [u64],
2070 &mut [u64],
2071 &mut [u64],
2072 &mut [u64],
2073 Pauli,
2074 Pauli,
2075 ),
2076 postcompose_pauli_gadget: impl Fn(&mut Tableau, &[u64], &[u64], u8),
2077 postcompose_tqe: impl Fn(&mut Tableau, Pauli, Pauli, usize, usize),
2078 postcompose_half_pi: impl Fn(&mut Tableau, Pauli, usize, bool),
2079 postcompose_pauli: impl Fn(&mut Tableau, Pauli, usize),
2080 ) {
2081 const N_TRIALS: usize = 100;
2082 let mut rng = StdRng::seed_from_u64(5);
2083 for (n_qubits, n_tqes) in [(4, 4), (100, 1000)] {
2084 for _ in 0..N_TRIALS {
2085 let support = rng.random_range(0..n_qubits);
2086 let theta = rng.random_range(0..4);
2087 let p = match rng.random_range(0..3) {
2088 0 => Pauli::X,
2089 1 => Pauli::Y,
2090 _ => Pauli::Z,
2091 };
2092 let mut qubit_slices_z_bits = vec![vec![0u64]; n_qubits];
2095 let mut qubit_slices_x_bits = vec![vec![0u64]; n_qubits];
2096 let mut sign_bits = vec![0u64];
2097 match p {
2098 Pauli::X => qubit_slices_x_bits[support][0] = 1,
2099 Pauli::Y => {
2100 qubit_slices_z_bits[support][0] = 1;
2101 qubit_slices_x_bits[support][0] = 1;
2102 }
2103 Pauli::Z => qubit_slices_z_bits[support][0] = 1,
2104 _ => panic!(),
2105 }
2106
2107 let tqes = random_tqes(n_qubits, n_tqes, &mut rng);
2108 for &(g0, g1, q0, q1) in tqes.iter() {
2109 let (q0_slice_z_bits, q1_slice_z_bits) =
2110 get_two_mut(&mut qubit_slices_z_bits, q0, q1);
2111 let (q0_slice_x_bits, q1_slice_x_bits) =
2112 get_two_mut(&mut qubit_slices_x_bits, q0, q1);
2113 apply_enum_tqe(
2114 q0_slice_z_bits,
2115 q0_slice_x_bits,
2116 q1_slice_z_bits,
2117 q1_slice_x_bits,
2118 &mut sign_bits,
2119 g0,
2120 g1,
2121 );
2122 }
2123 let n_words = n_qubits.div_ceil(64);
2125 let mut img_z_word = 0;
2126 let mut img_x_word = 0;
2127 let mut bits_filled = 0;
2128 let mut img_z_bits = Vec::with_capacity(n_words);
2129 let mut img_x_bits = Vec::with_capacity(n_words);
2130
2131 for output_q in 0..n_qubits {
2132 let slice_z_bit = qubit_slices_z_bits[output_q][0];
2133 let slice_x_bit = qubit_slices_x_bits[output_q][0];
2134 img_z_word |= slice_z_bit << bits_filled;
2135 img_x_word |= slice_x_bit << bits_filled;
2136 bits_filled += 1;
2137 if bits_filled == 64 {
2138 img_z_bits.push(img_z_word);
2139 img_x_bits.push(img_x_word);
2140 bits_filled = 0;
2141 img_z_word = 0;
2142 img_x_word = 0;
2143 }
2144 }
2145 if bits_filled > 0 {
2146 img_z_bits.push(img_z_word);
2147 img_x_bits.push(img_x_word);
2148 }
2149
2150 let mut tab1 = Tableau::random(n_qubits, 0, 1000, 1000);
2151 let mut tab2 = tab1.clone();
2152 assert_eq!(tab1, tab2);
2153
2154 let half_pis = if sign_bits[0] == 0 {
2155 theta
2156 } else {
2157 match theta {
2158 0 => 0,
2159 1 => 3,
2160 2 => 2,
2161 3 => 1,
2162 _ => panic!(),
2163 }
2164 };
2165 postcompose_pauli_gadget(&mut tab1, &img_z_bits, &img_x_bits, half_pis);
2166 for &(g0, g1, q0, q1) in tqes.iter().rev() {
2167 postcompose_tqe(&mut tab2, g0, g1, q0, q1);
2168 }
2169 match theta {
2170 0 => {}
2171 1 => {
2172 postcompose_half_pi(&mut tab2, p, support, false);
2173 }
2174 2 => {
2175 postcompose_pauli(&mut tab2, p, support);
2176 }
2177 3 => {
2178 postcompose_half_pi(&mut tab2, p, support, true);
2179 }
2180 _ => panic!(),
2181 }
2182 for &(g0, g1, q0, q1) in tqes.iter() {
2183 postcompose_tqe(&mut tab2, g0, g1, q0, q1);
2184 }
2185 assert_eq!(tab1, tab2);
2186 }
2187 }
2188 }
2189
2190 #[test]
2191 fn test_gadget() {
2192 gadget_body(
2193 apply_enum_tqe_slice,
2194 Tableau::postcompose_pauli_gadget,
2195 Tableau::postcompose_tqe,
2196 Tableau::postcompose_half_pi,
2197 Tableau::postcompose_pauli,
2198 );
2199 }
2200
2201 #[cfg(feature = "unstable_simd")]
2202 #[test]
2203 fn test_gadget_simd() {
2204 gadget_body(
2205 apply_enum_tqe_simd::<64>,
2206 Tableau::postcompose_pauli_gadget_simd::<64>,
2207 Tableau::postcompose_tqe_simd::<64>,
2208 Tableau::postcompose_half_pi_simd::<64>,
2209 Tableau::postcompose_pauli_simd::<64>,
2210 );
2211 }
2212}