GCC Code Coverage Report

Directory: ./
File: Transformations/ThreeQubitSquash.cpp
Date: 2022-10-15 05:10:18
Exec Total Coverage
Lines: 200 203 98.5%
Functions: 24 24 100.0%
Branches: 163 255 63.9%
Decisions: 14 14 100.0%
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 "ThreeQubitSquash.hpp"
16
17 #include <algorithm>
18 #include <array>
19 #include <iostream>
20 #include <iterator>
21 #include <memory>
22 #include <numeric>
23 #include <set>
24 #include <string>
25 #include <tkassert/Assert.hpp>
26
27 #include "BasicOptimisation.hpp"
28 #include "Circuit/CircUtils.hpp"
29 #include "Circuit/Circuit.hpp"
30 #include "Circuit/DAGDefs.hpp"
31 #include "Circuit/ThreeQubitConversion.hpp"
32 #include "Decomposition.hpp"
33 #include "OpType/EdgeType.hpp"
34 #include "OpType/OpType.hpp"
35 #include "OptimisationPass.hpp"
36 #include "Transform.hpp"
37 #include "Utils/GraphHeaders.hpp"
38
39 namespace tket {
40
41 namespace Transforms {
42
43 // Helper class defining a pure-quantum subcircuit of up to 3 qubits.
44 class QInteraction {
45 public:
46 // Construct an empty subcircuit with a single edge that is both input and
47 // output, and no vertices.
48 423 QInteraction(const Circuit &circ, const Edge &e) : circ_(circ) {
49
1/2
✓ Branch 1 taken 423 times.
✗ Branch 2 not taken.
 423 in_edges_.push_back(e);
50
1/2
✓ Branch 1 taken 423 times.
✗ Branch 2 not taken.
 423 out_edges_.push_back(e);
51 423 n_wires_ = 1;
52 423 }
53
54 // Combine with another subcircuit disjoint from this. Disjointness, and the
55 // fact that the combined subcircuit has at most three wires, is assumed.
56 237 void combine(const QInteraction &other) {
57
1/2
✓ Branch 4 taken 237 times.
✗ Branch 5 not taken.
 474 in_edges_.insert(
58 237 in_edges_.end(), other.in_edges_.begin(), other.in_edges_.end());
59
1/2
✓ Branch 4 taken 237 times.
✗ Branch 5 not taken.
 474 out_edges_.insert(
60 237 out_edges_.end(), other.out_edges_.begin(), other.out_edges_.end());
61 237 n_wires_ += other.n_wires_;
62 237 vertices_.insert(other.vertices_.begin(), other.vertices_.end());
63 237 }
64
65 3270 EdgeVec out_edges() const { return out_edges_; }
66
67 15 VertexSet vertices() const { return vertices_; }
68
69 1971 unsigned n_wires() const { return n_wires_; }
70
71 200 unsigned n_vertices() const { return vertices_.size(); }
72
73 142 Subcircuit subcircuit() const { return {in_edges_, out_edges_, vertices_}; }
74
75 // Append a vertex following the subcircuit. It is assumed that every input
76 // edge of the vertex matches exactly one output edge of the existing
77 // subcircuit.
78 1348 void append(const Vertex &v) {
79
1/2
✓ Branch 1 taken 1348 times.
✗ Branch 2 not taken.
 1348 EdgeVec v_ins = circ_.get_in_edges_of_type(v, EdgeType::Quantum);
80
1/2
✓ Branch 1 taken 1348 times.
✗ Branch 2 not taken.
 1348 EdgeVec v_outs = circ_.get_out_edges_of_type(v, EdgeType::Quantum);
81 1348 unsigned n = v_ins.size();
82 TKET_ASSERT(n == v_outs.size());
83 TKET_ASSERT(n <= n_wires_);
84
2/2
✓ Branch 0 taken 1864 times.
✓ Branch 1 taken 1348 times.
2/2
✓ Decision 'true' taken 1864 times.
✓ Decision 'false' taken 1348 times.
 3212 for (unsigned i = 0; i < n; i++) {
85 1864 Edge e_new_0 = v_ins[i];
86 1864 Edge e_new_1 = v_outs[i];
87 1864 bool matched = false;
88
2/2
✓ Branch 0 taken 4782 times.
✓ Branch 1 taken 1864 times.
2/2
✓ Decision 'true' taken 4782 times.
✓ Decision 'false' taken 1864 times.
 6646 for (unsigned j = 0; j < n_wires_; j++) {
89
3/4
✓ Branch 2 taken 4782 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1864 times.
✓ Branch 5 taken 2918 times.
2/2
✓ Decision 'true' taken 1864 times.
✓ Decision 'false' taken 2918 times.
 4782 if (out_edges_[j] == e_new_0) {
90 TKET_ASSERT(!matched);
91 1864 out_edges_[j] = e_new_1;
92 1864 matched = true;
93 }
94 }
95 TKET_ASSERT(matched);
96 }
97
1/2
✓ Branch 1 taken 1348 times.
✗ Branch 2 not taken.
 1348 vertices_.insert(v);
98 1348 }
99
100 private:
101 const Circuit &circ_;
102 EdgeVec in_edges_;
103 EdgeVec out_edges_;
104 unsigned n_wires_; // number of in/out edge pairs
105 VertexSet vertices_; // all internal vertices
106 };
107
108 typedef std::unique_ptr<QInteraction> iptr;
109
110 // Candidate substitution for a 2- or 3-qubit circuit.
111 142 static Circuit candidate_sub(const Circuit &circ, OpType target_2qb_gate) {
112 142 unsigned n_qb = circ.n_qubits();
113
2/2
✓ Branch 0 taken 47 times.
✓ Branch 1 taken 95 times.
2/2
✓ Decision 'true' taken 47 times.
✓ Decision 'false' taken 95 times.
 142 if (n_qb == 2) {
114
2/4
✓ Branch 1 taken 47 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 47 times.
✗ Branch 5 not taken.
 47 Circuit repl = two_qubit_canonical(get_matrix_from_2qb_circ(circ));
115 // TODO Remove this once `clifford_simp` supports TK2.
116
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 17 times.
2/2
✓ Decision 'true' taken 30 times.
✓ Decision 'false' taken 17 times.
 47 if (target_2qb_gate == OpType::CX) {
117
2/4
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 30 times.
✗ Branch 5 not taken.
 30 clifford_simp(false).apply(repl);
118 }
119
1/2
✓ Branch 1 taken 47 times.
✗ Branch 2 not taken.
 47 return repl;
120 47 } else {
121 TKET_ASSERT(n_qb == 3);
122
1/2
✓ Branch 1 taken 95 times.
✗ Branch 2 not taken.
 95 Eigen::MatrixXcd U = get_3q_unitary(circ);
123
2/2
✓ Branch 0 taken 59 times.
✓ Branch 1 taken 36 times.
2/2
✓ Decision 'true' taken 59 times.
✓ Decision 'false' taken 36 times.
 95 if (target_2qb_gate == OpType::CX) {
124
1/2
✓ Branch 1 taken 59 times.
✗ Branch 2 not taken.
 59 Circuit repl = three_qubit_synthesis(U);
125
2/4
✓ Branch 1 taken 59 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 59 times.
✗ Branch 5 not taken.
 59 normalise_TK2().apply(repl);
126
2/4
✓ Branch 1 taken 59 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 59 times.
✗ Branch 5 not taken.
 59 decompose_TK2().apply(repl);
127
2/4
✓ Branch 1 taken 59 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 59 times.
✗ Branch 5 not taken.
 59 clifford_simp(false).apply(repl);
128
2/4
✓ Branch 1 taken 59 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 59 times.
✗ Branch 5 not taken.
 59 squash_1qb_to_tk1().apply(repl);
129
1/2
✓ Branch 1 taken 59 times.
✗ Branch 2 not taken.
 59 return repl;
130 59 } else {
131 TKET_ASSERT(target_2qb_gate == OpType::TK2);
132
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 Circuit repl = three_qubit_tk_synthesis(U);
133
2/4
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 36 times.
✗ Branch 5 not taken.
 36 squash_1qb_to_tk1().apply(repl);
134
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 return repl;
135 36 }
136 95 }
137 }
138
139 // Helper class representing a system of disjoint interactions, each with at
140 // most three qubits. The interactions are represented by integer labels.
141 class QISystem {
142 public:
143 // Construct an empty system.
144 39 explicit QISystem(Circuit &circ, OpType target_2qb_gate)
145 39 : circ_(circ),
146 39 target_2qb_gate_(target_2qb_gate),
147 39 bin_(),
148 39 interactions_(),
149 39 idx_(0) {}
150
151 // Add a new interaction to the system consisting of a single edge, and
152 // return its index.
153 423 int create_new_interaction_from_edge(const Edge &e) {
154 TKET_ASSERT(!interactions_.contains(idx_));
155
1/2
✓ Branch 2 taken 423 times.
✗ Branch 3 not taken.
 423 interactions_[idx_] = std::make_unique<QInteraction>(circ_, e);
156 423 return idx_++;
157 }
158
159 // Return the set of (indices of) interactions in the system that have v as a
160 // direct successor.
161 1464 std::vector<int> interactions_feeding_vertex(const Vertex &v) const {
162
1/2
✓ Branch 1 taken 1464 times.
✗ Branch 2 not taken.
 1464 EdgeVec edges = circ_.get_in_edges_of_type(v, EdgeType::Quantum);
163 1464 std::vector<int> meets;
164
2/2
✓ Branch 7 taken 3084 times.
✓ Branch 8 taken 1464 times.
2/2
✓ Decision 'true' taken 3084 times.
✓ Decision 'false' taken 1464 times.
 4548 for (const auto &[i, I] : interactions_) {
165
1/2
✓ Branch 2 taken 3084 times.
✗ Branch 3 not taken.
 3084 EdgeVec I_outs = I->out_edges();
166
1/2
✓ Branch 3 taken 3084 times.
✗ Branch 4 not taken.
 3084 EdgeSet I_outset = {I_outs.begin(), I_outs.end()};
167
3/4
✓ Branch 3 taken 3084 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 1801 times.
✓ Branch 6 taken 1283 times.
 3084 if (std::any_of(edges.begin(), edges.end(), [&I_outset](const Edge &e) {
168 3933 return I_outset.contains(e);
169 })) {
170
1/2
✓ Branch 1 taken 1801 times.
✗ Branch 2 not taken.
 1801 meets.push_back(i);
171 }
172 3084 }
173 2928 return meets;
174 1464 }
175
176 // The total width (number of wires) of a subset of the interactions.
177 1448 unsigned total_n_wires(const std::vector<int> &S) const {
178 1448 unsigned total = 0;
179
2/2
✓ Branch 4 taken 1785 times.
✓ Branch 5 taken 1448 times.
 3233 for (int i : S) {
180
1/2
✓ Branch 1 taken 1785 times.
✗ Branch 2 not taken.
 1785 total += interactions_.at(i)->n_wires();
181 }
182 1448 return total;
183 }
184
185 // From a set of indices, choose the one indexing the largest interaction,
186 // in terms of vertex count.
187 100 int largest_interaction(const std::vector<int> &S) const {
188 100 return *std::max_element(
189 200 S.begin(), S.end(), [this](const int &i0, const int &i1) {
190 100 return interactions_.at(i0)->n_vertices() <
191 100 interactions_.at(i1)->n_vertices();
192 100 });
193 }
194
195 // Combine a set of existing interactions into one and append the vertex v.
196 // It is assumed that the interactions are combinable and the vertex
197 // appendable.
198 1348 void combine_and_append(const std::vector<int> &S, const Vertex &v) {
199 1348 unsigned N = S.size();
200 TKET_ASSERT(N > 0);
201 1348 iptr &I = interactions_.at(S[0]);
202
2/2
✓ Branch 0 taken 237 times.
✓ Branch 1 taken 1348 times.
 1585 for (unsigned i = 1; i < N; i++) {
203 237 I->combine(*interactions_.at(S[i]));
204 237 interactions_.erase(S[i]);
205 }
206 1348 I->append(v);
207 1348 }
208
209 // Close an interaction, squashing it if possible, and erasing it from the
210 // set. Return true iff any substitution was made, and the (possibly new)
211 // vector of outgoing edges from the region of the interaction.
212 186 std::pair<bool, EdgeVec> close_interaction(int i) {
213
1/2
✓ Branch 1 taken 186 times.
✗ Branch 2 not taken.
 186 iptr &I = interactions_.at(i);
214 186 bool changed = false;
215
1/2
✓ Branch 2 taken 186 times.
✗ Branch 3 not taken.
 186 EdgeVec outs = I->out_edges();
216
2/3
✓ Branch 2 taken 44 times.
✓ Branch 3 taken 142 times.
✗ Branch 4 not taken.
 186 switch (I->n_wires()) {
217 44 case 1:
218 44 break;
219 142 case 2:
220 case 3: {
221
1/2
✓ Branch 2 taken 142 times.
✗ Branch 3 not taken.
 142 Subcircuit sub = I->subcircuit();
222
1/2
✓ Branch 1 taken 142 times.
✗ Branch 2 not taken.
 142 Circuit subc = circ_.subcircuit(sub);
223
1/2
✓ Branch 1 taken 142 times.
✗ Branch 2 not taken.
 142 Circuit replacement = candidate_sub(subc, target_2qb_gate_);
224
1/2
✓ Branch 1 taken 142 times.
✗ Branch 2 not taken.
 142 if (replacement.count_gates(target_2qb_gate_) <
225
3/4
✓ Branch 1 taken 142 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 15 times.
✓ Branch 4 taken 127 times.
 142 subc.count_gates(target_2qb_gate_)) {
226 // 1. Collect data needed later to reconstruct the list of out-edges:
227 15 std::vector<std::pair<Vertex, port_t>> out_vertex_ports;
228
2/2
✓ Branch 4 taken 41 times.
✓ Branch 5 taken 15 times.
 56 for (const Edge &e : outs) {
229
1/2
✓ Branch 1 taken 41 times.
✗ Branch 2 not taken.
 41 out_vertex_ports.push_back(
230
2/4
✓ Branch 1 taken 41 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 41 times.
✗ Branch 5 not taken.
 82 {circ_.target(e), circ_.get_target_port(e)});
231 }
232 // 2. Do the substitution:
233
1/2
✓ Branch 2 taken 15 times.
✗ Branch 3 not taken.
 15 VertexSet old_vertices = I->vertices();
234
1/2
✓ Branch 5 taken 15 times.
✗ Branch 6 not taken.
 15 bin_.insert(bin_.end(), old_vertices.begin(), old_vertices.end());
235
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 circ_.substitute(replacement, sub, Circuit::VertexDeletion::No);
236 // 3. Construct the new list of out-edges:
237 15 EdgeVec new_outs;
238
2/2
✓ Branch 6 taken 41 times.
✓ Branch 7 taken 15 times.
 56 for (const auto &[v, p] : out_vertex_ports) {
239
2/4
✓ Branch 1 taken 41 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 41 times.
✗ Branch 5 not taken.
 41 new_outs.push_back(circ_.get_nth_in_edge(v, p));
240 }
241 15 changed = true;
242 15 outs = std::move(new_outs);
243 15 }
244 142 break;
245 142 }
246 ✗ default:
247 TKET_ASSERT(!"Interaction with invalid number of wires");
248 }
249
1/2
✓ Branch 1 taken 186 times.
✗ Branch 2 not taken.
 186 interactions_.erase(i);
250
1/2
✓ Branch 1 taken 186 times.
✗ Branch 2 not taken.
 372 return {changed, outs};
251 186 }
252
253 // Close an interaction and spawn new ones on its outgoing edges. Return true
254 // iff any substitution is made.
255 100 bool close_interaction_and_spawn(int i) {
256
1/2
✓ Branch 1 taken 100 times.
✗ Branch 2 not taken.
 100 auto [changed, outs] = close_interaction(i);
257
2/2
✓ Branch 5 taken 280 times.
✓ Branch 6 taken 100 times.
 380 for (const Edge &e : outs) {
258
1/2
✓ Branch 1 taken 280 times.
✗ Branch 2 not taken.
 280 create_new_interaction_from_edge(e);
259 }
260 100 return changed;
261 100 }
262
263 // Close all interactions that have v as a direct successor, and start new
264 // ones following them. Return true iff any substitution is made.
265 16 bool close_interactions_feeding_vertex(const Vertex &v) {
266 16 bool changed = false;
267
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 std::vector<int> v_interactions = interactions_feeding_vertex(v);
268
269
2/2
✓ Branch 5 taken 16 times.
✓ Branch 6 taken 16 times.
 32 for (int i : v_interactions) {
270
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 auto [change, outs] = close_interaction(i);
271 16 changed |= change;
272
2/2
✓ Branch 5 taken 32 times.
✓ Branch 6 taken 16 times.
 48 for (const Edge &e : outs) {
273
3/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 13 times.
✓ Branch 4 taken 19 times.
 32 if (circ_.target(e) != v) {
274
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 create_new_interaction_from_edge(e);
275 }
276 }
277 16 }
278
279
3/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 19 times.
✓ Branch 9 taken 16 times.
 35 for (const Edge &e : circ_.get_out_edges_of_type(v, EdgeType::Quantum)) {
280
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 create_new_interaction_from_edge(e);
281 16 }
282
283 16 return changed;
284 16 }
285
286 // Close all interactions. Return true iff any substitution is made.
287 39 bool close_all_interactions() {
288 39 bool changed = false;
289 // Form set of keys.
290 39 std::set<int> indices;
291
2/2
✓ Branch 5 taken 70 times.
✓ Branch 6 taken 39 times.
 109 for (const auto &pair : interactions_) {
292
1/2
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
 70 indices.insert(pair.first);
293 }
294 // Close each one.
295
2/2
✓ Branch 5 taken 70 times.
✓ Branch 6 taken 39 times.
 109 for (int i : indices) {
296
1/2
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
 70 auto [change, outs] = close_interaction(i);
297 70 changed |= change;
298 70 }
299 39 return changed;
300 39 }
301
302 // Delete all vertices marked for deletion.
303 39 void destroy_bin() {
304 39 circ_.remove_vertices(
305 39 bin_, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
306 39 }
307
308 private:
309 Circuit &circ_;
310 OpType target_2qb_gate_;
311 VertexList bin_;
312 std::map<int, iptr> interactions_;
313 int idx_;
314 };
315
316 40 Transform three_qubit_squash(OpType target_2qb_gate) {
317 555 return Transform([target_2qb_gate](Circuit &circ) {
318 39 bool changed = false;
319
320 // Step through the vertices in topological order.
321 39 QISystem Is(circ, target_2qb_gate); // set of "live" interactions
322
3/4
✓ Branch 1 taken 39 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 1604 times.
✓ Branch 9 taken 39 times.
 1643 for (const Vertex &v : circ.vertices_in_order()) {
323
1/2
✓ Branch 1 taken 1604 times.
✗ Branch 2 not taken.
 1604 const EdgeVec v_q_ins = circ.get_in_edges_of_type(v, EdgeType::Quantum);
324
1/2
✓ Branch 1 taken 1604 times.
✗ Branch 2 not taken.
 1604 const EdgeVec v_q_outs = circ.get_out_edges_of_type(v, EdgeType::Quantum);
325 1604 unsigned n_q_ins = v_q_ins.size();
326 1604 unsigned n_q_outs = v_q_outs.size();
327
328 // If v has no quantum wires, ignore it and move on.
329
4/4
✓ Branch 0 taken 129 times.
✓ Branch 1 taken 1475 times.
✓ Branch 2 taken 18 times.
✓ Branch 3 taken 111 times.
 1604 if (n_q_ins == 0 && n_q_outs == 0) continue;
330
331 // If v is initial, create an interaction from its out-edge, and move on.
332
2/2
✓ Branch 0 taken 111 times.
✓ Branch 1 taken 1475 times.
 1586 if (n_q_ins == 0) {
333 TKET_ASSERT(n_q_outs == 1);
334
1/2
✓ Branch 2 taken 111 times.
✗ Branch 3 not taken.
 111 Is.create_new_interaction_from_edge(v_q_outs[0]);
335 111 continue;
336 111 }
337
338 // If v is final, ignore it and move on.
339
2/2
✓ Branch 0 taken 111 times.
✓ Branch 1 taken 1364 times.
 1475 if (n_q_outs == 0) continue;
340
341 // It's an internal operation with >0 quantum wires.
342 TKET_ASSERT(n_q_ins == n_q_outs);
343
344
1/2
✓ Branch 1 taken 1364 times.
✗ Branch 2 not taken.
 1364 Op_ptr op = circ.get_Op_ptr_from_Vertex(v);
345 1364 OpType optype = op->get_type();
346
347 // If there are any incoming classical wires, or if this is a Barrier or
348 // Reset or Collapse operation, or if the operation contains symbols,
349 // close all existing interactions meeting v and create new ones, then
350 // move on.
351
2/4
✓ Branch 1 taken 16 times.
✓ Branch 2 taken 1348 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
 1364 if (!circ.get_in_edges_of_type(v, EdgeType::Classical).empty() ||
352
6/10
✓ Branch 1 taken 1357 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1353 times.
✓ Branch 5 taken 4 times.
✓ Branch 6 taken 1352 times.
✓ Branch 7 taken 1 times.
✓ Branch 9 taken 1364 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
 2721 !circ.get_in_edges_of_type(v, EdgeType::Boolean).empty() ||
353
3/4
✓ Branch 0 taken 1350 times.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 1350 times.
✗ Branch 3 not taken.
 1352 optype == OpType::Barrier || optype == OpType::Reset ||
354
10/14
✓ Branch 1 taken 1364 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1357 times.
✓ Branch 5 taken 7 times.
✓ Branch 8 taken 1350 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 2 times.
✓ Branch 12 taken 1348 times.
✓ Branch 13 taken 1350 times.
✓ Branch 14 taken 14 times.
✓ Branch 16 taken 1357 times.
✓ Branch 17 taken 7 times.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
 2721 optype == OpType::Collapse || !op->free_symbols().empty()) {
355
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 changed |= Is.close_interactions_feeding_vertex(v);
356 16 continue;
357 }
358
359 // The circuit should contain only 1-qubit and CX gates.
360
4/6
✓ Branch 0 taken 516 times.
✓ Branch 1 taken 832 times.
✓ Branch 2 taken 516 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 1348 times.
 1348 if ((n_q_ins == 2 && optype != target_2qb_gate) || (n_q_ins > 2)) {
361 ✗ throw std::invalid_argument(
362 "Three-qubit squash requires circuits with 1-qubit and target "
363 ✗ "2-qubit gates only");
364 }
365
366 // Absorb v into existing interactions, closing or merging as necessary.
367 1348 bool done_with_v = false;
368
2/2
✓ Branch 0 taken 1448 times.
✓ Branch 1 taken 1348 times.
 2796 while (!done_with_v) {
369
1/2
✓ Branch 1 taken 1448 times.
✗ Branch 2 not taken.
 1448 std::vector<int> v_Is = Is.interactions_feeding_vertex(v);
370
1/2
✓ Branch 1 taken 1448 times.
✗ Branch 2 not taken.
 1448 unsigned total_n_wires = Is.total_n_wires(v_Is);
371
2/2
✓ Branch 0 taken 1348 times.
✓ Branch 1 taken 100 times.
 1448 if (total_n_wires <= 3) {
372
1/2
✓ Branch 1 taken 1348 times.
✗ Branch 2 not taken.
 1348 Is.combine_and_append(v_Is, v);
373 1348 done_with_v = true;
374 } else {
375 // Close one of the interactions meeting v.
376
1/2
✓ Branch 1 taken 100 times.
✗ Branch 2 not taken.
 100 int i = Is.largest_interaction(v_Is);
377
1/2
✓ Branch 1 taken 100 times.
✗ Branch 2 not taken.
 100 changed |= Is.close_interaction_and_spawn(i);
378 }
379 1448 }
380
6/6
✓ Branch 1 taken 1348 times.
✓ Branch 2 taken 16 times.
✓ Branch 4 taken 1348 times.
✓ Branch 5 taken 256 times.
✓ Branch 7 taken 1348 times.
✓ Branch 8 taken 256 times.
 1915 }
381
382 // Close all remaining interactions.
383
1/2
✓ Branch 1 taken 39 times.
✗ Branch 2 not taken.
 39 changed |= Is.close_all_interactions();
384
385 // Delete removed vertices.
386
1/2
✓ Branch 1 taken 39 times.
✗ Branch 2 not taken.
 39 Is.destroy_bin();
387
388 39 return changed;
389
1/2
✓ Branch 2 taken 40 times.
✗ Branch 3 not taken.
 79 });
390 }
391
392 } // namespace Transforms
393
394 } // namespace tket
395