Skip to main content

tk_pg_optimize/
commuting_sets.rs

1use crate::packed_op::{PackedOp, PendingPackedOp};
2use tk_pg_core::{Op, PGPass, PauliGraph};
3
4fn group_ops(pg: &PauliGraph, max_set_size: usize) -> PauliGraph {
5    let mut output_pg = PauliGraph::new(pg.get_n_qubits());
6    let mut commuting_set: Vec<PackedOp> = Vec::new();
7    if pg.get_ops().is_empty() {
8        return output_pg;
9    }
10    output_pg.add_op(Op::SetBoundary);
11    for op in pg.get_ops() {
12        if matches!(op, Op::SetBoundary) {
13            continue;
14        }
15        let pending_op = PendingPackedOp::new(op.clone());
16        if commuting_set.iter().all(|s| s.commute_with(&pending_op))
17            && commuting_set.len() < max_set_size
18        {
19            commuting_set.push(pending_op.into());
20        } else if !commuting_set.is_empty() {
21            commuting_set
22                .drain(..)
23                .for_each(|set_op| output_pg.add_op(set_op.into()));
24            output_pg.add_op(Op::SetBoundary);
25            commuting_set.push(pending_op.into());
26        }
27    }
28    if !commuting_set.is_empty() {
29        commuting_set
30            .drain(..)
31            .for_each(|set_op| output_pg.add_op(set_op.into()));
32        output_pg.add_op(Op::SetBoundary);
33    }
34    if output_pg.get_ops().len() == 1 {
35        output_pg.remove_op(0);
36    }
37    output_pg
38}
39
40/// Groups commuting [`PauliGraph`] operations by inserting [`Op::SetBoundary`]
41/// operations.
42///
43/// This pass checks only the commutation of [`Op::Rotation`], [`Op::Measure`],
44/// [`Op::Reset`], and [`Op::ConditionalBox`]. All other operations are treated
45/// as non-commuting.
46///
47/// Consider running the `CanonicalFormPass` first.
48///
49/// # Warning
50///
51/// This pass does not insert group boundaries inside an [`Op::ConditionalBox`].
52///
53/// # Fields
54///
55/// - `max_set_size` (`usize`) - Maximum size of a commuting set. The default is
56///   50.
57///
58/// # Examples
59///
60/// ```
61/// use tk_pg_optimize::GroupCommutingOpsPass;
62///
63/// let s = GroupCommutingOpsPass::new().with_max_set_size(100);
64/// ```
65pub struct GroupCommutingOpsPass {
66    max_set_size: usize,
67}
68
69impl Default for GroupCommutingOpsPass {
70    fn default() -> Self {
71        Self::new()
72    }
73}
74
75impl GroupCommutingOpsPass {
76    /// Create a new instance of `GroupCommutingOpsPass` with default parameters.
77    pub fn new() -> Self {
78        Self { max_set_size: 50 }
79    }
80
81    /// Set the maximum size of a commuting set.
82    ///
83    /// # Arguments
84    ///
85    /// - `mut self` (`GroupCommutingOpsPass`) - The current instance of the pass.
86    /// - `max_set_size` (`usize`) - Maximum size of a commuting set.
87    ///
88    /// # Returns
89    ///
90    /// - `Self` - The updated instance of the pass.
91    ///
92    /// # Panics
93    ///
94    /// Panics if `max_set_size` is zero.
95    ///
96    pub fn with_max_set_size(mut self, max_set_size: usize) -> Self {
97        if max_set_size == 0 {
98            panic!("max_set_size must be greater than 0");
99        }
100        self.max_set_size = max_set_size;
101        self
102    }
103}
104
105impl PGPass for GroupCommutingOpsPass {
106    fn transform(&self, pg: &PauliGraph) -> PauliGraph {
107        group_ops(pg, self.max_set_size)
108    }
109}
110
111#[cfg(test)]
112mod tests {
113    use tk_pg_core::{
114        BlackBoxData, ConditionalBoxData, GateData, GateType, MeasureData, Pauli, ResetData,
115        RotationData,
116    };
117
118    use super::*;
119
120    #[test]
121    fn test_empty_graph() {
122        let pg = PauliGraph::new(2);
123        let grouped_pg = GroupCommutingOpsPass::new().transform(&pg);
124        assert_eq!(grouped_pg, pg);
125    }
126
127    #[test]
128    fn test_group_ops() {
129        let mut pg = PauliGraph::new(2);
130        // boundary
131        pg.add_op(Op::Rotation {
132            data: RotationData::new(vec![Pauli::X, Pauli::I], 0.1),
133        });
134        pg.add_op(Op::Rotation {
135            data: RotationData::new(vec![Pauli::X, Pauli::X], 0.1),
136        });
137        // boundary
138        pg.add_op(Op::Rotation {
139            data: RotationData::new(vec![Pauli::Z, Pauli::I], 0.1),
140        });
141        pg.add_op(Op::Rotation {
142            data: RotationData::new(vec![Pauli::Z, Pauli::X], 0.2),
143        });
144        pg.add_op(Op::Measure {
145            data: MeasureData::new(vec![Pauli::Z, Pauli::X], true, 0),
146        });
147        // boundary
148        pg.add_op(Op::Reset {
149            data: ResetData::new(
150                vec![Pauli::Z, Pauli::I],
151                vec![Pauli::X, Pauli::I],
152                true,
153                true,
154            ),
155        });
156        // boundary
157        let group_pass = GroupCommutingOpsPass::new();
158        let grouped_pg = group_pass.transform(&pg);
159        // 3 groups
160        assert_eq!(grouped_pg.get_ops().len(), 10);
161    }
162
163    #[test]
164    fn test_measurements_writing_same_cbit_are_in_separate_sets() {
165        let first_measurement = Op::Measure {
166            data: MeasureData::new(vec![Pauli::X, Pauli::I], false, 0),
167        };
168        let second_measurement = Op::Measure {
169            data: MeasureData::new(vec![Pauli::I, Pauli::Z], false, 0),
170        };
171        let pg = PauliGraph::new(2)
172            .with_ops(vec![first_measurement.clone(), second_measurement.clone()]);
173
174        let grouped_pg = GroupCommutingOpsPass::new().transform(&pg);
175
176        assert_eq!(
177            grouped_pg,
178            PauliGraph::new(2).with_ops(vec![
179                Op::SetBoundary,
180                first_measurement,
181                Op::SetBoundary,
182                second_measurement,
183                Op::SetBoundary,
184            ])
185        );
186    }
187
188    #[test]
189    fn test_black_boxes() {
190        let mut pg = PauliGraph::new(2);
191        // boundary
192        pg.add_op(Op::Rotation {
193            data: RotationData::new(vec![Pauli::X, Pauli::I], 0.1),
194        });
195        pg.add_op(Op::Rotation {
196            data: RotationData::new(vec![Pauli::X, Pauli::X], 0.5),
197        });
198        // boundary
199        pg.add_op(Op::BlackBox {
200            data: BlackBoxData::new(vec![0], "bb".into()),
201        });
202        // boundary
203        pg.add_op(Op::BlackBox {
204            data: BlackBoxData::new(vec![1], "bb2".into()),
205        });
206        // boundary
207        pg.add_op(Op::Rotation {
208            data: RotationData::new(vec![Pauli::Z, Pauli::Z], 0.5),
209        });
210        // boundary
211        let group_pass = GroupCommutingOpsPass::new();
212        let grouped_pg = group_pass.transform(&pg);
213        // Each black box should occupy its own group.
214        assert_eq!(grouped_pg.get_ops().len(), 10);
215    }
216
217    #[test]
218    fn test_non_pauli_ops() {
219        let mut pg = PauliGraph::new(2);
220        // boundary
221        pg.add_op(Op::Gate {
222            data: GateData::new(GateType::RX, vec![0]).with_params(vec![1.5]),
223        });
224        // boundary
225        pg.add_op(Op::Gate {
226            data: GateData::new(GateType::RX, vec![0]).with_params(vec![1.2]),
227        });
228        // boundary
229        let group_pass = GroupCommutingOpsPass::new();
230        let grouped_pg = group_pass.transform(&pg);
231        assert_eq!(grouped_pg.get_ops().len(), 5);
232    }
233
234    #[test]
235    fn test_conditional_boxes() {
236        let mut pg = PauliGraph::new(2);
237        // boundary
238        pg.add_op(Op::Rotation {
239            data: RotationData::new(vec![Pauli::X, Pauli::I], 0.1),
240        });
241        pg.add_op(Op::Rotation {
242            data: RotationData::new(vec![Pauli::X, Pauli::X], 0.5),
243        });
244        pg.add_op(Op::ConditionalBox {
245            data: ConditionalBoxData::new(
246                vec![
247                    Op::Rotation {
248                        data: RotationData::new(vec![Pauli::X, Pauli::I], 0.1),
249                    },
250                    Op::Rotation {
251                        data: RotationData::new(vec![Pauli::X, Pauli::X], 0.1),
252                    },
253                ],
254                vec![0],
255                vec![true],
256            ),
257        });
258        pg.add_op(Op::Rotation {
259            data: RotationData::new(vec![Pauli::I, Pauli::X], 0.5),
260        });
261        // boundary
262        let group_pass = GroupCommutingOpsPass::new();
263        let grouped_pg = group_pass.transform(&pg);
264        // One set
265        assert_eq!(grouped_pg.get_ops().len(), 6);
266    }
267
268    #[test]
269    fn test_measurement_writing_condition_bit_is_separate_from_conditional_box() {
270        let mut pg = PauliGraph::new(2);
271        pg.add_op(Op::Measure {
272            data: MeasureData::new(vec![Pauli::X, Pauli::I], false, 0),
273        });
274        pg.add_op(Op::ConditionalBox {
275            data: ConditionalBoxData::new(
276                vec![Op::Rotation {
277                    data: RotationData::new(vec![Pauli::X, Pauli::I], 0.1),
278                }],
279                vec![0],
280                vec![true],
281            ),
282        });
283
284        let grouped_pg = GroupCommutingOpsPass::new().transform(&pg);
285
286        assert_eq!(grouped_pg.get_ops().len(), 5);
287        assert!(matches!(grouped_pg.get_ops()[2], Op::SetBoundary));
288    }
289
290    #[test]
291    fn test_measurement_and_conditional_measurement_writing_same_cbit_are_separate() {
292        let mut pg = PauliGraph::new(2);
293        pg.add_op(Op::Measure {
294            data: MeasureData::new(vec![Pauli::X, Pauli::I], false, 0),
295        });
296        pg.add_op(Op::ConditionalBox {
297            data: ConditionalBoxData::new(
298                vec![Op::Measure {
299                    data: MeasureData::new(vec![Pauli::I, Pauli::Z], false, 0),
300                }],
301                vec![1],
302                vec![true],
303            ),
304        });
305
306        let grouped_pg = GroupCommutingOpsPass::new().transform(&pg);
307
308        assert_eq!(grouped_pg.get_ops().len(), 5);
309        assert!(matches!(grouped_pg.get_ops()[2], Op::SetBoundary));
310    }
311
312    #[test]
313    fn test_conditional_boxes_with_classical_dependencies_are_separate() {
314        let writer = Op::ConditionalBox {
315            data: ConditionalBoxData::new(
316                vec![Op::Measure {
317                    data: MeasureData::new(vec![Pauli::X, Pauli::I], false, 0),
318                }],
319                vec![1],
320                vec![true],
321            ),
322        };
323        let reader = Op::ConditionalBox {
324            data: ConditionalBoxData::new(
325                vec![Op::Rotation {
326                    data: RotationData::new(vec![Pauli::I, Pauli::Z], 0.1),
327                }],
328                vec![0],
329                vec![true],
330            ),
331        };
332        let second_writer = Op::ConditionalBox {
333            data: ConditionalBoxData::new(
334                vec![Op::Measure {
335                    data: MeasureData::new(vec![Pauli::I, Pauli::Z], false, 0),
336                }],
337                vec![2],
338                vec![true],
339            ),
340        };
341        let dependent_pairs = [
342            ("write followed by read", writer.clone(), reader.clone()),
343            ("read followed by write", reader, writer.clone()),
344            ("write followed by write", writer, second_writer),
345        ];
346
347        for (case, first_box, second_box) in dependent_pairs {
348            let grouped_pg = GroupCommutingOpsPass::new().transform(
349                &PauliGraph::new(2).with_ops(vec![first_box.clone(), second_box.clone()]),
350            );
351
352            assert_eq!(
353                grouped_pg,
354                PauliGraph::new(2).with_ops(vec![
355                    Op::SetBoundary,
356                    first_box,
357                    Op::SetBoundary,
358                    second_box,
359                    Op::SetBoundary,
360                ]),
361                "failed case: {case}"
362            );
363        }
364    }
365
366    #[test]
367    fn test_conditional_boxes_reading_same_cbit_commute() {
368        let first_box = Op::ConditionalBox {
369            data: ConditionalBoxData::new(
370                vec![Op::Rotation {
371                    data: RotationData::new(vec![Pauli::X, Pauli::I], 0.1),
372                }],
373                vec![0],
374                vec![true],
375            ),
376        };
377        let second_box = Op::ConditionalBox {
378            data: ConditionalBoxData::new(
379                vec![Op::Rotation {
380                    data: RotationData::new(vec![Pauli::I, Pauli::Z], 0.1),
381                }],
382                vec![0],
383                vec![true],
384            ),
385        };
386
387        let grouped_pg = GroupCommutingOpsPass::new()
388            .transform(&PauliGraph::new(2).with_ops(vec![first_box.clone(), second_box.clone()]));
389
390        assert_eq!(
391            grouped_pg,
392            PauliGraph::new(2).with_ops(vec![
393                Op::SetBoundary,
394                first_box,
395                second_box,
396                Op::SetBoundary,
397            ])
398        );
399    }
400
401    #[test]
402    fn test_measurement_commutes_with_classically_independent_conditional_box() {
403        let mut pg = PauliGraph::new(2);
404        pg.add_op(Op::Measure {
405            data: MeasureData::new(vec![Pauli::X, Pauli::I], false, 0),
406        });
407        pg.add_op(Op::ConditionalBox {
408            data: ConditionalBoxData::new(
409                vec![Op::Rotation {
410                    data: RotationData::new(vec![Pauli::I, Pauli::Z], 0.1),
411                }],
412                vec![1],
413                vec![true],
414            ),
415        });
416
417        let grouped_pg = GroupCommutingOpsPass::new().transform(&pg);
418
419        assert_eq!(grouped_pg.get_ops().len(), 4);
420    }
421
422    #[test]
423    fn test_max_set_size() {
424        let mut pg = PauliGraph::new(2);
425        pg.add_op(Op::Rotation {
426            data: RotationData::new(vec![Pauli::X, Pauli::I], 0.1),
427        });
428        pg.add_op(Op::Rotation {
429            data: RotationData::new(vec![Pauli::X, Pauli::X], 0.1),
430        });
431        pg.add_op(Op::Rotation {
432            data: RotationData::new(vec![Pauli::Z, Pauli::I], 0.1),
433        });
434        pg.add_op(Op::Rotation {
435            data: RotationData::new(vec![Pauli::Z, Pauli::X], 0.2),
436        });
437        let group_pass = GroupCommutingOpsPass::new().with_max_set_size(1);
438        let grouped_pg = group_pass.transform(&pg);
439        assert_eq!(grouped_pg.get_ops().len(), 9);
440    }
441
442    #[test]
443    fn test_pg_contains_set_boundary() {
444        let mut pg = PauliGraph::new(2);
445        pg.add_op(Op::SetBoundary);
446        pg.add_op(Op::Rotation {
447            data: RotationData::new(vec![Pauli::X, Pauli::I], 0.1),
448        });
449        pg.add_op(Op::Rotation {
450            data: RotationData::new(vec![Pauli::X, Pauli::X], 0.1),
451        });
452        let group_pass = GroupCommutingOpsPass::new();
453        let grouped_pg = group_pass.transform(&pg);
454        assert_eq!(grouped_pg.get_ops().len(), 4);
455    }
456
457    #[test]
458    fn test_pg_contains_only_set_boundaries() {
459        let pg = PauliGraph::new(2).with_ops(vec![Op::SetBoundary, Op::SetBoundary]);
460        let grouped_pg = GroupCommutingOpsPass::new().transform(&pg);
461        assert_eq!(grouped_pg, PauliGraph::new(2));
462    }
463
464    #[test]
465    fn test_idempotent() {
466        let mut pg = PauliGraph::new(2);
467        pg.add_op(Op::Rotation {
468            data: RotationData::new(vec![Pauli::X, Pauli::I], 0.1),
469        });
470        pg.add_op(Op::Rotation {
471            data: RotationData::new(vec![Pauli::X, Pauli::X], 0.1),
472        });
473        pg.add_op(Op::Rotation {
474            data: RotationData::new(vec![Pauli::Z, Pauli::I], 0.1),
475        });
476        pg.add_op(Op::Rotation {
477            data: RotationData::new(vec![Pauli::Z, Pauli::X], 0.2),
478        });
479        let group_pass = GroupCommutingOpsPass::new();
480        let grouped_pg = group_pass.transform(&pg);
481        let regrouped_pg = group_pass.transform(&grouped_pg);
482        assert_eq!(grouped_pg, regrouped_pg);
483    }
484}