Skip to main content

tk_pg_canonical_form/
lib.rs

1//! Pass to convert a Pauli graph into canonical form.
2use tk_pg_core::{
3    BlackBoxData, ConditionalBoxData, GateData, GateType, Op, PGPass, Pauli, PauliGraph,
4    RotationData, TableauData,
5};
6use tk_pg_ir_kernels::{PGTableau, get_dagger, is_clifford, is_clifford_gate_type};
7use tk_pg_qm_tableau::Tableau as QubitMajorTableau;
8use tk_pg_utils::cliff_angle;
9
10/// Decompose a Clifford gate into a sequence of rotations. We do this to process conditional Clifford gates.
11/// The current ConditionalBox only supports PauliRotation, Reset, and Measure, so we need to decompose Clifford gates into rotations to be able to process them.
12/// Many of these decompositions are inefficient. The hope is that the synthesis method, when working inside each conditional box, will be able to compress the decomposed gates into fewer rotations and tableaux.
13fn decompose_clifford(gate_type: &GateType, args: &[usize]) -> Vec<GateData> {
14    match gate_type {
15        GateType::H => vec![
16            GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![0.5]),
17            GateData::new(GateType::RX, vec![args[0]]).with_params(vec![0.5]),
18            GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![0.5]),
19        ],
20        GateType::S => vec![GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![0.5])],
21        GateType::V => vec![GateData::new(GateType::RX, vec![args[0]]).with_params(vec![0.5])],
22        GateType::Sdg => vec![GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![1.5])],
23        GateType::Vdg => vec![GateData::new(GateType::RX, vec![args[0]]).with_params(vec![1.5])],
24        GateType::X => vec![GateData::new(GateType::RX, vec![args[0]]).with_params(vec![1.0])],
25        GateType::Y => vec![GateData::new(GateType::RY, vec![args[0]]).with_params(vec![1.0])],
26        GateType::Z => vec![GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![1.0])],
27        GateType::XX => vec![
28            GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![3.5]),
29            GateData::new(GateType::RZ, vec![args[1]]).with_params(vec![3.5]),
30            GateData::new(GateType::RX, vec![args[0]]).with_params(vec![1.5]),
31            GateData::new(GateType::RX, vec![args[1]]).with_params(vec![2.5]),
32            GateData::new(GateType::ZZPHASE, vec![args[0], args[1]]).with_params(vec![0.5]),
33            GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![0.5]),
34            GateData::new(GateType::RZ, vec![args[1]]).with_params(vec![3.5]),
35            GateData::new(GateType::RX, vec![args[0]]).with_params(vec![0.5]),
36            GateData::new(GateType::RX, vec![args[1]]).with_params(vec![3.5]),
37            GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![0.5]),
38            GateData::new(GateType::RZ, vec![args[1]]).with_params(vec![0.5]),
39        ],
40        GateType::XY => vec![
41            GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![0.5]),
42            GateData::new(GateType::RZ, vec![args[1]]).with_params(vec![3.0]),
43            GateData::new(GateType::RX, vec![args[0]]).with_params(vec![1.5]),
44            GateData::new(GateType::RX, vec![args[1]]).with_params(vec![1.5]),
45            GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![0.5]),
46            GateData::new(GateType::ZZPHASE, vec![args[0], args[1]]).with_params(vec![0.5]),
47            GateData::new(GateType::RX, vec![args[0]]).with_params(vec![1.5]),
48            GateData::new(GateType::RZ, vec![args[1]]).with_params(vec![3.5]),
49            GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![0.5]),
50            GateData::new(GateType::RX, vec![args[1]]).with_params(vec![3.5]),
51        ],
52        GateType::XZ => vec![
53            GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![3.5]),
54            GateData::new(GateType::RZ, vec![args[1]]).with_params(vec![0.5]),
55            GateData::new(GateType::RX, vec![args[0]]).with_params(vec![2.5]),
56            GateData::new(GateType::ZZPHASE, vec![args[1], args[0]]).with_params(vec![0.5]),
57            GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![3.5]),
58            GateData::new(GateType::RX, vec![args[0]]).with_params(vec![3.5]),
59            GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![0.5]),
60        ],
61        GateType::YX => vec![
62            GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![3.0]),
63            GateData::new(GateType::RZ, vec![args[1]]).with_params(vec![0.5]),
64            GateData::new(GateType::RX, vec![args[0]]).with_params(vec![1.5]),
65            GateData::new(GateType::RX, vec![args[1]]).with_params(vec![1.5]),
66            GateData::new(GateType::RZ, vec![args[1]]).with_params(vec![0.5]),
67            GateData::new(GateType::ZZPHASE, vec![args[1], args[0]]).with_params(vec![0.5]),
68            GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![3.5]),
69            GateData::new(GateType::RX, vec![args[1]]).with_params(vec![1.5]),
70            GateData::new(GateType::RX, vec![args[0]]).with_params(vec![3.5]),
71            GateData::new(GateType::RZ, vec![args[1]]).with_params(vec![0.5]),
72        ],
73        GateType::YY => vec![
74            GateData::new(GateType::RX, vec![args[0]]).with_params(vec![1.5]),
75            GateData::new(GateType::RZ, vec![args[1]]).with_params(vec![3.0]),
76            GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![1.0]),
77            GateData::new(GateType::RX, vec![args[1]]).with_params(vec![1.5]),
78            GateData::new(GateType::ZZPHASE, vec![args[0], args[1]]).with_params(vec![0.5]),
79            GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![0.5]),
80            GateData::new(GateType::RZ, vec![args[1]]).with_params(vec![3.5]),
81            GateData::new(GateType::RX, vec![args[0]]).with_params(vec![0.5]),
82            GateData::new(GateType::RX, vec![args[1]]).with_params(vec![3.5]),
83        ],
84        GateType::YZ => vec![
85            GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![3.0]),
86            GateData::new(GateType::RZ, vec![args[1]]).with_params(vec![3.0]),
87            GateData::new(GateType::RX, vec![args[0]]).with_params(vec![1.5]),
88            GateData::new(GateType::RX, vec![args[1]]).with_params(vec![1.0]),
89            GateData::new(GateType::ZZPHASE, vec![args[1], args[0]]).with_params(vec![0.5]),
90            GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![3.5]),
91            GateData::new(GateType::RZ, vec![args[1]]).with_params(vec![0.5]),
92            GateData::new(GateType::RX, vec![args[0]]).with_params(vec![3.5]),
93            GateData::new(GateType::RX, vec![args[1]]).with_params(vec![1.0]),
94        ],
95        GateType::ZX => vec![
96            GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![0.5]),
97            GateData::new(GateType::RZ, vec![args[1]]).with_params(vec![3.5]),
98            GateData::new(GateType::RX, vec![args[1]]).with_params(vec![2.5]),
99            GateData::new(GateType::ZZPHASE, vec![args[0], args[1]]).with_params(vec![0.5]),
100            GateData::new(GateType::RZ, vec![args[1]]).with_params(vec![3.5]),
101            GateData::new(GateType::RX, vec![args[1]]).with_params(vec![3.5]),
102            GateData::new(GateType::RZ, vec![args[1]]).with_params(vec![0.5]),
103        ],
104        GateType::ZY => vec![
105            GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![3.0]),
106            GateData::new(GateType::RZ, vec![args[1]]).with_params(vec![3.0]),
107            GateData::new(GateType::RX, vec![args[0]]).with_params(vec![1.0]),
108            GateData::new(GateType::RX, vec![args[1]]).with_params(vec![1.5]),
109            GateData::new(GateType::ZZPHASE, vec![args[0], args[1]]).with_params(vec![0.5]),
110            GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![0.5]),
111            GateData::new(GateType::RZ, vec![args[1]]).with_params(vec![3.5]),
112            GateData::new(GateType::RX, vec![args[0]]).with_params(vec![1.0]),
113            GateData::new(GateType::RX, vec![args[1]]).with_params(vec![3.5]),
114        ],
115        GateType::ZZ => vec![
116            GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![3.5]),
117            GateData::new(GateType::RZ, vec![args[1]]).with_params(vec![1.5]),
118            GateData::new(GateType::RX, vec![args[0]]).with_params(vec![1.0]),
119            GateData::new(GateType::ZZPHASE, vec![args[0], args[1]]).with_params(vec![0.5]),
120            GateData::new(GateType::RZ, vec![args[0]]).with_params(vec![3.0]),
121            GateData::new(GateType::RZ, vec![args[1]]).with_params(vec![1.0]),
122            GateData::new(GateType::RX, vec![args[0]]).with_params(vec![1.0]),
123        ],
124        GateType::SWAP => [[args[0], args[1]], [args[1], args[0]], [args[0], args[1]]]
125            .into_iter()
126            .flat_map(|args| decompose_clifford(&GateType::ZX, &args))
127            .collect(),
128        _ => panic!(
129            "decompose_clifford called with non-Clifford gate type: {:?}",
130            gate_type
131        ),
132    }
133}
134
135fn absorb_clifford(tab: &mut QubitMajorTableau, op: &Op, forward: bool) {
136    // if moving forward, we maintain the dagger of the tableau.
137    // so updating the dagger of the tableau with a gate on the right
138    // is equivalent to pre-composing
139    // the dagger tableau with the dagger of the gate.
140    // (C;G)^\dagger = G^\dagger;C^\dagger
141    if forward {
142        tab.precompose_op(&get_dagger::<QubitMajorTableau>(op));
143    } else {
144        tab.precompose_op(op);
145    }
146}
147
148/// Flush the accumulated tableau and emit either black box representation as an Op::BlackBox.
149fn flush_black_box(
150    pg: &mut PauliGraph,
151    tab: &mut QubitMajorTableau,
152    qubits: &[usize],
153    content: &str,
154    forward: bool,
155) {
156    let tab_moved = std::mem::replace(tab, QubitMajorTableau::eye(pg.get_n_qubits()));
157    pg.add_op(Op::Tableau {
158        data: TableauData::from(if forward {
159            tab_moved.invert()
160        } else {
161            tab_moved
162        }),
163    });
164    pg.add_op(Op::BlackBox {
165        data: BlackBoxData::new(qubits.to_vec(), content.to_owned()),
166    });
167}
168
169/// The main function for processing an Op in the input PauliGraph.
170fn process_op(
171    pg: &mut PauliGraph,
172    op: &Op,
173    tab: &mut QubitMajorTableau,
174    forward: bool,
175    cliff_eval: bool,
176) {
177    match op {
178        Op::SetBoundary => return,
179        Op::Tableau { data } => {
180            let mut tableau_from_op = if forward {
181                QubitMajorTableau::from(data.clone()).get_dagger()
182            } else {
183                QubitMajorTableau::from(data.clone())
184            };
185            tableau_from_op.compose(tab);
186            *tab = tableau_from_op;
187            return;
188        }
189        Op::BlackBox { data } => {
190            flush_black_box(pg, tab, data.get_qubits(), data.get_content(), forward);
191            return;
192        }
193        Op::Gate { data } => {
194            let gate_type = data.get_gate_type();
195            let conditional = !data.get_conditional_bits().is_empty();
196            if gate_type == &GateType::BlackBox {
197                assert!(
198                    !conditional,
199                    "Conditional black box gates are not supported at the moment"
200                );
201                flush_black_box(
202                    pg,
203                    tab,
204                    data.get_args(),
205                    data.get_data().as_ref().expect("BlackBox data is missing"),
206                    forward,
207                );
208                return;
209            }
210            if is_clifford_gate_type(data) {
211                if conditional {
212                    let new_cond_ops = decompose_clifford(gate_type, data.get_args())
213                        .into_iter()
214                        .flat_map(|data| tab.conjugate(&Op::Gate { data }))
215                        .collect();
216                    pg.add_op(Op::ConditionalBox {
217                        data: ConditionalBoxData::new(
218                            new_cond_ops,
219                            data.get_conditional_bits().clone(),
220                            data.get_conditional_values().clone(),
221                        ),
222                    });
223                } else {
224                    absorb_clifford(tab, op, forward);
225                }
226                return;
227            }
228            if !conditional {
229                if cliff_eval && is_clifford(op) {
230                    absorb_clifford(tab, op, forward);
231                    return;
232                }
233                if gate_type == &GateType::PHASEDX {
234                    let alpha = data.get_params()[0];
235                    let beta = data.get_params()[1];
236                    let args = data.get_args();
237                    let compose_alpha = cliff_eval && cliff_angle(alpha).is_some();
238                    let compose_beta = cliff_eval && cliff_angle(beta).is_some();
239                    // Forward traversal uses a backward facing tableau, so
240                    // composition requires the inverse of the gate.
241                    // Backward traversal doesn't require inverses, but we need to process
242                    // the gates in reverse order, which means flipping the sign of beta.
243                    let alpha = if forward && compose_alpha {
244                        -alpha
245                    } else {
246                        alpha
247                    };
248                    let beta = if !forward || compose_beta {
249                        -beta
250                    } else {
251                        beta
252                    };
253                    for (gate_type, angle, compose) in [
254                        (GateType::RZ, -beta, compose_beta),
255                        (GateType::RX, alpha, compose_alpha),
256                        (GateType::RZ, beta, compose_beta),
257                    ] {
258                        let op = Op::Gate {
259                            data: GateData::new(gate_type, args.clone()).with_params(vec![angle]),
260                        };
261                        if compose {
262                            tab.precompose_op(&op);
263                        } else {
264                            process_op(pg, &op, tab, forward, cliff_eval);
265                        }
266                    }
267                    return;
268                }
269            }
270        }
271        Op::Rotation { data } => {
272            if cliff_eval && cliff_angle(data.get_angle()).is_some() {
273                absorb_clifford(tab, op, forward);
274                return;
275            }
276        }
277        Op::Measure { .. } | Op::Reset { .. } | Op::ConditionalBox { .. } => {}
278    }
279
280    // All remaining operations share the same conjugation path.
281    let mut conjugated_ops = tab.conjugate(op);
282    if !forward {
283        conjugated_ops.reverse();
284    }
285    for mut conjugated_op in conjugated_ops {
286        if cliff_eval && let Op::Rotation { data } = &mut conjugated_op {
287            let angle = data.get_angle();
288            if angle.is_finite() && angle.abs() >= 0.5 {
289                let remainder = angle % 0.5;
290                let correction = angle - remainder;
291                // The string is already conjugated, so append the correction to the tableau.
292                // Forward traversal maintains the inverse tableau.
293                if data.get_string().iter().any(|p| *p != Pauli::I) {
294                    tab.postcompose_op(&Op::Rotation {
295                        data: RotationData::new(
296                            data.get_string().clone(),
297                            if forward { -correction } else { correction },
298                        ),
299                    });
300                }
301                *data = RotationData::new(data.get_string().clone(), remainder);
302            }
303        }
304        pg.add_op(conjugated_op);
305    }
306}
307
308fn to_canonical_form(pg: &PauliGraph, forward: bool, cliff_eval: bool) -> PauliGraph {
309    let mut new_pg = PauliGraph::new(pg.get_n_qubits());
310    // We maintain a tableau that represents the inverse of the Clifford unitary if we are moving forward. (i.e. backward facing tableau)
311    let mut current_tableau = QubitMajorTableau::eye(pg.get_n_qubits());
312    let ops: Box<dyn Iterator<Item = &Op>> = if forward {
313        Box::new(pg.get_ops().iter())
314    } else {
315        Box::new(pg.get_ops().iter().rev())
316    };
317    for op in ops {
318        process_op(&mut new_pg, op, &mut current_tableau, forward, cliff_eval);
319    }
320    if forward {
321        // If we are moving forward, the tableau is facing backward, so we need to invert it to make sure the TableauData is forward facing.
322        new_pg.add_op(Op::Tableau {
323            data: TableauData::from(current_tableau.invert()),
324        });
325    } else {
326        new_pg.add_op(Op::Tableau {
327            data: TableauData::from(current_tableau),
328        });
329        // reverse the ops
330        let mut ops = new_pg.get_ops().clone();
331        ops.reverse();
332        new_pg = PauliGraph::new(pg.get_n_qubits()).with_ops(ops);
333    }
334    // Merge adjacent conditional boxes once both outer and inner ops are in circuit order.
335    let mut merged_pg = PauliGraph::new(pg.get_n_qubits());
336    for op in new_pg.get_ops() {
337        if let Op::ConditionalBox { data } = op {
338            for inner_op in data.get_ops() {
339                merged_pg.add_conditional_op(
340                    inner_op.clone(),
341                    data.get_conditional_bits().clone(),
342                    data.get_conditional_values().clone(),
343                );
344            }
345        } else {
346            merged_pg.add_conditional_op(op.clone(), vec![], vec![]);
347        }
348    }
349    merged_pg
350}
351
352/// Transform a Pauli graph into canonical form: non-Clifford gates are rewritten as Pauli
353/// rotations, while Clifford gates are commuted towards the end of the circuit (or the start,
354/// if the `forward` flag is false), merging into a tableau whenever they reach the boundary or
355/// an obstruction such as a `BlackBox`. The resulting graph may therefore contain multiple
356/// tableaux, interleaved with any obstructions and the non-Clifford ops (rotations, measures,
357/// resets, conditional operations) that are conjugated through and left in place.
358/// `cliff_eval` controls whether rotations with a Clifford angle are folded into the tableau
359/// (`true`) or kept as explicit rotations (`false`). When enabled, it also extracts
360/// Clifford corrections from unconditional rotations, leaving their angles strictly
361/// between -0.5 and 0.5 half turns.
362///
363/// # Panics
364///
365/// Panics if a conditional box contains an operation other than [`Op::Rotation`],
366/// [`Op::Measure`], or [`Op::Reset`].
367pub struct CanonicalFormPass {
368    forward: bool,
369    cliff_eval: bool,
370}
371
372impl Default for CanonicalFormPass {
373    fn default() -> Self {
374        Self::new()
375    }
376}
377
378impl CanonicalFormPass {
379    /// Create a new instance of `CanonicalFormPass` with default settings.
380    pub fn new() -> Self {
381        Self {
382            forward: true,
383            cliff_eval: true,
384        }
385    }
386    /// Set the direction of the pass.
387    pub fn with_forward(mut self, forward: bool) -> Self {
388        self.forward = forward;
389        self
390    }
391    /// Set whether to absorb Clifford rotations and the Clifford part of larger angles
392    /// into the tableau. Enabled by default; remaining unconditional rotation angles
393    /// lie strictly between -0.5 and 0.5 half turns.
394    pub fn with_cliff_eval(mut self, cliff_eval: bool) -> Self {
395        self.cliff_eval = cliff_eval;
396        self
397    }
398}
399
400impl PGPass for CanonicalFormPass {
401    fn transform(&self, pg: &PauliGraph) -> PauliGraph {
402        to_canonical_form(pg, self.forward, self.cliff_eval)
403    }
404}
405
406#[cfg(test)]
407mod tests {
408    use super::*;
409    use rstest::rstest;
410    use tk_pg_converter::compare_unitaries_via_tk;
411    use tk_pg_core::{
412        GateData, GateType, MeasureData, Op, Pauli, PauliGraph, ResetData, RotationData,
413    };
414
415    #[test]
416    fn test_empty_circuit() {
417        let pg = PauliGraph::new(3);
418        let pass = CanonicalFormPass::new();
419        let transformed = pass.transform(&pg);
420        // empty tableau
421        assert_eq!(transformed.get_ops().len(), 1);
422    }
423
424    #[rstest]
425    #[case(true)]
426    #[case(false)]
427    fn test_tableau_compose_cliffords(#[case] forward: bool) {
428        let mut pg = PauliGraph::new(3);
429        pg.add_op(Op::Gate {
430            data: GateData::new(GateType::H, vec![0]),
431        });
432        pg.add_op(Op::Gate {
433            data: GateData::new(GateType::X, vec![1]),
434        });
435        pg.add_op(Op::Gate {
436            data: GateData::new(GateType::S, vec![2]),
437        });
438        pg.add_op(Op::Gate {
439            data: GateData::new(GateType::ZX, vec![0, 1]),
440        });
441        pg.add_op(Op::Gate {
442            data: GateData::new(GateType::SWAP, vec![2, 0]),
443        });
444        let pass = CanonicalFormPass::new().with_forward(forward);
445        let transformed = pass.transform(&pg);
446        assert_eq!(transformed.get_ops().len(), 1);
447        assert!(compare_unitaries_via_tk(&pg, &transformed));
448    }
449
450    #[rstest]
451    #[case(true)]
452    #[case(false)]
453    fn test_tableau_compose_rotations(#[case] forward: bool) {
454        let mut pg = PauliGraph::new(3);
455        pg.add_op(Op::Gate {
456            data: GateData::new(GateType::RX, vec![0]).with_params(vec![1.0]),
457        });
458        pg.add_op(Op::Gate {
459            data: GateData::new(GateType::RZ, vec![1]).with_params(vec![-0.5]),
460        });
461        pg.add_op(Op::Gate {
462            data: GateData::new(GateType::RY, vec![2]).with_params(vec![1.5]),
463        });
464        pg.add_op(Op::Gate {
465            data: GateData::new(GateType::PHASEDX, vec![0]).with_params(vec![0.5, 1.0]),
466        });
467        pg.add_op(Op::Rotation {
468            data: RotationData::new(vec![Pauli::X, Pauli::Y, Pauli::Z], 0.5),
469        });
470        pg.add_op(Op::Rotation {
471            data: RotationData::new(vec![Pauli::I, Pauli::Z, Pauli::Z], 3.0),
472        });
473        let pass = CanonicalFormPass::new().with_forward(forward);
474        let transformed = pass.transform(&pg);
475        assert_eq!(transformed.get_ops().len(), 1);
476        assert!(compare_unitaries_via_tk(&pg, &transformed));
477    }
478
479    #[rstest]
480    #[case(true, true, 0.75, 0.25)]
481    #[case(false, true, 0.75, 0.25)]
482    #[case(true, true, -0.75, -0.25)]
483    #[case(false, true, -0.75, -0.25)]
484    #[case(true, true, 2.1, 0.1)]
485    #[case(false, true, 2.1, 0.1)]
486    #[case(true, true, -2.1, -0.1)]
487    #[case(false, true, -2.1, -0.1)]
488    #[case(true, false, 0.75, 0.75)]
489    #[case(false, false, 0.75, 0.75)]
490    #[case(true, false, -0.75, -0.75)]
491    #[case(false, false, -0.75, -0.75)]
492    #[case(true, false, 2.1, 2.1)]
493    #[case(false, false, 2.1, 2.1)]
494    #[case(true, false, -2.1, -2.1)]
495    #[case(false, false, -2.1, -2.1)]
496    fn test_extract_clifford_corrections(
497        #[case] forward: bool,
498        #[case] cliff_eval: bool,
499        #[case] angle: f64,
500        #[case] expected_angle: f64,
501    ) {
502        let mut pg = PauliGraph::new(2);
503        pg.add_op(Op::Gate {
504            data: GateData::new(GateType::RZ, vec![0]).with_params(vec![angle]),
505        });
506        pg.add_op(Op::Rotation {
507            data: RotationData::new(vec![Pauli::I, Pauli::Z], angle),
508        });
509        let pass = CanonicalFormPass::new()
510            .with_forward(forward)
511            .with_cliff_eval(cliff_eval);
512        let transformed = pass.transform(&pg);
513
514        assert_eq!(transformed.get_ops().len(), 3);
515        for op in transformed.get_ops() {
516            if let Op::Rotation { data } = op {
517                assert!((data.get_angle() - expected_angle).abs() < 1e-10);
518            }
519        }
520        assert!(compare_unitaries_via_tk(&pg, &transformed));
521    }
522
523    #[rstest]
524    #[case(true)]
525    #[case(false)]
526    fn test_clifford_corrections_propagate(#[case] forward: bool) {
527        let mut pg = PauliGraph::new(2);
528        pg.add_op(Op::Gate {
529            data: GateData::new(GateType::H, vec![0]),
530        });
531        pg.add_op(Op::Gate {
532            data: GateData::new(GateType::RX, vec![0]).with_params(vec![0.75]),
533        });
534        pg.add_op(Op::Gate {
535            data: GateData::new(GateType::RY, vec![0]).with_params(vec![-0.75]),
536        });
537        pg.add_op(Op::Rotation {
538            data: RotationData::new(vec![Pauli::X, Pauli::Y], 1.25),
539        });
540        pg.add_op(Op::Gate {
541            data: GateData::new(GateType::PHASEDX, vec![0]).with_params(vec![0.75, 1.25]),
542        });
543        pg.add_op(Op::Gate {
544            data: GateData::new(GateType::ZZPHASE, vec![0, 1]).with_params(vec![-1.25]),
545        });
546        pg.add_op(Op::Gate {
547            data: GateData::new(GateType::H, vec![1]),
548        });
549        let pass = CanonicalFormPass::new().with_forward(forward);
550        let transformed = pass.transform(&pg);
551
552        for op in transformed.get_ops() {
553            if let Op::Rotation { data } = op {
554                assert!(data.get_angle().abs() < 0.5);
555            }
556        }
557        assert!(compare_unitaries_via_tk(&pg, &transformed));
558    }
559
560    #[rstest]
561    #[case(true, true, vec![0.5, 1.0], 1)]
562    #[case(false, true, vec![0.5, 1.0], 1)]
563    #[case(true, false, vec![0.5, 1.0], 4)]
564    #[case(false, false, vec![1.5, 0.0], 4)]
565    #[case(true, true, vec![1.0, 1.0], 1)]
566    #[case(false, true, vec![0.0, 1.5], 1)]
567    fn test_tableau_compose_phasedx(
568        #[case] forward: bool,
569        #[case] cliff_eval: bool,
570        #[case] params: Vec<f64>,
571        #[case] expected_ops: usize,
572    ) {
573        let mut pg = PauliGraph::new(1);
574        pg.add_op(Op::Gate {
575            data: GateData::new(GateType::PHASEDX, vec![0]).with_params(params),
576        });
577        let pass = CanonicalFormPass::new()
578            .with_forward(forward)
579            .with_cliff_eval(cliff_eval);
580        let transformed = pass.transform(&pg);
581        assert_eq!(transformed.get_ops().len(), expected_ops);
582        assert!(compare_unitaries_via_tk(&pg, &transformed));
583    }
584
585    #[rstest]
586    #[case(true)]
587    #[case(false)]
588    fn test_tableau_compose_tableaux(#[case] forward: bool) {
589        let mut pg = PauliGraph::new(3);
590        pg.add_op(Op::Tableau {
591            data: QubitMajorTableau::random(3, 0, 10, 10).into(),
592        });
593        pg.add_op(Op::Tableau {
594            data: QubitMajorTableau::random(3, 1, 10, 10).into(),
595        });
596        let pass = CanonicalFormPass::new().with_forward(forward);
597        let transformed = pass.transform(&pg);
598        assert_eq!(transformed.get_ops().len(), 1);
599        assert!(compare_unitaries_via_tk(&pg, &transformed));
600    }
601
602    #[rstest]
603    #[case(true, true, 5)]
604    #[case(false, true, 5)]
605    #[case(true, false, 6)]
606    #[case(false, false, 6)]
607    fn test_unitary_circuits(
608        #[case] forward: bool,
609        #[case] cliff_eval: bool,
610        #[case] expected_ops: usize,
611    ) {
612        let mut pg = PauliGraph::new(3);
613        pg.add_op(Op::Gate {
614            data: GateData::new(GateType::XX, vec![0, 1]),
615        });
616        pg.add_op(Op::Gate {
617            data: GateData::new(GateType::RX, vec![0]).with_params(vec![1.3]),
618        });
619        pg.add_op(Op::Gate {
620            data: GateData::new(GateType::XY, vec![1, 2]),
621        });
622        pg.add_op(Op::Gate {
623            data: GateData::new(GateType::RZ, vec![1]).with_params(vec![-0.55]),
624        });
625        pg.add_op(Op::Rotation {
626            data: RotationData::new(vec![Pauli::X, Pauli::Y, Pauli::Z], 0.5),
627        });
628        pg.add_op(Op::Rotation {
629            data: RotationData::new(vec![Pauli::I, Pauli::X, Pauli::X], 1.1),
630        });
631        pg.add_op(Op::Tableau {
632            data: QubitMajorTableau::random(3, 0, 10, 10).into(),
633        });
634        pg.add_op(Op::Rotation {
635            data: RotationData::new(vec![Pauli::Z, Pauli::X, Pauli::Z], 2.1),
636        });
637        let pass = CanonicalFormPass::new()
638            .with_forward(forward)
639            .with_cliff_eval(cliff_eval);
640        let transformed = pass.transform(&pg);
641        assert_eq!(transformed.get_ops().len(), expected_ops);
642        assert!(compare_unitaries_via_tk(&pg, &transformed));
643    }
644
645    #[test]
646    fn test_measurement() {
647        let mut pg1 = PauliGraph::new(1);
648        pg1.add_op(Op::Gate {
649            data: GateData::new(GateType::V, vec![0]),
650        });
651        pg1.add_op(Op::Measure {
652            data: MeasureData::new(vec![Pauli::Z], false, 0),
653        });
654        let canonical_pass = CanonicalFormPass::new().with_forward(true);
655        let transformed1 = canonical_pass.transform(&pg1);
656
657        let mut pg2 = PauliGraph::new(1);
658        pg2.add_op(Op::Gate {
659            data: GateData::new(GateType::V, vec![0]),
660        });
661        pg2.add_op(Op::Gate {
662            data: GateData::new(GateType::Measure, vec![0, 0]),
663        });
664        let transformed2 = canonical_pass.transform(&pg2);
665
666        assert_eq!(transformed1.get_ops().len(), 2);
667        if let Op::Measure { data } = &transformed1.get_ops()[0] {
668            assert_eq!(*data.get_string(), vec![Pauli::Y]);
669            assert!(!data.get_sign_bit());
670            assert_eq!(data.get_cbit(), 0);
671        } else {
672            panic!("Expected a Measure op in the transformed graph");
673        }
674        assert_eq!(transformed1, transformed2);
675    }
676
677    #[test]
678    fn test_reset_gate() {
679        let mut pg = PauliGraph::new(1);
680        pg.add_op(Op::Gate {
681            data: GateData::new(GateType::Reset, vec![0]),
682        });
683        pg.add_op(Op::Gate {
684            data: GateData::new(GateType::V, vec![0]),
685        });
686        let canonical_pass = CanonicalFormPass::new().with_forward(false);
687        let transformed = canonical_pass.transform(&pg);
688        assert_eq!(transformed.get_ops().len(), 2);
689        if let Op::Reset { data } = &transformed.get_ops()[1] {
690            assert_eq!(*data.get_first_string(), vec![Pauli::Y]);
691            assert_eq!(*data.get_second_string(), vec![Pauli::X]);
692            assert!(data.get_first_sign_bit());
693            assert!(!data.get_second_sign_bit());
694        } else {
695            panic!("Expected a Reset op in the transformed graph");
696        }
697    }
698
699    #[test]
700    fn test_reset() {
701        let mut pg = PauliGraph::new(1);
702        pg.add_op(Op::Gate {
703            data: GateData::new(GateType::S, vec![0]),
704        });
705        pg.add_op(Op::Reset {
706            data: ResetData::new(vec![Pauli::X], vec![Pauli::Y], false, true),
707        });
708        let canonical_pass = CanonicalFormPass::new().with_forward(true);
709        let transformed = canonical_pass.transform(&pg);
710        assert_eq!(transformed.get_ops().len(), 2);
711        if let Op::Reset { data } = &transformed.get_ops()[0] {
712            assert_eq!(*data.get_first_string(), vec![Pauli::Y]);
713            assert_eq!(*data.get_second_string(), vec![Pauli::X]);
714            assert!(data.get_first_sign_bit());
715            assert!(data.get_second_sign_bit());
716        } else {
717            panic!("Expected a Reset op in the transformed graph");
718        }
719    }
720
721    #[test]
722    fn test_conditional_cliffords() {
723        let mut pg = PauliGraph::new(2);
724        pg.add_op(Op::Gate {
725            data: GateData::new(GateType::Y, vec![0]).with_conditional(vec![0], vec![true]),
726        });
727        pg.add_op(Op::Gate {
728            data: GateData::new(GateType::XZ, vec![0, 1]).with_conditional(vec![0], vec![true]),
729        });
730        let forward_canonical = CanonicalFormPass::new().with_forward(true).transform(&pg);
731        let backward_canonical = CanonicalFormPass::new().with_forward(false).transform(&pg);
732        let expectd_cond_ops = vec![
733            // Y
734            Op::Rotation {
735                data: RotationData::new(vec![Pauli::Y, Pauli::I], 1.0),
736            },
737            // XZ decomposed
738            Op::Rotation {
739                data: RotationData::new(vec![Pauli::Z, Pauli::I], 3.5),
740            },
741            Op::Rotation {
742                data: RotationData::new(vec![Pauli::I, Pauli::Z], 0.5),
743            },
744            Op::Rotation {
745                data: RotationData::new(vec![Pauli::X, Pauli::I], 2.5),
746            },
747            Op::Rotation {
748                data: RotationData::new(vec![Pauli::Z, Pauli::Z], 0.5),
749            },
750            Op::Rotation {
751                data: RotationData::new(vec![Pauli::Z, Pauli::I], 3.5),
752            },
753            Op::Rotation {
754                data: RotationData::new(vec![Pauli::X, Pauli::I], 3.5),
755            },
756            Op::Rotation {
757                data: RotationData::new(vec![Pauli::Z, Pauli::I], 0.5),
758            },
759        ];
760        assert_eq!(forward_canonical.get_ops().len(), 2);
761        let forward_cond_box = if let Op::ConditionalBox { data } = &forward_canonical.get_ops()[0]
762        {
763            data
764        } else {
765            panic!("Expected a ConditionalBox op in the transformed graph");
766        };
767        let backward_cond_box =
768            if let Op::ConditionalBox { data } = &backward_canonical.get_ops()[1] {
769                data
770            } else {
771                panic!("Expected a ConditionalBox op in the transformed graph");
772            };
773        assert_eq!(forward_cond_box.get_ops(), &expectd_cond_ops);
774        assert_eq!(forward_cond_box, backward_cond_box);
775    }
776
777    #[test]
778    fn test_conditional_box() {
779        let mut pg = PauliGraph::new(2);
780        let cond_ops = vec![
781            Op::Rotation {
782                data: RotationData::new(vec![Pauli::X, Pauli::I], 1.0),
783            },
784            Op::Rotation {
785                data: RotationData::new(vec![Pauli::Z, Pauli::Z], 0.5),
786            },
787        ];
788        pg.add_op(Op::ConditionalBox {
789            data: ConditionalBoxData::new(cond_ops.clone(), vec![0], vec![true]),
790        });
791        let forward_canonical = CanonicalFormPass::new().with_forward(true).transform(&pg);
792        let backward_canonical = CanonicalFormPass::new().with_forward(false).transform(&pg);
793        assert_eq!(forward_canonical.get_ops().len(), 2);
794        let forward_cond_box = if let Op::ConditionalBox { data } = &forward_canonical.get_ops()[0]
795        {
796            data
797        } else {
798            panic!("Expected a ConditionalBox op in the transformed graph");
799        };
800        let backward_cond_box =
801            if let Op::ConditionalBox { data } = &backward_canonical.get_ops()[1] {
802                data
803            } else {
804                panic!("Expected a ConditionalBox op in the transformed graph");
805            };
806        // unchanged by the identity tableau
807        assert_eq!(forward_cond_box.get_ops(), &cond_ops);
808        assert_eq!(forward_cond_box, backward_cond_box);
809    }
810
811    #[rstest]
812    #[case(true)]
813    #[case(false)]
814    fn test_black_box(#[case] forward: bool) {
815        let mut pg = PauliGraph::new(2);
816        let black_box_data = BlackBoxData::new(vec![0, 1], "bb".into());
817        pg.add_op(Op::Gate {
818            data: GateData::new(GateType::H, vec![0]),
819        });
820        pg.add_op(Op::BlackBox {
821            data: black_box_data.clone(),
822        });
823        pg.add_op(Op::Gate {
824            data: GateData::new(GateType::S, vec![0]),
825        });
826        let transformed = CanonicalFormPass::new()
827            .with_forward(forward)
828            .transform(&pg);
829        assert_eq!(transformed.get_ops().len(), 3);
830        // circuit is the same for forward and backward passes
831        // H tableau, black box, S tableau
832        if let Op::Tableau { .. } = &transformed.get_ops()[0] {
833            assert!(
834                compare_unitaries_via_tk(
835                    &PauliGraph::new(2).with_ops(vec![transformed.get_ops()[0].clone()]),
836                    &PauliGraph::new(2).with_ops(vec![Op::Gate {
837                        data: GateData::new(GateType::H, vec![0]),
838                    }]),
839                ),
840                "Expected first tableau to be equivalent to an H gate on qubit 0"
841            );
842        } else {
843            panic!("Expected a Tableau op in the transformed graph");
844        }
845        if let Op::BlackBox { data } = &transformed.get_ops()[1] {
846            assert_eq!(data, &black_box_data);
847        } else {
848            panic!("Expected a BlackBox op in the transformed graph");
849        }
850        if let Op::Tableau { .. } = &transformed.get_ops()[2] {
851            assert!(
852                compare_unitaries_via_tk(
853                    &PauliGraph::new(2).with_ops(vec![transformed.get_ops()[2].clone()]),
854                    &PauliGraph::new(2).with_ops(vec![Op::Gate {
855                        data: GateData::new(GateType::S, vec![0]),
856                    }]),
857                ),
858                "Expected last tableau to be equivalent to an S gate on qubit 0"
859            );
860        } else {
861            panic!("Expected a Tableau op in the transformed graph");
862        }
863    }
864
865    #[rstest]
866    #[case(GateType::H, vec![0])]
867    #[case(GateType::S, vec![0])]
868    #[case(GateType::V, vec![0])]
869    #[case(GateType::Vdg, vec![0])]
870    #[case(GateType::Sdg, vec![0])]
871    #[case(GateType::X, vec![0])]
872    #[case(GateType::Y, vec![0])]
873    #[case(GateType::Z, vec![0])]
874    #[case(GateType::XX, vec![0,1])]
875    #[case(GateType::XY, vec![0,1])]
876    #[case(GateType::XZ, vec![0,1])]
877    #[case(GateType::YX, vec![0,1])]
878    #[case(GateType::YY, vec![0,1])]
879    #[case(GateType::YZ, vec![0,1])]
880    #[case(GateType::ZX, vec![0,1])]
881    #[case(GateType::ZY, vec![0,1])]
882    #[case(GateType::ZZ, vec![0,1])]
883    fn test_clifford_decomposition(#[case] gate_type: GateType, #[case] args: Vec<usize>) {
884        let mut og_pg = PauliGraph::new(2);
885        og_pg.add_op(Op::Gate {
886            data: GateData::new(gate_type.clone(), args.clone()),
887        });
888        let decomposed_gates = decompose_clifford(&gate_type, &args);
889        let mut decomposed_pg = PauliGraph::new(2);
890        for sub_gate in decomposed_gates {
891            decomposed_pg.add_op(Op::Gate { data: sub_gate });
892        }
893        assert!(compare_unitaries_via_tk(&og_pg, &decomposed_pg));
894    }
895
896    #[rstest]
897    #[case(true, 2.0, 1.6)]
898    #[case(false, 2.0, 1.6)]
899    #[case(false, 3.0, 1.25)]
900    #[case(true, 3.0, 1.25)]
901    fn test_clifford_phased_x(#[case] forward: bool, #[case] alpha: f64, #[case] beta: f64) {
902        let mut pg = PauliGraph::new(1);
903        pg.add_op(Op::Gate {
904            data: GateData::new(GateType::PHASEDX, vec![0]).with_params(vec![alpha, beta]),
905        });
906        pg.add_op(Op::Gate {
907            data: GateData::new(GateType::RZ, vec![0]).with_params(vec![0.7]),
908        });
909        let transformed = CanonicalFormPass::new()
910            .with_forward(forward)
911            .transform(&pg);
912        assert_eq!(transformed.get_ops().len(), 2);
913        assert!(compare_unitaries_via_tk(&pg, &transformed));
914    }
915}