Skip to main content

tk_pg_optimize/
rotation_merging.rs

1use crate::packed_op::{PackedOp, XZPackedPaulis};
2use std::collections::HashMap;
3use tk_pg_core::{
4    BlackBoxData, ConditionalBoxData, MeasureData, Op, PGPass, PauliGraph, ResetData, RotationData,
5};
6use tk_pg_ir_kernels::PGTableau;
7use tk_pg_qm_tableau::Tableau;
8use tk_pg_utils::cliff_angle;
9
10fn rotation_merging(pg: &PauliGraph) -> PauliGraph {
11    let n_qubits = pg.get_n_qubits();
12    let n_ops = pg.get_ops().len();
13    let mut output_pg = PauliGraph::new(n_qubits);
14    let mut output_ops: Vec<PackedOp> = Vec::with_capacity(n_ops);
15    // Use `removed` to flag operations removed from `output_ops`.
16    let mut removed: Vec<bool> = Vec::with_capacity(n_ops);
17    let mut tab: Tableau = Tableau::eye(n_qubits);
18    let mut tab_touched = false;
19    // Group rotations by their Pauli strings while preserving their order in
20    // the original graph. For each rotation, find the most recent rotation with
21    // the same Pauli string. If it commutes with every intervening operation,
22    // merge its angle into the current rotation and mark the earlier rotation
23    // for removal. Otherwise, append the current rotation without merging it.
24    //
25    // Lookup keys use XZ bit-packing, whereas output operations use ZX
26    // bit-packing. Commutation checks require these opposite encodings.
27    let mut lookup: HashMap<XZPackedPaulis, Vec<usize>> = HashMap::new();
28    for op in pg.get_ops().iter() {
29        match op {
30            Op::Rotation { data } => {
31                let (s, sign_bit) = tab.conjugate_string(data.get_string());
32                let mut angle = if sign_bit {
33                    -data.get_angle()
34                } else {
35                    data.get_angle()
36                };
37                let key = XZPackedPaulis::from(s.as_slice());
38                // Check whether a previous rotation with the same Pauli string
39                // can be merged with the current one.
40                if let Some(indices) = lookup.get_mut(&key)
41                    && let Some(&last_index) = indices.last()
42                {
43                    let last_op = &output_ops[last_index];
44                    // Check whether `last_op` commutes with every intervening
45                    // op, ignoring operations already marked for removal.
46                    let commute =
47                        output_ops[last_index + 1..]
48                            .iter()
49                            .enumerate()
50                            .all(|(i, inter_op)| {
51                                removed[last_index + 1 + i] || inter_op.commute_with_string(&key)
52                            });
53                    if commute {
54                        // Merge the angles.
55                        if let Op::Rotation { data: last_data } = &last_op.op {
56                            angle += last_data.get_angle();
57                        } else {
58                            // The lookup contains only rotations.
59                            panic!("expected a rotation op");
60                        }
61                        // Mark the previous rotation for removal.
62                        removed[last_index] = true;
63                        // Remove the previous rotation from the lookup.
64                        indices.pop();
65                    }
66                }
67                // If the angle is Clifford, fold the rotation into the tableau.
68                // Because the tableau faces backwards and the rotation is to
69                // its left, post-compose the inverse rotation (with the
70                // negative angle).
71                let cliff = cliff_angle(angle);
72                if cliff.is_some() {
73                    tab.postcompose_op(&Op::Rotation {
74                        data: RotationData::new(s, -angle),
75                    });
76                    tab_touched = true;
77                } else {
78                    output_ops.push(PackedOp::new(Op::Rotation {
79                        data: RotationData::new(s.clone(), angle),
80                    }));
81                    removed.push(false);
82                    lookup.entry(key).or_default().push(output_ops.len() - 1);
83                }
84            }
85            Op::Measure { data } => {
86                let (s, sign_bit) = tab.conjugate_string(data.get_string());
87                output_ops.push(PackedOp::new(Op::Measure {
88                    data: MeasureData::new(s, sign_bit ^ data.get_sign_bit(), data.get_cbit()),
89                }));
90                removed.push(false);
91            }
92            Op::Reset { data } => {
93                let (z_string, mut z_sign_bit) = tab.conjugate_string(data.get_first_string());
94                let (x_string, mut x_sign_bit) = tab.conjugate_string(data.get_second_string());
95                z_sign_bit ^= data.get_first_sign_bit();
96                x_sign_bit ^= data.get_second_sign_bit();
97                output_ops.push(PackedOp::new(Op::Reset {
98                    data: ResetData::new(z_string, x_string, z_sign_bit, x_sign_bit),
99                }));
100                removed.push(false);
101            }
102            Op::ConditionalBox { data } => {
103                let mut new_cond_ops = Vec::with_capacity(data.get_ops().len());
104                for cond_op in data.get_ops() {
105                    match cond_op {
106                        Op::Rotation { data } => {
107                            let (s, sign_bit) = tab.conjugate_string(data.get_string());
108                            let theta = if sign_bit {
109                                -data.get_angle()
110                            } else {
111                                data.get_angle()
112                            };
113                            new_cond_ops.push(Op::Rotation {
114                                data: RotationData::new(s, theta),
115                            });
116                        }
117                        Op::Reset { data } => {
118                            let (z_string, mut z_sign_bit) =
119                                tab.conjugate_string(data.get_first_string());
120                            let (x_string, mut x_sign_bit) =
121                                tab.conjugate_string(data.get_second_string());
122                            z_sign_bit ^= data.get_first_sign_bit();
123                            x_sign_bit ^= data.get_second_sign_bit();
124                            new_cond_ops.push(Op::Reset {
125                                data: ResetData::new(z_string, x_string, z_sign_bit, x_sign_bit),
126                            });
127                        }
128                        Op::Measure { data } => {
129                            let (s, mut sign_bit) = tab.conjugate_string(data.get_string());
130                            sign_bit ^= data.get_sign_bit();
131                            new_cond_ops.push(Op::Measure {
132                                data: MeasureData::new(s, sign_bit, data.get_cbit()),
133                            });
134                        }
135                        _ => unimplemented!(
136                            "only non-blocking Pauli operations (`Rotation`, `Reset`, and `Measure`) are currently supported inside conditional boxes"
137                        ),
138                    }
139                }
140                output_ops.push(PackedOp::new(Op::ConditionalBox {
141                    data: ConditionalBoxData::new(
142                        new_cond_ops,
143                        data.get_conditional_bits().clone(),
144                        data.get_conditional_values().clone(),
145                    ),
146                }));
147                removed.push(false);
148            }
149            Op::BlackBox { data } => {
150                if tab_touched {
151                    output_ops.push(PackedOp::new(Op::Tableau {
152                        data: tab.invert().into(),
153                    }));
154                    removed.push(false);
155                }
156                output_ops.push(PackedOp::new(Op::BlackBox {
157                    data: BlackBoxData::new(data.get_qubits().clone(), data.get_content().clone()),
158                }));
159                removed.push(false);
160                tab = Tableau::eye(n_qubits);
161                tab_touched = false;
162            }
163            Op::Tableau { data } => {
164                let mut tableau_from_op = Tableau::from(data.clone()).invert();
165                tableau_from_op.compose(&tab);
166                tab = tableau_from_op;
167                tab_touched = true;
168            }
169            Op::SetBoundary => {
170                // Remove set boundaries because rotation merging can produce
171                // empty sets.
172                continue;
173            }
174            _ => {
175                panic!(
176                    "Unsupported op type in `RotationMergingPass`. Consider running the `CanonicalFormPass` first."
177                );
178            }
179        }
180    }
181    assert_eq!(output_ops.len(), removed.len());
182    for (op, is_removed) in output_ops.into_iter().zip(removed) {
183        if !is_removed {
184            output_pg.add_op(op.op);
185        }
186    }
187    if tab_touched {
188        output_pg.add_op(Op::Tableau {
189            data: tab.invert().into(),
190        });
191    }
192    output_pg
193}
194
195/// Greedily merges Pauli rotations with the same Pauli string when possible.
196///
197/// Consider running the `CanonicalFormPass` first.
198///
199/// # Panics
200///
201/// The supported operations are [`Op::Rotation`], [`Op::Measure`],
202/// [`Op::Reset`], [`Op::ConditionalBox`], [`Op::BlackBox`], [`Op::Tableau`],
203/// and [`Op::SetBoundary`]. The pass panics if the graph contains any other
204/// operation, or if a conditional box contains an operation other than
205/// [`Op::Rotation`], [`Op::Reset`], or [`Op::Measure`].
206///
207pub struct RotationMergingPass {}
208
209impl Default for RotationMergingPass {
210    fn default() -> Self {
211        Self::new()
212    }
213}
214
215impl RotationMergingPass {
216    /// Create a new instance of `RotationMergingPass`.
217    pub fn new() -> Self {
218        Self {}
219    }
220}
221impl PGPass for RotationMergingPass {
222    fn transform(&self, pg: &PauliGraph) -> PauliGraph {
223        rotation_merging(pg)
224    }
225}
226
227#[cfg(test)]
228mod tests {
229    use super::*;
230    use rand::{RngExt, SeedableRng, rngs::StdRng};
231    use tk_pg_converter::compare_unitaries_via_tk;
232    use tk_pg_core::{GateData, GateType, Pauli, TableauData};
233
234    fn s_tableau_op() -> Op {
235        let mut tableau = Tableau::eye(1);
236        tableau.postcompose_op(&Op::Gate {
237            data: GateData::new(GateType::S, vec![0]),
238        });
239        Op::Tableau {
240            data: tableau.into(),
241        }
242    }
243
244    #[test]
245    fn test_rotation_merging() {
246        let mut pg = PauliGraph::new(2);
247        pg.add_op(Op::Rotation {
248            data: RotationData::new(vec![Pauli::X, Pauli::I], 0.1),
249        });
250        pg.add_op(Op::Rotation {
251            data: RotationData::new(vec![Pauli::X, Pauli::I], 0.2),
252        });
253        pg.add_op(Op::Rotation {
254            data: RotationData::new(vec![Pauli::Z, Pauli::I], 0.1),
255        });
256        pg.add_op(Op::Rotation {
257            data: RotationData::new(vec![Pauli::Z, Pauli::I], 0.2),
258        });
259        let merged_pg = rotation_merging(&pg);
260        assert_eq!(merged_pg.get_ops().len(), 2);
261        assert!(compare_unitaries_via_tk(&pg, &merged_pg));
262    }
263
264    #[test]
265    fn test_rotation_merging_v() {
266        let mut pg = PauliGraph::new(2);
267        pg.add_op(Op::Rotation {
268            data: RotationData::new(vec![Pauli::X, Pauli::I], 0.1),
269        });
270        pg.add_op(Op::Rotation {
271            data: RotationData::new(vec![Pauli::X, Pauli::I], 0.4),
272        });
273        let merged_pg = rotation_merging(&pg);
274        assert_eq!(merged_pg.get_ops().len(), 1);
275        assert!(compare_unitaries_via_tk(&pg, &merged_pg));
276    }
277
278    #[test]
279    fn test_x_rotations_only() {
280        let mut pg = PauliGraph::new(2);
281        pg.add_op(Op::Rotation {
282            data: RotationData::new(vec![Pauli::X, Pauli::I], 0.1),
283        });
284        pg.add_op(Op::Rotation {
285            data: RotationData::new(vec![Pauli::X, Pauli::X], 0.4),
286        });
287
288        pg.add_op(Op::Rotation {
289            data: RotationData::new(vec![Pauli::X, Pauli::X], 0.4),
290        });
291
292        pg.add_op(Op::Rotation {
293            data: RotationData::new(vec![Pauli::X, Pauli::X], 0.4),
294        });
295        pg.add_op(Op::Rotation {
296            data: RotationData::new(vec![Pauli::X, Pauli::I], 0.4),
297        });
298        let merged_pg = rotation_merging(&pg);
299        assert_eq!(merged_pg.get_ops().len(), 2);
300        assert!(compare_unitaries_via_tk(&pg, &merged_pg));
301    }
302
303    #[test]
304    fn test_rotation_merging_across_commuting_ops() {
305        let commuting_ops = [
306            (
307                "measurement",
308                Op::Measure {
309                    data: MeasureData::new(vec![Pauli::I, Pauli::Z], true, 3),
310                },
311            ),
312            (
313                "reset",
314                Op::Reset {
315                    data: ResetData::new(
316                        vec![Pauli::I, Pauli::Z],
317                        vec![Pauli::I, Pauli::X],
318                        true,
319                        false,
320                    ),
321                },
322            ),
323            (
324                "conditional box",
325                Op::ConditionalBox {
326                    data: ConditionalBoxData::new(
327                        vec![Op::Rotation {
328                            data: RotationData::new(vec![Pauli::I, Pauli::Z], 0.125),
329                        }],
330                        vec![2],
331                        vec![false],
332                    ),
333                },
334            ),
335        ];
336
337        for (case, commuting_op) in commuting_ops {
338            let pg = PauliGraph::new(2).with_ops(vec![
339                Op::Rotation {
340                    data: RotationData::new(vec![Pauli::X, Pauli::I], 0.125),
341                },
342                commuting_op.clone(),
343                Op::Rotation {
344                    data: RotationData::new(vec![Pauli::X, Pauli::I], 0.125),
345                },
346            ]);
347
348            let merged_pg = rotation_merging(&pg);
349
350            assert_eq!(
351                merged_pg,
352                PauliGraph::new(2).with_ops(vec![
353                    commuting_op,
354                    Op::Rotation {
355                        data: RotationData::new(vec![Pauli::X, Pauli::I], 0.25),
356                    },
357                ]),
358                "failed case: {case}"
359            );
360        }
361    }
362
363    #[test]
364    fn test_rotation_not_merged_across_anticommuting_op() {
365        let pg = PauliGraph::new(1).with_ops(vec![
366            Op::Rotation {
367                data: RotationData::new(vec![Pauli::X], 0.125),
368            },
369            Op::Rotation {
370                data: RotationData::new(vec![Pauli::Z], 0.25),
371            },
372            Op::Rotation {
373                data: RotationData::new(vec![Pauli::X], 0.125),
374            },
375        ]);
376
377        let merged_pg = rotation_merging(&pg);
378
379        assert_eq!(merged_pg, pg);
380    }
381
382    #[test]
383    fn test_tableau_propagation_through_supported_ops() {
384        let conditional_box = Op::ConditionalBox {
385            data: ConditionalBoxData::new(
386                vec![
387                    Op::Rotation {
388                        data: RotationData::new(vec![Pauli::X], 0.25),
389                    },
390                    Op::Measure {
391                        data: MeasureData::new(vec![Pauli::X], false, 4),
392                    },
393                    Op::Reset {
394                        data: ResetData::new(vec![Pauli::Z], vec![Pauli::X], false, true),
395                    },
396                ],
397                vec![4, 5],
398                vec![true, false],
399            ),
400        };
401        let pg = PauliGraph::new(1).with_ops(vec![
402            s_tableau_op(),
403            Op::Measure {
404                data: MeasureData::new(vec![Pauli::X], true, 3),
405            },
406            Op::Reset {
407                data: ResetData::new(vec![Pauli::Z], vec![Pauli::X], true, false),
408            },
409            conditional_box,
410        ]);
411
412        let transformed = rotation_merging(&pg);
413
414        assert_eq!(
415            transformed,
416            PauliGraph::new(1).with_ops(vec![
417                Op::Measure {
418                    data: MeasureData::new(vec![Pauli::Y], false, 3),
419                },
420                Op::Reset {
421                    data: ResetData::new(vec![Pauli::Z], vec![Pauli::Y], true, true),
422                },
423                Op::ConditionalBox {
424                    data: ConditionalBoxData::new(
425                        vec![
426                            Op::Rotation {
427                                data: RotationData::new(vec![Pauli::Y], -0.25),
428                            },
429                            Op::Measure {
430                                data: MeasureData::new(vec![Pauli::Y], true, 4),
431                            },
432                            Op::Reset {
433                                data: ResetData::new(vec![Pauli::Z], vec![Pauli::Y], false, false,),
434                            },
435                        ],
436                        vec![4, 5],
437                        vec![true, false],
438                    ),
439                },
440                s_tableau_op(),
441            ])
442        );
443    }
444
445    #[test]
446    fn test_preserving_tableau() {
447        let mut pg = PauliGraph::new(2);
448        let z_images = vec![
449            (vec![Pauli::X, Pauli::X], true),
450            (vec![Pauli::Z, Pauli::Z], false),
451        ];
452        let x_images = vec![
453            (vec![Pauli::Z, Pauli::I], true),
454            (vec![Pauli::I, Pauli::X], true),
455        ];
456        pg.add_op(Op::Tableau {
457            data: TableauData::new(z_images, x_images),
458        });
459        let pass = RotationMergingPass::new();
460        let transformed = pass.transform(&pg);
461        assert!(compare_unitaries_via_tk(&pg, &transformed));
462    }
463
464    #[test]
465    fn test_preserving_black_box() {
466        let mut pg = PauliGraph::new(1);
467        pg.add_op(Op::BlackBox {
468            data: BlackBoxData::new(vec![0], "payload".into()),
469        });
470        let transformed = RotationMergingPass::new().transform(&pg);
471        assert_eq!(pg, transformed);
472    }
473
474    #[test]
475    fn test_pending_tableau_emitted_before_black_box() {
476        let black_box = Op::BlackBox {
477            data: BlackBoxData::new(vec![0], "payload".into()),
478        };
479        let pg = PauliGraph::new(1).with_ops(vec![
480            Op::Rotation {
481                data: RotationData::new(vec![Pauli::Z], 0.5),
482            },
483            black_box.clone(),
484        ]);
485
486        let transformed = rotation_merging(&pg);
487
488        assert_eq!(
489            transformed,
490            PauliGraph::new(1).with_ops(vec![s_tableau_op(), black_box])
491        );
492    }
493
494    #[test]
495    fn test_set_boundaries_removed() {
496        let rotation = Op::Rotation {
497            data: RotationData::new(vec![Pauli::X], 0.25),
498        };
499        let pg =
500            PauliGraph::new(1).with_ops(vec![Op::SetBoundary, rotation.clone(), Op::SetBoundary]);
501
502        let transformed = rotation_merging(&pg);
503
504        assert_eq!(transformed, PauliGraph::new(1).with_ops(vec![rotation]));
505    }
506
507    #[test]
508    fn test_negative_angle_rotation_merging() {
509        let pg = PauliGraph::new(1).with_ops(vec![
510            Op::Rotation {
511                data: RotationData::new(vec![Pauli::X], -0.125),
512            },
513            Op::Rotation {
514                data: RotationData::new(vec![Pauli::X], 0.375),
515            },
516        ]);
517
518        let transformed = rotation_merging(&pg);
519
520        assert_eq!(
521            transformed,
522            PauliGraph::new(1).with_ops(vec![Op::Rotation {
523                data: RotationData::new(vec![Pauli::X], 0.25),
524            }])
525        );
526        assert!(compare_unitaries_via_tk(&pg, &transformed));
527    }
528
529    #[test]
530    fn test_rotation_cancellation() {
531        let pg = PauliGraph::new(1).with_ops(vec![
532            Op::Rotation {
533                data: RotationData::new(vec![Pauli::X], 0.125),
534            },
535            Op::Rotation {
536                data: RotationData::new(vec![Pauli::X], -0.125),
537            },
538        ]);
539
540        let transformed = rotation_merging(&pg);
541
542        assert_eq!(
543            transformed,
544            PauliGraph::new(1).with_ops(vec![Op::Tableau {
545                data: Tableau::eye(1).into(),
546            }])
547        );
548        assert!(compare_unitaries_via_tk(&pg, &transformed));
549    }
550
551    #[test]
552    #[should_panic(expected = "Unsupported op type in `RotationMergingPass`")]
553    fn test_gate_panics() {
554        let pg = PauliGraph::new(1).with_ops(vec![Op::Gate {
555            data: GateData::new(GateType::RX, vec![0]).with_params(vec![0.25]),
556        }]);
557        RotationMergingPass::new().transform(&pg);
558    }
559
560    #[test]
561    #[should_panic(expected = "only non-blocking Pauli operations")]
562    fn test_unsupported_conditional_op_panics() {
563        let pg = PauliGraph::new(1).with_ops(vec![Op::ConditionalBox {
564            data: ConditionalBoxData::new(
565                vec![Op::BlackBox {
566                    data: BlackBoxData::new(vec![0], "payload".into()),
567                }],
568                vec![0],
569                vec![true],
570            ),
571        }]);
572        RotationMergingPass::new().transform(&pg);
573    }
574
575    #[test]
576    #[should_panic(expected = "No non-identity Pauli found in the string")]
577    fn test_all_identity_clifford_rotation_panics() {
578        let pg = PauliGraph::new(1).with_ops(vec![Op::Rotation {
579            data: RotationData::new(vec![Pauli::I], 0.5),
580        }]);
581        RotationMergingPass::new().transform(&pg);
582    }
583
584    #[test]
585    fn test_random_rotation_merging() {
586        let strings = [
587            vec![Pauli::X, Pauli::I, Pauli::I],
588            vec![Pauli::I, Pauli::Y, Pauli::I],
589            vec![Pauli::I, Pauli::I, Pauli::Z],
590            vec![Pauli::X, Pauli::X, Pauli::I],
591            vec![Pauli::Z, Pauli::Z, Pauli::Z],
592        ];
593        let angles = [-0.125, 0.125, 0.25, 0.5, 0.75, 1.0];
594        let mut rng = StdRng::seed_from_u64(7);
595        let ops = (0..48)
596            .map(|_| Op::Rotation {
597                data: RotationData::new(
598                    strings[rng.random_range(0..strings.len())].clone(),
599                    angles[rng.random_range(0..angles.len())],
600                ),
601            })
602            .collect();
603        let pg = PauliGraph::new(3).with_ops(ops);
604
605        let transformed = rotation_merging(&pg);
606
607        assert!(compare_unitaries_via_tk(&pg, &transformed));
608    }
609
610    #[test]
611    fn test_empty_graph() {
612        let pg = PauliGraph::new(2);
613        let transformed = RotationMergingPass::new().transform(&pg);
614        assert_eq!(pg, transformed);
615    }
616}