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
40pub 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 pub fn new() -> Self {
78 Self { max_set_size: 50 }
79 }
80
81 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 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 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 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 let group_pass = GroupCommutingOpsPass::new();
158 let grouped_pg = group_pass.transform(&pg);
159 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 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 pg.add_op(Op::BlackBox {
200 data: BlackBoxData::new(vec![0], "bb".into()),
201 });
202 pg.add_op(Op::BlackBox {
204 data: BlackBoxData::new(vec![1], "bb2".into()),
205 });
206 pg.add_op(Op::Rotation {
208 data: RotationData::new(vec![Pauli::Z, Pauli::Z], 0.5),
209 });
210 let group_pass = GroupCommutingOpsPass::new();
212 let grouped_pg = group_pass.transform(&pg);
213 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 pg.add_op(Op::Gate {
222 data: GateData::new(GateType::RX, vec![0]).with_params(vec![1.5]),
223 });
224 pg.add_op(Op::Gate {
226 data: GateData::new(GateType::RX, vec![0]).with_params(vec![1.2]),
227 });
228 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 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 let group_pass = GroupCommutingOpsPass::new();
263 let grouped_pg = group_pass.transform(&pg);
264 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}