GCC Code Coverage Report

Directory: ./
File: Transformations/BasicOptimisation.cpp
Date: 2022-10-15 05:10:18
Warnings: 12 unchecked decisions!
Exec Total Coverage
Lines: 451 530 85.1%
Functions: 20 27 74.1%
Branches: 581 1074 54.1%
Decisions: 138 194 71.1%
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 "BasicOptimisation.hpp"
16
17 #include <optional>
18 #include <tkassert/Assert.hpp>
19
20 #include "Characterisation/DeviceCharacterisation.hpp"
21 #include "Characterisation/ErrorTypes.hpp"
22 #include "Circuit/CircPool.hpp"
23 #include "Circuit/CircUtils.hpp"
24 #include "Circuit/Command.hpp"
25 #include "Circuit/DAGDefs.hpp"
26 #include "Decomposition.hpp"
27 #include "Gate/Gate.hpp"
28 #include "Gate/GatePtr.hpp"
29 #include "Gate/Rotation.hpp"
30 #include "Transform.hpp"
31 #include "Utils/EigenConfig.hpp"
32 #include "Utils/MatrixAnalysis.hpp"
33
34 namespace tket {
35
36 namespace Transforms {
37
38 static bool redundancy_removal(Circuit &circ);
39 static bool remove_redundancy(
40 Circuit &circ, const Vertex &vert, VertexSet &bin,
41 std::set<IVertex> &new_affected_verts, IndexMap &im);
42 static bool commute_singles_to_front(Circuit &circ);
43
44
1/2
✓ Branch 2 taken 1638 times.
✗ Branch 3 not taken.
 1638 Transform remove_redundancies() { return Transform(redundancy_removal); }
45
46 // this method annihilates all primitives next to each other (accounting for
47 // previous annihilations)
48 // also removes redundant non-classically controlled Z basis gates before a z
49 // basis measurement so that eg. -H-X-X-H- always annihilates to -----
50 2016 static bool redundancy_removal(Circuit &circ) {
51 2016 bool success = false;
52 2016 bool found_redundancy = true;
53
1/2
✓ Branch 1 taken 2016 times.
✗ Branch 2 not taken.
 2016 IndexMap im = circ.index_map();
54 2016 std::set<IVertex> old_affected_verts;
55
7/8
✓ Branch 1 taken 2016 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 74300 times.
✓ Branch 5 taken 2016 times.
✓ Branch 7 taken 74300 times.
✓ Branch 8 taken 2016 times.
✓ Branch 10 taken 2016 times.
✓ Branch 11 taken 2016 times.
 78332 BGL_FORALL_VERTICES(v, circ.dag, DAG) {
56
2/4
✓ Branch 1 taken 74300 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 74300 times.
✗ Branch 6 not taken.
 74300 old_affected_verts.insert({im.at(v), v});
57 }
58 2016 VertexSet bin;
59
2/2
✓ Branch 0 taken 3332 times.
✓ Branch 1 taken 2016 times.
2/2
✓ Decision 'true' taken 3332 times.
✓ Decision 'false' taken 2016 times.
 5348 while (found_redundancy) {
60 3332 std::set<IVertex> new_affected_verts;
61 3332 bool removed = false;
62
2/2
✓ Branch 4 taken 77365 times.
✓ Branch 5 taken 3332 times.
2/2
✓ Decision 'true' taken 77365 times.
✓ Decision 'false' taken 3332 times.
 80697 for (const IVertex &p : old_affected_verts) {
63
1/2
✓ Branch 1 taken 77365 times.
✗ Branch 2 not taken.
 77365 removed |= remove_redundancy(circ, p.second, bin, new_affected_verts, im);
64 }
65 3332 found_redundancy = removed;
66 3332 success |= removed;
67
1/2
✓ Branch 1 taken 3332 times.
✗ Branch 2 not taken.
 3332 old_affected_verts = new_affected_verts;
68 3332 }
69
1/2
✓ Branch 1 taken 2016 times.
✗ Branch 2 not taken.
 2016 circ.remove_vertices(
70 bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
71 2016 return success;
72 2016 }
73
74 // called by the previous method. This should generally not be called
75 // independently
76 77365 static bool remove_redundancy(
77 Circuit &circ, const Vertex &vert, VertexSet &bin,
78 std::set<IVertex> &new_affected_verts, IndexMap &im) {
79
1/2
✓ Branch 1 taken 77365 times.
✗ Branch 2 not taken.
 77365 const Op_ptr op = circ.get_Op_ptr_from_Vertex(vert);
80
1/2
✓ Branch 2 taken 77365 times.
✗ Branch 3 not taken.
 77365 const OpDesc desc = op->get_desc();
81
3/4
✓ Branch 1 taken 77365 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 12904 times.
✓ Branch 4 taken 64461 times.
2/2
✓ Decision 'true' taken 64461 times.
✓ Decision 'false' taken 12904 times.
 77365 if (!desc.is_gate()) return false;
82
83
3/4
✓ Branch 1 taken 64461 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 535 times.
✓ Branch 4 taken 63926 times.
2/2
✓ Decision 'true' taken 535 times.
✓ Decision 'false' taken 63926 times.
 64461 if (bin.contains(vert)) {
84 535 return false; // we have already removed it
85 }
86
87 379 auto remove_single_vertex = [&bin, &circ, &new_affected_verts,
88 1520 &im](const Vertex &v_remove) {
89 379 bin.insert(v_remove);
90
3/4
✓ Branch 1 taken 379 times.
✗ Branch 2 not taken.
✓ Branch 7 taken 383 times.
✓ Branch 8 taken 379 times.
0/1
? Decision couldn't be analyzed.
 762 for (const Vertex &l : circ.get_predecessors(v_remove)) {
91
2/4
✓ Branch 1 taken 383 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 383 times.
✗ Branch 6 not taken.
 383 new_affected_verts.insert({im.at(l), l});
92 379 }
93 379 circ.remove_vertex(
94 v_remove, Circuit::GraphRewiring::Yes, Circuit::VertexDeletion::No);
95 379 };
96 // remove identities from circuit
97
1/2
✓ Branch 2 taken 63926 times.
✗ Branch 3 not taken.
 63926 std::optional<double> a = op->is_identity();
98
2/2
✓ Branch 1 taken 375 times.
✓ Branch 2 taken 63551 times.
2/2
✓ Decision 'true' taken 375 times.
✓ Decision 'false' taken 63551 times.
 63926 if (a) {
99
1/2
✓ Branch 1 taken 375 times.
✗ Branch 2 not taken.
 375 remove_single_vertex(vert);
100
3/6
✓ Branch 1 taken 375 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 375 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 375 times.
✗ Branch 8 not taken.
 375 circ.add_phase(a.value());
101 375 return true;
102 }
103
1/2
✓ Branch 1 taken 63551 times.
✗ Branch 2 not taken.
 63551 VertexVec kids = circ.get_successors(vert);
104
105 // if op is immediately followed by a z basis measurement on all qubits,
106 // remove
107
3/4
✓ Branch 1 taken 63551 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 63468 times.
✓ Branch 4 taken 83 times.
2/2
✓ Decision 'true' taken 63468 times.
✓ Decision 'false' taken 83 times.
 63551 if (circ.n_out_edges_of_type(vert, EdgeType::Classical) == 0) {
108 63468 bool z_followed_by_measures = true;
109
6/6
✓ Branch 1 taken 87443 times.
✓ Branch 2 taken 39511 times.
✓ Branch 3 taken 63486 times.
✓ Branch 4 taken 23957 times.
✓ Branch 5 taken 63486 times.
✓ Branch 6 taken 63468 times.
0/1
? Decision couldn't be analyzed.
 126954 for (port_t port = 0; port < kids.size() && z_followed_by_measures;
110 port++) {
111
3/4
✓ Branch 2 taken 63486 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 54 times.
✓ Branch 5 taken 63432 times.
2/2
✓ Decision 'true' taken 54 times.
✓ Decision 'false' taken 63432 times.
 63486 if (circ.get_OpType_from_Vertex(kids[port]) == OpType::Measure) {
112 54 z_followed_by_measures &=
113
1/2
✓ Branch 2 taken 54 times.
✗ Branch 3 not taken.
 54 circ.commutes_with_basis(vert, Pauli::Z, PortType::Source, port);
114 } else {
115 63432 z_followed_by_measures = false;
116 }
117 }
118
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 63464 times.
2/2
✓ Decision 'true' taken 4 times.
✓ Decision 'false' taken 63464 times.
 63468 if (z_followed_by_measures) {
119
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 remove_single_vertex(vert);
120 4 return true;
121 }
122 }
123
124 // check that both the vertex and its successor have each other and only each
125 // other
126
9/12
✓ Branch 1 taken 39490 times.
✓ Branch 2 taken 24057 times.
✓ Branch 5 taken 39490 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 13743 times.
✓ Branch 9 taken 25747 times.
✓ Branch 10 taken 39490 times.
✓ Branch 11 taken 24057 times.
✓ Branch 13 taken 13743 times.
✓ Branch 14 taken 49804 times.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
2/2
✓ Decision 'true' taken 13743 times.
✓ Decision 'false' taken 49804 times.
 63547 if ((kids.size() == 1) && (circ.get_predecessors(kids[0]).size() == 1)) {
127 // check that the ports match up between vertices
128 13743 Vertex b = kids[0];
129
1/2
✓ Branch 1 taken 13743 times.
✗ Branch 2 not taken.
 13743 EdgeVec ins = circ.get_in_edges(b);
130
2/2
✓ Branch 5 taken 14852 times.
✓ Branch 6 taken 13606 times.
2/2
✓ Decision 'true' taken 14852 times.
✓ Decision 'false' taken 13606 times.
 28458 for (const Edge &in : ins) {
131
4/6
✓ Branch 1 taken 14852 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 14852 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 137 times.
✓ Branch 7 taken 14715 times.
2/2
✓ Decision 'true' taken 13606 times.
✓ Decision 'false' taken 1246 times.
 14852 if (circ.get_source_port(in) != circ.get_target_port(in)) return false;
132 }
133
134 // check that the classical edges match up correctly
135
2/4
✓ Branch 1 taken 13606 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 13606 times.
1/2
✓ Decision 'true' taken 13606 times.
✗ Decision 'false' not taken.
 13606 if (circ.n_in_edges_of_type(vert, EdgeType::Boolean) != 0) return false;
136
137
1/2
✓ Branch 1 taken 13606 times.
✗ Branch 2 not taken.
 13606 const Op_ptr b_op = circ.get_Op_ptr_from_Vertex(b);
138
1/2
✓ Branch 2 taken 13606 times.
✗ Branch 3 not taken.
 13606 const OpDesc b_desc = b_op->get_desc();
139
140
3/4
✓ Branch 1 taken 13606 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 10715 times.
✓ Branch 4 taken 2891 times.
2/2
✓ Decision 'true' taken 10715 times.
✓ Decision 'false' taken 2891 times.
 13606 if (!b_desc.is_oneway()) {
141 // if A = B.dagger(), AB = I
142 // This method cannot detect matches between rotation gates.
143 // Rotation gates are covered by the rotation gate combiner, everything
144 // else in this.
145
4/6
✓ Branch 3 taken 10715 times.
✗ Branch 4 not taken.
✓ Branch 7 taken 10715 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 1463 times.
✓ Branch 11 taken 9252 times.
2/2
✓ Decision 'true' taken 1463 times.
✓ Decision 'false' taken 9252 times.
 10715 if (*b_op->dagger() == *op) {
146
1/2
✓ Branch 1 taken 1463 times.
✗ Branch 2 not taken.
 1463 bin.insert(vert);
147
1/2
✓ Branch 1 taken 1463 times.
✗ Branch 2 not taken.
 1463 bin.insert(b);
148
1/2
✓ Branch 1 taken 1463 times.
✗ Branch 2 not taken.
 1463 VertexVec last_verts = circ.get_predecessors(vert);
149
2/2
✓ Branch 4 taken 2532 times.
✓ Branch 5 taken 1463 times.
2/2
✓ Decision 'true' taken 2532 times.
✓ Decision 'false' taken 1463 times.
 3995 for (const Vertex &l : last_verts) {
150
2/4
✓ Branch 1 taken 2532 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 2532 times.
✗ Branch 6 not taken.
 2532 new_affected_verts.insert({im.at(l), l});
151 }
152
1/2
✓ Branch 2 taken 1463 times.
✗ Branch 3 not taken.
 1463 VertexList to_detach{vert, b};
153 // detached from circuit but not removed from graph
154
1/2
✓ Branch 1 taken 1463 times.
✗ Branch 2 not taken.
 1463 circ.remove_vertices(
155 to_detach, Circuit::GraphRewiring::Yes,
156 Circuit::VertexDeletion::No);
157 1463 return true;
158
3/4
✓ Branch 3 taken 9252 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 2106 times.
✓ Branch 6 taken 7146 times.
2/2
✓ Decision 'true' taken 2106 times.
✓ Decision 'false' taken 8609 times.
 10715 } else if (desc.is_rotation()) {
159 // combine two rotation gates together, then if the combined
160 // operation is the identity up to phase, remove from circuit
161
4/6
✓ Branch 1 taken 2106 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2106 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 160 times.
✓ Branch 7 taken 1946 times.
2/2
✓ Decision 'true' taken 160 times.
✓ Decision 'false' taken 1946 times.
 2106 if (b_desc.type() == desc.type()) {
162
2/4
✓ Branch 2 taken 160 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 160 times.
✗ Branch 7 not taken.
 160 Expr expr1 = op->get_params()[0];
163
2/4
✓ Branch 2 taken 160 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 160 times.
✗ Branch 7 not taken.
 160 Expr expr2 = b_op->get_params()[0];
164
1/2
✓ Branch 1 taken 160 times.
✗ Branch 2 not taken.
 160 VertexVec last_verts = circ.get_predecessors(vert);
165
2/2
✓ Branch 4 taken 160 times.
✓ Branch 5 taken 160 times.
2/2
✓ Decision 'true' taken 160 times.
✓ Decision 'false' taken 160 times.
 320 for (const Vertex &l : last_verts) {
166
2/4
✓ Branch 1 taken 160 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 160 times.
✗ Branch 6 not taken.
 160 new_affected_verts.insert({im.at(l), l});
167 }
168
1/2
✓ Branch 1 taken 160 times.
✗ Branch 2 not taken.
 160 circ.remove_vertex(
169 b, Circuit::GraphRewiring::Yes, Circuit::VertexDeletion::No);
170
1/2
✓ Branch 1 taken 160 times.
✗ Branch 2 not taken.
 160 bin.insert(b);
171
2/4
✓ Branch 1 taken 160 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 160 times.
✗ Branch 6 not taken.
 480 std::vector<Expr> params_new = {expr1 + expr2};
172
2/4
✓ Branch 2 taken 160 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 160 times.
✗ Branch 6 not taken.
 160 Op_ptr op_new = get_op_ptr(desc.type(), params_new, ins.size());
173
1/2
✓ Branch 2 taken 160 times.
✗ Branch 3 not taken.
 160 std::optional<double> a = op_new->is_identity();
174
2/2
✓ Branch 1 taken 53 times.
✓ Branch 2 taken 107 times.
2/2
✓ Decision 'true' taken 53 times.
✓ Decision 'false' taken 107 times.
 160 if (a) {
175
1/2
✓ Branch 1 taken 53 times.
✗ Branch 2 not taken.
 53 bin.insert(vert);
176
1/2
✓ Branch 1 taken 53 times.
✗ Branch 2 not taken.
 53 circ.remove_vertex(
177 vert, Circuit::GraphRewiring::Yes, Circuit::VertexDeletion::No);
178
3/6
✓ Branch 1 taken 53 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 53 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 53 times.
✗ Branch 8 not taken.
 53 circ.add_phase(a.value());
179 } else {
180
2/4
✓ Branch 1 taken 107 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 107 times.
✗ Branch 6 not taken.
 107 new_affected_verts.insert({im[vert], vert});
181
1/2
✓ Branch 1 taken 107 times.
✗ Branch 2 not taken.
 107 circ.dag[vert].op = op_new;
182 }
183 160 return true;
184 160 }
185 }
186 }
187
6/6
✓ Branch 1 taken 11983 times.
✓ Branch 2 taken 1623 times.
✓ Branch 4 taken 11983 times.
✓ Branch 5 taken 1623 times.
✓ Branch 7 taken 11983 times.
✓ Branch 8 taken 1760 times.
 16989 }
188 61787 return false;
189 77365 }
190
191 150 Transform commute_through_multis() {
192
1/2
✓ Branch 2 taken 150 times.
✗ Branch 3 not taken.
 150 return Transform(commute_singles_to_front);
193 }
194
195 // whether source and target commute
196 16182 static bool ends_commute(const Circuit &circ, const Edge &e) {
197
1/2
✓ Branch 1 taken 16182 times.
✗ Branch 2 not taken.
 16182 const std::pair<port_t, port_t> ports = circ.get_ports(e);
198
1/2
✓ Branch 1 taken 16182 times.
✗ Branch 2 not taken.
 16182 const Vertex source = circ.source(e);
199
1/2
✓ Branch 1 taken 16182 times.
✗ Branch 2 not taken.
 16182 const Vertex target = circ.target(e);
200
201 // We currently do not support commuting multi-qubit gates
202 // TODO: It would be useful to support commuting single-qubit gates with
203 // classical conditioning
204
7/10
✓ Branch 1 taken 16182 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 16182 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 16182 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 48 times.
✓ Branch 9 taken 16134 times.
✓ Branch 10 taken 48 times.
✓ Branch 11 taken 16134 times.
2/2
✓ Decision 'true' taken 48 times.
✓ Decision 'false' taken 16134 times.
 16182 if (circ.n_in_edges(source) > 1 && circ.n_in_edges(target) > 1) {
205 48 return false;
206 }
207
208
1/2
✓ Branch 1 taken 16134 times.
✗ Branch 2 not taken.
 16134 auto colour = circ.commuting_basis(target, PortType::Target, ports.second);
209 32268 return circ.commutes_with_basis(
210
1/2
✓ Branch 1 taken 16134 times.
✗ Branch 2 not taken.
 16134 source, colour, PortType::Source, ports.first);
211 }
212
213 // moves single qubit operations past multiqubit operations they commute with,
214 // towards front of circuit (hardcoded)
215 419 static bool commute_singles_to_front(Circuit &circ) {
216 419 bool success = false;
217 // follow each qubit path from output to input
218
3/4
✓ Branch 1 taken 419 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 1577 times.
✓ Branch 9 taken 419 times.
0/1
? Decision couldn't be analyzed.
 1996 for (const Qubit &q : circ.all_qubits()) {
219
1/2
✓ Branch 1 taken 1577 times.
✗ Branch 2 not taken.
 1577 Vertex prev_v = circ.get_out(q);
220
1/2
✓ Branch 1 taken 1577 times.
✗ Branch 2 not taken.
 1577 Edge current_e = circ.get_nth_in_edge(prev_v, 0);
221
1/2
✓ Branch 1 taken 1577 times.
✗ Branch 2 not taken.
 1577 Vertex current_v = circ.source(current_e);
222
4/6
✓ Branch 1 taken 44928 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 44928 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 43351 times.
✓ Branch 7 taken 1577 times.
0/1
? Decision couldn't be analyzed.
 44928 while (!is_initial_q_type(circ.get_OpType_from_Vertex(current_v))) {
223
1/2
✓ Branch 1 taken 43351 times.
✗ Branch 2 not taken.
 43351 const Op_ptr curr_op = circ.get_Op_ptr_from_Vertex(current_v);
224 // if current vertex is a multiqubit gate
225
3/4
✓ Branch 1 taken 43351 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 21481 times.
✓ Branch 4 taken 21870 times.
2/2
✓ Decision 'true' taken 41026 times.
✓ Decision 'false' taken 2325 times.
 43351 if (circ.n_in_edges_of_type(current_v, EdgeType::Quantum) > 1) {
226
5/6
✓ Branch 1 taken 24844 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 16182 times.
✓ Branch 4 taken 8662 times.
✓ Branch 5 taken 3363 times.
✓ Branch 6 taken 21481 times.
0/1
? Decision couldn't be analyzed.
 41026 while (circ.n_in_edges_of_type(prev_v, EdgeType::Quantum) == 1 &&
227
3/4
✓ Branch 1 taken 16182 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 3363 times.
✓ Branch 4 taken 12819 times.
 16182 ends_commute(circ, current_e)) {
228 // subsequent op on qubit path is a single qubit gate
229 // and commutes with current multi qubit gate
230 3363 success = true;
231 3363 EdgeVec rewire_edges;
232 3363 op_signature_t edge_types;
233
3/4
✓ Branch 1 taken 3363 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 3363 times.
✓ Branch 9 taken 3363 times.
0/1
? Decision couldn't be analyzed.
 6726 for (const Edge &e : circ.get_in_edges(prev_v)) {
234
1/2
✓ Branch 1 taken 3363 times.
✗ Branch 2 not taken.
 3363 EdgeType type = circ.get_edgetype(e);
235
1/2
✓ Branch 1 taken 3363 times.
✗ Branch 2 not taken.
 3363 Edge boundary_edge;
236 // Currently, only purely-quantum operations can be commuted
237 // through. This is guaranteed by `ends_commute`. It follows that
238 // any wire out of `prev_v` must be EdgeType::Quantum.
239 TKET_ASSERT(type == EdgeType::Quantum);
240
1/2
✓ Branch 1 taken 3363 times.
✗ Branch 2 not taken.
 3363 boundary_edge = circ.get_last_edge(current_v, current_e);
241
1/2
✓ Branch 1 taken 3363 times.
✗ Branch 2 not taken.
 3363 rewire_edges.push_back(boundary_edge);
242
1/2
✓ Branch 1 taken 3363 times.
✗ Branch 2 not taken.
 3363 edge_types.push_back(type);
243 3363 }
244
1/2
✓ Branch 1 taken 3363 times.
✗ Branch 2 not taken.
 3363 const port_t backup_port = circ.get_source_port(current_e);
245
1/2
✓ Branch 1 taken 3363 times.
✗ Branch 2 not taken.
 3363 circ.remove_vertex(
246 prev_v, Circuit::GraphRewiring::Yes, Circuit::VertexDeletion::No);
247
1/2
✓ Branch 1 taken 3363 times.
✗ Branch 2 not taken.
 3363 circ.rewire(prev_v, rewire_edges, edge_types);
248
1/2
✓ Branch 1 taken 3363 times.
✗ Branch 2 not taken.
 3363 current_e = circ.get_nth_out_edge(current_v, backup_port);
249
1/2
✓ Branch 1 taken 3363 times.
✗ Branch 2 not taken.
 3363 prev_v = circ.target(current_e);
250 3363 }
251 }
252 // move to next vertex (towards input)
253 43351 prev_v = current_v;
254
1/2
✓ Branch 1 taken 43351 times.
✗ Branch 2 not taken.
 43351 std::tie(current_v, current_e) = circ.get_prev_pair(current_v, current_e);
255 43351 }
256 419 }
257
258 419 return success;
259 }
260
261 // helper class subcircuits representing 2qb interactions
262 struct Interaction {
263
2/4
✓ Branch 3 taken 749 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 749 times.
✗ Branch 7 not taken.
 749 Interaction(const Qubit &_q0, const Qubit &_q1) : q0(_q0), q1(_q1) {}
264 Qubit q0; // Qubit numbers
265 Qubit q1;
266 Edge e0; // In edges starting interaction
267 Edge e1;
268 unsigned count; // Number of two qubit gates in interaction
269 VertexSet vertices; // Vertices in interaction subcircuit
270 };
271
272 150 static bool replace_two_qubit_interaction(
273 Circuit &circ, Interaction &i, std::map<Qubit, Edge> &current_edges,
274 VertexList &bin, OpType target, double cx_fidelity, bool allow_swaps) {
275
1/2
✓ Branch 2 taken 150 times.
✗ Branch 3 not taken.
 150 EdgeVec in_edges = {i.e0, i.e1};
276
3/6
✓ Branch 1 taken 150 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 150 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 150 times.
✗ Branch 9 not taken.
 150 EdgeVec out_edges = {current_edges[i.q0], current_edges[i.q1]};
277
2/4
✓ Branch 1 taken 150 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 150 times.
✗ Branch 5 not taken.
 150 Edge next0, next1;
278
1/2
✓ Branch 1 taken 150 times.
✗ Branch 2 not taken.
 150 bool q0_is_out = is_final_q_type(
279
3/6
✓ Branch 1 taken 150 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 150 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 150 times.
✗ Branch 8 not taken.
 150 circ.get_OpType_from_Vertex(circ.target(current_edges[i.q0])));
280
1/2
✓ Branch 1 taken 150 times.
✗ Branch 2 not taken.
 150 bool q1_is_out = is_final_q_type(
281
3/6
✓ Branch 1 taken 150 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 150 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 150 times.
✗ Branch 8 not taken.
 150 circ.get_OpType_from_Vertex(circ.target(current_edges[i.q1])));
282
2/2
✓ Branch 0 taken 106 times.
✓ Branch 1 taken 44 times.
2/2
✓ Decision 'true' taken 106 times.
✓ Decision 'false' taken 44 times.
 150 if (!q0_is_out) {
283 106 next0 = circ.get_next_edge(
284
4/8
✓ Branch 1 taken 106 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 106 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 106 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 106 times.
✗ Branch 11 not taken.
 106 circ.target(current_edges[i.q0]), current_edges[i.q0]);
285 }
286
2/2
✓ Branch 0 taken 94 times.
✓ Branch 1 taken 56 times.
2/2
✓ Decision 'true' taken 94 times.
✓ Decision 'false' taken 56 times.
 150 if (!q1_is_out) {
287 94 next1 = circ.get_next_edge(
288
4/8
✓ Branch 1 taken 94 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 94 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 94 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 94 times.
✗ Branch 11 not taken.
 94 circ.target(current_edges[i.q1]), current_edges[i.q1]);
289 }
290 // Circuit to (potentially) substitute
291
1/2
✓ Branch 1 taken 150 times.
✗ Branch 2 not taken.
 150 Subcircuit sub = {in_edges, out_edges, i.vertices};
292
1/2
✓ Branch 1 taken 150 times.
✗ Branch 2 not taken.
 150 Circuit subc = circ.subcircuit(sub);
293
294 // Try to simplify using KAK
295
1/2
✓ Branch 1 taken 150 times.
✗ Branch 2 not taken.
 150 Circuit replacement = subc;
296
2/4
✓ Branch 1 taken 150 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 150 times.
✗ Branch 5 not taken.
 150 decompose_multi_qubits_TK2().apply(replacement);
297
1/2
✓ Branch 1 taken 150 times.
✗ Branch 2 not taken.
 150 Eigen::Matrix4cd mat = get_matrix_from_2qb_circ(replacement);
298
2/4
✓ Branch 1 taken 150 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 150 times.
✗ Branch 5 not taken.
 150 replacement = two_qubit_canonical(mat);
299 150 TwoQbFidelities fid;
300 150 fid.CX_fidelity = cx_fidelity;
301
2/2
✓ Branch 0 taken 111 times.
✓ Branch 1 taken 39 times.
2/2
✓ Decision 'true' taken 111 times.
✓ Decision 'false' taken 39 times.
 150 if (target != OpType::TK2) {
302
2/4
✓ Branch 1 taken 111 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 111 times.
✗ Branch 5 not taken.
 111 decompose_TK2(fid, allow_swaps).apply(replacement);
303 }
304
305 // Whether to substitute old circuit with new
306 150 bool substitute = false;
307
3/4
✓ Branch 1 taken 150 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 1176 times.
✓ Branch 9 taken 126 times.
0/1
? Decision couldn't be analyzed.
 1302 for (Vertex v : subc.vertices_in_order()) {
308
1/2
✓ Branch 1 taken 1176 times.
✗ Branch 2 not taken.
 1176 unsigned n_ins = subc.n_in_edges_of_type(v, EdgeType::Quantum);
309
7/8
✓ Branch 0 taken 346 times.
✓ Branch 1 taken 830 times.
✓ Branch 3 taken 346 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 24 times.
✓ Branch 6 taken 322 times.
✓ Branch 7 taken 24 times.
✓ Branch 8 taken 1152 times.
2/2
✓ Decision 'true' taken 24 times.
✓ Decision 'false' taken 1152 times.
 1176 if (n_ins == 2 && subc.get_OpType_from_Vertex(v) != target) {
310 // Old circuit has non-target gates => we need to substitute
311 24 substitute = true;
312 24 break;
313 }
314 150 }
315
2/2
✓ Branch 0 taken 126 times.
✓ Branch 1 taken 24 times.
2/2
✓ Decision 'true' taken 126 times.
✓ Decision 'false' taken 24 times.
 150 if (!substitute) {
316
2/2
✓ Branch 0 taken 103 times.
✓ Branch 1 taken 23 times.
2/2
✓ Decision 'true' taken 103 times.
✓ Decision 'false' taken 23 times.
 126 if (target == OpType::CX) {
317
1/2
✓ Branch 1 taken 103 times.
✗ Branch 2 not taken.
 103 unsigned nb_2qb_old = subc.count_gates(target);
318
1/2
✓ Branch 1 taken 103 times.
✗ Branch 2 not taken.
 103 unsigned nb_2qb_new = replacement.count_gates(target);
319 103 substitute |= nb_2qb_new < nb_2qb_old;
320
1/2
✓ Branch 0 taken 23 times.
✗ Branch 1 not taken.
1/2
✓ Decision 'true' taken 23 times.
✗ Decision 'false' not taken.
 23 } else if (target == OpType::TK2) {
321 23 unsigned cnt_2qb = 0;
322
3/4
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
✓ Branch 7 taken 212 times.
✓ Branch 8 taken 23 times.
0/1
? Decision couldn't be analyzed.
 235 for (Vertex v : subc.vertices_in_order()) {
323
1/2
✓ Branch 1 taken 212 times.
✗ Branch 2 not taken.
 212 unsigned n_ins = subc.n_in_edges_of_type(v, EdgeType::Quantum);
324 212 cnt_2qb += n_ins == 2;
325 23 }
326 23 substitute |= cnt_2qb >= 2;
327 }
328 }
329
330
2/2
✓ Branch 0 taken 110 times.
✓ Branch 1 taken 40 times.
2/2
✓ Decision 'true' taken 110 times.
✓ Decision 'false' taken 40 times.
 150 if (substitute) {
331 // Substitute interaction with new circuit
332
1/2
✓ Branch 5 taken 110 times.
✗ Branch 6 not taken.
 110 bin.insert(bin.end(), sub.verts.begin(), sub.verts.end());
333
1/2
✓ Branch 1 taken 110 times.
✗ Branch 2 not taken.
 110 circ.substitute(replacement, sub, Circuit::VertexDeletion::No);
334
2/2
✓ Branch 0 taken 70 times.
✓ Branch 1 taken 40 times.
2/2
✓ Decision 'true' taken 70 times.
✓ Decision 'false' taken 40 times.
 110 if (!q0_is_out) {
335
3/6
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 70 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 70 times.
✗ Branch 8 not taken.
 70 current_edges[i.q0] = circ.get_last_edge(circ.source(next0), next0);
336 }
337
2/2
✓ Branch 0 taken 72 times.
✓ Branch 1 taken 38 times.
2/2
✓ Decision 'true' taken 72 times.
✓ Decision 'false' taken 38 times.
 110 if (!q1_is_out) {
338
3/6
✓ Branch 1 taken 72 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 72 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 72 times.
✗ Branch 8 not taken.
 72 current_edges[i.q1] = circ.get_last_edge(circ.source(next1), next1);
339 }
340 110 return true;
341 } else {
342 // Leave circuit untouched
343 40 return false;
344 }
345 150 }
346
347 12 Transform commute_and_combine_HQS2() {
348 20 return Transform([](Circuit &circ) {
349 20 bool success = false;
350 20 VertexList bin;
351
7/8
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 578 times.
✓ Branch 6 taken 20 times.
✓ Branch 8 taken 578 times.
✓ Branch 9 taken 20 times.
✓ Branch 11 taken 20 times.
✓ Branch 12 taken 20 times.
 618 BGL_FORALL_VERTICES(v, circ.dag, DAG) {
352
1/2
✓ Branch 1 taken 578 times.
✗ Branch 2 not taken.
 578 EdgeVec outs = circ.get_all_out_edges(v);
353
6/8
✓ Branch 1 taken 578 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 78 times.
✓ Branch 4 taken 500 times.
✓ Branch 6 taken 78 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 78 times.
✓ Branch 9 taken 500 times.
2/2
✓ Decision 'true' taken 78 times.
✓ Decision 'false' taken 500 times.
 578 if (circ.get_OpType_from_Vertex(v) == OpType::ZZMax && outs.size() == 2) {
354 78 Vertex next0 = boost::target(outs[0], circ.dag);
355 78 Vertex next1 = boost::target(outs[1], circ.dag);
356
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 78 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 78 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 78 times.
 78 if (next0 == next1 &&
357 ✗ circ.get_OpType_from_Vertex(next0) == OpType::ZZMax) {
358 ✗ success = true;
359 ✗ EdgeVec h_in = circ.get_in_edges(v);
360 ✗ EdgeVec h_out = circ.get_all_out_edges(next0);
361
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (circ.get_target_port(outs[0]) != 0) {
362 ✗ h_out = {h_out[1], h_out[0]};
363 }
364 ✗ bin.push_back(v);
365 ✗ bin.push_back(next0);
366 ✗ Subcircuit sub = {h_in, h_out};
367 ✗ circ.substitute(
368 CircPool::two_Rz1(), sub, Circuit::VertexDeletion::No);
369 ✗ circ.add_phase(0.5);
370 ✗ continue;
371 }
372
3/4
✓ Branch 1 taken 78 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 19 times.
✓ Branch 4 taken 59 times.
2/2
✓ Decision 'true' taken 19 times.
✓ Decision 'false' taken 59 times.
 78 if (circ.get_OpType_from_Vertex(next0) == OpType::Rz) {
373 19 success = true;
374
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 circ.remove_vertex(
375 next0, Circuit::GraphRewiring::Yes, Circuit::VertexDeletion::No);
376
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 Edge in_0 = circ.get_nth_in_edge(v, 0);
377
3/6
✓ Branch 2 taken 19 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 19 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 19 times.
✗ Branch 10 not taken.
 19 circ.rewire(next0, {in_0}, {EdgeType::Quantum});
378 }
379
2/4
✓ Branch 1 taken 78 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 78 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 78 times.
 78 if (circ.get_OpType_from_Vertex(next1) == OpType::Rz) {
380 ✗ success = true;
381 ✗ circ.remove_vertex(
382 next1, Circuit::GraphRewiring::Yes, Circuit::VertexDeletion::No);
383 ✗ Edge in_1 = circ.get_nth_in_edge(v, 1);
384 ✗ circ.rewire(next1, {in_1}, {EdgeType::Quantum});
385 }
386 }
387
1/2
✓ Branch 1 taken 578 times.
✗ Branch 2 not taken.
 578 }
388
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 circ.remove_vertices(
389 bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
390 20 return success;
391
1/2
✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.
 32 });
392 }
393
394 31 Transform two_qubit_squash(bool allow_swaps) {
395 31 return two_qubit_squash(OpType::CX, 1., allow_swaps);
396 }
397
398 82 Transform two_qubit_squash(
399 OpType target_2qb_gate, double cx_fidelity, bool allow_swaps) {
400
1/2
✓ Branch 2 taken 82 times.
✗ Branch 3 not taken.
 82 const std::set<OpType> accepted_ots{OpType::CX, OpType::TK2};
401
2/4
✓ Branch 1 taken 82 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 82 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 82 times.
 82 if (!accepted_ots.contains(target_2qb_gate)) {
402 ✗ throw BadOpType(
403 "KAKDecomposition currently supports CX and TK2. "
404 "Cannot decompose to",
405 ✗ target_2qb_gate);
406 }
407
2/4
✓ Branch 0 taken 82 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 82 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 82 times.
 82 if (cx_fidelity < 0 || cx_fidelity > 1) {
408 ✗ throw std::invalid_argument("The CX fidelity must be between 0 and 1.");
409 }
410
411 235 return Transform([target_2qb_gate, cx_fidelity, allow_swaps](Circuit &circ) {
412 85 bool success = false;
413 85 VertexList bin;
414 // Get map from vertex/port to qubit number
415 85 std::map<VertPort, Qubit> v_to_qb;
416 85 std::map<Qubit, Edge> current_edge_on_qb;
417 85 std::vector<Interaction> i_vec;
418 85 std::map<Qubit, int> current_interaction;
419
3/4
✓ Branch 1 taken 85 times.
✗ Branch 2 not taken.
✓ Branch 7 taken 254 times.
✓ Branch 8 taken 85 times.
0/1
? Decision couldn't be analyzed.
 339 for (const Qubit &qb : circ.all_qubits()) {
420
3/4
✓ Branch 1 taken 254 times.
✗ Branch 2 not taken.
✓ Branch 7 taken 3780 times.
✓ Branch 8 taken 254 times.
0/1
? Decision couldn't be analyzed.
 4034 for (const VertPort &vp : circ.unit_path(qb)) {
421
1/2
✓ Branch 2 taken 3780 times.
✗ Branch 3 not taken.
 3780 v_to_qb.insert({vp, qb});
422 254 }
423
1/2
✓ Branch 1 taken 254 times.
✗ Branch 2 not taken.
 254 Vertex input = circ.get_in(qb);
424
1/2
✓ Branch 1 taken 254 times.
✗ Branch 2 not taken.
 254 Edge e = circ.get_nth_out_edge(input, 0);
425
1/2
✓ Branch 1 taken 254 times.
✗ Branch 2 not taken.
 254 current_edge_on_qb[qb] = e;
426
1/2
✓ Branch 1 taken 254 times.
✗ Branch 2 not taken.
 254 current_interaction[qb] = -1;
427 85 }
428
1/2
✓ Branch 1 taken 85 times.
✗ Branch 2 not taken.
 85 SliceVec slices = circ.get_slices();
429
2/4
✓ Branch 1 taken 85 times.
✗ Branch 2 not taken.
✓ Branch 6 taken 85 times.
✗ Branch 7 not taken.
 85 slices.insert(slices.begin(), circ.q_inputs());
430
2/4
✓ Branch 1 taken 85 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 85 times.
✗ Branch 5 not taken.
 85 slices.push_back(circ.q_outputs());
431
2/2
✓ Branch 4 taken 1717 times.
✓ Branch 5 taken 85 times.
2/2
✓ Decision 'true' taken 1717 times.
✓ Decision 'false' taken 85 times.
 1802 for (SliceVec::iterator s = slices.begin(); s != slices.end(); ++s) {
432
2/2
✓ Branch 6 taken 2793 times.
✓ Branch 7 taken 1717 times.
2/2
✓ Decision 'true' taken 2793 times.
✓ Decision 'false' taken 1717 times.
 4510 for (Slice::iterator v = s->begin(); v != s->end(); ++v) {
433
1/2
✓ Branch 2 taken 2793 times.
✗ Branch 3 not taken.
 2793 const Op_ptr o = circ.get_Op_ptr_from_Vertex(*v);
434 2793 OpType type = o->get_type();
435
1/2
✓ Branch 2 taken 2793 times.
✗ Branch 3 not taken.
 2793 unsigned n_ins = circ.n_in_edges_of_type(*v, EdgeType::Quantum);
436 // Ignore classical ops
437
3/4
✓ Branch 1 taken 2793 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 5 times.
✓ Branch 4 taken 2788 times.
2/2
✓ Decision 'true' taken 5 times.
✓ Decision 'false' taken 2788 times.
 2793 if (is_classical_type(type)) {
438 5 continue;
439 2788 } else if (
440
4/6
✓ Branch 1 taken 2774 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 2520 times.
✓ Branch 4 taken 254 times.
✓ Branch 5 taken 2520 times.
✗ Branch 6 not taken.
 2774 is_projective_type(type) || is_final_q_type(type) ||
441
4/4
✓ Branch 0 taken 2513 times.
✓ Branch 1 taken 7 times.
✓ Branch 2 taken 2509 times.
✓ Branch 3 taken 4 times.
 2520 type == OpType::Barrier || type == OpType::Conditional ||
442
10/14
✓ Branch 1 taken 2788 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 2774 times.
✓ Branch 4 taken 14 times.
✓ Branch 7 taken 2509 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 11 times.
✓ Branch 11 taken 2498 times.
✓ Branch 12 taken 2509 times.
✓ Branch 13 taken 279 times.
✓ Branch 15 taken 290 times.
✓ Branch 16 taken 2498 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
 5562 n_ins > 2 || !o->free_symbols().empty()) {
443 // Measures, resets, outputs, barriers, symbolic gates, conditionals
444 // and many-qubit gates close interactions
445
1/2
✓ Branch 2 taken 290 times.
✗ Branch 3 not taken.
 290 EdgeVec q_edges = circ.get_in_edges_of_type(*v, EdgeType::Quantum);
446 290 std::vector<port_t> q_ports;
447
2/2
✓ Branch 4 taken 301 times.
✓ Branch 5 taken 290 times.
2/2
✓ Decision 'true' taken 301 times.
✓ Decision 'false' taken 290 times.
 591 for (const Edge &e : q_edges) {
448
2/4
✓ Branch 1 taken 301 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 301 times.
✗ Branch 5 not taken.
 301 q_ports.push_back(circ.get_target_port(e));
449 }
450
2/2
✓ Branch 5 taken 301 times.
✓ Branch 6 taken 290 times.
2/2
✓ Decision 'true' taken 301 times.
✓ Decision 'false' taken 290 times.
 591 for (const port_t &port : q_ports) {
451
1/2
✓ Branch 3 taken 301 times.
✗ Branch 4 not taken.
 301 Qubit q = v_to_qb.at({*v, port});
452
1/2
✓ Branch 1 taken 301 times.
✗ Branch 2 not taken.
 301 int i = current_interaction[q];
453
2/2
✓ Branch 0 taken 121 times.
✓ Branch 1 taken 180 times.
2/2
✓ Decision 'true' taken 121 times.
✓ Decision 'false' taken 180 times.
 301 if (i != -1) {
454
2/2
✓ Branch 1 taken 59 times.
✓ Branch 2 taken 62 times.
2/2
✓ Decision 'true' taken 59 times.
✓ Decision 'false' taken 62 times.
 121 if (i_vec[i].count >= 2) {
455 // Replace subcircuit
456
1/2
✓ Branch 1 taken 59 times.
✗ Branch 2 not taken.
 59 success |= replace_two_qubit_interaction(
457 59 circ, i_vec[i], current_edge_on_qb, bin, target_2qb_gate,
458 cx_fidelity, allow_swaps);
459 }
460
1/2
✓ Branch 2 taken 121 times.
✗ Branch 3 not taken.
 121 current_interaction[i_vec[i].q0] = -1;
461
1/2
✓ Branch 2 taken 121 times.
✗ Branch 3 not taken.
 121 current_interaction[i_vec[i].q1] = -1;
462 }
463
3/4
✓ Branch 1 taken 301 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 47 times.
✓ Branch 4 taken 254 times.
2/2
✓ Decision 'true' taken 47 times.
✓ Decision 'false' taken 254 times.
 301 if (!is_final_q_type(type)) {
464
1/2
✓ Branch 1 taken 47 times.
✗ Branch 2 not taken.
 47 current_edge_on_qb[q] =
465
2/4
✓ Branch 1 taken 47 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 47 times.
✗ Branch 6 not taken.
 47 circ.get_next_edge(*v, current_edge_on_qb[q]);
466 }
467 301 }
468
3/4
✓ Branch 4 taken 2498 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 981 times.
✓ Branch 7 taken 1517 times.
2/2
✓ Decision 'true' taken 981 times.
✓ Decision 'false' taken 1807 times.
 2788 } else if (circ.n_in_edges_of_type(*v, EdgeType::Quantum) == 2) {
469 // Check for 2qb gate
470
1/2
✓ Branch 3 taken 981 times.
✗ Branch 4 not taken.
 981 Qubit q0 = v_to_qb.at({*v, 0});
471
1/2
✓ Branch 3 taken 981 times.
✗ Branch 4 not taken.
 981 Qubit q1 = v_to_qb.at({*v, 1});
472
1/2
✓ Branch 1 taken 981 times.
✗ Branch 2 not taken.
 981 int i0 = current_interaction[q0];
473
1/2
✓ Branch 1 taken 981 times.
✗ Branch 2 not taken.
 981 int i1 = current_interaction[q1];
474 // If they are already interacting, extend it
475
4/4
✓ Branch 0 taken 642 times.
✓ Branch 1 taken 339 times.
✓ Branch 2 taken 232 times.
✓ Branch 3 taken 410 times.
2/2
✓ Decision 'true' taken 232 times.
✓ Decision 'false' taken 749 times.
 981 if (i0 != -1 && i0 == i1) {
476 232 i_vec[i0].count++;
477
1/2
✓ Branch 3 taken 232 times.
✗ Branch 4 not taken.
 232 i_vec[i0].vertices.insert(*v);
478
1/2
✓ Branch 1 taken 232 times.
✗ Branch 2 not taken.
 232 current_edge_on_qb[q0] =
479
2/4
✓ Branch 1 taken 232 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 232 times.
✗ Branch 6 not taken.
 232 circ.get_next_edge(*v, current_edge_on_qb[q0]);
480
1/2
✓ Branch 1 taken 232 times.
✗ Branch 2 not taken.
 232 current_edge_on_qb[q1] =
481
2/4
✓ Branch 1 taken 232 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 232 times.
✗ Branch 6 not taken.
 232 circ.get_next_edge(*v, current_edge_on_qb[q1]);
482 } else {
483 // End any other interactions on q0
484
2/2
✓ Branch 0 taken 410 times.
✓ Branch 1 taken 339 times.
2/2
✓ Decision 'true' taken 410 times.
✓ Decision 'false' taken 339 times.
 749 if (i0 != -1) {
485
2/2
✓ Branch 1 taken 54 times.
✓ Branch 2 taken 356 times.
2/2
✓ Decision 'true' taken 54 times.
✓ Decision 'false' taken 356 times.
 410 if (i_vec[i0].count >= 2) {
486 // Replace subcircuit
487
1/2
✓ Branch 1 taken 54 times.
✗ Branch 2 not taken.
 54 success |= replace_two_qubit_interaction(
488 54 circ, i_vec[i0], current_edge_on_qb, bin, target_2qb_gate,
489 cx_fidelity, allow_swaps);
490 }
491
1/2
✓ Branch 2 taken 410 times.
✗ Branch 3 not taken.
 410 current_interaction[i_vec[i0].q0] = -1;
492
1/2
✓ Branch 2 taken 410 times.
✗ Branch 3 not taken.
 410 current_interaction[i_vec[i0].q1] = -1;
493 }
494 // End any other interactions on q1
495
2/2
✓ Branch 0 taken 218 times.
✓ Branch 1 taken 531 times.
2/2
✓ Decision 'true' taken 218 times.
✓ Decision 'false' taken 531 times.
 749 if (i1 != -1) {
496
2/2
✓ Branch 1 taken 37 times.
✓ Branch 2 taken 181 times.
2/2
✓ Decision 'true' taken 37 times.
✓ Decision 'false' taken 181 times.
 218 if (i_vec[i1].count >= 2) {
497 // Replace subcircuit
498
499
1/2
✓ Branch 1 taken 37 times.
✗ Branch 2 not taken.
 37 success |= replace_two_qubit_interaction(
500 37 circ, i_vec[i1], current_edge_on_qb, bin, target_2qb_gate,
501 cx_fidelity, allow_swaps);
502 }
503
1/2
✓ Branch 2 taken 218 times.
✗ Branch 3 not taken.
 218 current_interaction[i_vec[i1].q0] = -1;
504
1/2
✓ Branch 2 taken 218 times.
✗ Branch 3 not taken.
 218 current_interaction[i_vec[i1].q1] = -1;
505 }
506 // Add new interaction
507
1/2
✓ Branch 1 taken 749 times.
✗ Branch 2 not taken.
 749 Interaction new_i(q0, q1);
508
1/2
✓ Branch 1 taken 749 times.
✗ Branch 2 not taken.
 749 new_i.e0 = current_edge_on_qb[q0];
509
1/2
✓ Branch 1 taken 749 times.
✗ Branch 2 not taken.
 749 new_i.e1 = current_edge_on_qb[q1];
510 749 new_i.count = 1;
511
1/2
✓ Branch 2 taken 749 times.
✗ Branch 3 not taken.
 749 new_i.vertices = {*v};
512
1/2
✓ Branch 2 taken 749 times.
✗ Branch 3 not taken.
 749 current_interaction[q0] = i_vec.size();
513
1/2
✓ Branch 2 taken 749 times.
✗ Branch 3 not taken.
 749 current_interaction[q1] = i_vec.size();
514
1/2
✓ Branch 1 taken 749 times.
✗ Branch 2 not taken.
 749 i_vec.push_back(new_i);
515
1/2
✓ Branch 1 taken 749 times.
✗ Branch 2 not taken.
 749 current_edge_on_qb[q0] =
516
2/4
✓ Branch 1 taken 749 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 749 times.
✗ Branch 6 not taken.
 749 circ.get_next_edge(*v, current_edge_on_qb[q0]);
517
1/2
✓ Branch 1 taken 749 times.
✗ Branch 2 not taken.
 749 current_edge_on_qb[q1] =
518
2/4
✓ Branch 1 taken 749 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 749 times.
✗ Branch 6 not taken.
 749 circ.get_next_edge(*v, current_edge_on_qb[q1]);
519 749 }
520 981 } else {
521 // We don't care about single-qubit vertices, so just update edges
522 // and add vertices if interactions exist
523
3/4
✓ Branch 2 taken 2780 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1263 times.
✓ Branch 5 taken 1517 times.
0/1
? Decision couldn't be analyzed.
 2780 for (port_t i = 0; i < circ.n_in_edges(*v); i++) {
524
1/2
✓ Branch 3 taken 1263 times.
✗ Branch 4 not taken.
 1263 Qubit q = v_to_qb.at({*v, i});
525
1/2
✓ Branch 1 taken 1263 times.
✗ Branch 2 not taken.
 1263 current_edge_on_qb[q] =
526
2/4
✓ Branch 1 taken 1263 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 1263 times.
✗ Branch 6 not taken.
 1263 circ.get_next_edge(*v, current_edge_on_qb[q]);
527
1/2
✓ Branch 1 taken 1263 times.
✗ Branch 2 not taken.
 1263 int inter = current_interaction[q];
528
2/2
✓ Branch 0 taken 1054 times.
✓ Branch 1 taken 209 times.
2/2
✓ Decision 'true' taken 1054 times.
✓ Decision 'false' taken 209 times.
 1263 if (inter != -1) {
529
1/2
✓ Branch 3 taken 1054 times.
✗ Branch 4 not taken.
 1054 i_vec[inter].vertices.insert(*v);
530 }
531 1263 }
532 }
533
2/2
✓ Branch 1 taken 2788 times.
✓ Branch 2 taken 5 times.
 2793 }
534 }
535
1/2
✓ Branch 1 taken 85 times.
✗ Branch 2 not taken.
 85 circ.remove_vertices(
536 bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
537
538
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 25 times.
2/2
✓ Decision 'true' taken 60 times.
✓ Decision 'false' taken 25 times.
 85 if (success) {
539
2/4
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 60 times.
✗ Branch 5 not taken.
 60 squash_1qb_to_tk1().apply(circ);
540 }
541 85 return success;
542
2/4
✓ Branch 1 taken 82 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 82 times.
✗ Branch 5 not taken.
 249 });
543 82 }
544
545 // Given a 'SWAP_chain', finds edge in chain (or qubit wire) with best fidelity
546 // and rewires the associated single qubit vertex in to it
547 ✗ static bool find_edge_rewire_vertex(
548 Circuit &circ,
549 std::pair<std::vector<std::pair<Edge, double>>, Vertex> &entry) {
550 ✗ std::vector<std::pair<Edge, double>> candidates = entry.first;
551 ✗ std::pair<Edge, double> best_pair = candidates[0];
552 ✗ bool do_rewire = false; // prevents rewiring if current edge is best edge
553 // (causes many issues...)
554
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ for (unsigned i = 1; i < candidates.size(); i++) { // find best edge
555
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (candidates[i].second > best_pair.second) {
556 ✗ best_pair = candidates[i];
557 ✗ do_rewire = true;
558 }
559 }
560
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (do_rewire) {
561 // rewire in to best edge
562 ✗ circ.remove_vertex(
563 ✗ entry.second, Circuit::GraphRewiring::Yes, Circuit::VertexDeletion::No);
564 ✗ circ.rewire(entry.second, {best_pair.first}, {EdgeType::Quantum});
565 }
566 ✗ return do_rewire;
567 }
568
569 // Given a SWAP vertex, which has some predecessor SWAP vertex, find the
570 // 'SWAP_chain' this predecessor SWAP vertex is in and add to it
571 ✗ static void extend_SWAP_chain(
572 std::list<std::pair<std::vector<std::pair<Edge, double>>, Vertex>>
573 &swap_chains,
574 Edge entry_edge, Node entry_node, const Edge &match, const Circuit &circ,
575 const DeviceCharacterisation &characterisation) {
576
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ for (auto it = swap_chains.begin(); it != swap_chains.end(); ++it) {
577
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if ((*it).first.back().first == match) {
578 // extend chain, adding a new pair of edge and double to the end
579 ✗ (*it).first.push_back(
580 {entry_edge,
581 ✗ 1.0 - characterisation.get_error(
582 ✗ entry_node, circ.get_OpType_from_Vertex((*it).second))});
583 ✗ return;
584 }
585 }
586 }
587
588 // Finds sequences of adjacent SWAP gates, with a predecessor Single Qubit
589 // Vertex. The error rate of the required Single Qubit Vertex is stored for each
590 // of the PhysicalQubits the LogicalQubit passes through Once 'SWAP_chains' are
591 // found throughout the whole circuit, predecessor Single Qubit Vertices are
592 // rewired into the edge with best error rate
593 ✗ static bool find_rewire_sq(
594 Circuit &circ, const DeviceCharacterisation &characterisation) {
595 std::list<std::pair<std::vector<std::pair<Edge, double>>, Vertex>>
596 ✗ swap_chains;
597
0/1
? Decision couldn't be analyzed.
 ✗ for (auto it = circ.begin(); it != circ.end(); ++it) {
598
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (it->get_op_ptr()->get_type() == OpType::SWAP) {
599 // find SWAP, if either predecessor is a single qubit unitary
600 // find resulting swap chain...
601 ✗ Vertex swap_vert = it.get_vertex();
602 ✗ unit_vector_t qubits = it->get_args();
603 ✗ node_vector_t nodes = {qubits.begin(), qubits.end()};
604 ✗ VertexVec pred_verts = circ.get_predecessors(swap_vert);
605 ✗ EdgeVec pred_edges = circ.get_in_edges(swap_vert);
606 ✗ EdgeVec post_edges = circ.get_all_out_edges(swap_vert);
607
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ for (unsigned i = 0; i < pred_verts.size(); i++) {
608 ✗ OpType optype = circ.get_OpType_from_Vertex(
609 ✗ pred_verts[i]); // OPT IS PREDECESSOR OPTYPE
610
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (circ.detect_singleq_unitary_op(pred_verts[i])) {
611 // wire has single qubit unitary->add a new swap chain
612 std::vector<std::pair<Edge, double>> swap_chain = {
613 ✗ {pred_edges[i],
614 ✗ 1.0 - characterisation.get_error(nodes[i], optype)},
615 ✗ {post_edges[1 - i],
616 ✗ 1.0 - characterisation.get_error(nodes[1 - i], optype)}};
617 ✗ swap_chains.push_back(std::make_pair(swap_chain, pred_verts[i]));
618
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ } else if (optype == OpType::SWAP) { // wire has swap->assume this swap
619 // already in chain, find chain
620 ✗ Edge pre_edge = pred_edges[i];
621 ✗ extend_SWAP_chain(
622 ✗ swap_chains, post_edges[1 - i], nodes[1 - i], pre_edge, circ,
623 characterisation);
624 }
625 }
626 }
627 }
628 // having produced swap chains, now find best qubit for gate to act on and
629 // implement
630 ✗ bool success = false;
631
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ while (!swap_chains.empty()) {
632
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (find_edge_rewire_vertex(circ, (*swap_chains.begin())) == true) {
633 ✗ success = true;
634 }
635 ✗ swap_chains.erase(swap_chains.begin());
636 }
637 ✗ return success;
638 }
639
640 ✗ static Transform commute_SQ_gates_through_SWAPS_helper(
641 const DeviceCharacterisation &characterisation) {
642 ✗ return Transform([characterisation](Circuit &circ) {
643 ✗ bool success = false;
644
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ while (find_rewire_sq(circ, characterisation)) {
645 ✗ success = true;
646 }
647 ✗ return success;
648 ✗ });
649 }
650
651 ✗ Transform commute_SQ_gates_through_SWAPS(const avg_node_errors_t &node_errors) {
652 return commute_SQ_gates_through_SWAPS_helper(
653 ✗ DeviceCharacterisation(node_errors));
654 }
655 ✗ Transform commute_SQ_gates_through_SWAPS(const op_node_errors_t &node_errors) {
656 return commute_SQ_gates_through_SWAPS_helper(
657 ✗ DeviceCharacterisation(node_errors));
658 }
659
660 62 Transform absorb_Rz_NPhasedX() {
661 62 return Transform([](Circuit &circ) {
662 62 bool success = false;
663 62 VertexSet all_bins;
664
665 // Start by squashing Rz gates
666
2/4
✓ Branch 1 taken 62 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 62 times.
✗ Branch 5 not taken.
 62 success |= squash_1qb_to_pqp(OpType::Rz, OpType::Rx).apply(circ);
667
668 // Loop through all NPhasedX gates
669
7/8
✓ Branch 1 taken 62 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 1332 times.
✓ Branch 6 taken 62 times.
✓ Branch 8 taken 1332 times.
✓ Branch 9 taken 62 times.
✓ Branch 11 taken 62 times.
✓ Branch 12 taken 62 times.
 1456 BGL_FORALL_VERTICES(v, circ.dag, DAG) {
670
1/2
✓ Branch 1 taken 1332 times.
✗ Branch 2 not taken.
 1332 Op_ptr op = circ.get_Op_ptr_from_Vertex(v);
671
2/2
✓ Branch 2 taken 167 times.
✓ Branch 3 taken 1165 times.
2/2
✓ Decision 'true' taken 167 times.
✓ Decision 'false' taken 1165 times.
 1332 if (op->get_type() == OpType::NPhasedX) {
672 // gather surrounding Rz gates
673
1/2
✓ Branch 2 taken 167 times.
✗ Branch 3 not taken.
 167 unsigned arity = op->n_qubits();
674
1/2
✓ Branch 2 taken 167 times.
✗ Branch 3 not taken.
 167 std::vector<Expr> in_rz(arity);
675
1/2
✓ Branch 2 taken 167 times.
✗ Branch 3 not taken.
 167 std::vector<Expr> out_rz(arity);
676
1/2
✓ Branch 1 taken 167 times.
✗ Branch 2 not taken.
 167 EdgeVec in_edges = circ.get_in_edges_of_type(v, EdgeType::Quantum);
677
1/2
✓ Branch 1 taken 167 times.
✗ Branch 2 not taken.
 167 EdgeVec out_edges = circ.get_out_edges_of_type(v, EdgeType::Quantum);
678 TKET_ASSERT(in_edges.size() == arity);
679 TKET_ASSERT(out_edges.size() == arity);
680
2/2
✓ Branch 0 taken 554 times.
✓ Branch 1 taken 167 times.
2/2
✓ Decision 'true' taken 554 times.
✓ Decision 'false' taken 167 times.
 721 for (unsigned i = 0; i < arity; ++i) {
681
1/2
✓ Branch 2 taken 554 times.
✗ Branch 3 not taken.
 554 Vertex in_v = circ.source(in_edges[i]);
682
1/2
✓ Branch 1 taken 554 times.
✗ Branch 2 not taken.
 554 Op_ptr in_op = circ.get_Op_ptr_from_Vertex(in_v);
683
1/2
✓ Branch 2 taken 554 times.
✗ Branch 3 not taken.
 554 Vertex out_v = circ.target(out_edges[i]);
684
1/2
✓ Branch 1 taken 554 times.
✗ Branch 2 not taken.
 554 Op_ptr out_op = circ.get_Op_ptr_from_Vertex(out_v);
685
686
2/2
✓ Branch 2 taken 313 times.
✓ Branch 3 taken 241 times.
2/2
✓ Decision 'true' taken 313 times.
✓ Decision 'false' taken 241 times.
 554 if (in_op->get_type() == OpType::Rz) {
687
3/6
✓ Branch 2 taken 313 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 313 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 313 times.
✗ Branch 9 not taken.
 313 in_rz[i] = -in_op->get_params().at(0);
688 } else {
689
1/2
✓ Branch 1 taken 241 times.
✗ Branch 2 not taken.
 241 in_rz[i] = 0.;
690 }
691
2/2
✓ Branch 2 taken 315 times.
✓ Branch 3 taken 239 times.
2/2
✓ Decision 'true' taken 315 times.
✓ Decision 'false' taken 239 times.
 554 if (out_op->get_type() == OpType::Rz) {
692
3/6
✓ Branch 2 taken 315 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 315 times.
✗ Branch 6 not taken.
✓ Branch 9 taken 315 times.
✗ Branch 10 not taken.
 315 out_rz[i] = out_op->get_params().at(0);
693 } else {
694
1/2
✓ Branch 1 taken 239 times.
✗ Branch 2 not taken.
 239 out_rz[i] = 0.;
695 }
696 554 }
697
698 // Find out which Rz angle is most popular.
699 // Note that we only compare expr[i] with expr[j] when j < i. This means
700 // that only the largest i from a set of equivalent exprs will have the
701 // right occurence count, but that is good enough.
702
1/2
✓ Branch 1 taken 167 times.
✗ Branch 2 not taken.
 167 std::vector<Expr> all_rz = in_rz;
703
1/2
✓ Branch 5 taken 167 times.
✗ Branch 6 not taken.
 167 all_rz.insert(all_rz.end(), out_rz.begin(), out_rz.end());
704
1/2
✓ Branch 2 taken 167 times.
✗ Branch 3 not taken.
 167 std::vector<unsigned> occurences_count(2 * arity);
705
2/2
✓ Branch 0 taken 1108 times.
✓ Branch 1 taken 167 times.
2/2
✓ Decision 'true' taken 1108 times.
✓ Decision 'false' taken 167 times.
 1275 for (unsigned i = 0; i < 2 * arity; ++i) {
706 1108 unsigned cnt = 0;
707
2/2
✓ Branch 0 taken 3354 times.
✓ Branch 1 taken 1108 times.
2/2
✓ Decision 'true' taken 3354 times.
✓ Decision 'false' taken 1108 times.
 4462 for (unsigned j = 0; j < i; ++j) {
708
3/4
✓ Branch 3 taken 3354 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 1088 times.
✓ Branch 6 taken 2266 times.
2/2
✓ Decision 'true' taken 1088 times.
✓ Decision 'false' taken 2266 times.
 3354 if (equiv_expr(all_rz[i], all_rz[j], 4)) {
709 1088 ++cnt;
710 }
711 }
712 1108 occurences_count[i] = cnt;
713 }
714 unsigned max_i =
715
1/2
✓ Branch 3 taken 167 times.
✗ Branch 4 not taken.
 167 std::max_element(occurences_count.begin(), occurences_count.end()) -
716 167 occurences_count.begin();
717
1/2
✓ Branch 2 taken 167 times.
✗ Branch 3 not taken.
 167 Expr absorb_rz = all_rz[max_i];
718
719
3/4
✓ Branch 1 taken 167 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 64 times.
✓ Branch 4 taken 103 times.
2/2
✓ Decision 'true' taken 64 times.
✓ Decision 'false' taken 103 times.
 167 if (!equiv_0(absorb_rz, 4)) {
720 64 success = true;
721
722 // Subtract absorb_rz in NPhasedX
723
1/2
✓ Branch 2 taken 64 times.
✗ Branch 3 not taken.
 64 std::vector<Expr> new_params = op->get_params();
724 TKET_ASSERT(new_params.size() == 2);
725
1/2
✓ Branch 2 taken 64 times.
✗ Branch 3 not taken.
 64 new_params[1] += absorb_rz;
726
3/6
✓ Branch 2 taken 64 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 64 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 64 times.
✗ Branch 9 not taken.
 64 circ.dag[v] = get_op_ptr(OpType::NPhasedX, new_params, arity);
727
728 // Finally, adjust +-absorb_rz in Rz everywhere around
729
2/2
✓ Branch 0 taken 229 times.
✓ Branch 1 taken 64 times.
2/2
✓ Decision 'true' taken 229 times.
✓ Decision 'false' taken 64 times.
 293 for (unsigned i = 0; i < arity; ++i) {
730
1/2
✓ Branch 2 taken 229 times.
✗ Branch 3 not taken.
 229 Vertex in_v = circ.source(in_edges[i]);
731
1/2
✓ Branch 1 taken 229 times.
✗ Branch 2 not taken.
 229 Op_ptr in_op = circ.get_Op_ptr_from_Vertex(in_v);
732
1/2
✓ Branch 2 taken 229 times.
✗ Branch 3 not taken.
 229 Vertex out_v = circ.target(out_edges[i]);
733
1/2
✓ Branch 1 taken 229 times.
✗ Branch 2 not taken.
 229 Op_ptr out_op = circ.get_Op_ptr_from_Vertex(out_v);
734
735
1/2
✓ Branch 1 taken 229 times.
✗ Branch 2 not taken.
 229 Expr angle;
736
2/4
✓ Branch 1 taken 229 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 229 times.
✗ Branch 5 not taken.
 229 Edge in_e, out_e;
737 229 VertexSet bin;
738
2/2
✓ Branch 2 taken 199 times.
✓ Branch 3 taken 30 times.
2/2
✓ Decision 'true' taken 199 times.
✓ Decision 'false' taken 30 times.
 229 if (in_op->get_type() == OpType::Rz) {
739
3/6
✓ Branch 2 taken 199 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 199 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 199 times.
✗ Branch 9 not taken.
 199 angle = in_op->get_params().at(0) + absorb_rz;
740 199 out_e = in_edges[i];
741
1/2
✓ Branch 1 taken 199 times.
✗ Branch 2 not taken.
 199 in_e = circ.get_last_edge(in_v, out_e);
742
1/2
✓ Branch 1 taken 199 times.
✗ Branch 2 not taken.
 199 bin = {in_v};
743 } else {
744
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 angle = absorb_rz;
745 30 out_e = in_edges[i];
746 30 in_e = out_e;
747
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 bin = {};
748 }
749
3/6
✓ Branch 2 taken 229 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 229 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 229 times.
✗ Branch 10 not taken.
 458 Subcircuit sub{{in_e}, {out_e}, bin};
750
1/2
✓ Branch 2 taken 229 times.
✗ Branch 3 not taken.
 229 Circuit c(1);
751
3/4
✓ Branch 1 taken 229 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 105 times.
✓ Branch 4 taken 124 times.
2/2
✓ Decision 'true' taken 105 times.
✓ Decision 'false' taken 124 times.
 229 if (!equiv_0(angle, 4)) {
752
2/4
✓ Branch 3 taken 105 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 105 times.
✗ Branch 7 not taken.
 105 c.add_op<unsigned>(OpType::Rz, angle, {0});
753 }
754
1/2
✓ Branch 1 taken 229 times.
✗ Branch 2 not taken.
 229 circ.substitute(c, sub, Circuit::VertexDeletion::No);
755
1/2
✓ Branch 3 taken 229 times.
✗ Branch 4 not taken.
 229 all_bins.insert(bin.begin(), bin.end());
756
757
2/2
✓ Branch 2 taken 172 times.
✓ Branch 3 taken 57 times.
2/2
✓ Decision 'true' taken 172 times.
✓ Decision 'false' taken 57 times.
 229 if (out_op->get_type() == OpType::Rz) {
758
3/6
✓ Branch 2 taken 172 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 172 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 172 times.
✗ Branch 9 not taken.
 172 angle = out_op->get_params().at(0) - absorb_rz;
759 172 in_e = out_edges[i];
760
1/2
✓ Branch 1 taken 172 times.
✗ Branch 2 not taken.
 172 out_e = circ.get_next_edge(out_v, in_e);
761
1/2
✓ Branch 1 taken 172 times.
✗ Branch 2 not taken.
 172 bin = {out_v};
762 } else {
763
1/2
✓ Branch 1 taken 57 times.
✗ Branch 2 not taken.
 57 angle = -absorb_rz;
764 57 in_e = out_edges[i];
765 57 out_e = in_e;
766
1/2
✓ Branch 1 taken 57 times.
✗ Branch 2 not taken.
 57 bin = {};
767 }
768
3/6
✓ Branch 2 taken 229 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 229 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 229 times.
✗ Branch 10 not taken.
 229 sub = Subcircuit{{in_e}, {out_e}, bin};
769
2/4
✓ Branch 2 taken 229 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 229 times.
✗ Branch 6 not taken.
 229 c = Circuit(1);
770
3/4
✓ Branch 1 taken 229 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 175 times.
✓ Branch 4 taken 54 times.
2/2
✓ Decision 'true' taken 175 times.
✓ Decision 'false' taken 54 times.
 229 if (!equiv_0(angle, 4)) {
771
2/4
✓ Branch 3 taken 175 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 175 times.
✗ Branch 7 not taken.
 175 c.add_op<unsigned>(OpType::Rz, angle, {0});
772 }
773
1/2
✓ Branch 1 taken 229 times.
✗ Branch 2 not taken.
 229 circ.substitute(c, sub, Circuit::VertexDeletion::No);
774
1/2
✓ Branch 3 taken 229 times.
✗ Branch 4 not taken.
 229 all_bins.insert(bin.begin(), bin.end());
775 229 }
776 64 }
777 167 }
778 1332 }
779
1/2
✓ Branch 1 taken 62 times.
✗ Branch 2 not taken.
 62 circ.remove_vertices(
780 all_bins, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
781
782 62 return success;
783
1/2
✓ Branch 2 taken 62 times.
✗ Branch 3 not taken.
 124 });
784 }
785
786 2 Transform ZZPhase_to_Rz() {
787 // basic optimisation, replace ZZPhase with two Rz(1)
788 4 return Transform([](Circuit &circ) {
789 4 bool success = false;
790 4 VertexSet bin;
791
792
7/8
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 102 times.
✓ Branch 6 taken 4 times.
✓ Branch 8 taken 102 times.
✓ Branch 9 taken 4 times.
✓ Branch 11 taken 4 times.
✓ Branch 12 taken 4 times.
 110 BGL_FORALL_VERTICES(v, circ.dag, DAG) {
793
1/2
✓ Branch 1 taken 102 times.
✗ Branch 2 not taken.
 102 Op_ptr op = circ.get_Op_ptr_from_Vertex(v);
794
2/2
✓ Branch 2 taken 10 times.
✓ Branch 3 taken 92 times.
2/2
✓ Decision 'true' taken 10 times.
✓ Decision 'false' taken 92 times.
 102 if (op->get_type() == OpType::ZZPhase) {
795
1/2
✓ Branch 2 taken 10 times.
✗ Branch 3 not taken.
 10 auto params = op->get_params();
796 TKET_ASSERT(params.size() == 1);
797 // evaluate
798
2/4
✓ Branch 2 taken 10 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 10 times.
✗ Branch 6 not taken.
 10 double param_value = eval_expr(params[0]).value();
799
2/2
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 8 times.
2/2
✓ Decision 'true' taken 2 times.
✓ Decision 'false' taken 8 times.
 10 if (std::abs(param_value) == 1.0) {
800 2 success = true;
801 // basic optimisation, replace ZZPhase with two Rz(1)
802
1/2
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
 2 Circuit replacement(2);
803
3/6
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 2 times.
✗ Branch 10 not taken.
 2 replacement.add_op<unsigned>(OpType::Rz, 1.0, {0});
804
3/6
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 2 times.
✗ Branch 10 not taken.
 2 replacement.add_op<unsigned>(OpType::Rz, 1.0, {1});
805
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 circ.substitute(replacement, v, Circuit::VertexDeletion::No);
806
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 bin.insert(v);
807 2 }
808 10 }
809 102 }
810
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 circ.remove_vertices(
811 bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
812 4 return success;
813
1/2
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
 6 });
814 }
815
816 60 Transform normalise_TK2() {
817 65 return Transform([](Circuit &circ) {
818 65 bool success = false;
819 65 VertexSet bin;
820
821
7/8
✓ Branch 1 taken 65 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 5686 times.
✓ Branch 6 taken 65 times.
✓ Branch 8 taken 5686 times.
✓ Branch 9 taken 65 times.
✓ Branch 11 taken 65 times.
✓ Branch 12 taken 65 times.
 5816 BGL_FORALL_VERTICES(v, circ.dag, DAG) {
822
1/2
✓ Branch 1 taken 5686 times.
✗ Branch 2 not taken.
 5686 Op_ptr op = circ.get_Op_ptr_from_Vertex(v);
823 5686 bool conditional = op->get_type() == OpType::Conditional;
824
2/2
✓ Branch 0 taken 27 times.
✓ Branch 1 taken 5659 times.
2/2
✓ Decision 'true' taken 27 times.
✓ Decision 'false' taken 5659 times.
 5686 if (conditional) {
825 27 const Conditional &cond = static_cast<const Conditional &>(*op);
826
1/2
✓ Branch 1 taken 27 times.
✗ Branch 2 not taken.
 27 op = cond.get_op();
827 }
828
2/2
✓ Branch 2 taken 26 times.
✓ Branch 3 taken 5660 times.
2/2
✓ Decision 'true' taken 26 times.
✓ Decision 'false' taken 5660 times.
 5686 if (op->get_type() == OpType::TK2) {
829
1/2
✓ Branch 2 taken 26 times.
✗ Branch 3 not taken.
 26 auto params = op->get_params();
830 TKET_ASSERT(params.size() == 3);
831
6/10
✓ Branch 2 taken 26 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 26 times.
✗ Branch 7 not taken.
✓ Branch 10 taken 26 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 26 times.
✗ Branch 14 not taken.
✓ Branch 16 taken 4 times.
✓ Branch 17 taken 22 times.
2/2
✓ Decision 'true' taken 4 times.
✓ Decision 'false' taken 22 times.
 26 if (!in_weyl_chamber({params[0], params[1], params[2]})) {
832 4 success = true;
833
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 3 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 3 times.
 4 if (conditional) {
834
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 circ.substitute_conditional(
835
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 2 CircPool::TK2_using_normalised_TK2(
836 1 params[0], params[1], params[2]),
837 v, Circuit::VertexDeletion::No);
838 } else {
839
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 circ.substitute(
840
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 6 CircPool::TK2_using_normalised_TK2(
841 3 params[0], params[1], params[2]),
842 v, Circuit::VertexDeletion::No);
843 }
844
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 bin.insert(v);
845 }
846 26 }
847 5686 }
848
849
1/2
✓ Branch 1 taken 65 times.
✗ Branch 2 not taken.
 65 circ.remove_vertices(
850 bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
851
852 65 return success;
853
1/2
✓ Branch 2 taken 60 times.
✗ Branch 3 not taken.
 125 });
854 }
855
856 } // namespace Transforms
857
858 } // namespace tket
859