Skip to main content

tk_pg_t_optimize/
lib.rs

1//! T-count optimization for Clifford+T Pauli graphs.
2//!
3//! Bit-vector operations are scalar by default. The `unstable_simd` feature enables
4//! portable SIMD and requires a nightly Rust toolchain.
5
6#![cfg_attr(feature = "unstable_simd", feature(portable_simd))]
7
8mod clifford_propagation;
9mod hadamard_optimizer;
10mod optimizer;
11mod simd_vector;
12mod t_optimizer;
13
14use tk_pg_core::{PGPass, PauliGraph};
15
16use crate::optimizer::optimize;
17
18/// A T-count optimization pass for rotations, tableaux, and unconditional H gates.
19#[derive(Default)]
20pub struct TOptimizationPass {
21    ancilla_budget: usize,
22    first_bit: usize,
23}
24
25impl TOptimizationPass {
26    /// Create a pass that uses no ancillas.
27    pub fn new() -> Self {
28        Self::default()
29    }
30
31    /// Reserve the last `budget` input qubits as idle ancillas prepared in zero.
32    ///
33    /// Using ancillas may introduce measurements, resets, and conditional corrections.
34    pub fn with_ancilla_budget(mut self, budget: usize) -> Self {
35        self.ancilla_budget = budget;
36        self
37    }
38
39    /// Start numbering new measurement results at `first_bit` (default: zero).
40    /// Set this to the number of existing classical bits to avoid overwriting them.
41    pub fn with_first_bit(mut self, first_bit: usize) -> Self {
42        self.first_bit = first_bit;
43        self
44    }
45
46    /// Optimize a graph whose rotation angles are multiples of 0.25 half turns.
47    ///
48    /// Panics if the input contains unsupported operations or non-idle reserved ancillas.
49    pub fn optimize(&self, graph: &PauliGraph) -> PauliGraph {
50        optimize(graph, self.ancilla_budget, self.first_bit)
51    }
52}
53
54impl PGPass for TOptimizationPass {
55    fn transform(&self, pauli_graph: &PauliGraph) -> PauliGraph {
56        self.optimize(pauli_graph)
57    }
58}
59
60#[cfg(test)]
61mod tests {
62    use super::*;
63    use tk_pg_converter::compare_unitaries_via_tk;
64    use tk_pg_core::{GateData, GateType, Op, Pauli, RotationData};
65    use tk_pg_ir_kernels::PGTableau;
66    use tk_pg_qm_tableau::Tableau;
67
68    #[test]
69    fn reduces_t_count_without_ancillas() {
70        let mut clifford = Tableau::eye(4);
71        clifford.postcompose_op(&Op::Gate {
72            data: GateData::new(GateType::H, vec![0]),
73        });
74        clifford.postcompose_op(&Op::Gate {
75            data: GateData::new(GateType::S, vec![0]),
76        });
77        clifford.postcompose_op(&Op::Gate {
78            data: GateData::new(GateType::ZX, vec![0, 1]),
79        });
80        clifford.postcompose_op(&Op::Gate {
81            data: GateData::new(GateType::H, vec![2]),
82        });
83        clifford.postcompose_op(&Op::Gate {
84            data: GateData::new(GateType::ZX, vec![2, 3]),
85        });
86        clifford.postcompose_op(&Op::Gate {
87            data: GateData::new(GateType::S, vec![3]),
88        });
89        clifford.postcompose_op(&Op::Gate {
90            data: GateData::new(GateType::ZX, vec![1, 2]),
91        });
92        clifford.postcompose_op(&Op::Gate {
93            data: GateData::new(GateType::H, vec![1]),
94        });
95
96        for (input_t_count, max_t_count) in [(14, 1), (15, 0)] {
97            // T rotations on all 15 nonzero four-qubit parities give identity up to phase.
98            // Omitting one parity leaves a single inverse T rotation.
99            // The Clifford conjugation preserves commutation and introduces X/Y terms.
100            let pg = PauliGraph::new(4).with_ops(
101                (1..=input_t_count)
102                    .flat_map(|parity| {
103                        let string = (0..4)
104                            .map(|q| {
105                                if parity & (1 << q) == 0 {
106                                    Pauli::I
107                                } else {
108                                    Pauli::Z
109                                }
110                            })
111                            .collect();
112                        clifford.conjugate(&Op::Rotation {
113                            data: RotationData::new(string, 0.25),
114                        })
115                    })
116                    .collect(),
117            );
118
119            for pauli in [Pauli::X, Pauli::Y] {
120                assert!(pg.get_ops().iter().any(|op| {
121                    matches!(op, Op::Rotation { data } if data.get_string().contains(&pauli))
122                }));
123            }
124
125            let optimized = TOptimizationPass::new().transform(&pg);
126            optimized.try_validate().unwrap();
127            assert_eq!(optimized.get_n_qubits(), pg.get_n_qubits());
128            let rotations: Vec<_> = optimized
129                .get_ops()
130                .iter()
131                .filter_map(|op| match op {
132                    Op::Rotation { data } => Some(data),
133                    _ => None,
134                })
135                .collect();
136            assert!(rotations.iter().all(|data| data.get_angle().abs() == 0.25));
137            assert!(
138                rotations.len() <= max_t_count,
139                "input T count: {input_t_count}"
140            );
141            assert!(compare_unitaries_via_tk(&pg, &optimized));
142        }
143    }
144}