GCC Code Coverage Report

Directory: ./
File: Transformations/CliffordReductionPass.cpp
Date: 2022-10-15 05:10:18
Warnings: 12 unchecked decisions!
Exec Total Coverage
Lines: 480 495 97.0%
Functions: 16 16 100.0%
Branches: 552 928 59.5%
Decisions: 154 186 82.8%
Line Branch Decision Exec Source
1 // Copyright 2019-2022 Cambridge Quantum Computing
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "CliffordReductionPass.hpp"
16
17 #include "Circuit/DAGDefs.hpp"
18 #include "PauliGraph/ConjugatePauliFunctions.hpp"
19
20 namespace tket {
21
22 /**
23 * Finds Clifford circuit C such that
24 * R[p](a); R[q](b) = C; RZ(a); RZ(b); C^\dagger if p==q or
25 * C; RZ(a); RY(b); C^\dagger if p!=q
26 */
27 static const std::map<std::pair<Pauli, Pauli>, std::list<OpType>>
28 mapping_to_zz_or_zy_lut{
29 {{Pauli::X, Pauli::X}, {OpType::H}},
30 {{Pauli::X, Pauli::Y}, {OpType::H, OpType::Z}},
31 {{Pauli::X, Pauli::Z}, {OpType::H, OpType::S}},
32 {{Pauli::Y, Pauli::X}, {OpType::V, OpType::S}},
33 {{Pauli::Y, Pauli::Y}, {OpType::V}},
34 {{Pauli::Y, Pauli::Z}, {OpType::V, OpType::Z}},
35 {{Pauli::Z, Pauli::X}, {OpType::S}},
36 {{Pauli::Z, Pauli::Y}, {}},
37 {{Pauli::Z, Pauli::Z}, {}},
38 };
39
40 static const std::map<Pauli, OpType> pauli_to_pauli_gate_lut{
41 {Pauli::X, OpType::X},
42 {Pauli::Y, OpType::Y},
43 {Pauli::Z, OpType::Z},
44 };
45
46 /**
47 * Consider an interaction of R[p0, p1](+-0.5); R[q0, q1](+-0.5)
48 * where p0, p1, q0, q1 in {X, Y, Z}.
49 * Returns the equivalent replacement circuit with fewer 2qb interactions.
50 */
51 333 static Circuit interaction_replacement(const InteractionMatch &match) {
52 333 const Pauli &p0 = match.point0.p;
53 333 const Pauli &p1 = match.point1.p;
54 333 const Pauli &q0 = match.rev0.p;
55 333 const Pauli &q1 = match.rev1.p;
56
1/2
✓ Branch 2 taken 333 times.
✗ Branch 3 not taken.
 333 Circuit replacement(2);
57
2/2
✓ Branch 0 taken 100 times.
✓ Branch 1 taken 233 times.
2/2
✓ Decision 'true' taken 100 times.
✓ Decision 'false' taken 233 times.
 333 if (match.point0.phase ^ match.point1.phase) {
58
3/6
✓ Branch 3 taken 100 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 100 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 100 times.
✗ Branch 10 not taken.
 100 replacement.add_op<unsigned>(pauli_to_pauli_gate_lut.at(p0), {0});
59
3/6
✓ Branch 3 taken 100 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 100 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 100 times.
✗ Branch 10 not taken.
 100 replacement.add_op<unsigned>(pauli_to_pauli_gate_lut.at(p1), {1});
60
2/4
✓ Branch 1 taken 100 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 100 times.
✗ Branch 5 not taken.
 100 replacement.add_phase(0.5);
61 }
62
2/2
✓ Branch 0 taken 257 times.
✓ Branch 1 taken 76 times.
2/2
✓ Decision 'true' taken 257 times.
✓ Decision 'false' taken 76 times.
 333 if (p0 == q0) {
63
2/2
✓ Branch 0 taken 136 times.
✓ Branch 1 taken 121 times.
2/2
✓ Decision 'true' taken 136 times.
✓ Decision 'false' taken 121 times.
 257 if (p1 == q1) {
64 // R[p0, p1](1) = R[p0, I](1); R[I, p1](1)
65
1/2
✓ Branch 1 taken 136 times.
✗ Branch 2 not taken.
 136 OpType op0 = pauli_to_pauli_gate_lut.at(p0);
66
1/2
✓ Branch 1 taken 136 times.
✗ Branch 2 not taken.
 136 OpType op1 = pauli_to_pauli_gate_lut.at(p1);
67
2/4
✓ Branch 3 taken 136 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 136 times.
✗ Branch 7 not taken.
 136 replacement.add_op<unsigned>(op0, {0});
68
2/4
✓ Branch 3 taken 136 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 136 times.
✗ Branch 7 not taken.
 136 replacement.add_op<unsigned>(op1, {1});
69
2/4
✓ Branch 1 taken 136 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 136 times.
✗ Branch 5 not taken.
 136 replacement.add_phase(-0.5);
70 } else {
71 // Map to R[Z, Z](0.5); R[Z, Y](0.5)
72
1/2
✓ Branch 2 taken 121 times.
✗ Branch 3 not taken.
 121 Circuit basis_change(2);
73
2/4
✓ Branch 2 taken 121 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 121 times.
✗ Branch 6 not taken.
 121 std::list<OpType> ops0 = mapping_to_zz_or_zy_lut.at({p0, q0});
74
2/4
✓ Branch 2 taken 121 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 121 times.
✗ Branch 6 not taken.
 121 std::list<OpType> ops1 = mapping_to_zz_or_zy_lut.at({p1, q1});
75
1/2
✗ Branch 4 not taken.
✓ Branch 5 taken 121 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 121 times.
 121 for (OpType op : ops0) {
76 ✗ basis_change.add_op<unsigned>(op, {0});
77 }
78
2/2
✓ Branch 4 taken 210 times.
✓ Branch 5 taken 121 times.
2/2
✓ Decision 'true' taken 210 times.
✓ Decision 'false' taken 121 times.
 331 for (OpType op : ops1) {
79
2/4
✓ Branch 3 taken 210 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 210 times.
✗ Branch 7 not taken.
 210 basis_change.add_op<unsigned>(op, {1});
80 }
81
1/2
✓ Branch 1 taken 121 times.
✗ Branch 2 not taken.
 121 replacement.append(basis_change);
82
2/4
✓ Branch 3 taken 121 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 121 times.
✗ Branch 7 not taken.
 121 replacement.add_op<unsigned>(OpType::V, {1});
83
2/4
✓ Branch 3 taken 121 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 121 times.
✗ Branch 7 not taken.
 121 replacement.add_op<unsigned>(OpType::ZZMax, {0, 1});
84
2/4
✓ Branch 1 taken 121 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 121 times.
✗ Branch 5 not taken.
 121 replacement.append(basis_change.dagger());
85 121 }
86 } else {
87
2/2
✓ Branch 0 taken 41 times.
✓ Branch 1 taken 35 times.
2/2
✓ Decision 'true' taken 41 times.
✓ Decision 'false' taken 35 times.
 76 if (p1 == q1) {
88 // Map to R[Z, Z](0.5); R[Y, Z](0.5)
89
1/2
✓ Branch 2 taken 41 times.
✗ Branch 3 not taken.
 41 Circuit basis_change(2);
90
2/4
✓ Branch 2 taken 41 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 41 times.
✗ Branch 6 not taken.
 41 std::list<OpType> ops0 = mapping_to_zz_or_zy_lut.at({p0, q0});
91
2/4
✓ Branch 2 taken 41 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 41 times.
✗ Branch 6 not taken.
 41 std::list<OpType> ops1 = mapping_to_zz_or_zy_lut.at({p1, q1});
92
2/2
✓ Branch 4 taken 76 times.
✓ Branch 5 taken 41 times.
2/2
✓ Decision 'true' taken 76 times.
✓ Decision 'false' taken 41 times.
 117 for (OpType op : ops0) {
93
2/4
✓ Branch 3 taken 76 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 76 times.
✗ Branch 7 not taken.
 76 basis_change.add_op<unsigned>(op, {0});
94 }
95
2/2
✓ Branch 4 taken 38 times.
✓ Branch 5 taken 41 times.
2/2
✓ Decision 'true' taken 38 times.
✓ Decision 'false' taken 41 times.
 79 for (OpType op : ops1) {
96
2/4
✓ Branch 3 taken 38 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 38 times.
✗ Branch 7 not taken.
 38 basis_change.add_op<unsigned>(op, {1});
97 }
98
1/2
✓ Branch 1 taken 41 times.
✗ Branch 2 not taken.
 41 replacement.append(basis_change);
99
2/4
✓ Branch 3 taken 41 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 41 times.
✗ Branch 7 not taken.
 41 replacement.add_op<unsigned>(OpType::V, {0});
100
2/4
✓ Branch 3 taken 41 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 41 times.
✗ Branch 7 not taken.
 41 replacement.add_op<unsigned>(OpType::ZZMax, {0, 1});
101
2/4
✓ Branch 1 taken 41 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 41 times.
✗ Branch 5 not taken.
 41 replacement.append(basis_change.dagger());
102 41 } else {
103 // Map to R[Z, Z](0.5); R[Y, Y](0.5)
104
1/2
✓ Branch 2 taken 35 times.
✗ Branch 3 not taken.
 35 Circuit basis_change(2);
105
2/4
✓ Branch 2 taken 35 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 35 times.
✗ Branch 6 not taken.
 35 std::list<OpType> ops0 = mapping_to_zz_or_zy_lut.at({p0, q0});
106
2/4
✓ Branch 2 taken 35 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 35 times.
✗ Branch 6 not taken.
 35 std::list<OpType> ops1 = mapping_to_zz_or_zy_lut.at({p1, q1});
107
2/2
✓ Branch 4 taken 70 times.
✓ Branch 5 taken 35 times.
2/2
✓ Decision 'true' taken 70 times.
✓ Decision 'false' taken 35 times.
 105 for (OpType op : ops0) {
108
2/4
✓ Branch 3 taken 70 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 70 times.
✗ Branch 7 not taken.
 70 basis_change.add_op<unsigned>(op, {0});
109 }
110
2/2
✓ Branch 4 taken 44 times.
✓ Branch 5 taken 35 times.
2/2
✓ Decision 'true' taken 44 times.
✓ Decision 'false' taken 35 times.
 79 for (OpType op : ops1) {
111
2/4
✓ Branch 3 taken 44 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 44 times.
✗ Branch 7 not taken.
 44 basis_change.add_op<unsigned>(op, {1});
112 }
113
1/2
✓ Branch 1 taken 35 times.
✗ Branch 2 not taken.
 35 replacement.append(basis_change);
114
2/4
✓ Branch 3 taken 35 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 35 times.
✗ Branch 7 not taken.
 35 replacement.add_op<unsigned>(OpType::H, {0});
115
2/4
✓ Branch 3 taken 35 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 35 times.
✗ Branch 7 not taken.
 35 replacement.add_op<unsigned>(OpType::H, {1});
116
2/4
✓ Branch 3 taken 35 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 35 times.
✗ Branch 7 not taken.
 35 replacement.add_op<unsigned>(OpType::Z, {0});
117
2/4
✓ Branch 3 taken 35 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 35 times.
✗ Branch 7 not taken.
 35 replacement.add_op<unsigned>(OpType::Z, {1});
118
2/4
✓ Branch 3 taken 35 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 35 times.
✗ Branch 7 not taken.
 35 replacement.add_op<unsigned>(OpType::ZZMax, {0, 1});
119
2/4
✓ Branch 3 taken 35 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 35 times.
✗ Branch 7 not taken.
 35 replacement.add_op<unsigned>(OpType::H, {0});
120
2/4
✓ Branch 3 taken 35 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 35 times.
✗ Branch 7 not taken.
 35 replacement.add_op<unsigned>(OpType::H, {1});
121
2/4
✓ Branch 3 taken 35 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 35 times.
✗ Branch 7 not taken.
 35 replacement.add_op<unsigned>(OpType::SWAP, {0, 1});
122
2/4
✓ Branch 1 taken 35 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 35 times.
✗ Branch 5 not taken.
 35 replacement.add_phase(0.25);
123
2/4
✓ Branch 1 taken 35 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 35 times.
✗ Branch 5 not taken.
 35 replacement.append(basis_change.dagger());
124 35 }
125 }
126
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 305 times.
2/2
✓ Decision 'true' taken 28 times.
✓ Decision 'false' taken 305 times.
 333 if (match.rev0.phase ^ match.rev1.phase) {
127
3/6
✓ Branch 3 taken 28 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 28 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 28 times.
✗ Branch 10 not taken.
 28 replacement.add_op<unsigned>(pauli_to_pauli_gate_lut.at(q0), {0});
128
3/6
✓ Branch 3 taken 28 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 28 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 28 times.
✗ Branch 10 not taken.
 28 replacement.add_op<unsigned>(pauli_to_pauli_gate_lut.at(q1), {1});
129
2/4
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 28 times.
✗ Branch 5 not taken.
 28 replacement.add_phase(0.5);
130 }
131 333 return replacement;
132 }
133
134 /**
135 * Given a 2qb Clifford gate, returns just the local operations applied around
136 * the maximally-entangling gadget.
137 */
138 666 static Circuit local_cliffords(OpType op) {
139
1/2
✓ Branch 2 taken 666 times.
✗ Branch 3 not taken.
 666 Circuit locals(2);
140
4/5
✓ Branch 0 taken 621 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 42 times.
✗ Branch 4 not taken.
 666 switch (op) {
141
1/1
✓ Decision 'true' taken 621 times.
 621 case OpType::CX: {
142
2/4
✓ Branch 3 taken 621 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 621 times.
✗ Branch 7 not taken.
 621 locals.add_op<unsigned>(OpType::Sdg, {0});
143
2/4
✓ Branch 3 taken 621 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 621 times.
✗ Branch 7 not taken.
 621 locals.add_op<unsigned>(OpType::Vdg, {1});
144 621 break;
145 }
146
1/1
✓ Decision 'true' taken 1 times.
 1 case OpType::CZ: {
147
2/4
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
 1 locals.add_op<unsigned>(OpType::Sdg, {0});
148
2/4
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
 1 locals.add_op<unsigned>(OpType::Sdg, {1});
149
2/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
 1 locals.add_phase(0.25);
150 1 break;
151 }
152
1/1
✓ Decision 'true' taken 2 times.
 2 case OpType::CY: {
153
2/4
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
 2 locals.add_op<unsigned>(OpType::Sdg, {0});
154
2/4
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
 2 locals.add_op<unsigned>(OpType::V, {1});
155
2/4
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
 2 locals.add_op<unsigned>(OpType::Sdg, {1});
156
2/4
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
 2 locals.add_op<unsigned>(OpType::Vdg, {1});
157
2/4
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
 2 locals.add_phase(0.25);
158 2 break;
159 }
160
1/1
✓ Decision 'true' taken 42 times.
 42 case OpType::ZZMax: {
161 42 break;
162 }
163
0/1
✗ Decision 'true' not taken.
 ✗ default: {
164 ✗ throw CircuitInvalidity(
165 "Attempting to replace non-Clifford gate with Clifford "
166 ✗ "optimisation");
167 break;
168 }
169 }
170 666 return locals;
171 }
172
173 5411 void CliffordReductionPass::insert_interaction_point(InteractionPoint ip) {
174
1/2
✓ Branch 1 taken 5411 times.
✗ Branch 2 not taken.
 5411 itable.insert(ip);
175
1/2
✓ Branch 1 taken 5411 times.
✗ Branch 2 not taken.
 5411 Vertex next = circ.target(ip.e);
176
1/2
✓ Branch 1 taken 5411 times.
✗ Branch 2 not taken.
 5411 port_t next_p = circ.get_target_port(ip.e);
177 5411 bool commute = true;
178
2/2
✓ Branch 0 taken 11945 times.
✓ Branch 1 taken 5411 times.
2/2
✓ Decision 'true' taken 11945 times.
✓ Decision 'false' taken 5411 times.
 17356 while (commute) {
179
3/4
✓ Branch 2 taken 11945 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 4697 times.
✓ Branch 6 taken 7248 times.
2/2
✓ Decision 'true' taken 4697 times.
✓ Decision 'false' taken 7248 times.
 11945 if (v_to_depth.find(next) == v_to_depth.end()) {
180 4697 commute = false;
181 5411 continue;
182 }
183
1/2
✓ Branch 1 taken 7248 times.
✗ Branch 2 not taken.
 7248 Op_ptr op = circ.get_Op_ptr_from_Vertex(next);
184
3/6
✓ Branch 2 taken 7248 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 7248 times.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 7248 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 7248 times.
 7248 if (!op->get_desc().is_gate()) {
185 ✗ commute = false;
186 ✗ continue;
187 }
188 7248 OpType type = op->get_type();
189
3/3
✓ Branch 0 taken 5332 times.
✓ Branch 1 taken 83 times.
✓ Branch 2 taken 1833 times.
 7248 switch (type) {
190 5332 case OpType::H:
191 case OpType::S:
192 case OpType::Sdg:
193 case OpType::V:
194 case OpType::Vdg:
195 case OpType::X:
196 case OpType::Y:
197 case OpType::Z: {
198
1/2
✓ Branch 1 taken 5332 times.
✗ Branch 2 not taken.
 5332 std::pair<Pauli, bool> new_basis = conjugate_Pauli(type, ip.p, true);
199 5332 ip.p = new_basis.first;
200 5332 ip.phase ^= new_basis.second;
201 5332 break;
202 }
203
1/1
✓ Decision 'true' taken 83 times.
 83 case OpType::SWAP: {
204 83 next_p = 1 - next_p;
205 83 break;
206 }
207
1/1
✓ Decision 'true' taken 1833 times.
 1833 default: {
208
3/4
✓ Branch 2 taken 1833 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 714 times.
✓ Branch 5 taken 1119 times.
2/2
✓ Decision 'true' taken 714 times.
✓ Decision 'false' taken 1119 times.
 1833 if (!circ.commutes_with_basis(next, ip.p, PortType::Target, next_p)) {
209 714 commute = false;
210 714 continue;
211 }
212 1119 break;
213 }
214 }
215
1/2
✓ Branch 1 taken 6534 times.
✗ Branch 2 not taken.
 6534 ip.e = circ.get_nth_out_edge(next, next_p);
216
1/2
✓ Branch 1 taken 6534 times.
✗ Branch 2 not taken.
 6534 auto inserted = itable.insert(ip);
217 6534 commute = inserted.second;
218
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6534 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 6534 times.
 6534 if (!commute) {
219 // Now `inserted.first` points to the element of the table that
220 // blocked insertion, i.e. had the same source/edge combination.
221 // Check that its `p` and `phase` are correct: if not, something has
222 // gone wrong.
223 ✗ auto blocker = inserted.first;
224 TKET_ASSERT(blocker->p == ip.p && blocker->phase == ip.phase);
225 }
226
1/2
✓ Branch 1 taken 6534 times.
✗ Branch 2 not taken.
 6534 next = circ.target(ip.e);
227
1/2
✓ Branch 1 taken 6534 times.
✗ Branch 2 not taken.
 6534 next_p = circ.get_target_port(ip.e);
228
2/2
✓ Branch 1 taken 6534 times.
✓ Branch 2 taken 714 times.
 7248 }
229 5411 }
230
231 2173 std::optional<InteractionMatch> CliffordReductionPass::search_back_for_match(
232 const RevInteractionPoint &rip0, const RevInteractionPoint &rip1) const {
233
3/4
✓ Branch 1 taken 4346 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 4346 times.
✓ Branch 4 taken 2173 times.
 6519 RevInteractionPoint point[2];
234 2173 point[0] = rip0;
235 2173 point[1] = rip1;
236 2173 std::map<Edge, RevInteractionPoint> point_lookup;
237
1/2
✓ Branch 1 taken 2173 times.
✗ Branch 2 not taken.
 2173 IndexMap im = circ.index_map();
238
239 // interactions met when commuting back; point lists are in causal order of
240 // circuit:
241
2/2
✓ Branch 1 taken 4346 times.
✓ Branch 2 taken 2173 times.
 13038 std::map<IVertex, std::list<InteractionPoint>> candidates[2];
242
243
2/2
✓ Branch 0 taken 4346 times.
✓ Branch 1 taken 2173 times.
2/2
✓ Decision 'true' taken 4346 times.
✓ Decision 'false' taken 2173 times.
 6519 for (unsigned i = 0; i < 2; ++i) {
244 // Commute edge i back as far as possible
245 4346 bool commute = true;
246
2/2
✓ Branch 0 taken 23111 times.
✓ Branch 1 taken 4346 times.
2/2
✓ Decision 'true' taken 23111 times.
✓ Decision 'false' taken 4346 times.
 27457 while (commute) {
247
1/2
✓ Branch 2 taken 23111 times.
✗ Branch 3 not taken.
 23111 point_lookup.insert({point[i].e, point[i]});
248
1/2
✓ Branch 2 taken 23111 times.
✗ Branch 3 not taken.
 23111 auto r = itable.get<TagEdge>().equal_range(point[i].e);
249
3/4
✓ Branch 1 taken 40853 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 17742 times.
✓ Branch 4 taken 23111 times.
0/1
? Decision couldn't be analyzed.
 40853 for (auto it = r.first; it != r.second; ++it) {
250
1/2
✓ Branch 1 taken 17742 times.
✗ Branch 2 not taken.
 17742 Vertex v = it->source;
251
5/10
✓ Branch 1 taken 17742 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 17742 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 17742 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 17742 times.
✗ Branch 12 not taken.
✓ Branch 14 taken 17742 times.
✗ Branch 15 not taken.
 17742 candidates[i][{im.at(v), v}].push_front(*it);
252 }
253
1/2
✓ Branch 1 taken 23111 times.
✗ Branch 2 not taken.
 23111 Vertex pred = circ.source(point[i].e);
254
1/2
✓ Branch 1 taken 23111 times.
✗ Branch 2 not taken.
 23111 port_t pred_port = circ.get_source_port(point[i].e);
255
1/2
✓ Branch 1 taken 23111 times.
✗ Branch 2 not taken.
 23111 Op_ptr pred_op = circ.get_Op_ptr_from_Vertex(pred);
256
4/6
✓ Branch 2 taken 23111 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 23111 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 847 times.
✓ Branch 9 taken 22264 times.
2/2
✓ Decision 'true' taken 847 times.
✓ Decision 'false' taken 22264 times.
 23111 if (!pred_op->get_desc().is_gate()) {
257 847 commute = false;
258 847 continue;
259 }
260 22264 OpType type = pred_op->get_type();
261
3/3
✓ Branch 0 taken 16764 times.
✓ Branch 1 taken 93 times.
✓ Branch 2 taken 5407 times.
 22264 switch (type) {
262 16764 case OpType::H:
263 case OpType::S:
264 case OpType::Sdg:
265 case OpType::V:
266 case OpType::Vdg:
267 case OpType::X:
268 case OpType::Y:
269 case OpType::Z: {
270
1/2
✓ Branch 1 taken 16764 times.
✗ Branch 2 not taken.
 16764 std::pair<Pauli, bool> new_basis = conjugate_Pauli(type, point[i].p);
271 16764 point[i].p = new_basis.first;
272 16764 point[i].phase ^= new_basis.second;
273 16764 break;
274 }
275
1/1
✓ Decision 'true' taken 93 times.
 93 case OpType::SWAP: {
276 93 pred_port = 1 - pred_port;
277 93 break;
278 }
279
1/1
✓ Decision 'true' taken 5407 times.
 5407 default: {
280
1/2
✓ Branch 1 taken 5407 times.
✗ Branch 2 not taken.
 5407 commute = circ.commutes_with_basis(
281 5407 pred, point[i].p, PortType::Source, pred_port);
282 5407 break;
283 }
284 }
285
1/2
✓ Branch 1 taken 22264 times.
✗ Branch 2 not taken.
 22264 point[i].e = circ.get_nth_in_edge(pred, pred_port);
286
2/2
✓ Branch 1 taken 22264 times.
✓ Branch 2 taken 847 times.
 23111 }
287 }
288 // Check for matching interactions
289 2173 for (const std::pair<const IVertex, std::list<InteractionPoint>> &pair :
290
2/2
✓ Branch 5 taken 1841 times.
✓ Branch 6 taken 1840 times.
 5854 candidates[0]) {
291
1/2
✓ Branch 1 taken 1841 times.
✗ Branch 2 not taken.
 1841 auto found = candidates[1].find(pair.first);
292
2/2
✓ Branch 2 taken 401 times.
✓ Branch 3 taken 1440 times.
2/2
✓ Decision 'true' taken 401 times.
✓ Decision 'false' taken 1440 times.
 1841 if (found != candidates[1].end()) {
293 std::optional<std::pair<InteractionPoint, InteractionPoint>>
294
1/2
✓ Branch 2 taken 401 times.
✗ Branch 3 not taken.
 401 insert_point = valid_insertion_point(pair.second, found->second);
295
2/2
✓ Branch 1 taken 394 times.
✓ Branch 2 taken 7 times.
2/2
✓ Decision 'true' taken 394 times.
✓ Decision 'false' taken 7 times.
 401 if (insert_point) {
296 InteractionMatch match = {
297 394 insert_point->first, insert_point->second,
298
1/2
✓ Branch 1 taken 394 times.
✗ Branch 2 not taken.
 394 point_lookup.at(insert_point->first.e),
299
1/2
✓ Branch 4 taken 394 times.
✗ Branch 5 not taken.
 788 point_lookup.at(insert_point->second.e)};
300
2/2
✓ Branch 0 taken 282 times.
✓ Branch 1 taken 112 times.
2/2
✓ Decision 'true' taken 282 times.
✓ Decision 'false' taken 112 times.
 394 if (!allow_swaps) {
301
4/4
✓ Branch 0 taken 87 times.
✓ Branch 1 taken 195 times.
✓ Branch 2 taken 61 times.
✓ Branch 3 taken 26 times.
2/2
✓ Decision 'true' taken 61 times.
✓ Decision 'false' taken 221 times.
 282 if (match.point0.p != match.rev0.p && match.point1.p != match.rev1.p)
302 61 continue;
303 }
304 333 return match;
305 }
306 }
307 }
308 1840 return std::nullopt;
309
2/4
✓ Branch 0 taken 4346 times.
✓ Branch 1 taken 2173 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
 8692 }
310
311 1976 void CliffordReductionPass::process_new_interaction(const Vertex &inter) {
312 // Process the vertex as well as any new 2qb Cliffords that get inserted
313 // while doing so (and so on until there are none left to process).
314
1/2
✓ Branch 2 taken 1976 times.
✗ Branch 3 not taken.
 1976 std::list<Vertex> to_process = {inter};
315
2/2
✓ Branch 1 taken 2173 times.
✓ Branch 2 taken 1976 times.
2/2
✓ Decision 'true' taken 2173 times.
✓ Decision 'false' taken 1976 times.
 4149 while (!to_process.empty()) {
316 2173 Vertex v = to_process.front();
317 2173 to_process.pop_front();
318
1/2
✓ Branch 1 taken 2173 times.
✗ Branch 2 not taken.
 2173 Op_ptr op = circ.get_Op_ptr_from_Vertex(v);
319
1/2
✓ Branch 2 taken 2173 times.
✗ Branch 3 not taken.
 2173 Pauli basis0 = *op->commuting_basis(0);
320
1/2
✓ Branch 2 taken 2173 times.
✗ Branch 3 not taken.
 2173 Pauli basis1 = *op->commuting_basis(1);
321
1/2
✓ Branch 1 taken 2173 times.
✗ Branch 2 not taken.
 2173 EdgeVec ins = circ.get_in_edges(v);
322
1/2
✓ Branch 1 taken 2173 times.
✗ Branch 2 not taken.
 2173 RevInteractionPoint rip0 = {ins.at(0), basis0, false};
323
1/2
✓ Branch 1 taken 2173 times.
✗ Branch 2 not taken.
 2173 RevInteractionPoint rip1 = {ins.at(1), basis1, false};
324
1/2
✓ Branch 1 taken 2173 times.
✗ Branch 2 not taken.
 2173 std::optional<InteractionMatch> match = search_back_for_match(rip0, rip1);
325
2/2
✓ Branch 1 taken 333 times.
✓ Branch 2 taken 1840 times.
2/2
✓ Decision 'true' taken 333 times.
✓ Decision 'false' taken 1840 times.
 2173 if (match) {
326
1/2
✓ Branch 2 taken 333 times.
✗ Branch 3 not taken.
 333 Circuit replacement = interaction_replacement(*match);
327 333 Subcircuit site;
328
2/4
✓ Branch 3 taken 333 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 333 times.
✗ Branch 7 not taken.
 333 site.q_in_hole = site.q_out_hole = {match->point0.e, match->point1.e};
329
1/2
✓ Branch 1 taken 333 times.
✗ Branch 2 not taken.
 333 Subcircuit inserted = substitute(replacement, site);
330 333 const Vertex &source = match->point0.source;
331 Circuit source_locals =
332
2/4
✓ Branch 1 taken 333 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 333 times.
✗ Branch 5 not taken.
 333 local_cliffords(circ.get_OpType_from_Vertex(source));
333 333 Subcircuit source_site;
334
1/2
✓ Branch 1 taken 333 times.
✗ Branch 2 not taken.
 333 source_site.q_in_hole = circ.get_in_edges(source);
335 ✗ source_site.q_out_hole = {
336
3/6
✓ Branch 1 taken 333 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 333 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 333 times.
✗ Branch 8 not taken.
 333 circ.get_nth_out_edge(source, 0), circ.get_nth_out_edge(source, 1)};
337
1/2
✓ Branch 1 taken 333 times.
✗ Branch 2 not taken.
 333 source_site.verts.insert(source);
338
1/2
✓ Branch 1 taken 333 times.
✗ Branch 2 not taken.
 333 substitute(source_locals, source_site);
339
1/2
✓ Branch 3 taken 333 times.
✗ Branch 4 not taken.
 333 Circuit v_locals = local_cliffords(op->get_type());
340 333 Subcircuit v_site;
341
1/2
✓ Branch 1 taken 333 times.
✗ Branch 2 not taken.
 333 v_site.q_in_hole = circ.get_in_edges(v);
342 ✗ v_site.q_out_hole = {
343
3/6
✓ Branch 1 taken 333 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 333 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 333 times.
✗ Branch 8 not taken.
 333 circ.get_nth_out_edge(v, 0), circ.get_nth_out_edge(v, 1)};
344
1/2
✓ Branch 1 taken 333 times.
✗ Branch 2 not taken.
 333 v_site.verts.insert(v);
345
1/2
✓ Branch 1 taken 333 times.
✗ Branch 2 not taken.
 333 substitute(v_locals, v_site);
346
2/2
✓ Branch 5 taken 1514 times.
✓ Branch 6 taken 136 times.
2/2
✓ Decision 'true' taken 1514 times.
✓ Decision 'false' taken 136 times.
 1650 for (const Vertex &new_v : inserted.verts) {
347
5/6
✓ Branch 1 taken 1514 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 211 times.
✓ Branch 4 taken 1303 times.
✓ Branch 5 taken 197 times.
✓ Branch 6 taken 1317 times.
2/2
✓ Decision 'true' taken 197 times.
✓ Decision 'false' taken 1528 times.
 1725 if (circ.n_in_edges(new_v) == 2 &&
348
3/4
✓ Branch 1 taken 211 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 197 times.
✓ Branch 4 taken 14 times.
 211 circ.get_OpType_from_Vertex(new_v) != OpType::SWAP) {
349
1/2
✓ Branch 1 taken 197 times.
✗ Branch 2 not taken.
 197 to_process.push_back(new_v);
350 197 break;
351 }
352 }
353 333 success = true;
354 333 } else {
355
1/2
✓ Branch 1 taken 1840 times.
✗ Branch 2 not taken.
 1840 std::vector<std::optional<Edge>> outs = circ.get_linear_out_edges(v);
356
1/2
✓ Branch 1 taken 1840 times.
✗ Branch 2 not taken.
 1840 InteractionPoint ip0 = {*outs.at(0), v, basis0, false};
357
1/2
✓ Branch 1 taken 1840 times.
✗ Branch 2 not taken.
 1840 insert_interaction_point(ip0);
358
1/2
✓ Branch 1 taken 1840 times.
✗ Branch 2 not taken.
 1840 InteractionPoint ip1 = {*outs.at(1), v, basis1, false};
359
1/2
✓ Branch 1 taken 1840 times.
✗ Branch 2 not taken.
 1840 insert_interaction_point(ip1);
360 1840 }
361 2173 }
362 1976 }
363
364 999 Subcircuit CliffordReductionPass::substitute(
365 const Circuit &to_insert, const Subcircuit &to_replace) {
366 999 unsigned q_width = to_replace.q_in_hole.size();
367 TKET_ASSERT(q_width == 2);
368
369 // Construct tables of predecessors, successors, units, in-edges, out-edges.
370 // Only quantum circuit replacments here so don't care about classical stuff
371
1/2
✓ Branch 2 taken 999 times.
✗ Branch 3 not taken.
 999 std::vector<VertPort> preds(q_width);
372
1/2
✓ Branch 2 taken 999 times.
✗ Branch 3 not taken.
 999 std::vector<VertPort> succs(q_width);
373
1/2
✓ Branch 2 taken 999 times.
✗ Branch 3 not taken.
 999 std::vector<UnitID> units(q_width);
374
1/2
✓ Branch 2 taken 999 times.
✗ Branch 3 not taken.
 999 std::vector<Edge> in_edges(q_width);
375
1/2
✓ Branch 2 taken 999 times.
✗ Branch 3 not taken.
 999 std::vector<Edge> out_edges(q_width);
376
2/2
✓ Branch 0 taken 1998 times.
✓ Branch 1 taken 999 times.
2/2
✓ Decision 'true' taken 1998 times.
✓ Decision 'false' taken 999 times.
 2997 for (unsigned qi = 0; qi < q_width; ++qi) {
377
1/2
✓ Branch 1 taken 1998 times.
✗ Branch 2 not taken.
 1998 const Edge &in = to_replace.q_in_hole.at(qi);
378
1/2
✓ Branch 1 taken 1998 times.
✗ Branch 2 not taken.
 1998 const Edge &out = to_replace.q_out_hole.at(qi);
379
2/4
✓ Branch 1 taken 1998 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1998 times.
✗ Branch 5 not taken.
 1998 preds[qi] = {circ.source(in), circ.get_source_port(in)};
380
2/4
✓ Branch 1 taken 1998 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1998 times.
✗ Branch 5 not taken.
 1998 succs[qi] = {circ.target(out), circ.get_target_port(out)};
381
1/2
✓ Branch 1 taken 1998 times.
✗ Branch 2 not taken.
 1998 units[qi] = e_to_unit.at(in);
382 1998 in_edges[qi] = in;
383 1998 out_edges[qi] = out;
384 TKET_ASSERT(in == out || circ.target(in) == circ.source(out));
385 }
386
387 // List of points that will be invalidated by the substitution.
388 999 std::list<InteractionPoint> invalidated_points;
389
390 // Lists of points having the same "in"/"out" edge as the replacement:
391 // These are all invalidated (though the "in" ones can be replaced later
392 // with the new edge).
393
1/2
✓ Branch 2 taken 999 times.
✗ Branch 3 not taken.
 999 std::vector<std::list<InteractionPoint>> points_with_in(q_width);
394
1/2
✓ Branch 2 taken 999 times.
✗ Branch 3 not taken.
 999 std::vector<std::list<InteractionPoint>> points_with_out(q_width);
395
2/2
✓ Branch 0 taken 1998 times.
✓ Branch 1 taken 999 times.
2/2
✓ Decision 'true' taken 1998 times.
✓ Decision 'false' taken 999 times.
 2997 for (unsigned qi = 0; qi < q_width; ++qi) {
396
1/2
✓ Branch 3 taken 1998 times.
✗ Branch 4 not taken.
 1998 auto r = itable.get<TagEdge>().equal_range(in_edges[qi]);
397
4/6
✓ Branch 1 taken 1731 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3729 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 1731 times.
✓ Branch 7 taken 1998 times.
0/1
? Decision couldn't be analyzed.
 3729 for (auto it = r.first; it != r.second; it++) {
398
2/4
✓ Branch 2 taken 1731 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1731 times.
✗ Branch 6 not taken.
 1731 points_with_in[qi].push_back(*it);
399
2/4
✓ Branch 1 taken 1731 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1731 times.
✗ Branch 5 not taken.
 1731 invalidated_points.push_back(*it);
400 }
401
1/2
✓ Branch 3 taken 1998 times.
✗ Branch 4 not taken.
 1998 r = itable.get<TagEdge>().equal_range(out_edges[qi]);
402
4/6
✓ Branch 1 taken 2015 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4013 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2015 times.
✓ Branch 7 taken 1998 times.
0/1
? Decision couldn't be analyzed.
 4013 for (auto it = r.first; it != r.second; it++) {
403
2/4
✓ Branch 2 taken 2015 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 2015 times.
✗ Branch 6 not taken.
 2015 points_with_out[qi].push_back(*it);
404
2/4
✓ Branch 1 taken 2015 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2015 times.
✗ Branch 5 not taken.
 2015 invalidated_points.push_back(*it);
405 }
406 }
407
408 // For any (e0, v0) in points_with_out, any point (e1, v0) where e1 is in
409 // the causal future of e0 is also invalidated. Calculate all the future
410 // edges.
411 999 EdgeList future_edges;
412 999 VertexSet v_frontier;
413
2/2
✓ Branch 0 taken 1998 times.
✓ Branch 1 taken 999 times.
2/2
✓ Decision 'true' taken 1998 times.
✓ Decision 'false' taken 999 times.
 2997 for (unsigned qi = 0; qi < q_width; ++qi) {
414
2/4
✓ Branch 2 taken 1998 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1998 times.
✗ Branch 6 not taken.
 1998 v_frontier.insert(circ.target(out_edges[qi]));
415 }
416
2/2
✓ Branch 1 taken 5616 times.
✓ Branch 2 taken 999 times.
2/2
✓ Decision 'true' taken 5616 times.
✓ Decision 'false' taken 999 times.
 6615 while (!v_frontier.empty()) {
417 5616 EdgeSet out_edges;
418
2/2
✓ Branch 5 taken 15529 times.
✓ Branch 6 taken 5616 times.
2/2
✓ Decision 'true' taken 15529 times.
✓ Decision 'false' taken 5616 times.
 21145 for (auto v : v_frontier) {
419
3/4
✓ Branch 2 taken 15529 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 11282 times.
✓ Branch 6 taken 4247 times.
2/2
✓ Decision 'true' taken 11282 times.
✓ Decision 'false' taken 4247 times.
 15529 if (v_to_depth.find(v) != v_to_depth.end()) {
420
1/2
✓ Branch 1 taken 11282 times.
✗ Branch 2 not taken.
 11282 EdgeVec v_out_edges = circ.get_out_edges_of_type(v, EdgeType::Quantum);
421
1/2
✓ Branch 3 taken 11282 times.
✗ Branch 4 not taken.
 11282 out_edges.insert(v_out_edges.begin(), v_out_edges.end());
422 11282 }
423 }
424
1/2
✓ Branch 5 taken 5616 times.
✗ Branch 6 not taken.
 5616 future_edges.insert(future_edges.end(), out_edges.begin(), out_edges.end());
425 5616 VertexSet new_v_frontier;
426
2/2
✓ Branch 4 taken 14245 times.
✓ Branch 5 taken 5616 times.
2/2
✓ Decision 'true' taken 14245 times.
✓ Decision 'false' taken 5616 times.
 19861 for (auto e : out_edges) {
427
2/4
✓ Branch 1 taken 14245 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 14245 times.
✗ Branch 5 not taken.
 14245 new_v_frontier.insert(circ.target(e));
428 }
429 5616 v_frontier = std::move(new_v_frontier);
430 5616 }
431
432 // Invalidate the (e1, v0) as above.
433 999 VertexSet invalid_sources;
434
2/2
✓ Branch 0 taken 1998 times.
✓ Branch 1 taken 999 times.
2/2
✓ Decision 'true' taken 1998 times.
✓ Decision 'false' taken 999 times.
 2997 for (unsigned qi = 0; qi < q_width; ++qi) {
435
2/2
✓ Branch 6 taken 2015 times.
✓ Branch 7 taken 1998 times.
2/2
✓ Decision 'true' taken 2015 times.
✓ Decision 'false' taken 1998 times.
 4013 for (auto ip : points_with_out[qi]) {
436 TKET_ASSERT(ip.e == out_edges[qi]);
437
1/2
✓ Branch 1 taken 2015 times.
✗ Branch 2 not taken.
 2015 invalid_sources.insert(ip.source);
438 }
439 }
440
2/2
✓ Branch 5 taken 14245 times.
✓ Branch 6 taken 999 times.
2/2
✓ Decision 'true' taken 14245 times.
✓ Decision 'false' taken 999 times.
 15244 for (auto e1 : future_edges) {
441
1/2
✓ Branch 2 taken 14245 times.
✗ Branch 3 not taken.
 14245 auto r = itable.get<TagEdge>().equal_range(e1);
442
4/6
✓ Branch 1 taken 15629 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 29874 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 15629 times.
✓ Branch 7 taken 14245 times.
0/1
? Decision couldn't be analyzed.
 29874 for (auto it = r.first; it != r.second; ++it) {
443
4/6
✓ Branch 2 taken 15629 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 15629 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 7464 times.
✓ Branch 9 taken 8165 times.
2/2
✓ Decision 'true' taken 7464 times.
✓ Decision 'false' taken 8165 times.
 15629 if (invalid_sources.find(it->source) != invalid_sources.end()) {
444
2/4
✓ Branch 1 taken 7464 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 7464 times.
✗ Branch 5 not taken.
 7464 invalidated_points.push_back(*it);
445 }
446 }
447 }
448
449 // Erase the invalidated points from the table.
450
2/2
✓ Branch 4 taken 11210 times.
✓ Branch 5 taken 999 times.
2/2
✓ Decision 'true' taken 11210 times.
✓ Decision 'false' taken 999 times.
 12209 for (auto ip : invalidated_points) {
451
2/4
✓ Branch 1 taken 11210 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 11210 times.
✗ Branch 5 not taken.
 11210 itable.erase(ip.key());
452 }
453
454 // Erase edges from e_to_unit
455
2/2
✓ Branch 0 taken 1998 times.
✓ Branch 1 taken 999 times.
2/2
✓ Decision 'true' taken 1998 times.
✓ Decision 'false' taken 999 times.
 2997 for (unsigned qi = 0; qi < q_width; ++qi) {
456
1/2
✓ Branch 2 taken 1998 times.
✗ Branch 3 not taken.
 1998 e_to_unit.erase(in_edges[qi]);
457
1/2
✓ Branch 2 taken 1998 times.
✗ Branch 3 not taken.
 1998 e_to_unit.erase(out_edges[qi]);
458 // Depth of to_replace is at most 1, so there are no other edges
459 }
460
461 // Remove replaced vertices from depth and units maps and erase all points
462 // from the itable that have a replaced vertex as source.
463
2/2
✓ Branch 5 taken 666 times.
✓ Branch 6 taken 999 times.
2/2
✓ Decision 'true' taken 666 times.
✓ Decision 'false' taken 999 times.
 1665 for (const Vertex &v : to_replace.verts) {
464
1/2
✓ Branch 1 taken 666 times.
✗ Branch 2 not taken.
 666 v_to_depth.erase(v);
465
1/2
✓ Branch 1 taken 666 times.
✗ Branch 2 not taken.
 666 v_to_units.erase(v);
466
1/2
✓ Branch 2 taken 666 times.
✗ Branch 3 not taken.
 666 auto r = itable.get<TagSource>().equal_range(v);
467
2/4
✓ Branch 1 taken 666 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 666 times.
0/1
? Decision couldn't be analyzed.
 666 for (auto next = r.first; next != r.second; r.first = next) {
468 ✗ ++next;
469 ✗ itable.erase(itable.project<TagKey>(r.first));
470 }
471 }
472
473
1/2
✓ Branch 1 taken 999 times.
✗ Branch 2 not taken.
 999 circ.substitute(to_insert, to_replace);
474
475 // Update the tables of in and out edges, and amend the stored points
476
2/2
✓ Branch 0 taken 1998 times.
✓ Branch 1 taken 999 times.
2/2
✓ Decision 'true' taken 1998 times.
✓ Decision 'false' taken 999 times.
 2997 for (unsigned qi = 0; qi < q_width; ++qi) {
477
1/2
✓ Branch 3 taken 1998 times.
✗ Branch 4 not taken.
 1998 in_edges[qi] = circ.get_nth_out_edge(preds[qi].first, preds[qi].second);
478
1/2
✓ Branch 3 taken 1998 times.
✗ Branch 4 not taken.
 1998 out_edges[qi] = circ.get_nth_in_edge(succs[qi].first, succs[qi].second);
479
2/2
✓ Branch 5 taken 1731 times.
✓ Branch 6 taken 1998 times.
2/2
✓ Decision 'true' taken 1731 times.
✓ Decision 'false' taken 1998 times.
 3729 for (InteractionPoint &ip : points_with_in[qi]) {
480 1731 ip.e = in_edges[qi];
481 }
482 }
483
484 // Construct inserted Subcircuit, update e_to_unit and v_to_units, and
485 // add new vertices to v_to_depth, with (temporary) value 0.
486 999 Subcircuit inserted;
487
2/2
✓ Branch 0 taken 1998 times.
✓ Branch 1 taken 999 times.
2/2
✓ Decision 'true' taken 1998 times.
✓ Decision 'false' taken 999 times.
 2997 for (unsigned qi = 0; qi < q_width; ++qi) {
488 1998 Edge in = in_edges[qi];
489
1/2
✓ Branch 1 taken 1998 times.
✗ Branch 2 not taken.
 1998 inserted.q_in_hole.push_back(in);
490 1998 Edge out = out_edges[qi];
491
1/2
✓ Branch 1 taken 1998 times.
✗ Branch 2 not taken.
 1998 inserted.q_out_hole.push_back(out);
492
3/4
✓ Branch 1 taken 5490 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 3492 times.
✓ Branch 4 taken 1998 times.
0/1
? Decision couldn't be analyzed.
 5490 while (in != out) {
493
1/2
✓ Branch 1 taken 3492 times.
✗ Branch 2 not taken.
 3492 Vertex next = circ.target(in);
494
1/2
✓ Branch 1 taken 3492 times.
✗ Branch 2 not taken.
 3492 inserted.verts.insert(next);
495
1/2
✓ Branch 3 taken 3492 times.
✗ Branch 4 not taken.
 3492 e_to_unit.insert({in, units[qi]});
496
1/2
✓ Branch 2 taken 3492 times.
✗ Branch 3 not taken.
 3492 v_to_depth.insert({next, 0});
497
2/4
✓ Branch 1 taken 3492 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 3492 times.
✗ Branch 6 not taken.
 3492 v_to_units[next].insert(units[qi]);
498
2/4
✓ Branch 1 taken 3492 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3492 times.
✗ Branch 5 not taken.
 3492 in = circ.get_nth_out_edge(next, circ.get_target_port(in));
499 }
500
1/2
✓ Branch 3 taken 1998 times.
✗ Branch 4 not taken.
 1998 e_to_unit.insert({in, units[qi]});
501 }
502
503 // Now `v_to_depth` is 0 at all `inserted.verts`. Fix this and propagate
504 // updates to the depth map into the future cone, ensuring that the depths
505 // are strictly increasing along wires. Stop when we reach a vertex that
506 // isn't already in v_to_depth (because we haven't processed it yet).
507
2/2
✓ Branch 0 taken 1998 times.
✓ Branch 1 taken 999 times.
2/2
✓ Decision 'true' taken 1998 times.
✓ Decision 'false' taken 999 times.
 2997 for (unsigned qi = 0; qi < q_width; ++qi) {
508 1998 Edge in = in_edges[qi];
509
1/2
✓ Branch 1 taken 1998 times.
✗ Branch 2 not taken.
 1998 Vertex next = circ.target(in);
510
2/2
✓ Branch 1 taken 1914 times.
✓ Branch 2 taken 84 times.
2/2
✓ Decision 'true' taken 1914 times.
✓ Decision 'false' taken 84 times.
 1998 if (next != succs[qi].first) {
511
4/6
✓ Branch 2 taken 1914 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1914 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 1913 times.
✓ Branch 8 taken 1 times.
2/2
✓ Decision 'true' taken 1913 times.
✓ Decision 'false' taken 1 times.
 1914 if (v_to_depth.at(preds[qi].first) >= v_to_depth[next]) {
512 // We may have already set v_to_depth[next] to a higher value
513 // when tracing another qubit, so the check above is necessary.
514
2/4
✓ Branch 2 taken 1913 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1913 times.
✗ Branch 6 not taken.
 1913 v_to_depth[next] = v_to_depth.at(preds[qi].first) + 1;
515 }
516 std::function<bool(const Vertex &, const Vertex &)> c =
517 2152 [&](const Vertex &a, const Vertex &b) {
518 2152 unsigned deptha = v_to_depth.at(a);
519 2152 unsigned depthb = v_to_depth.at(b);
520
2/2
✓ Branch 0 taken 1233 times.
✓ Branch 1 taken 919 times.
2/2
✓ Decision 'true' taken 1233 times.
✓ Decision 'false' taken 919 times.
 2152 if (deptha == depthb) {
521
2/4
✓ Branch 1 taken 1233 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1233 times.
✗ Branch 5 not taken.
 1233 unit_set_t unitsa = v_to_units.at(a);
522
2/4
✓ Branch 1 taken 1233 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1233 times.
✗ Branch 5 not taken.
 1233 unit_set_t unitsb = v_to_units.at(b);
523
1/2
✓ Branch 2 taken 1233 times.
✗ Branch 3 not taken.
 1233 return unitsa < unitsb;
524 1233 }
525 919 return deptha < depthb;
526 1914 };
527 1914 std::set<Vertex> to_search;
528
1/2
✓ Branch 1 taken 1914 times.
✗ Branch 2 not taken.
 1914 to_search.insert(next);
529
2/2
✓ Branch 1 taken 5502 times.
✓ Branch 2 taken 1914 times.
2/2
✓ Decision 'true' taken 5502 times.
✓ Decision 'false' taken 1914 times.
 7416 while (!to_search.empty()) {
530
2/4
✓ Branch 1 taken 5502 times.
✗ Branch 2 not taken.
✓ Branch 6 taken 5502 times.
✗ Branch 7 not taken.
 5502 Vertex v = *std::min_element(to_search.begin(), to_search.end(), c);
531
1/2
✓ Branch 1 taken 5502 times.
✗ Branch 2 not taken.
 5502 to_search.erase(v);
532
1/2
✓ Branch 1 taken 5502 times.
✗ Branch 2 not taken.
 5502 unsigned v_depth = v_to_depth.at(v);
533
1/2
✓ Branch 1 taken 5502 times.
✗ Branch 2 not taken.
 5502 EdgeVec outs = circ.get_all_out_edges(v);
534
2/2
✓ Branch 5 taken 6651 times.
✓ Branch 6 taken 5502 times.
2/2
✓ Decision 'true' taken 6651 times.
✓ Decision 'false' taken 5502 times.
 12153 for (const Edge &e : outs) {
535
1/2
✓ Branch 1 taken 6651 times.
✗ Branch 2 not taken.
 6651 Vertex succ = circ.target(e);
536
1/2
✓ Branch 1 taken 6651 times.
✗ Branch 2 not taken.
 6651 std::map<Vertex, unsigned>::iterator succ_it = v_to_depth.find(succ);
537
2/2
✓ Branch 2 taken 4729 times.
✓ Branch 3 taken 1922 times.
2/2
✓ Decision 'true' taken 4729 times.
✓ Decision 'false' taken 1922 times.
 6651 if (succ_it != v_to_depth.end()) {
538
2/2
✓ Branch 1 taken 3628 times.
✓ Branch 2 taken 1101 times.
2/2
✓ Decision 'true' taken 3628 times.
✓ Decision 'false' taken 1101 times.
 4729 if (succ_it->second <= v_depth) {
539 3628 succ_it->second = v_depth + 1;
540
2/2
✓ Branch 0 taken 1506 times.
✓ Branch 1 taken 2122 times.
2/2
✓ Decision 'true' taken 1506 times.
✓ Decision 'false' taken 2122 times.
 3628 if (v_depth >= current_depth) {
541 1506 current_depth = v_depth + 1;
542 }
543
1/2
✓ Branch 1 taken 3628 times.
✗ Branch 2 not taken.
 3628 to_search.insert(succ);
544 }
545 }
546 }
547 5502 }
548 1914 }
549 }
550
551 // Re-insert all the interaction points we erased above.
552
2/2
✓ Branch 0 taken 1998 times.
✓ Branch 1 taken 999 times.
2/2
✓ Decision 'true' taken 1998 times.
✓ Decision 'false' taken 999 times.
 2997 for (unsigned qi = 0; qi < q_width; ++qi) {
553
2/2
✓ Branch 6 taken 1731 times.
✓ Branch 7 taken 1998 times.
2/2
✓ Decision 'true' taken 1731 times.
✓ Decision 'false' taken 1998 times.
 3729 for (const InteractionPoint &ip : points_with_in[qi]) {
554
1/2
✓ Branch 1 taken 1731 times.
✗ Branch 2 not taken.
 1731 insert_interaction_point(ip);
555 }
556 }
557
558 1998 return inserted;
559 999 }
560
561 14 std::optional<Edge> CliffordReductionPass::find_earliest_successor(
562 const Edge &source, const EdgeSet &candidates) const {
563 typedef std::function<bool(Vertex, Vertex)> Comp;
564 214 Comp c = [&](Vertex a, Vertex b) {
565 214 unsigned deptha = v_to_depth.at(a);
566 214 unsigned depthb = v_to_depth.at(b);
567
2/2
✓ Branch 0 taken 78 times.
✓ Branch 1 taken 136 times.
2/2
✓ Decision 'true' taken 78 times.
✓ Decision 'false' taken 136 times.
 214 if (deptha == depthb) {
568
2/4
✓ Branch 1 taken 78 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 78 times.
✗ Branch 5 not taken.
 78 unit_set_t unitsa = v_to_units.at(a);
569
2/4
✓ Branch 1 taken 78 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 78 times.
✗ Branch 5 not taken.
 78 unit_set_t unitsb = v_to_units.at(b);
570
1/2
✓ Branch 2 taken 78 times.
✗ Branch 3 not taken.
 78 return unitsa < unitsb;
571 78 }
572 136 return deptha < depthb;
573 14 };
574
1/2
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
 14 std::set<Vertex, Comp> to_search(c);
575
2/4
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 14 times.
✗ Branch 5 not taken.
 14 to_search.insert(circ.target(source));
576
1/2
✓ Branch 1 taken 93 times.
✗ Branch 2 not taken.
1/2
✓ Decision 'true' taken 93 times.
✗ Decision 'false' not taken.
 93 while (!to_search.empty()) {
577 93 Vertex v = *to_search.begin();
578
1/2
✓ Branch 2 taken 93 times.
✗ Branch 3 not taken.
 93 to_search.erase(to_search.begin());
579
1/2
✓ Branch 1 taken 93 times.
✗ Branch 2 not taken.
 93 EdgeVec outs = circ.get_all_out_edges(v);
580
2/2
✓ Branch 5 taken 113 times.
✓ Branch 6 taken 79 times.
2/2
✓ Decision 'true' taken 113 times.
✓ Decision 'false' taken 79 times.
 192 for (const Edge &e : outs) {
581
3/4
✓ Branch 2 taken 113 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 14 times.
✓ Branch 6 taken 99 times.
2/2
✓ Decision 'true' taken 99 times.
✓ Decision 'false' taken 14 times.
 113 if (candidates.find(e) != candidates.end()) return e;
582
1/2
✓ Branch 1 taken 99 times.
✗ Branch 2 not taken.
 99 Vertex succ = circ.target(e);
583
4/6
✓ Branch 2 taken 99 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 91 times.
✓ Branch 6 taken 8 times.
✓ Branch 8 taken 91 times.
✗ Branch 9 not taken.
2/2
✓ Decision 'true' taken 93 times.
✓ Decision 'false' taken 6 times.
 99 if (v_to_depth.find(succ) != v_to_depth.end()) to_search.insert(succ);
584 }
585
2/2
✓ Branch 1 taken 79 times.
✓ Branch 2 taken 14 times.
 93 }
586 ✗ return std::nullopt;
587 14 }
588
589 std::optional<std::pair<InteractionPoint, InteractionPoint>>
590 402 CliffordReductionPass::valid_insertion_point(
591 const std::list<InteractionPoint> &seq0,
592 const std::list<InteractionPoint> &seq1) const {
593 // seq0 is chain of edges (in temporal order) from the first qubit
594 // likewise seq1 for the other qubit
595 402 InteractionPoint seq0max = seq0.back();
596 402 InteractionPoint seq1max = seq1.back();
597 1206 if (circ.in_causal_order(
598
4/6
✓ Branch 1 taken 402 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 402 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 3 times.
✓ Branch 7 taken 399 times.
 402 circ.source(seq1max.e), circ.target(seq0max.e), true, v_to_depth,
599
1/2
✓ Branch 1 taken 402 times.
✗ Branch 2 not taken.
 402 v_to_units, false)) {
600 // Search for any points in seq1 from future of seq0max
601 3 EdgeSet candidates;
602 3 std::map<Edge, InteractionPoint> lookup;
603
2/2
✓ Branch 4 taken 76 times.
✓ Branch 5 taken 3 times.
2/2
✓ Decision 'true' taken 76 times.
✓ Decision 'false' taken 3 times.
 79 for (const InteractionPoint &ip : seq1) {
604
1/2
✓ Branch 1 taken 76 times.
✗ Branch 2 not taken.
 76 candidates.insert(ip.e);
605
1/2
✓ Branch 2 taken 76 times.
✗ Branch 3 not taken.
 76 lookup.insert({ip.e, ip});
606 }
607 std::optional<Edge> successor =
608
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 find_earliest_successor(seq0max.e, candidates);
609
4/8
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 3 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 3 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 3 times.
1/2
✓ Decision 'true' taken 3 times.
✗ Decision 'false' not taken.
 3 if (!successor || successor == seq1.front().e) return std::nullopt;
610
1/2
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 3 Vertex v = circ.source(*successor);
611
1/2
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 3 port_t p = circ.get_source_port(*successor);
612
2/4
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 3 times.
1/2
✓ Decision 'true' taken 3 times.
✗ Decision 'false' not taken.
 3 if (circ.get_OpType_from_Vertex(v) == OpType::SWAP) p = 1 - p;
613
2/4
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3 times.
✗ Branch 5 not taken.
 3 return {{seq0max, lookup.at(circ.get_nth_in_edge(v, p))}};
614 3 } else if (circ.in_causal_order(
615
4/6
✓ Branch 1 taken 399 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 399 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 11 times.
✓ Branch 7 taken 388 times.
 399 circ.source(seq0max.e), circ.target(seq1max.e), true,
616
1/2
✓ Branch 1 taken 399 times.
✗ Branch 2 not taken.
 399 v_to_depth, v_to_units, false)) {
617 // Search for any points in seq0 from future of seq1max
618 11 EdgeSet candidates;
619 11 std::map<Edge, InteractionPoint> lookup;
620
2/2
✓ Branch 4 taken 34 times.
✓ Branch 5 taken 11 times.
2/2
✓ Decision 'true' taken 34 times.
✓ Decision 'false' taken 11 times.
 45 for (const InteractionPoint &ip : seq0) {
621
1/2
✓ Branch 1 taken 34 times.
✗ Branch 2 not taken.
 34 candidates.insert(ip.e);
622
1/2
✓ Branch 2 taken 34 times.
✗ Branch 3 not taken.
 34 lookup.insert({ip.e, ip});
623 }
624 std::optional<Edge> successor =
625
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 find_earliest_successor(seq1max.e, candidates);
626
6/8
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 11 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 7 times.
✓ Branch 8 taken 4 times.
✓ Branch 9 taken 7 times.
✓ Branch 10 taken 4 times.
2/2
✓ Decision 'true' taken 4 times.
✓ Decision 'false' taken 7 times.
 11 if (!successor || successor == seq0.front().e) return std::nullopt;
627
1/2
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
 4 Vertex v = circ.source(*successor);
628
1/2
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
 4 port_t p = circ.get_source_port(*successor);
629
2/4
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 4 times.
1/2
✓ Decision 'true' taken 4 times.
✗ Decision 'false' not taken.
 4 if (circ.get_OpType_from_Vertex(v) == OpType::SWAP) p = 1 - p;
630
2/4
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
 4 return {{lookup.at(circ.get_nth_in_edge(v, p)), seq1max}};
631 11 } else {
632 // seq0max and seq1max are space-like separated
633 388 return {{seq0max, seq1max}};
634 }
635 }
636
637 181 CliffordReductionPass::CliffordReductionPass(Circuit &c, bool swaps)
638 181 : circ(c),
639 181 itable(),
640 181 v_to_depth(),
641 181 success(false),
642 181 current_depth(1),
643 181 allow_swaps(swaps) {
644
1/2
✓ Branch 1 taken 181 times.
✗ Branch 2 not taken.
 181 v_to_units = circ.vertex_unit_map();
645
1/2
✓ Branch 1 taken 181 times.
✗ Branch 2 not taken.
 181 e_to_unit = circ.edge_unit_map();
646 181 }
647
648 180 bool CliffordReductionPass::reduce_circuit(Circuit &circ, bool allow_swaps) {
649
1/2
✓ Branch 1 taken 180 times.
✗ Branch 2 not taken.
 180 CliffordReductionPass context(circ, allow_swaps);
650
651
1/2
✓ Branch 1 taken 180 times.
✗ Branch 2 not taken.
 180 SliceVec slices = circ.get_slices();
652
653
3/4
✓ Branch 1 taken 180 times.
✗ Branch 2 not taken.
✓ Branch 7 taken 519 times.
✓ Branch 8 taken 180 times.
0/1
? Decision couldn't be analyzed.
 699 for (const Vertex &in : circ.all_inputs()) {
654
1/2
✓ Branch 2 taken 519 times.
✗ Branch 3 not taken.
 519 context.v_to_depth.insert({in, 0});
655 180 }
656
657 // Process all 2qb Clifford vertices.
658
2/2
✓ Branch 4 taken 6992 times.
✓ Branch 5 taken 180 times.
2/2
✓ Decision 'true' taken 6992 times.
✓ Decision 'false' taken 180 times.
 7172 for (const Slice &sl : slices) {
659
2/2
✓ Branch 5 taken 11985 times.
✓ Branch 6 taken 6992 times.
2/2
✓ Decision 'true' taken 11985 times.
✓ Decision 'false' taken 6992 times.
 18977 for (const Vertex &v : sl) {
660
1/2
✓ Branch 2 taken 11985 times.
✗ Branch 3 not taken.
 11985 context.v_to_depth.insert({v, context.current_depth});
661
1/2
✓ Branch 1 taken 11985 times.
✗ Branch 2 not taken.
 11985 Op_ptr op = circ.get_Op_ptr_from_Vertex(v);
662
4/6
✓ Branch 2 taken 11985 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 11985 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 20 times.
✓ Branch 9 taken 11965 times.
2/2
✓ Decision 'true' taken 11965 times.
✓ Decision 'false' taken 20 times.
 11985 if (!op->get_desc().is_gate()) continue;
663
1/2
✓ Branch 1 taken 11965 times.
✗ Branch 2 not taken.
 11965 EdgeVec ins = circ.get_in_edges(v);
664
1/2
✓ Branch 1 taken 11965 times.
✗ Branch 2 not taken.
 11965 std::vector<std::optional<Edge>> outs = circ.get_linear_out_edges(v);
665 11965 OpType type = op->get_type();
666 11965 std::list<InteractionPoint> new_points;
667
3/3
✓ Branch 0 taken 8437 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 3527 times.
 11965 switch (type) {
668 8437 case OpType::H:
669 case OpType::S:
670 case OpType::Sdg:
671 case OpType::V:
672 case OpType::Vdg:
673 case OpType::X:
674 case OpType::Y:
675 case OpType::Z: {
676
1/2
✓ Branch 3 taken 8437 times.
✗ Branch 4 not taken.
 8437 auto r = context.itable.get<TagEdge>().equal_range(ins[0]);
677
4/6
✓ Branch 1 taken 7589 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 16026 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 7589 times.
✓ Branch 7 taken 8437 times.
0/1
? Decision couldn't be analyzed.
 16026 for (auto it = r.first; it != r.second; ++it) {
678
1/2
✓ Branch 1 taken 7589 times.
✗ Branch 2 not taken.
 7589 InteractionPoint ip = *it;
679 std::pair<Pauli, bool> new_basis =
680
1/2
✓ Branch 1 taken 7589 times.
✗ Branch 2 not taken.
 7589 conjugate_Pauli(type, ip.p, true);
681 7589 ip.p = new_basis.first;
682 7589 ip.phase ^= new_basis.second;
683 7589 ip.e = *outs[0];
684
1/2
✓ Branch 1 taken 7589 times.
✗ Branch 2 not taken.
 7589 new_points.push_back(ip);
685 }
686 8437 break;
687 }
688
1/1
✓ Decision 'true' taken 1 times.
 1 case OpType::SWAP: {
689
1/2
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
 1 auto r0 = context.itable.get<TagEdge>().equal_range(ins[0]);
690
2/6
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 1 times.
0/1
? Decision couldn't be analyzed.
 1 for (auto it = r0.first; it != r0.second; ++it) {
691 ✗ InteractionPoint ip = *it;
692 ✗ ip.e = *outs[1];
693 ✗ new_points.push_back(ip);
694 }
695
1/2
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
 1 auto r1 = context.itable.get<TagEdge>().equal_range(ins[1]);
696
4/6
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 1 times.
✓ Branch 7 taken 1 times.
0/1
? Decision couldn't be analyzed.
 2 for (auto it = r1.first; it != r1.second; ++it) {
697
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 InteractionPoint ip = *it;
698 1 ip.e = *outs[0];
699
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 new_points.push_back(ip);
700 }
701 1 break;
702 }
703
1/1
✓ Decision 'true' taken 9047 times.
 3527 default: {
704
2/2
✓ Branch 1 taken 5520 times.
✓ Branch 2 taken 3527 times.
2/2
✓ Decision 'true' taken 5520 times.
✓ Decision 'false' taken 3527 times.
 9047 for (unsigned i = 0; i < ins.size(); ++i) {
705
1/2
✓ Branch 3 taken 5520 times.
✗ Branch 4 not taken.
 5520 auto r = context.itable.get<TagEdge>().equal_range(ins[i]);
706
4/6
✓ Branch 1 taken 4506 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 10026 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 4506 times.
✓ Branch 7 taken 5520 times.
0/1
? Decision couldn't be analyzed.
 10026 for (auto it = r.first; it != r.second; ++it) {
707
1/2
✓ Branch 1 taken 4506 times.
✗ Branch 2 not taken.
 4506 InteractionPoint ip = *it;
708
3/4
✓ Branch 2 taken 4506 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1715 times.
✓ Branch 5 taken 2791 times.
2/2
✓ Decision 'true' taken 1715 times.
✓ Decision 'false' taken 2791 times.
 4506 if (circ.commutes_with_basis(v, ip.p, PortType::Target, i)) {
709 1715 ip.e = *outs[i];
710
1/2
✓ Branch 1 taken 1715 times.
✗ Branch 2 not taken.
 1715 new_points.push_back(ip);
711 }
712 }
713 }
714 3527 break;
715 }
716 }
717
2/2
✓ Branch 5 taken 9305 times.
✓ Branch 6 taken 11965 times.
2/2
✓ Decision 'true' taken 9305 times.
✓ Decision 'false' taken 11965 times.
 21270 for (const InteractionPoint &ip : new_points) {
718
1/2
✓ Branch 1 taken 9305 times.
✗ Branch 2 not taken.
 9305 context.itable.insert(ip);
719 }
720
2/2
✓ Branch 0 taken 1976 times.
✓ Branch 1 taken 9989 times.
 11965 switch (type) {
721 1976 case OpType::CX:
722 case OpType::CY:
723 case OpType::CZ:
724 case OpType::ZZMax: {
725
1/2
✓ Branch 1 taken 1976 times.
✗ Branch 2 not taken.
 1976 context.process_new_interaction(v);
726 1976 break;
727 }
728
1/1
✓ Decision 'true' taken 9989 times.
 9989 default: {
729 9989 break;
730 }
731 }
732
2/2
✓ Branch 4 taken 11965 times.
✓ Branch 5 taken 20 times.
 11985 }
733 6992 ++context.current_depth;
734 }
735
736
2/2
✓ Branch 0 taken 71 times.
✓ Branch 1 taken 109 times.
2/2
✓ Decision 'true' taken 71 times.
✓ Decision 'false' taken 109 times.
 180 if (allow_swaps) {
737
1/2
✓ Branch 1 taken 71 times.
✗ Branch 2 not taken.
 71 circ.replace_SWAPs();
738 }
739
740 180 return context.success;
741 180 }
742
743 namespace Transforms {
744
745 177 Transform clifford_reduction(bool allow_swaps) {
746 180 return Transform([=](Circuit &circ) {
747 180 return CliffordReductionPass::reduce_circuit(circ, allow_swaps);
748
1/2
✓ Branch 2 taken 177 times.
✗ Branch 3 not taken.
 177 });
749 }
750
751 } // namespace Transforms
752
753 1 CliffordReductionPassTester::CliffordReductionPassTester(Circuit &circ)
754 1 : context(circ, true) {
755 // populate v_to_depth
756
3/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 7 taken 4 times.
✓ Branch 8 taken 1 times.
0/1
? Decision couldn't be analyzed.
 5 for (const Vertex &in : circ.all_inputs()) {
757
1/2
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
 4 context.v_to_depth.insert({in, 0});
758 1 }
759
760
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 SliceVec slices = circ.get_slices();
761
2/2
✓ Branch 5 taken 3 times.
✓ Branch 6 taken 1 times.
2/2
✓ Decision 'true' taken 3 times.
✓ Decision 'false' taken 1 times.
 4 for (const Slice &sl : slices) {
762
2/2
✓ Branch 4 taken 4 times.
✓ Branch 5 taken 3 times.
2/2
✓ Decision 'true' taken 4 times.
✓ Decision 'false' taken 3 times.
 7 for (const Vertex &v : sl) {
763
1/2
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
 4 context.v_to_depth.insert({v, context.current_depth});
764 }
765 }
766 1 }
767
768 std::optional<std::pair<InteractionPoint, InteractionPoint>>
769 1 CliffordReductionPassTester::valid_insertion_point(
770 const std::list<InteractionPoint> &seq0,
771 const std::list<InteractionPoint> &seq1) const {
772 1 return context.valid_insertion_point(seq0, seq1);
773 }
774
775 } // namespace tket
776