1use std::vec;
2
3use crate::tableau_trait::PGTableau;
4use tk_pg_core::{ConditionalBoxData, GateData, GateType, Op, Pauli, PauliGraph, RotationData};
5use tk_pg_utils::{cliff_angle, equiv_0};
6
7pub fn can_be_conjugated(op: &Op) -> bool {
24 match op {
25 Op::Rotation { .. } | Op::Measure { .. } | Op::Reset { .. } | Op::ConditionalBox { .. } => {
26 true
27 }
28 Op::Gate { data } => {
29 is_rotation_gate_type(data)
30 || (*data.get_gate_type() == GateType::Measure)
31 || (*data.get_gate_type() == GateType::Reset)
32 }
33 _ => false,
34 }
35}
36
37fn clifford_dagger(gate: &GateData) -> GateData {
39 let gate_type = match gate.get_gate_type() {
40 GateType::H => GateType::H,
41 GateType::S => GateType::Sdg,
42 GateType::V => GateType::Vdg,
43 GateType::Sdg => GateType::S,
44 GateType::Vdg => GateType::V,
45 GateType::X
46 | GateType::Y
47 | GateType::Z
48 | GateType::XX
49 | GateType::XY
50 | GateType::XZ
51 | GateType::YX
52 | GateType::YY
53 | GateType::YZ
54 | GateType::ZX
55 | GateType::ZY
56 | GateType::ZZ
57 | GateType::SWAP => gate.get_gate_type().clone(),
58 gate_type => panic!("Unsupported gate type for Clifford dagger: {gate_type:?}"),
59 };
60 GateData::new(gate_type, gate.get_args().clone()).with_conditional(
61 gate.get_conditional_bits().clone(),
62 gate.get_conditional_values().clone(),
63 )
64}
65
66pub fn get_dagger<T: PGTableau>(op: &Op) -> Op {
80 match op {
81 Op::Rotation { data } => Op::Rotation {
82 data: RotationData::new(data.get_string().clone(), -data.get_angle()),
83 },
84 Op::Gate { data } => {
85 match data.get_gate_type() {
86 GateType::RX | GateType::RY | GateType::RZ | GateType::ZZPHASE => Op::Gate {
87 data: data.clone().with_params(vec![-data.get_params()[0]]),
88 },
89 GateType::PHASEDX => {
90 Op::Gate {
92 data: data
93 .clone()
94 .with_params(vec![-data.get_params()[0], data.get_params()[1]]),
95 }
96 }
97 GateType::S
98 | GateType::V
99 | GateType::H
100 | GateType::Sdg
101 | GateType::Vdg
102 | GateType::X
103 | GateType::Y
104 | GateType::Z
105 | GateType::XX
106 | GateType::XY
107 | GateType::XZ
108 | GateType::YX
109 | GateType::YY
110 | GateType::YZ
111 | GateType::ZX
112 | GateType::ZY
113 | GateType::ZZ
114 | GateType::SWAP => Op::Gate {
115 data: clifford_dagger(data),
116 },
117 _ => panic!("Unsupported gate type for getting dagger"),
118 }
119 }
120 Op::ConditionalBox { data } => {
121 let new_ops = data
122 .get_ops()
123 .iter()
124 .rev()
125 .map(|op| get_dagger::<T>(op))
126 .collect();
127 Op::ConditionalBox {
128 data: ConditionalBoxData::new(
129 new_ops,
130 data.get_conditional_bits().clone(),
131 data.get_conditional_values().clone(),
132 ),
133 }
134 }
135 Op::Tableau { data } => Op::Tableau {
136 data: T::from(data.clone()).get_dagger().into(),
137 },
138 _ => panic!("Unsupported op type for getting dagger"),
139 }
140}
141
142pub fn is_clifford_gate_type(gate: &GateData) -> bool {
144 matches!(
145 gate.get_gate_type(),
146 GateType::H
147 | GateType::S
148 | GateType::V
149 | GateType::Sdg
150 | GateType::Vdg
151 | GateType::X
152 | GateType::Y
153 | GateType::Z
154 | GateType::XX
155 | GateType::XY
156 | GateType::XZ
157 | GateType::YX
158 | GateType::YY
159 | GateType::YZ
160 | GateType::ZX
161 | GateType::ZY
162 | GateType::ZZ
163 | GateType::SWAP,
164 )
165}
166
167pub fn is_clifford(op: &Op) -> bool {
178 match op {
179 Op::Gate { data } => {
180 data.get_conditional_bits().is_empty()
181 && (is_clifford_gate_type(data)
182 || (is_rotation_gate_type(data)
183 && (data.get_params().iter().all(|&p| cliff_angle(p).is_some())
184 || (data.get_gate_type() == &GateType::PHASEDX
185 && (equiv_0(data.get_params()[0], 2.0)
188 || (equiv_0(data.get_params()[0], 1.0)
189 && equiv_0(data.get_params()[1], 0.25)))))))
190 }
191 Op::Rotation { data } => cliff_angle(data.get_angle()).is_some(),
192 Op::Tableau { .. } => true,
193 _ => false,
194 }
195}
196
197fn is_rotation_gate_type(gate: &GateData) -> bool {
199 matches!(
200 gate.get_gate_type(),
201 GateType::RX | GateType::RY | GateType::RZ | GateType::ZZPHASE | GateType::PHASEDX
202 )
203}
204
205fn strings_commute(s0: &[Pauli], s1: &[Pauli]) -> bool {
207 let diff_count = s0
208 .iter()
209 .zip(s1.iter())
210 .filter(|(p0, p1)| **p0 != Pauli::I && **p1 != Pauli::I && **p0 != **p1)
211 .count();
212 diff_count % 2 == 0
213}
214
215fn get_weight_1_string(n_qubits: usize, i: usize, pauli: Pauli) -> Vec<Pauli> {
217 let mut s = vec![Pauli::I; n_qubits];
218 s[i] = pauli;
219 s
220}
221
222fn get_pauli_strings(op: &Op, n_qubits: usize) -> Vec<Vec<Pauli>> {
225 match op {
226 Op::Rotation { data } => vec![data.get_string().clone()],
227 Op::Measure { data } => vec![data.get_string().clone()],
228 Op::Reset { data } => vec![
229 data.get_first_string().clone(),
230 data.get_second_string().clone(),
231 ],
232 Op::Gate { data } => match data.get_gate_type() {
233 GateType::RX => {
234 vec![get_weight_1_string(n_qubits, data.get_args()[0], Pauli::X)]
235 }
236 GateType::RY => {
237 vec![get_weight_1_string(n_qubits, data.get_args()[0], Pauli::Y)]
238 }
239 GateType::RZ => {
240 vec![get_weight_1_string(n_qubits, data.get_args()[0], Pauli::Z)]
241 }
242 GateType::ZZPHASE => {
243 let mut s = vec![Pauli::I; n_qubits];
244 s[data.get_args()[0]] = Pauli::Z;
245 s[data.get_args()[1]] = Pauli::Z;
246 vec![s]
247 }
248 GateType::PHASEDX => {
249 vec![
250 get_weight_1_string(n_qubits, data.get_args()[0], Pauli::Z),
251 get_weight_1_string(n_qubits, data.get_args()[0], Pauli::X),
252 get_weight_1_string(n_qubits, data.get_args()[0], Pauli::Z),
253 ]
254 }
255 GateType::Measure => {
256 vec![get_weight_1_string(n_qubits, data.get_args()[0], Pauli::Z)]
257 }
258 GateType::Reset => {
259 vec![
260 get_weight_1_string(n_qubits, data.get_args()[0], Pauli::Z),
261 get_weight_1_string(n_qubits, data.get_args()[0], Pauli::X),
262 ]
263 }
264 _ => panic!("Unsupported gate type for getting Pauli strings"),
265 },
266 Op::ConditionalBox { data } => {
267 let mut strings = Vec::new();
268 for op in data.get_ops() {
269 strings.extend(get_pauli_strings(op, n_qubits));
270 }
271 strings
272 }
273 _ => panic!("Unsupported gate type for getting Pauli strings"),
274 }
275}
276
277fn commutes_via_conjugation<T: PGTableau>(
280 n_qubits: usize,
281 cliff: &Op,
282 op: &Op,
283 use_dagger: bool,
284) -> bool {
285 let mut tab = T::eye(n_qubits);
286 if use_dagger {
287 tab.postcompose_op(&get_dagger::<T>(cliff));
288 } else {
289 tab.postcompose_op(cliff);
290 }
291 tab.conjugate(op) == T::eye(n_qubits).conjugate(op)
293}
294
295pub trait PGRewrite {
301 fn is_left_boundary(&self, i: usize) -> bool;
303 fn is_right_boundary(&self, i: usize) -> bool;
305 fn is_identity<T: PGTableau>(&self, i: usize) -> bool;
307 fn do_commute<T: PGTableau>(&self, i: usize, j: usize) -> bool;
309 fn commute_ops<T: PGTableau>(&mut self, i: usize, j: usize);
311 fn is_clifford(&self, i: usize) -> bool;
313 fn can_be_conjugated(&self, i: usize) -> bool;
315 fn conj_left_op<T: PGTableau>(&mut self, i: usize);
317 fn conj_right_op<T: PGTableau>(&mut self, i: usize);
319 fn can_merge(&self, i: usize, j: usize) -> bool;
321 fn merge_ops<T: PGTableau>(&mut self, i: usize, j: usize);
323 fn op_to_tableau<T: PGTableau>(&mut self, i: usize);
325}
326
327impl PGRewrite for PauliGraph {
328 fn is_left_boundary(&self, i: usize) -> bool {
329 i == 0
330 }
331
332 fn is_right_boundary(&self, i: usize) -> bool {
333 i == self.get_ops().len() - 1
334 }
335
336 fn is_clifford(&self, i: usize) -> bool {
337 is_clifford(&self.get_ops()[i])
338 }
339
340 fn can_be_conjugated(&self, i: usize) -> bool {
342 can_be_conjugated(&self.get_ops()[i])
343 }
344
345 fn is_identity<T: PGTableau>(&self, i: usize) -> bool {
346 if !self.is_clifford(i) {
347 return false;
348 }
349 let mut tab = T::eye(self.get_n_qubits());
351 tab.postcompose_op(&self.get_ops()[i]);
352 tab == T::eye(self.get_n_qubits())
353 }
354
355 fn op_to_tableau<T: PGTableau>(&mut self, i: usize) {
356 if !self.is_clifford(i) {
357 panic!("Only Clifford unitary can be converted to tableau");
358 }
359 let mut tab = T::eye(self.get_n_qubits());
360 tab.postcompose_op(&self.get_ops()[i]);
361 self.remove_op(i);
362 self.insert_op(i, Op::Tableau { data: tab.into() });
363 }
364
365 fn conj_left_op<T: PGTableau>(&mut self, i: usize) {
366 if !self.is_clifford(i) {
367 panic!("Only Clifford unitary can be used for conjugation");
368 }
369 if self.is_left_boundary(i) {
370 panic!("Cannot conjugate left by a Clifford unitary at the left boundary");
371 }
372 if !self.can_be_conjugated(i - 1) {
373 panic!("The operation to be conjugated cannot be conjugated");
374 }
375 let cliff = &self.get_ops()[i];
376 let left_op = &self.get_ops()[i - 1];
377 let mut tab = T::eye(self.get_n_qubits());
378 tab.postcompose_op(cliff);
379 let mut replacement = vec![cliff.clone()];
380 replacement.extend(tab.conjugate(left_op));
381 self.replace_slice(i - 1..i + 1, replacement);
382 }
383
384 fn conj_right_op<T: PGTableau>(&mut self, i: usize) {
385 if !self.is_clifford(i) {
386 panic!("Only Clifford unitary can be used for conjugation");
387 }
388 if self.is_right_boundary(i) {
389 panic!("Cannot conjugate right by a Clifford unitary at the right boundary");
390 }
391 if !self.can_be_conjugated(i + 1) {
392 panic!("The operation to be conjugated cannot be conjugated");
393 }
394 let cliff = &self.get_ops()[i];
395 let right_op = &self.get_ops()[i + 1];
396 let mut tab = T::eye(self.get_n_qubits());
397 tab.postcompose_op(&get_dagger::<T>(cliff));
398 let mut replacement = tab.conjugate(right_op);
399 replacement.push(cliff.clone());
400 self.replace_slice(i..i + 2, replacement);
401 }
402
403 fn do_commute<T: PGTableau>(&self, i: usize, j: usize) -> bool {
404 let op_i = &self.get_ops()[i];
406 let op_j = &self.get_ops()[j];
407 if matches!(op_i, Op::SetBoundary) || matches!(op_j, Op::SetBoundary) {
409 return true;
410 }
411 if self.can_be_conjugated(i) && self.can_be_conjugated(j) {
412 let strings_i = get_pauli_strings(op_i, self.get_n_qubits());
413 let strings_j = get_pauli_strings(op_j, self.get_n_qubits());
414 return strings_i
415 .iter()
416 .all(|s0| strings_j.iter().all(|s1| strings_commute(s0, s1)));
417 }
418 if self.is_clifford(i) && self.can_be_conjugated(j) {
420 return commutes_via_conjugation::<T>(self.get_n_qubits(), op_i, op_j, true);
421 }
422 if self.is_clifford(j) && self.can_be_conjugated(i) {
423 return commutes_via_conjugation::<T>(self.get_n_qubits(), op_j, op_i, false);
424 }
425
426 if self.is_clifford(i) && self.is_clifford(j) {
428 let mut t0 = T::eye(self.get_n_qubits());
429 t0.postcompose_op(op_i);
430 t0.postcompose_op(op_j);
431 let mut t1 = T::eye(self.get_n_qubits());
432 t1.postcompose_op(op_j);
433 t1.postcompose_op(op_i);
434 return t0 == t1;
435 }
436 false
437 }
438
439 fn commute_ops<T: PGTableau>(&mut self, i: usize, j: usize) {
440 if !self.do_commute::<T>(i, j) {
441 panic!("Cannot commute ops that do not commute");
442 }
443 self.swap_ops(i, j);
444 }
445
446 fn can_merge(&self, i: usize, j: usize) -> bool {
447 let op_i = &self.get_ops()[i];
448 let op_j = &self.get_ops()[j];
449 if self.is_clifford(i) && self.is_clifford(j) {
451 return true;
452 }
453 match (&op_i, &op_j) {
454 (Op::Rotation { data: data_i }, Op::Rotation { data: data_j }) => {
455 data_i.get_string() == data_j.get_string()
456 }
457 (Op::Gate { data: data_i }, Op::Gate { data: data_j }) => {
458 match (data_i.get_gate_type(), data_j.get_gate_type()) {
459 (GateType::RX, GateType::RX)
460 | (GateType::RY, GateType::RY)
461 | (GateType::RZ, GateType::RZ)
462 | (GateType::ZZPHASE, GateType::ZZPHASE) => {
463 data_i.get_args() == data_j.get_args()
464 && data_i.get_conditional_bits() == data_j.get_conditional_bits()
465 && data_i.get_conditional_values() == data_j.get_conditional_values()
466 }
467 _ => false,
468 }
469 }
470 (Op::ConditionalBox { data: data_i }, Op::ConditionalBox { data: data_j }) => {
472 data_i.get_conditional_bits() == data_j.get_conditional_bits()
473 && data_i.get_conditional_values() == data_j.get_conditional_values()
474 }
475 _ => false,
476 }
477 }
478
479 fn merge_ops<T: PGTableau>(&mut self, i: usize, j: usize) {
480 if !self.can_merge(i, j) {
481 panic!("Ops that cannot be merged");
482 }
483 let op_i = &self.get_ops()[i];
484 let op_j = &self.get_ops()[j];
485 if self.is_clifford(i) && self.is_clifford(j) {
486 let mut tab_i = T::eye(self.get_n_qubits());
487 tab_i.postcompose_op(op_i);
488 tab_i.postcompose_op(op_j);
489 self.replace_slice(i..j + 1, vec![Op::Tableau { data: tab_i.into() }]);
490 return;
491 }
492 match (&op_i, &op_j) {
493 (Op::Rotation { data: data_i }, Op::Rotation { data: data_j }) => self.replace_slice(
494 i..j + 1,
495 vec![Op::Rotation {
496 data: RotationData::new(
497 data_i.get_string().clone(),
498 data_i.get_angle() + data_j.get_angle(),
499 ),
500 }],
501 ),
502 (Op::Gate { data: data_i }, Op::Gate { data: data_j }) => {
503 match (data_i.get_gate_type(), data_j.get_gate_type()) {
504 (GateType::RX, GateType::RX)
505 | (GateType::RY, GateType::RY)
506 | (GateType::RZ, GateType::RZ)
507 | (GateType::ZZPHASE, GateType::ZZPHASE) => self.replace_slice(
508 i..j + 1,
509 vec![Op::Gate {
510 data: data_i
511 .clone()
512 .with_params(vec![data_i.get_params()[0] + data_j.get_params()[0]]),
513 }],
514 ),
515 _ => panic!("Unsupported gate type for merging"),
516 }
517 }
518 (Op::ConditionalBox { data: data_i }, Op::ConditionalBox { data: data_j }) => {
520 let mut new_ops = data_i.get_ops().clone();
521 new_ops.extend(data_j.get_ops().clone());
522 self.replace_slice(
523 i..j + 1,
524 vec![Op::ConditionalBox {
525 data: ConditionalBoxData::new(
526 new_ops,
527 data_i.get_conditional_bits().clone(),
528 data_i.get_conditional_values().clone(),
529 ),
530 }],
531 )
532 }
533 _ => panic!("Unsupported op type for merging"),
534 }
535 }
536}
537
538#[cfg(test)]
541mod tests {
542 use super::*;
543 use tk_pg_core::{
544 BlackBoxData, ConditionalBoxData, GateData, GateType, MeasureData, Op, Pauli, PauliGraph,
545 ResetData, RotationData, TableauData,
546 };
547
548 #[test]
549 fn test_can_be_conjugated() {
550 assert!(can_be_conjugated(&Op::Rotation {
552 data: RotationData::new(vec![Pauli::Z], 0.3)
553 }));
554 assert!(can_be_conjugated(&Op::Measure {
556 data: MeasureData::new(vec![Pauli::Z], true, 0)
557 }));
558 assert!(can_be_conjugated(&Op::Reset {
560 data: ResetData::new(vec![Pauli::Z], vec![Pauli::X], true, true)
561 }));
562 assert!(can_be_conjugated(&Op::Gate {
564 data: GateData::new(GateType::RZ, vec![0]).with_params(vec![0.3])
565 }));
566 let inner = Op::Gate {
568 data: GateData::new(GateType::H, vec![0]),
569 };
570 assert!(can_be_conjugated(&Op::ConditionalBox {
571 data: ConditionalBoxData::new(vec![inner], vec![0], vec![true])
572 }));
573 assert!(can_be_conjugated(&Op::Gate {
575 data: GateData::new(GateType::RZ, vec![0])
576 .with_params(vec![0.3])
577 .with_conditional(vec![0], vec![true])
578 }));
579 }
580
581 #[test]
582 fn test_cannot_be_conjugated() {
583 assert!(!can_be_conjugated(&Op::Gate {
585 data: GateData::new(GateType::H, vec![0])
586 }));
587 assert!(!can_be_conjugated(&Op::Tableau {
589 data: TableauData::new(vec![(vec![Pauli::Z], true)], vec![(vec![Pauli::X], false)])
590 }));
591 assert!(!can_be_conjugated(&Op::SetBoundary));
593 assert!(!can_be_conjugated(&Op::BlackBox {
595 data: BlackBoxData::new(vec![0], "test".to_string())
596 }));
597 }
598
599 #[test]
600 fn test_is_clifford() {
601 assert!(is_clifford(&Op::Gate {
603 data: GateData::new(GateType::H, vec![0])
604 }));
605 assert!(is_clifford(&Op::Gate {
607 data: GateData::new(GateType::RZ, vec![0]).with_params(vec![0.5])
608 }));
609 assert!(is_clifford(&Op::Gate {
611 data: GateData::new(GateType::PHASEDX, vec![0]).with_params(vec![0.5, 0.5])
612 }));
613 assert!(is_clifford(&Op::Gate {
615 data: GateData::new(GateType::PHASEDX, vec![0]).with_params(vec![2.0, 1.6])
616 }));
617 assert!(is_clifford(&Op::Gate {
619 data: GateData::new(GateType::PHASEDX, vec![0]).with_params(vec![3.0, 0.25])
620 }));
621 assert!(is_clifford(&Op::Rotation {
623 data: RotationData::new(vec![Pauli::Z], 0.5)
624 }));
625 assert!(is_clifford(&Op::Tableau {
627 data: TableauData::new(vec![(vec![Pauli::Z], true)], vec![(vec![Pauli::X], false)])
628 }));
629 }
630
631 #[test]
632 fn test_is_not_clifford() {
633 assert!(!is_clifford(&Op::Gate {
635 data: GateData::new(GateType::RZ, vec![0]).with_params(vec![0.3])
636 }));
637 assert!(!is_clifford(&Op::Rotation {
639 data: RotationData::new(vec![Pauli::Z], 0.3)
640 }));
641 assert!(!is_clifford(&Op::SetBoundary));
643 assert!(!is_clifford(&Op::BlackBox {
645 data: BlackBoxData::new(vec![0], "test".to_string())
646 }));
647 }
648
649 #[test]
650 fn test_boundary_ops() {
651 let pg = PauliGraph::new(1).with_ops(vec![
652 Op::Gate {
653 data: GateData::new(GateType::H, vec![0]),
654 },
655 Op::Gate {
656 data: GateData::new(GateType::S, vec![0]),
657 },
658 Op::Gate {
659 data: GateData::new(GateType::H, vec![0]),
660 },
661 ]);
662 assert!(pg.is_left_boundary(0));
663 assert!(!pg.is_left_boundary(1));
664 assert!(!pg.is_right_boundary(0));
665 assert!(!pg.is_right_boundary(1));
666 assert!(pg.is_right_boundary(2));
667 }
668
669 #[test]
670 fn can_merge_same_rotation_string() {
671 let pg = PauliGraph::new(2).with_ops(vec![
672 Op::Rotation {
673 data: RotationData::new(vec![Pauli::Z, Pauli::I], 0.3),
674 },
675 Op::Rotation {
676 data: RotationData::new(vec![Pauli::Z, Pauli::I], 0.5),
677 },
678 ]);
679 assert!(pg.can_merge(0, 1));
680 }
681
682 #[test]
683 fn can_merge_diff_rotation_string() {
684 let pg = PauliGraph::new(2).with_ops(vec![
685 Op::Rotation {
686 data: RotationData::new(vec![Pauli::Z, Pauli::I], 0.3),
687 },
688 Op::Rotation {
689 data: RotationData::new(vec![Pauli::X, Pauli::I], 0.5),
690 },
691 ]);
692 assert!(!pg.can_merge(0, 1));
693 }
694
695 #[test]
696 fn can_merge_rz_same_qubit() {
697 let pg = PauliGraph::new(2).with_ops(vec![
698 Op::Gate {
699 data: GateData::new(GateType::RZ, vec![0]).with_params(vec![0.3]),
700 },
701 Op::Gate {
702 data: GateData::new(GateType::RZ, vec![0]).with_params(vec![0.5]),
703 },
704 ]);
705 assert!(pg.can_merge(0, 1));
706 }
707
708 #[test]
709 fn can_merge_rz_diff_qubit() {
710 let pg = PauliGraph::new(2).with_ops(vec![
711 Op::Gate {
712 data: GateData::new(GateType::RZ, vec![0]).with_params(vec![0.3]),
713 },
714 Op::Gate {
715 data: GateData::new(GateType::RZ, vec![1]).with_params(vec![0.5]),
716 },
717 ]);
718 assert!(!pg.can_merge(0, 1));
719 }
720
721 #[test]
722 fn can_merge_two_cliffords() {
723 let pg = PauliGraph::new(1).with_ops(vec![
724 Op::Gate {
725 data: GateData::new(GateType::H, vec![0]),
726 },
727 Op::Gate {
728 data: GateData::new(GateType::S, vec![0]),
729 },
730 ]);
731 assert!(pg.can_merge(0, 1));
732 }
733
734 #[test]
735 fn can_merge_clifford_and_rotation_returns_false() {
736 let pg = PauliGraph::new(1).with_ops(vec![
737 Op::Gate {
738 data: GateData::new(GateType::H, vec![0]),
739 },
740 Op::Rotation {
741 data: RotationData::new(vec![Pauli::Z], 0.3),
742 },
743 ]);
744 assert!(!pg.can_merge(0, 1));
745 }
746}