GCC Code Coverage Report

Directory: ./
File: Transformations/PhasedXFrontier.cpp
Date: 2022-10-15 05:10:18
Warnings: 12 unchecked decisions!
Exec Total Coverage
Lines: 272 283 96.1%
Functions: 25 25 100.0%
Branches: 316 576 54.9%
Decisions: 67 106 63.2%
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 "PhasedXFrontier.hpp"
16
17 #include <string>
18
19 #include "Circuit/CircPool.hpp"
20 #include "Circuit/CircUtils.hpp"
21 #include "Circuit/Circuit.hpp"
22 #include "OpType/OpType.hpp"
23 #include "OpType/OpTypeInfo.hpp"
24 #include "StandardSquash.hpp"
25 #include "Utils/Expression.hpp"
26
27 namespace tket {
28
29 namespace Transforms {
30
31 template <typename T>
32 628 static std::map<T, unsigned> count(std::vector<T> xs) {
33 628 std::map<T, unsigned> cnts;
34
2/2
✓ Branch 5 taken 1388 times.
✓ Branch 6 taken 628 times.
2/2
✓ Decision 'true' taken 1388 times.
✓ Decision 'false' taken 628 times.
 2016 for (const auto& x : xs) {
35
1/2
✓ Branch 1 taken 1388 times.
✗ Branch 2 not taken.
 1388 auto it = cnts.find(x);
36
2/2
✓ Branch 2 taken 409 times.
✓ Branch 3 taken 979 times.
2/2
✓ Decision 'true' taken 409 times.
✓ Decision 'false' taken 979 times.
 1388 if (it != cnts.end()) {
37 409 ++(it->second);
38 } else {
39
1/2
✓ Branch 1 taken 979 times.
✗ Branch 2 not taken.
 979 cnts[x] = 1;
40 }
41 }
42 628 return cnts;
43 }
44
45 45 bool PhasedXFrontier::is_finished() {
46
2/2
✓ Branch 1 taken 134 times.
✓ Branch 2 taken 45 times.
2/2
✓ Decision 'true' taken 134 times.
✓ Decision 'false' taken 45 times.
 179 for (unsigned i = 0; i < circ_.n_qubits(); ++i) {
47
1/2
✓ Branch 2 taken 134 times.
✗ Branch 3 not taken.
 134 Vertex v = circ_.target(intervals_[i].second);
48
2/4
✓ Branch 1 taken 134 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 134 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 134 times.
 134 if (!circ_.detect_final_Op(v)) {
49 ✗ return false;
50 }
51 }
52 45 return true;
53 }
54
55 176 std::set<unsigned> PhasedXFrontier::qubits_ending_in(const Vertex& v) const {
56 176 std::set<unsigned> qubits;
57
3/4
✓ Branch 1 taken 824 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 648 times.
✓ Branch 4 taken 176 times.
0/1
? Decision couldn't be analyzed.
 824 for (unsigned i = 0; i < circ_.n_qubits(); ++i) {
58
3/4
✓ Branch 2 taken 648 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 352 times.
✓ Branch 5 taken 296 times.
2/2
✓ Decision 'true' taken 352 times.
✓ Decision 'false' taken 296 times.
 648 if (circ_.target(intervals_[i].second) == v) {
59
1/2
✓ Branch 1 taken 352 times.
✗ Branch 2 not taken.
 352 qubits.insert(i);
60 }
61 }
62 176 return qubits;
63 }
64
65 92 void PhasedXFrontier::squash_intervals() {
66
2/2
✓ Branch 1 taken 295 times.
✓ Branch 2 taken 92 times.
2/2
✓ Decision 'true' taken 295 times.
✓ Decision 'false' taken 92 times.
 387 for (unsigned i = 0; i < circ_.n_qubits(); ++i) {
67 295 squash_interval(i);
68 }
69 92 }
70
71 2200 OptEdge PhasedXFrontier::get_beta_edge(unsigned i) const {
72 2200 const auto& [start, end] = intervals_[i];
73 2200 Edge e = start;
74
3/4
✓ Branch 1 taken 3061 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 2249 times.
✓ Branch 4 taken 812 times.
0/1
? Decision couldn't be analyzed.
 3061 while (e != end) {
75
1/2
✓ Branch 1 taken 2249 times.
✗ Branch 2 not taken.
 2249 Vertex v = circ_.target(e);
76
1/2
✓ Branch 1 taken 2249 times.
✗ Branch 2 not taken.
 2249 OpType type = circ_.get_OpType_from_Vertex(v);
77
4/4
✓ Branch 0 taken 1693 times.
✓ Branch 1 taken 556 times.
✓ Branch 2 taken 832 times.
✓ Branch 3 taken 861 times.
2/2
✓ Decision 'true' taken 1388 times.
✓ Decision 'false' taken 861 times.
 2249 if (type == OpType::PhasedX || type == OpType::NPhasedX) {
78 1388 return e;
79 }
80
1/2
✓ Branch 1 taken 861 times.
✗ Branch 2 not taken.
 861 e = circ_.get_next_edge(v, e);
81 }
82 812 return std::nullopt;
83 }
84
85 628 OptEdgeVec PhasedXFrontier::get_all_beta_edges() const {
86 628 OptEdgeVec beta_edges;
87 628 std::vector<Vertex> beta_vertices;
88
3/4
✓ Branch 1 taken 2828 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 2200 times.
✓ Branch 4 taken 628 times.
0/1
? Decision couldn't be analyzed.
 2828 for (unsigned i = 0; i < circ_.n_qubits(); ++i) {
89
1/2
✓ Branch 1 taken 2200 times.
✗ Branch 2 not taken.
 2200 OptEdge beta_e = get_beta_edge(i);
90
1/2
✓ Branch 1 taken 2200 times.
✗ Branch 2 not taken.
 2200 beta_edges.push_back(beta_e);
91
2/2
✓ Branch 1 taken 1388 times.
✓ Branch 2 taken 812 times.
2/2
✓ Decision 'true' taken 1388 times.
✓ Decision 'false' taken 812 times.
 2200 if (beta_e) {
92
2/4
✓ Branch 2 taken 1388 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1388 times.
✗ Branch 6 not taken.
 1388 beta_vertices.push_back(circ_.target(*beta_e));
93 }
94 }
95
96 // for OpType::NPhasedX, we need to reset some betas to zero if they
97 // are shadowed (i.e. if one NPhasedX is behind another one)
98
2/4
✓ Branch 1 taken 628 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 628 times.
✗ Branch 5 not taken.
 628 std::map<Vertex, unsigned> arities = count(beta_vertices);
99
2/2
✓ Branch 5 taken 2200 times.
✓ Branch 6 taken 628 times.
2/2
✓ Decision 'true' taken 2200 times.
✓ Decision 'false' taken 628 times.
 2828 for (auto& e : beta_edges) {
100
2/2
✓ Branch 1 taken 1388 times.
✓ Branch 2 taken 812 times.
2/2
✓ Decision 'true' taken 1388 times.
✓ Decision 'false' taken 812 times.
 2200 if (e) {
101
1/2
✓ Branch 2 taken 1388 times.
✗ Branch 3 not taken.
 1388 Vertex v = circ_.target(*e);
102
1/2
✓ Branch 1 taken 1388 times.
✗ Branch 2 not taken.
 1388 Op_ptr op = circ_.get_Op_ptr_from_Vertex(v);
103
4/6
✓ Branch 1 taken 1388 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 1388 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 128 times.
✓ Branch 8 taken 1260 times.
2/2
✓ Decision 'true' taken 128 times.
✓ Decision 'false' taken 1260 times.
 1388 if (arities[v] != op->n_qubits()) {
104 128 e = std::nullopt;
105 }
106 1388 }
107 }
108 1256 return beta_edges;
109 628 }
110
111 492 OptVertexVec PhasedXFrontier::get_all_beta_vertices() const {
112 492 OptVertexVec vertices;
113
3/4
✓ Branch 1 taken 492 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 1714 times.
✓ Branch 9 taken 492 times.
0/1
? Decision couldn't be analyzed.
 2206 for (const auto& e : get_all_beta_edges()) {
114
2/2
✓ Branch 1 taken 933 times.
✓ Branch 2 taken 781 times.
2/2
✓ Decision 'true' taken 933 times.
✓ Decision 'false' taken 781 times.
 1714 if (e) {
115
1/2
✓ Branch 2 taken 933 times.
✗ Branch 3 not taken.
 933 Vertex v = circ_.target(*e);
116
1/2
✓ Branch 2 taken 933 times.
✗ Branch 3 not taken.
 933 vertices.push_back(v);
117 } else {
118 781 OptVertex optv;
119
1/2
✓ Branch 1 taken 781 times.
✗ Branch 2 not taken.
 781 vertices.push_back(optv);
120 }
121 492 }
122 492 return vertices;
123 }
124
125 148 std::vector<Expr> PhasedXFrontier::get_all_betas() const {
126 148 std::vector<Expr> betas;
127
3/4
✓ Branch 1 taken 148 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 534 times.
✓ Branch 9 taken 148 times.
0/1
? Decision couldn't be analyzed.
 682 for (const auto& v : get_all_beta_vertices()) {
128
1/2
✓ Branch 1 taken 534 times.
✗ Branch 2 not taken.
 534 Expr beta = 0.;
129
2/2
✓ Branch 1 taken 341 times.
✓ Branch 2 taken 193 times.
2/2
✓ Decision 'true' taken 341 times.
✓ Decision 'false' taken 193 times.
 534 if (v) {
130
1/2
✓ Branch 2 taken 341 times.
✗ Branch 3 not taken.
 341 Op_ptr op = circ_.get_Op_ptr_from_Vertex(*v);
131
2/4
✓ Branch 2 taken 341 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 341 times.
✗ Branch 7 not taken.
 341 beta = op->get_params().front();
132 341 }
133
1/2
✓ Branch 1 taken 534 times.
✗ Branch 2 not taken.
 534 betas.push_back(beta);
134 682 }
135 148 return betas;
136 }
137
138 197 void PhasedXFrontier::next_interval(unsigned i) {
139 197 auto& [start, end] = intervals_[i];
140
141 // new interval
142 197 start = get_interval_start(end);
143 197 end = get_interval_end(start);
144 197 }
145
146 81 void PhasedXFrontier::next_multiqb(const Vertex& v) {
147
1/2
✓ Branch 1 taken 81 times.
✗ Branch 2 not taken.
 81 std::set<unsigned> curr_qubits = qubits_ending_in(v);
148 // move forward
149
2/2
✓ Branch 5 taken 162 times.
✓ Branch 6 taken 81 times.
2/2
✓ Decision 'true' taken 162 times.
✓ Decision 'false' taken 81 times.
 243 for (unsigned i : curr_qubits) {
150
1/2
✓ Branch 1 taken 162 times.
✗ Branch 2 not taken.
 162 next_interval(i);
151 }
152 81 }
153
154 436 Edge PhasedXFrontier::get_interval_end(Edge e) const {
155
1/2
✓ Branch 1 taken 436 times.
✗ Branch 2 not taken.
 436 Vertex v = circ_.target(e);
156
8/10
✓ Branch 1 taken 885 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 615 times.
✓ Branch 4 taken 270 times.
✓ Branch 6 taken 615 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 449 times.
✓ Branch 9 taken 166 times.
✓ Branch 10 taken 449 times.
✓ Branch 11 taken 436 times.
0/1
? Decision couldn't be analyzed.
 885 while (!circ_.detect_final_Op(v) && !is_interval_boundary(v)) {
157
1/2
✓ Branch 1 taken 449 times.
✗ Branch 2 not taken.
 449 auto p = circ_.get_next_pair(v, e);
158 449 v = p.first;
159 449 e = p.second;
160 }
161 436 return e;
162 }
163
164 197 Edge PhasedXFrontier::get_interval_start(Edge e) const {
165
1/2
✓ Branch 1 taken 197 times.
✗ Branch 2 not taken.
 197 Vertex v = circ_.target(e);
166
3/4
✓ Branch 1 taken 197 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 184 times.
✓ Branch 4 taken 13 times.
2/2
✓ Decision 'true' taken 184 times.
✓ Decision 'false' taken 13 times.
 197 if (!circ_.detect_final_Op(v)) {
167
1/2
✓ Branch 1 taken 184 times.
✗ Branch 2 not taken.
 184 e = circ_.get_next_edge(v, e);
168 }
169 197 return e;
170 }
171
172 1322 bool PhasedXFrontier::is_interval_boundary(Op_ptr op) {
173 1322 OpType type = op->get_type();
174
11/18
✓ Branch 1 taken 1322 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 978 times.
✓ Branch 4 taken 344 times.
✓ Branch 7 taken 978 times.
✗ Branch 8 not taken.
✓ Branch 11 taken 978 times.
✗ Branch 12 not taken.
✓ Branch 13 taken 517 times.
✓ Branch 14 taken 461 times.
✓ Branch 15 taken 244 times.
✓ Branch 16 taken 273 times.
✓ Branch 18 taken 978 times.
✓ Branch 19 taken 344 times.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
 2644 return is_gate_type(type) && as_gate_ptr(op)->n_qubits() > 1 &&
175
2/2
✓ Branch 0 taken 978 times.
✓ Branch 1 taken 344 times.
 2644 type != OpType::NPhasedX;
176 }
177
178 615 bool PhasedXFrontier::is_interval_boundary(Vertex v) const {
179
1/2
✓ Branch 1 taken 615 times.
✗ Branch 2 not taken.
 615 Op_ptr op = circ_.get_Op_ptr_from_Vertex(v);
180
1/2
✓ Branch 2 taken 615 times.
✗ Branch 3 not taken.
 1230 return is_interval_boundary(op);
181 615 }
182
183 /**
184 * @brief Implements the AbstractSquasher interface for squashing to PhasedX+Rz
185 */
186 class PhasedXSquasher : public StandardSquasher {
187 public:
188 75 PhasedXSquasher()
189 75 : StandardSquasher(
190
1/2
✓ Branch 2 taken 75 times.
✗ Branch 3 not taken.
 150 OpTypeSet{OpType::Rz, OpType::PhasedX},
191
1/2
✓ Branch 2 taken 75 times.
✗ Branch 3 not taken.
 225 CircPool::tk1_to_PhasedXRz) {}
192
193 // Accept any single-qubit gate that has TK1 angles to squash it.
194 299 bool accepts(Gate_ptr gp) const override {
195 299 OpType optype = gp->get_type();
196 299 return is_single_qubit_unitary_type(optype);
197 }
198 };
199
200 75 PhasedXFrontier::PhasedXFrontier(Circuit& circ)
201 75 : intervals_(),
202 75 circ_(circ),
203
1/2
✓ Branch 1 taken 75 times.
✗ Branch 2 not taken.
 75 squasher_(std::make_unique<PhasedXSquasher>(), circ, false) {
204
1/2
✓ Branch 1 taken 75 times.
✗ Branch 2 not taken.
 75 const unsigned n = circ_.n_qubits();
205
1/2
✓ Branch 1 taken 75 times.
✗ Branch 2 not taken.
 75 intervals_.resize(n);
206
207 // initialise intervals
208
1/2
✓ Branch 1 taken 75 times.
✗ Branch 2 not taken.
 75 const qubit_vector_t all_qbs = circ_.all_qubits();
209
2/2
✓ Branch 0 taken 239 times.
✓ Branch 1 taken 75 times.
2/2
✓ Decision 'true' taken 239 times.
✓ Decision 'false' taken 75 times.
 314 for (unsigned i = 0; i < n; ++i) {
210 239 Qubit q = all_qbs[i];
211
1/2
✓ Branch 1 taken 239 times.
✗ Branch 2 not taken.
 239 Vertex v_in = circ_.get_in(q);
212
1/2
✓ Branch 1 taken 239 times.
✗ Branch 2 not taken.
 239 EdgeVec e_vec = circ_.get_all_out_edges(v_in);
213 TKET_ASSERT(e_vec.size() == 1);
214
215 // interval [start, end]
216 239 Edge start = e_vec.front();
217
1/2
✓ Branch 1 taken 239 times.
✗ Branch 2 not taken.
 239 Edge end = get_interval_end(start);
218 239 intervals_[i] = {start, end};
219 239 }
220 75 }
221
222 295 void PhasedXFrontier::squash_interval(unsigned i) {
223 295 auto& [start_e, end_e] = intervals_[i];
224
225 // backup edges
226
2/4
✓ Branch 1 taken 295 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 295 times.
✗ Branch 5 not taken.
 295 VertPort start{circ_.source(start_e), circ_.get_source_port(start_e)};
227
2/4
✓ Branch 1 taken 295 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 295 times.
✗ Branch 5 not taken.
 295 VertPort end{circ_.target(end_e), circ_.get_target_port(end_e)};
228
229
1/2
✓ Branch 1 taken 295 times.
✗ Branch 2 not taken.
 295 squasher_.squash_between(start_e, end_e);
230
231 // restore interval edges
232
1/2
✓ Branch 1 taken 295 times.
✗ Branch 2 not taken.
 295 start_e = circ_.get_nth_out_edge(start.first, start.second);
233
1/2
✓ Branch 1 taken 295 times.
✗ Branch 2 not taken.
 295 end_e = circ_.get_nth_in_edge(end.first, end.second);
234 295 }
235
236 136 PhasedXFrontier::BackupIntervals PhasedXFrontier::backup_intervals() const {
237 136 BackupIntervals ret;
238
3/4
✓ Branch 1 taken 622 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 486 times.
✓ Branch 4 taken 136 times.
0/1
? Decision couldn't be analyzed.
 622 for (unsigned i = 0; i < circ_.n_qubits(); ++i) {
239 486 const auto& [start, end] = intervals_[i];
240
3/6
✓ Branch 1 taken 486 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 486 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 486 times.
✗ Branch 9 not taken.
 486 ret.start.push_back({circ_.source(start), circ_.get_source_port(start)});
241
3/6
✓ Branch 1 taken 486 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 486 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 486 times.
✗ Branch 9 not taken.
 486 ret.end.push_back({circ_.target(end), circ_.get_target_port(end)});
242 }
243 136 return ret;
244 }
245
246 136 void PhasedXFrontier::restore_intervals(const BackupIntervals& b) {
247
2/2
✓ Branch 1 taken 486 times.
✓ Branch 2 taken 136 times.
2/2
✓ Decision 'true' taken 486 times.
✓ Decision 'false' taken 136 times.
 622 for (unsigned i = 0; i < circ_.n_qubits(); ++i) {
248
1/2
✓ Branch 3 taken 486 times.
✗ Branch 4 not taken.
 486 Edge start = circ_.get_nth_out_edge(b.start[i].first, b.start[i].second);
249
1/2
✓ Branch 3 taken 486 times.
✗ Branch 4 not taken.
 486 Edge end = circ_.get_nth_in_edge(b.end[i].first, b.end[i].second);
250 486 intervals_[i].first = start;
251 486 intervals_[i].second = end;
252 }
253 136 }
254
255 147 void PhasedXFrontier::skip_global_gates(unsigned n) {
256
2/2
✓ Branch 1 taken 516 times.
✓ Branch 2 taken 147 times.
2/2
✓ Decision 'true' taken 516 times.
✓ Decision 'false' taken 147 times.
 663 for (unsigned i = 0; i < circ_.n_qubits(); ++i) {
257 516 unsigned count = 0;
258 516 auto& [e, end] = intervals_[i];
259
1/2
✓ Branch 1 taken 1602 times.
✗ Branch 2 not taken.
1/2
✓ Decision 'true' taken 1602 times.
✗ Decision 'false' not taken.
 1602 while (e != end) {
260
1/2
✓ Branch 1 taken 1602 times.
✗ Branch 2 not taken.
 1602 Vertex v = circ_.target(e);
261
1/2
✓ Branch 1 taken 1602 times.
✗ Branch 2 not taken.
 1602 OpType type = circ_.get_OpType_from_Vertex(v);
262
1/2
✓ Branch 1 taken 1602 times.
✗ Branch 2 not taken.
 1602 e = circ_.get_next_edge(v, e);
263
4/4
✓ Branch 0 taken 674 times.
✓ Branch 1 taken 928 times.
✓ Branch 2 taken 928 times.
✓ Branch 3 taken 674 times.
2/2
✓ Decision 'true' taken 928 times.
✓ Decision 'false' taken 1348 times.
 2276 if (type == OpType::NPhasedX ||
264
2/6
✓ Branch 1 taken 674 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 674 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
 674 (circ_.n_qubits() == 1 && type == OpType::PhasedX)) {
265
1/2
✓ Branch 1 taken 928 times.
✗ Branch 2 not taken.
 928 unsigned in_edges = circ_.n_in_edges_of_type(v, EdgeType::Quantum);
266
1/2
✓ Branch 1 taken 928 times.
✗ Branch 2 not taken.
 928 unsigned out_edges = circ_.n_out_edges_of_type(v, EdgeType::Quantum);
267
5/10
✓ Branch 1 taken 928 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 928 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 928 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 928 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 928 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 928 times.
 928 if (in_edges != circ_.n_qubits() || out_edges != circ_.n_qubits()) {
268 ✗ throw CircuitInvalidity("Found non-global NPhasedX gate");
269 }
270 928 ++count;
271
2/2
✓ Branch 0 taken 516 times.
✓ Branch 1 taken 412 times.
2/2
✓ Decision 'true' taken 516 times.
✓ Decision 'false' taken 412 times.
 928 if (count == n) {
272 516 break;
273 }
274 }
275 }
276
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 516 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 516 times.
 516 if (count < n) {
277 ✗ throw CircuitInvalidity("Did not find expected global gates");
278 }
279 }
280 147 }
281
282 10 bool PhasedXFrontier::are_phasedx_left() const {
283
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 PhasedXFrontier copy = *this;
284
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 const unsigned n = circ_.n_qubits();
285
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 10 times.
2/2
✓ Decision 'true' taken 34 times.
✓ Decision 'false' taken 10 times.
 44 for (unsigned i = 0; i < n; ++i) {
286
1/2
✓ Branch 1 taken 34 times.
✗ Branch 2 not taken.
 34 copy.next_interval(i);
287 }
288
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 OptVertexVec all_phasedx = copy.get_all_beta_vertices();
289
290
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 20 return !all_nullopt(all_phasedx);
291 10 }
292
293 23 void PhasedXFrontier::insert_1_phasedx(unsigned i) {
294
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 std::vector<Expr> betas = get_all_betas();
295
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 OptEdgeVec edges = get_all_beta_edges();
296
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 OptVertexVec vertices = get_all_beta_vertices();
297
298
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 23 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 23 times.
 23 if (!vertices[i]) {
299 ✗ throw CircuitInvalidity("No PhasedX found on qubit " + std::to_string(i));
300 }
301
1/2
✓ Branch 2 taken 23 times.
✗ Branch 3 not taken.
 23 Expr beta = betas[i];
302
303 23 VertexSet bin;
304 23 EdgeVec in_hole, out_hole;
305
2/4
✓ Branch 2 taken 23 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 23 times.
✗ Branch 6 not taken.
 23 Circuit sub1(circ_.n_qubits());
306
2/4
✓ Branch 2 taken 23 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 23 times.
✗ Branch 6 not taken.
 23 Circuit sub2(circ_.n_qubits());
307
308
3/4
✓ Branch 1 taken 97 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 74 times.
✓ Branch 4 taken 23 times.
0/1
? Decision couldn't be analyzed.
 97 for (unsigned i = 0; i < circ_.n_qubits(); ++i) {
309
2/2
✓ Branch 2 taken 66 times.
✓ Branch 3 taken 8 times.
2/2
✓ Decision 'true' taken 66 times.
✓ Decision 'false' taken 8 times.
 74 if (vertices[i]) {
310
1/2
✓ Branch 2 taken 66 times.
✗ Branch 3 not taken.
 66 Vertex v = vertices[i].value();
311
1/2
✓ Branch 2 taken 66 times.
✗ Branch 3 not taken.
 66 Edge e = edges[i].value();
312
1/2
✓ Branch 1 taken 66 times.
✗ Branch 2 not taken.
 66 Op_ptr op = circ_.get_Op_ptr_from_Vertex(v);
313 66 OpType type = op->get_type();
314
1/2
✓ Branch 2 taken 66 times.
✗ Branch 3 not taken.
 66 Expr new_beta = betas[i] - beta;
315
316
1/2
✓ Branch 1 taken 66 times.
✗ Branch 2 not taken.
 66 in_hole.push_back(e);
317
2/4
✓ Branch 1 taken 66 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 66 times.
✗ Branch 5 not taken.
 66 out_hole.push_back(circ_.get_next_edge(v, e));
318
319
3/4
✓ Branch 1 taken 66 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 58 times.
✓ Branch 4 taken 8 times.
2/2
✓ Decision 'true' taken 58 times.
✓ Decision 'false' taken 8 times.
 66 if (!bin.contains(v)) {
320
1/2
✓ Branch 1 taken 58 times.
✗ Branch 2 not taken.
 58 bin.insert(v);
321
322 // v's qubits
323 58 std::vector<unsigned> qubits;
324
3/4
✓ Branch 1 taken 252 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 194 times.
✓ Branch 4 taken 58 times.
0/1
? Decision couldn't be analyzed.
 252 for (unsigned j = 0; j < circ_.n_qubits(); ++j) {
325
2/2
✓ Branch 2 taken 66 times.
✓ Branch 3 taken 128 times.
2/2
✓ Decision 'true' taken 66 times.
✓ Decision 'false' taken 128 times.
 194 if (vertices[j] == v) {
326
1/2
✓ Branch 1 taken 66 times.
✗ Branch 2 not taken.
 66 qubits.push_back(j);
327 }
328 }
329
330
3/4
✓ Branch 0 taken 50 times.
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 50 times.
✗ Branch 3 not taken.
1/2
✓ Decision 'true' taken 58 times.
✗ Decision 'false' not taken.
 58 if (type == OpType::NPhasedX || type == OpType::PhasedX) {
331
2/4
✓ Branch 2 taken 58 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 58 times.
✗ Branch 7 not taken.
 58 Expr alpha = op->get_params()[1];
332
3/4
✓ Branch 1 taken 58 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 14 times.
✓ Branch 4 taken 44 times.
2/2
✓ Decision 'true' taken 14 times.
✓ Decision 'false' taken 44 times.
 58 if (!equiv_0(new_beta, 4)) {
333
2/4
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 14 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 14 times.
 14 if (equiv_0(new_beta, 2)) {
334
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (qubits.size() % 2) {
335 ✗ sub1.add_phase(-1);
336 }
337 } else {
338
6/12
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 14 times.
✗ Branch 6 not taken.
✓ Branch 9 taken 14 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 14 times.
✗ Branch 13 not taken.
✓ Branch 16 taken 28 times.
✓ Branch 17 taken 14 times.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
 42 sub2.add_op(type, {new_beta, 0.}, qubits);
339 }
340 }
341
3/4
✓ Branch 1 taken 58 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 44 times.
✓ Branch 4 taken 14 times.
0/1
? Decision couldn't be analyzed.
 58 if (!equiv_0(alpha, 2)) {
342
2/2
✓ Branch 4 taken 52 times.
✓ Branch 5 taken 44 times.
2/2
✓ Decision 'true' taken 52 times.
✓ Decision 'false' taken 44 times.
 96 for (unsigned q : qubits) {
343
3/6
✓ Branch 3 taken 52 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 52 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 52 times.
✗ Branch 10 not taken.
 52 sub1.add_op<unsigned>(OpType::Rz, {-alpha}, {q});
344
2/4
✓ Branch 3 taken 52 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 52 times.
✗ Branch 7 not taken.
 52 sub2.add_op<unsigned>(OpType::Rz, {alpha}, {q});
345 }
346 }
347 58 } else {
348 ✗ throw BadOpType("Encountered invalid beta angle OpType", type);
349 }
350 58 }
351 66 } else {
352 8 Edge interval_begin = intervals_[i].first;
353
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 in_hole.push_back(interval_begin);
354
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 out_hole.push_back(interval_begin);
355
2/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
0/1
? Decision couldn't be analyzed.
 8 if (!equiv_0(beta, 2)) {
356
7/14
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 8 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 8 times.
✗ Branch 10 not taken.
✓ Branch 13 taken 8 times.
✗ Branch 14 not taken.
✓ Branch 16 taken 8 times.
✗ Branch 17 not taken.
✓ Branch 20 taken 16 times.
✓ Branch 21 taken 8 times.
✗ Branch 28 not taken.
✗ Branch 29 not taken.
 24 sub2.add_op<unsigned>(OpType::PhasedX, {-beta, 0}, {i});
357
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ } else if (!equiv_0(beta, 4)) {
358 ✗ sub2.add_phase(-1);
359 }
360 }
361 }
362
363
2/4
✓ Branch 2 taken 23 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 23 times.
✗ Branch 6 not taken.
 23 Circuit sub(circ_.n_qubits());
364
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 sub.append(sub1);
365
7/14
✓ Branch 2 taken 23 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 23 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 23 times.
✗ Branch 9 not taken.
✓ Branch 12 taken 23 times.
✗ Branch 13 not taken.
✓ Branch 15 taken 23 times.
✗ Branch 16 not taken.
✓ Branch 19 taken 46 times.
✓ Branch 20 taken 23 times.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
 69 sub.add_op<Qubit>(OpType::NPhasedX, {beta, 0}, sub.all_qubits());
366
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 sub.append(sub2);
367
368
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 Subcircuit hole{in_hole, out_hole, bin};
369
370 // perform substitution
371
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 BackupIntervals backup = backup_intervals();
372
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 circ_.substitute(sub, hole, Circuit::VertexDeletion::Yes);
373
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 restore_intervals(backup);
374
375
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 skip_global_gates(1);
376 23 }
377
378 113 void PhasedXFrontier::insert_2_phasedx() {
379 113 EdgeVec hole_in, hole_out;
380
2/4
✓ Branch 2 taken 113 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 113 times.
✗ Branch 6 not taken.
 113 Circuit sub1(circ_.n_qubits());
381
2/4
✓ Branch 2 taken 113 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 113 times.
✗ Branch 6 not taken.
 113 Circuit sub2(circ_.n_qubits());
382
2/4
✓ Branch 2 taken 113 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 113 times.
✗ Branch 6 not taken.
 113 Circuit sub3(circ_.n_qubits());
383 113 VertexSet bin;
384
385
1/2
✓ Branch 1 taken 113 times.
✗ Branch 2 not taken.
 113 std::vector<Expr> betas = get_all_betas();
386
1/2
✓ Branch 1 taken 113 times.
✗ Branch 2 not taken.
 113 OptEdgeVec edges = get_all_beta_edges();
387
1/2
✓ Branch 1 taken 113 times.
✗ Branch 2 not taken.
 113 OptVertexVec vertices = get_all_beta_vertices();
388
389
3/4
✓ Branch 1 taken 525 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 412 times.
✓ Branch 4 taken 113 times.
0/1
? Decision couldn't be analyzed.
 525 for (unsigned i = 0; i < circ_.n_qubits(); ++i) {
390
2/2
✓ Branch 2 taken 261 times.
✓ Branch 3 taken 151 times.
2/2
✓ Decision 'true' taken 261 times.
✓ Decision 'false' taken 151 times.
 412 if (vertices[i]) {
391
1/2
✓ Branch 2 taken 261 times.
✗ Branch 3 not taken.
 261 Vertex v = vertices[i].value();
392
1/2
✓ Branch 2 taken 261 times.
✗ Branch 3 not taken.
 261 Edge e = edges[i].value();
393
1/2
✓ Branch 1 taken 261 times.
✗ Branch 2 not taken.
 261 Op_ptr op = circ_.get_Op_ptr_from_Vertex(v);
394 261 OpType type = op->get_type();
395
1/2
✓ Branch 1 taken 261 times.
✗ Branch 2 not taken.
 261 hole_in.push_back(e);
396
2/4
✓ Branch 1 taken 261 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 261 times.
✗ Branch 5 not taken.
 261 hole_out.push_back(circ_.get_next_edge(v, e));
397
1/2
✓ Branch 1 taken 261 times.
✗ Branch 2 not taken.
 261 bin.insert(v);
398
1/2
✓ Branch 2 taken 261 times.
✗ Branch 3 not taken.
 261 Expr beta = betas[i];
399
3/4
✓ Branch 0 taken 85 times.
✓ Branch 1 taken 176 times.
✓ Branch 2 taken 85 times.
✗ Branch 3 not taken.
1/2
✓ Decision 'true' taken 261 times.
✗ Decision 'false' not taken.
 261 if (type == OpType::NPhasedX || type == OpType::PhasedX) {
400
2/4
✓ Branch 2 taken 261 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 261 times.
✗ Branch 7 not taken.
 261 Expr alpha = op->get_params()[1];
401
3/4
✓ Branch 1 taken 261 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 241 times.
✓ Branch 4 taken 20 times.
2/2
✓ Decision 'true' taken 241 times.
✓ Decision 'false' taken 20 times.
 261 if (!equiv_0(alpha, 2)) {
402
3/6
✓ Branch 3 taken 241 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 241 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 241 times.
✗ Branch 10 not taken.
 241 sub1.add_op<unsigned>(OpType::Rz, {-alpha}, {i});
403
2/4
✓ Branch 3 taken 241 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 241 times.
✗ Branch 7 not taken.
 241 sub3.add_op<unsigned>(OpType::Rz, {alpha}, {i});
404 }
405 261 }
406
2/4
✓ Branch 1 taken 261 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 261 times.
✗ Branch 4 not taken.
1/2
✓ Decision 'true' taken 261 times.
✗ Decision 'false' not taken.
 261 if (!equiv_0(beta, 2)) {
407
2/4
✓ Branch 3 taken 261 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 261 times.
✗ Branch 7 not taken.
 261 sub2.add_op<unsigned>(OpType::Rz, {beta}, {i});
408
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ } else if (!equiv_0(beta, 4)) {
409 ✗ sub2.add_phase(-1);
410 }
411 261 } else {
412 151 Edge interval_begin = intervals_[i].first;
413
1/2
✓ Branch 1 taken 151 times.
✗ Branch 2 not taken.
 151 hole_in.push_back(interval_begin);
414
1/2
✓ Branch 1 taken 151 times.
✗ Branch 2 not taken.
 151 hole_out.push_back(interval_begin);
415 }
416 }
417
418
2/4
✓ Branch 2 taken 113 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 113 times.
✗ Branch 6 not taken.
 113 Circuit sub(circ_.n_qubits());
419
1/2
✓ Branch 1 taken 113 times.
✗ Branch 2 not taken.
 113 sub.append(sub1);
420
7/14
✓ Branch 2 taken 113 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 113 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 113 times.
✗ Branch 9 not taken.
✓ Branch 12 taken 113 times.
✗ Branch 13 not taken.
✓ Branch 15 taken 113 times.
✗ Branch 16 not taken.
✓ Branch 19 taken 226 times.
✓ Branch 20 taken 113 times.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
 339 sub.add_op(OpType::NPhasedX, {-0.5, 0.5}, sub.all_qubits());
421
1/2
✓ Branch 1 taken 113 times.
✗ Branch 2 not taken.
 113 sub.append(sub2);
422
7/14
✓ Branch 2 taken 113 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 113 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 113 times.
✗ Branch 9 not taken.
✓ Branch 12 taken 113 times.
✗ Branch 13 not taken.
✓ Branch 15 taken 113 times.
✗ Branch 16 not taken.
✓ Branch 19 taken 226 times.
✓ Branch 20 taken 113 times.
✗ Branch 26 not taken.
✗ Branch 27 not taken.
 339 sub.add_op(OpType::NPhasedX, {0.5, 0.5}, sub.all_qubits());
423
1/2
✓ Branch 1 taken 113 times.
✗ Branch 2 not taken.
 113 sub.append(sub3);
424
1/2
✓ Branch 1 taken 113 times.
✗ Branch 2 not taken.
 113 Subcircuit hole{hole_in, hole_out, bin};
425
426
1/2
✓ Branch 1 taken 113 times.
✗ Branch 2 not taken.
 113 BackupIntervals backup = backup_intervals();
427
1/2
✓ Branch 1 taken 113 times.
✗ Branch 2 not taken.
 113 circ_.substitute(sub, hole, Circuit::VertexDeletion::Yes);
428
1/2
✓ Branch 1 taken 113 times.
✗ Branch 2 not taken.
 113 restore_intervals(backup);
429
430
1/2
✓ Branch 1 taken 113 times.
✗ Branch 2 not taken.
 113 skip_global_gates(2);
431 113 }
432
433 192 bool all_nullopt(const OptVertexVec& vec) {
434
2/2
✓ Branch 5 taken 354 times.
✓ Branch 6 taken 100 times.
2/2
✓ Decision 'true' taken 354 times.
✓ Decision 'false' taken 100 times.
 454 for (const OptVertex& v : vec) {
435
2/2
✓ Branch 1 taken 92 times.
✓ Branch 2 taken 262 times.
2/2
✓ Decision 'true' taken 100 times.
✓ Decision 'false' taken 254 times.
 354 if (v) return false;
436 }
437 100 return true;
438 }
439
440 } // namespace Transforms
441
442 } // namespace tket
443