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 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 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 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 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 if let Op::Rotation { data: last_data } = &last_op.op {
56 angle += last_data.get_angle();
57 } else {
58 panic!("expected a rotation op");
60 }
61 removed[last_index] = true;
63 indices.pop();
65 }
66 }
67 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 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
195pub struct RotationMergingPass {}
208
209impl Default for RotationMergingPass {
210 fn default() -> Self {
211 Self::new()
212 }
213}
214
215impl RotationMergingPass {
216 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}