Skip to main content

tk_pg_qm_tableau/
lib.rs

1//! Clifford tableaux using a qubit major memory layout.
2#![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
25/// Hard-coded n-qubit threshold for when to use multi-threading.
26/// This value was chosen based on earlier benchmarking and may need re-tuning.
27const MT_THRESH: usize = 500;
28
29// Type aliases for function pointers to various gate application functions
30// These are used to allow for different implementations (e.g., SIMD vs. non-SIMD) to be used interchangeably.
31type 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
38/// Returns mutable references to the elements at indices `i` and `j`.
39///
40/// # Arguments
41///
42/// * `v` - A mutable slice.
43/// * `i` - The first index.
44/// * `j` - The second index.
45///
46/// # Returns
47///
48/// A tuple containing mutable references to the elements at indices `i` and `j`.
49fn 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
60/// Panics with a clear message if `q0` and `q1` are not distinct qubit indices.
61fn 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
67/// Multiplies two bit-packed Pauli strings, computing the phase.
68/// We count the number of anti-commuting sites and the number of anti-cyclic sites (e.g. YX = -iZ)
69/// to determine the phase factor.
70///
71/// # Arguments
72///
73/// * `lhs_z_bits` - Mutable Z-bits of the first Pauli string (modified in-place)
74/// * `lhs_x_bits` - Mutable X-bits of the first Pauli string (modified in-place)
75/// * `rhs_z_bits` - Z-bits of the second Pauli string
76/// * `rhs_x_bits` - X-bits of the second Pauli string
77///
78/// # Returns
79///
80/// The phase factor as the position in [1, i, -1, -i]
81///
82fn 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
109/// Given a Pauli string, count the number of Ys
110fn 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/// Multiplies two bit-packed Pauli strings using SIMD operations, computing the phase.
120#[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    // TODO: Use SIMD for the remaining elements.
153    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/// Given a Pauli string, count the number of Ys using SIMD
173#[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    // TODO: Use SIMD for the remaining elements.
187    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/// A qubit-major implementation of a unitary tableau.
197/// # Example
198/// |     | Z0 | X0 | Z1 | X1 |
199/// | -------- | - | - | - | - |
200/// | \(Q_0\)  | Z | X | Y | I |
201/// | \(Q_1\)  | X | X | Z | X |
202/// | Sign |+|+|+|-|
203///
204/// The X0 image, represented by a column, says that an X operator at qubit 0
205/// on the input will be transformed into XX over the output.
206///
207/// Our tableau implementation is qubit(row)-major, and the Z bits and X bits of the Pauli letters
208/// are stored separately. The tableau above is therefore stored, before bit packing, as:
209/// qubit_slices_z_bits = \[
210/// \[1,0,1,0\],
211/// \[0,0,1,0\]
212/// \]
213/// qubit_slices_x_bits = \[
214/// \[0,1,1,0\],
215/// \[1,1,0,1\]
216/// \]
217/// sign_bits = \[0, 0, 0, 1\]
218/// n_qubits = 2
219#[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    /// Get the number of qubits in the tableau.
261    pub fn get_n_qubits(&self) -> usize {
262        self.n_qubits
263    }
264    /// Get the packed Z bits for each qubit slice.
265    pub fn qubit_slices_z_bits(&self) -> &Vec<Vec<u64>> {
266        &self.qubit_slices_z_bits
267    }
268    /// Get the packed X bits for each qubit slice.
269    pub fn qubit_slices_x_bits(&self) -> &Vec<Vec<u64>> {
270        &self.qubit_slices_x_bits
271    }
272    /// Get the sign bits of the tableau rows. 1 represents a negative sign, and 0 represents a positive sign.
273    pub fn get_sign_bits(&self) -> &Vec<u64> {
274        &self.sign_bits
275    }
276
277    /// Split the tableau into mutable references for two qubits.
278    ///
279    /// # Panics
280    ///
281    /// Panics if `q0 == q1`.
282    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    /// Post-compose a TQE gate.
306    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    /// Pre-compose a TQE gate.
390    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                // z0 <- z0 * x1
417                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                // z1 <- z1 * x0
430                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                // z0 <- z0 * y1 = i * z0 * x1 * z1
445                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                // z1 <- z1 * x0
465                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                // x1 <- x1 * x0
478                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                // z0 <- z0 * z1
493                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                // x1 <- x1 * x0
506                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                // convert sign to phase for readability
521                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                // y1 = i * x1 * z1
526                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                // z0 <- z0 * y1
537                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                // x0 <- x0 * y1
552                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                // y0 = i * x0 * z0 = i * (x0 * y1) * (z0 * y1)
567                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                // z1 <- z1 * y0
578                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                // x1 <- x1 * y0 = (-i * y1 * z1) * y0
593                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                // x1 <- x1 * y0 = i * x1 * x0 * z0
613                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                // z0 <- z0 * z1
633                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                // x0 <- x0 * z1
646                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                // x0 <- x0 * z1
661                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                // x1 <- x1 * z0
674                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    /// Precompose a half-pi Pauli rotation gate.
692    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                // rx(pi/2) gate
706                // x <- x
707                // z <- -y = iz*x
708                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                // 1 is i
715                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                // ry(pi/2) gate
725                // x <- -z
726                // z <- x
727                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                // rz(pi/2) gate
742                // x <- y = ix*z
743                // z <- z
744                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                // 1 is i
751                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    /// Postcompose a half-pi Pauli rotation gate.
764    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    /// Post compose a Pauli gate.
781    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    /// Post compose a Pauli gadget.
810    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        // we apply the gadget using a ladder
854        // we find the first non-identity
855        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        // Store the TQE gates to apply in reverse later
886        let mut tqe_gates = Vec::new();
887
888        // Forward TQE gates
889        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            // Skip identity
895            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            // Store the gate for reverse application
903            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        // apply the 1q clifford gate
919        self.postcompose_half_pi_with(pa, a, half_pis == 3, apply_half_pi);
920        // Apply TQE gates in reverse order
921        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    /// Conjugate a Pauli string by conjugating the z bits and x bits separately
939    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        // count the number of ys, each y contribute a i phase, hence shift the total phase by 1
989        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    /// Multi-threaded version of apply_to_pauli_with
998    /// the conjugation of z-bits and x-bits, as well as the counting of ys, are done in parallel
999    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        // count the number of ys, each y contributes a i phase, hence shift the total phase by 1
1070        (
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    /// Invert the tableau
1080    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        // TODO: consider parallelising this loop
1090        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        // Set sign bits.
1137        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    /// Postcompose another tableau.
1157    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    /// Creates a tableau from packed qubit slices.
1199    ///
1200    /// # Arguments
1201    ///
1202    /// * `qubit_slices_z_bits` - Packed Z bits for each qubit slice
1203    /// * `qubit_slices_x_bits` - Packed X bits for each qubit slice
1204    /// * `sign_bits` - Sign bits for each column, 0: + and 1: -
1205    /// * `n_qubits` - Number of qubits the tableau operates on
1206    ///
1207    /// # Returns
1208    ///
1209    /// A new Tableau instance
1210    // TODO: need input validation
1211    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    /// Initialize an identity Tableau
1226    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    /// Create a random tableau by applying `n_tqe` TQE gates and `n_half_pi` half-pi Pauli
1248    /// rotations to an identity tableau.
1249    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        // Apply random half-pi Pauli rotations
1254        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        // Apply random TQE gates
1264        if n_qubits == 1 {
1265            return tableau;
1266        }
1267        // add a ladder of TQE first
1268        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    /// Get a packed image by index.
1303    // TODO: consider reusable scratch buffers for images to avoid repeated allocations.
1304    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    /// Set a packed image.
1342    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    /// flip sign
1368    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    /// set sign
1374    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    /// Postcompose a TQE gate.
1385    /// The gate is specified by Pauli operators
1386    /// on two qubits.
1387    ///
1388    /// # Arguments
1389    ///
1390    /// * `g0` - Pauli operator for the first qubit
1391    /// * `g1` - Pauli operator for the second qubit
1392    /// * `q0` - Index of the first qubit
1393    /// * `q1` - Index of the second qubit
1394    ///
1395    /// # Panics
1396    ///
1397    /// Panics if `q0 == q1`, or if `g0` or `g1` is `Pauli::I`.
1398    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    /// Precompose a TQE gate.
1415    /// The gate is specified by Pauli operators
1416    /// on two qubits.
1417    ///
1418    /// # Arguments
1419    ///
1420    /// * `g0` - Pauli operator for the first qubit
1421    /// * `g1` - Pauli operator for the second qubit
1422    /// * `q0` - Index of the first qubit
1423    /// * `q1` - Index of the second qubit
1424    ///
1425    /// # Panics
1426    ///
1427    /// Panics if `q0 == q1`, or if `g0` or `g1` is `Pauli::I`.
1428    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    /// Precompose a single-qubit half-pi Pauli rotation.
1434    ///
1435    /// # Arguments
1436    ///
1437    /// * `axis` - The Pauli axis for the rotation (X, Y, or Z)
1438    /// * `q` - Index of the qubit to apply the rotation to
1439    /// * `dagger` - Whether to apply the inverse (daggered) version of the gate
1440    ///
1441    /// # Panics
1442    ///
1443    /// Panics if `axis` is `Pauli::I`.
1444    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    /// Precompose a single-qubit Pauli gate.
1449    ///
1450    /// # Arguments
1451    ///
1452    /// * `p` - The Pauli axis for the Pauli (X, Y, or Z)
1453    /// * `q` - Index of the qubit to apply the Pauli to
1454    ///
1455    /// # Panics
1456    ///
1457    /// Panics if `p` is `Pauli::I`.
1458    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    /// Precompose a SWAP gate.
1477    ///
1478    /// # Arguments
1479    ///
1480    /// * `q0` - Index of the first qubit
1481    /// * `q1` - Index of the second qubit
1482    ///
1483    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    /// Postcompose a SWAP gate.
1495    ///
1496    /// # Arguments
1497    ///
1498    /// * `q0` - Index of the first qubit
1499    /// * `q1` - Index of the second qubit
1500    ///
1501    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    /// Postcompose a half-pi Pauli rotation gate.
1507    ///
1508    /// # Arguments
1509    ///
1510    /// * `axis` - The Pauli axis for the rotation (X, Y, or Z)
1511    /// * `q` - Index of the qubit
1512    /// * `dagger` - Whether to apply the inverse (daggered) version of the gate
1513    ///
1514    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    /// Precompose a Hadamard gate.
1519    ///
1520    /// # Arguments
1521    ///
1522    /// * `q` - Index of the qubit
1523    ///
1524    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    /// Postcompose a Hadamard gate.
1534    ///
1535    /// # Arguments
1536    ///
1537    /// * `q` - Index of the qubit
1538    ///
1539    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    /// Postcompose a multi-qubit Clifford angle Pauli rotation.
1548    /// of the tableau.
1549    ///
1550    ///
1551    /// # Arguments
1552    ///
1553    /// * `pauli_z_bits` - Z bits of the Pauli string
1554    /// * `pauli_x_bits` - X bits of the Pauli string
1555    /// * `half_pis` - number of half pi turns, \[0,1,2,3\]
1556    ///
1557    /// # Panics
1558    ///
1559    /// Panics if `pauli_z_bits`/`pauli_x_bits` encode the all-identity Pauli string.
1560    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    /// Conjugate a Pauli string.
1579    ///
1580    /// Applies the tableau transformation to conjugate the input Pauli string,
1581    /// computing both the resulting Pauli operators and any sign changes.
1582    ///
1583    /// # Arguments
1584    ///
1585    /// * `pauli_z_bits` - Packed Z bits of the Pauli string (modified in-place)
1586    /// * `pauli_x_bits` - Packed X bits of the Pauli string (modified in-place)
1587    ///
1588    /// # Returns
1589    ///
1590    /// The conjugated Z bits, X bits, and a boolean indicating whether the transformation results in a sign flip
1591    ///
1592    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    /// Multi-threaded version of apply_to_pauli
1601    ///
1602    /// Note: For small tableaus it's worth benchmarking against the non-MT `apply_to_pauli`.
1603    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    /// Invert the tableau
1612    /// <https://algassert.com/post/2002>
1613    pub fn invert(&self) -> Tableau {
1614        self.invert_with(Tableau::apply_to_pauli, Tableau::apply_to_pauli_mt)
1615    }
1616
1617    /// Postcompose another tableau.
1618    /// self   other
1619    /// >[]> + >[]>
1620    pub fn compose(&mut self, other: &Tableau) {
1621        self.compose_with(other, Tableau::apply_to_pauli, Tableau::apply_to_pauli_mt);
1622    }
1623
1624    /// Postcompose a single-qubit Pauli gate
1625    ///
1626    /// # Panics
1627    ///
1628    /// Panics if `pauli` is `Pauli::I`.
1629    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    /// Return image of X on the ith qubit. The boolean is true when the image has a -1 phase.
1634    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    /// Return image of Z on the ith qubit. The boolean is true when the image has a -1 phase.
1643    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/// Trait for SIMD operations on Tableau
1653#[cfg(feature = "unstable_simd")]
1654pub trait SimdTableau {
1655    /// Postcompose a TQE gate using SIMD operations.
1656    ///
1657    /// # Panics
1658    ///
1659    /// Panics if `q0 == q1`, or if `g0` or `g1` is `Pauli::I`.
1660    fn postcompose_tqe_simd<const N: usize>(&mut self, g0: Pauli, g1: Pauli, q0: usize, q1: usize);
1661    /// Precompose a TQE gate using SIMD operations.
1662    ///
1663    /// # Panics
1664    ///
1665    /// Panics if `q0 == q1`, or if `g0` or `g1` is `Pauli::I`.
1666    fn precompose_tqe_simd<const N: usize>(&mut self, g0: Pauli, g1: Pauli, q0: usize, q1: usize);
1667    /// Precompose a half-pi Pauli rotation using SIMD operations.
1668    ///
1669    /// # Panics
1670    ///
1671    /// Panics if `axis` is `Pauli::I`.
1672    fn precompose_half_pi_simd<const N: usize>(&mut self, axis: Pauli, q: usize, dagger: bool);
1673    /// Postcompose a half-pi Pauli rotation using SIMD operations.
1674    fn postcompose_half_pi_simd<const N: usize>(&mut self, axis: Pauli, q: usize, dagger: bool);
1675    /// Postcompose a multi-qubit Clifford angle Pauli rotation using SIMD operations.
1676    ///
1677    /// # Panics
1678    ///
1679    /// Panics if `pauli_z_bits`/`pauli_x_bits` encode the all-identity Pauli string.
1680    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    /// Conjugate a Pauli string using SIMD operations.
1687    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    /// Multi-threaded version of apply_to_pauli_simd.
1693    ///
1694    /// Note: For small tableaus it's worth benchmarking against the non-MT
1695    /// `apply_to_pauli_simd`.
1696    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    /// Invert the tableau using SIMD operations.
1702    fn invert_simd<const N: usize>(&self) -> Tableau;
1703    /// Postcompose another tableau using SIMD operations.
1704    fn compose_simd<const N: usize>(&mut self, other: &Tableau);
1705    /// Postcompose a single-qubit Pauli gate using SIMD operations.
1706    ///
1707    /// # Panics
1708    ///
1709    /// Panics if `pauli` is `Pauli::I`.
1710    fn postcompose_pauli_simd<const N: usize>(&mut self, pauli: Pauli, q: usize);
1711
1712    /// Postcompose a Hadamard gate using SIMD operations.
1713    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    /// Shared body for `test_tableau_invert_roundtrip[_simd]`: inversion should round-trip and
1880    /// composing a tableau with its inverse in either order should produce the identity.
1881    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    /// Shared body for `test_tqe[_simd]_precompose_postcompose_matches`: precomposing a
1914    /// sequence of TQE gates is equivalent to postcomposing the same sequence in reverse order.
1915    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    /// Shared body for `test_half_pi[_simd]_precompose_postcompose_matches`: precomposing
1949    /// a sequence of half-pi rotations is equivalent to postcomposing the same sequence in
1950    /// reverse order.
1951    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    /// Shared body for `test_compose[_simd]`.
1990    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    /// Shared body for `test_gadget[_simd]`.
2058    ///
2059    /// We construct random gadgets by applying random TQEs
2060    /// to a Pauli string of weight 1 (with letter P), and an angle theta.
2061    /// Let the resulting string be Q'.
2062    /// We call this circuit composed of TQEs unitary U.
2063    /// U_dagger;P(theta);U = Q'(theta)
2064    ///
2065    /// We then verify this equation holds.
2066    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                // construct the string
2093                // Each qubit slice has one u64, and only one is nonzero.
2094                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                // Pack P' into an image.
2124                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}