GCC Code Coverage Report

Directory: ./
File: Mapping/MappingFrontier.cpp
Date: 2022-10-15 05:10:18
Warnings: 6 unchecked decisions!
Exec Total Coverage
Lines: 426 449 94.9%
Functions: 21 21 100.0%
Branches: 476 878 54.2%
Decisions: 14 28 50.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 "Mapping/MappingFrontier.hpp"
16
17 #include "Circuit/Circuit.hpp"
18 #include "Utils/UnitID.hpp"
19
20 namespace tket {
21
22 /**
23 * unit_vertport_frontier_t is <UnitID, VertPort>, helper function returns
24 * UnitID corresponding to given VertPort
25 */
26 27975 UnitID get_unitid_from_unit_frontier(
27 const std::shared_ptr<unit_vertport_frontier_t>& u_frontier,
28 const VertPort& vp) {
29
1/2
✓ Branch 3 taken 27975 times.
✗ Branch 4 not taken.
 27975 auto it = u_frontier->get<TagValue>().find(vp);
30
3/6
✓ Branch 4 taken 27975 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 27975 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 27975 times.
✗ Branch 10 not taken.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 55950 times.
 55950 if (it != u_frontier->get<TagValue>().end()) return it->first;
31 ✗ throw MappingFrontierError(
32 ✗ std::string("Edge provided not in unit_frontier_t object."));
33 }
34
35 /**
36 * bit_frontier_t is <Bit, EdgeVec>, helper function returns
37 * Bit corresponding to given Edge
38 */
39 1932 static Bit get_bit_from_bool_frontier(
40 const std::shared_ptr<b_frontier_t>& b_frontier, const EdgeVec& ev) {
41 TKET_ASSERT(ev.size() > 0);
42 // condition is that if one Edge in EdgeVector ev is in a
43 // held bundle, then all are so return true
44 1932 for (auto it = b_frontier->get<TagKey>().begin();
45
3/6
✓ Branch 1 taken 7524 times.
✗ Branch 2 not taken.
✓ Branch 7 taken 9456 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 9456 times.
✗ Branch 10 not taken.
 9456 it != b_frontier->get<TagKey>().end(); ++it) {
46
2/2
✓ Branch 5 taken 9456 times.
✓ Branch 6 taken 7524 times.
2/2
✓ Decision 'true' taken 9456 times.
✓ Decision 'false' taken 7524 times.
 16980 for (const Edge& e0 : ev) {
47
3/4
✓ Branch 1 taken 9456 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 429236 times.
✓ Branch 9 taken 7524 times.
0/1
? Decision couldn't be analyzed.
 436760 for (const Edge& e1 : it->second) {
48
3/4
✓ Branch 1 taken 429236 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1932 times.
✓ Branch 4 taken 427304 times.
2/2
✓ Decision 'true' taken 1932 times.
✓ Decision 'false' taken 427304 times.
 429236 if (e0 == e1) {
49
1/2
✓ Branch 1 taken 1932 times.
✗ Branch 2 not taken.
 1932 return it->first;
50 }
51 }
52 }
53 }
54 ✗ throw MappingFrontierError(
55 ✗ std::string("EdgeVec provided not in b_frontier_t object."));
56 }
57
58 29586 std::shared_ptr<unit_frontier_t> frontier_convert_vertport_to_edge(
59 const Circuit& circuit,
60 const std::shared_ptr<unit_vertport_frontier_t>& u_frontier) {
61 // make empty unit_frontier_t object
62 std::shared_ptr<unit_frontier_t> output_frontier =
63 29586 std::make_shared<unit_frontier_t>();
64 // iterate through u_frontier, convert VertPort to Edge and insert
65
4/6
✓ Branch 5 taken 1038592 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 1068178 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 1038592 times.
✓ Branch 11 taken 29586 times.
0/1
? Decision couldn't be analyzed.
 1068178 for (const std::pair<UnitID, VertPort>& pair : u_frontier->get<TagKey>()) {
66
1/2
✓ Branch 3 taken 1038592 times.
✗ Branch 4 not taken.
 2077184 output_frontier->insert(
67 1038592 {pair.first,
68
2/4
✓ Branch 1 taken 1038592 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1038592 times.
✗ Branch 5 not taken.
 2077184 circuit.get_nth_out_edge(pair.second.first, pair.second.second)});
69 }
70 29586 return output_frontier;
71 }
72
73 /**
74 * Initialise linear_boundary and boolean_boundary from
75 * out edges of Input vertices
76 */
77 115 MappingFrontier::MappingFrontier(Circuit& _circuit) : circuit_(_circuit) {
78
1/2
✓ Branch 1 taken 115 times.
✗ Branch 2 not taken.
 115 this->linear_boundary = std::make_shared<unit_vertport_frontier_t>();
79
1/2
✓ Branch 1 taken 115 times.
✗ Branch 2 not taken.
 115 this->boolean_boundary = std::make_shared<b_frontier_t>();
80
1/2
✓ Branch 1 taken 115 times.
✗ Branch 2 not taken.
 115 this->bimaps_ = std::make_shared<unit_bimaps_t>();
81
82 // Set up {UnitID, VertPort} objects for quantum and classical boundaries
83
3/4
✓ Branch 1 taken 115 times.
✗ Branch 2 not taken.
✓ Branch 7 taken 719 times.
✓ Branch 8 taken 115 times.
0/1
? Decision couldn't be analyzed.
 834 for (const Qubit& qb : this->circuit_.all_qubits()) {
84
2/4
✓ Branch 2 taken 719 times.
✗ Branch 3 not taken.
✓ Branch 7 taken 719 times.
✗ Branch 8 not taken.
 719 this->linear_boundary->insert({qb, {this->circuit_.get_in(qb), 0}});
85
2/4
✓ Branch 2 taken 719 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 719 times.
✗ Branch 6 not taken.
 719 this->bimaps_->initial.insert({qb, qb});
86
2/4
✓ Branch 2 taken 719 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 719 times.
✗ Branch 6 not taken.
 719 this->bimaps_->final.insert({qb, qb});
87 115 }
88
3/4
✓ Branch 1 taken 115 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 31 times.
✓ Branch 9 taken 115 times.
0/1
? Decision couldn't be analyzed.
 146 for (const Bit& bit : this->circuit_.all_bits()) {
89
1/2
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
 31 Vertex bit_input = this->circuit_.get_in(bit);
90
1/2
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
 31 EdgeVec bool_bundle = this->circuit_.get_nth_b_out_bundle(bit_input, 0);
91
2/2
✓ Branch 1 taken 21 times.
✓ Branch 2 taken 10 times.
2/2
✓ Decision 'true' taken 21 times.
✓ Decision 'false' taken 10 times.
 31 if (bool_bundle.size() != 0) {
92
2/4
✓ Branch 2 taken 21 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 21 times.
✗ Branch 6 not taken.
 21 this->boolean_boundary->insert({bit, bool_bundle});
93 }
94
2/4
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 31 times.
✗ Branch 4 not taken.
0/1
? Decision couldn't be analyzed.
 31 if (this->circuit_.n_out_edges_of_type(bit_input, EdgeType::Classical) >
95 0) {
96
1/2
✓ Branch 4 taken 31 times.
✗ Branch 5 not taken.
 31 this->linear_boundary->insert({bit, {bit_input, 0}});
97 }
98 146 }
99 115 }
100
101 /**
102 * Initialise linear_boundary and boolean_boundary from
103 * out edges of Input vertices
104 */
105 39 MappingFrontier::MappingFrontier(
106 39 Circuit& _circuit, std::shared_ptr<unit_bimaps_t> _bimaps)
107 39 : circuit_(_circuit), bimaps_(_bimaps) {
108 // Check that the maps are valid
109
3/4
✓ Branch 1 taken 39 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 200 times.
✓ Branch 9 taken 37 times.
 237 for (const Qubit& q : _circuit.all_qubits()) {
110
5/8
✓ Branch 2 taken 200 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 200 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 200 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 2 times.
✓ Branch 12 taken 198 times.
 200 if (_bimaps->initial.right.find(q) == _bimaps->initial.right.end()) {
111
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 throw MappingFrontierError(
112
3/6
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 2 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
 4 "Uid " + q.repr() + " not found in initial map.");
113 }
114
4/8
✓ Branch 2 taken 198 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 198 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 198 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✓ Branch 12 taken 198 times.
 198 if (_bimaps->final.right.find(q) == _bimaps->final.right.end()) {
115 ✗ throw MappingFrontierError(
116 ✗ "Uid " + q.repr() + " not found in final map.");
117 }
118 39 }
119
120
1/2
✓ Branch 1 taken 37 times.
✗ Branch 2 not taken.
 37 this->linear_boundary = std::make_shared<unit_vertport_frontier_t>();
121
1/2
✓ Branch 1 taken 37 times.
✗ Branch 2 not taken.
 37 this->boolean_boundary = std::make_shared<b_frontier_t>();
122
123 // Set up {UnitID, VertPort} objects for quantum and classical boundaries
124
3/4
✓ Branch 1 taken 37 times.
✗ Branch 2 not taken.
✓ Branch 7 taken 196 times.
✓ Branch 8 taken 37 times.
 233 for (const Qubit& qb : this->circuit_.all_qubits()) {
125
2/4
✓ Branch 2 taken 196 times.
✗ Branch 3 not taken.
✓ Branch 7 taken 196 times.
✗ Branch 8 not taken.
 196 this->linear_boundary->insert({qb, {this->circuit_.get_in(qb), 0}});
126 37 }
127
3/4
✓ Branch 1 taken 37 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 9 times.
✓ Branch 9 taken 37 times.
 46 for (const Bit& bit : this->circuit_.all_bits()) {
128
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 Vertex bit_input = this->circuit_.get_in(bit);
129
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 EdgeVec bool_bundle = this->circuit_.get_nth_b_out_bundle(bit_input, 0);
130
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 9 times.
 9 if (bool_bundle.size() != 0) {
131 ✗ this->boolean_boundary->insert({bit, bool_bundle});
132 } else {
133
1/2
✓ Branch 4 taken 9 times.
✗ Branch 5 not taken.
 9 this->linear_boundary->insert({bit, {bit_input, 0}});
134 }
135 46 }
136 45 }
137
138 2 MappingFrontier::MappingFrontier(const MappingFrontier& mapping_frontier)
139 2 : circuit_(mapping_frontier.circuit_), bimaps_(mapping_frontier.bimaps_) {
140
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 this->linear_boundary = std::make_shared<unit_vertport_frontier_t>();
141
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 this->boolean_boundary = std::make_shared<b_frontier_t>();
142
143 2 for (const std::pair<UnitID, VertPort>& pair :
144
4/6
✓ Branch 5 taken 8 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 10 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 8 times.
✓ Branch 11 taken 2 times.
 12 mapping_frontier.linear_boundary->get<TagKey>()) {
145
2/4
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
✓ Branch 7 taken 8 times.
✗ Branch 8 not taken.
 8 this->linear_boundary->insert({pair.first, pair.second});
146 }
147 2 for (const std::pair<Bit, EdgeVec>& pair :
148
2/8
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✓ Branch 11 taken 2 times.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✓ Branch 14 taken 2 times.
 4 mapping_frontier.boolean_boundary->get<TagKey>()) {
149 ✗ EdgeVec edges;
150 ✗ for (const Edge& edge : pair.second) {
151 ✗ edges.push_back(edge);
152 }
153 ✗ this->boolean_boundary->insert({pair.first, edges});
154 }
155
1/2
✗ Branch 5 not taken.
✓ Branch 6 taken 2 times.
 2 for (const Node& node : mapping_frontier.ancilla_nodes_) {
156 ✗ this->ancilla_nodes_.insert(node);
157 }
158 2 }
159
160 22490 void MappingFrontier::advance_next_2qb_slice(unsigned max_advance) {
161 22490 bool boundary_updated = false;
162 22490 unsigned loop = 0;
163 std::shared_ptr<unit_frontier_t> current_frontier =
164
1/2
✓ Branch 1 taken 22490 times.
✗ Branch 2 not taken.
 22490 frontier_convert_vertport_to_edge(this->circuit_, this->linear_boundary);
165
166 // Get all vertices in first cut
167 VertexVec immediate_cut_vertices_v =
168 22490 *(this->circuit_
169
2/4
✓ Branch 1 taken 22490 times.
✗ Branch 2 not taken.
✓ Branch 6 taken 22490 times.
✗ Branch 7 not taken.
 44980 .next_cut(current_frontier, std::make_shared<b_frontier_t>())
170
1/2
✓ Branch 2 taken 22490 times.
✗ Branch 3 not taken.
 22490 .slice);
171
172 do {
173 // each do section first finds the next set of edges after the held set
174 // for edges with target vertices with all their edges presented in the
175 // first set
176 25928 loop++;
177 25928 boundary_updated = false;
178 // produce next frontier object
179 std::shared_ptr<unit_frontier_t> next_frontier =
180
1/2
✓ Branch 1 taken 25928 times.
✗ Branch 2 not taken.
 25928 std::make_shared<unit_frontier_t>();
181
182 25928 for (const std::pair<UnitID, Edge>& pair :
183
5/8
✓ Branch 5 taken 958521 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 958521 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 984449 times.
✗ Branch 12 not taken.
✓ Branch 13 taken 958521 times.
✓ Branch 14 taken 25928 times.
 1010377 current_frontier->get<TagKey>()) {
184 // if target_v not in immediate_cut_vertices, then do not pass it
185
1/2
✓ Branch 1 taken 958521 times.
✗ Branch 2 not taken.
 958521 Vertex target_v = this->circuit_.target(pair.second);
186 EdgeVec in_edges =
187
1/2
✓ Branch 1 taken 958521 times.
✗ Branch 2 not taken.
 958521 this->circuit_.get_in_edges_of_type(target_v, EdgeType::Quantum);
188
189 bool in_slice =
190
1/2
✓ Branch 3 taken 958521 times.
✗ Branch 4 not taken.
 958521 std::find(
191 immediate_cut_vertices_v.begin(), immediate_cut_vertices_v.end(),
192 1917042 target_v) != immediate_cut_vertices_v.end();
193
1/2
✓ Branch 1 taken 958521 times.
✗ Branch 2 not taken.
 958521 OpType ot = this->circuit_.get_OpType_from_Vertex(target_v);
194
6/6
✓ Branch 1 taken 428239 times.
✓ Branch 2 taken 496562 times.
✓ Branch 3 taken 154096 times.
✓ Branch 4 taken 307863 times.
✓ Branch 5 taken 116662 times.
✓ Branch 6 taken 37434 times.
 958521 if (((!in_slice && in_edges.size() > 1) || ot == OpType::Output ||
195
4/4
✓ Branch 0 taken 924801 times.
✓ Branch 1 taken 33720 times.
✓ Branch 2 taken 921087 times.
✓ Branch 3 taken 37434 times.
 1917042 ot == OpType::ClOutput) &&
196
2/4
✓ Branch 1 taken 921087 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 921087 times.
✗ Branch 4 not taken.
 921087 this->circuit_.get_OpType_from_Vertex(target_v) != OpType::Barrier) {
197 // Vertex either not allowed to pass, or is output vertex => update
198 // nothing
199
1/2
✓ Branch 3 taken 921087 times.
✗ Branch 4 not taken.
 921087 next_frontier->insert({pair.first, pair.second});
200 } else {
201 // vertex can be surpassed, so update linear_boundary and
202 // next_frontier with next edge
203
1/2
✓ Branch 1 taken 37434 times.
✗ Branch 2 not taken.
 37434 Edge next_edge = this->circuit_.get_next_edge(target_v, pair.second);
204
1/2
✓ Branch 3 taken 37434 times.
✗ Branch 4 not taken.
 112302 this->linear_boundary->replace(
205
1/2
✓ Branch 3 taken 37434 times.
✗ Branch 4 not taken.
 37434 this->linear_boundary->get<TagKey>().find(pair.first),
206 37434 {pair.first,
207
1/2
✓ Branch 1 taken 37434 times.
✗ Branch 2 not taken.
 37434 {target_v, this->circuit_.get_source_port(next_edge)}});
208
1/2
✓ Branch 3 taken 37434 times.
✗ Branch 4 not taken.
 37434 next_frontier->insert({pair.first, next_edge});
209 }
210 958521 }
211 // Given new frontier, find the actual next cut
212 25928 CutFrontier next_cut = this->circuit_.next_cut(
213
2/4
✓ Branch 1 taken 25928 times.
✗ Branch 2 not taken.
✓ Branch 6 taken 25928 times.
✗ Branch 7 not taken.
 51856 next_frontier, std::make_shared<b_frontier_t>());
214 // For each vertex in a slice, if its physically permitted, update
215 // linear_boundary with quantum out edges from vertex (i.e.
216 // next_cut.u_frontier)
217
2/2
✓ Branch 6 taken 23568 times.
✓ Branch 7 taken 25928 times.
 49496 for (const Vertex& vert : *next_cut.slice) {
218 // Output means we don't want to pass, so just leave
219
1/2
✓ Branch 1 taken 23568 times.
✗ Branch 2 not taken.
 23568 OpType ot = this->circuit_.get_OpType_from_Vertex(vert);
220
2/4
✓ Branch 0 taken 23568 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 23568 times.
 23568 if (ot == OpType::Output || ot == OpType::ClOutput) {
221 19870 continue;
222 }
223 EdgeVec in_edges =
224
1/2
✓ Branch 1 taken 23568 times.
✗ Branch 2 not taken.
 23568 this->circuit_.get_in_edges_of_type(vert, EdgeType::Quantum);
225 // More than 1 edge means we want to keep edges, so continue
226
2/2
✓ Branch 1 taken 19870 times.
✓ Branch 2 taken 3698 times.
 23568 if (in_edges.size() > 1) {
227 19870 continue;
228 }
229 // can guarantee that we update now as non-updating cases have been
230 // continued
231 3698 boundary_updated = true;
232 // push edge past single qubit vertex, repeat
233 UnitID uid = get_unitid_from_unit_frontier(
234
1/2
✓ Branch 2 taken 3698 times.
✗ Branch 3 not taken.
 3698 this->linear_boundary, {this->circuit_.source(in_edges[0]),
235
2/4
✓ Branch 2 taken 3698 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 3698 times.
✗ Branch 7 not taken.
 3698 this->circuit_.get_source_port(in_edges[0])});
236
237 Edge replacement_edge =
238
2/4
✓ Branch 3 taken 3698 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 3698 times.
✗ Branch 7 not taken.
 3698 next_cut.u_frontier->get<TagKey>().find(uid)->second;
239
240
1/2
✓ Branch 1 taken 3698 times.
✗ Branch 2 not taken.
 3698 Vertex source_vertex = this->circuit_.source(replacement_edge);
241
1/2
✓ Branch 1 taken 3698 times.
✗ Branch 2 not taken.
 3698 port_t source_port = this->circuit_.get_source_port(replacement_edge);
242
243
2/4
✓ Branch 4 taken 3698 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 3698 times.
✗ Branch 8 not taken.
 7396 this->linear_boundary->replace(
244 3698 this->linear_boundary->get<TagKey>().find(uid),
245 {uid, {source_vertex, source_port}});
246
2/2
✓ Branch 2 taken 3698 times.
✓ Branch 3 taken 19870 times.
 23568 }
247 25928 current_frontier = next_frontier;
248
3/4
✓ Branch 2 taken 3438 times.
✓ Branch 3 taken 22490 times.
✓ Branch 4 taken 3438 times.
✗ Branch 5 not taken.
0/1
? Decision couldn't be analyzed.
 25928 } while (boundary_updated && loop <= max_advance);
249 44980 return;
250 22490 }
251
252 /**
253 * advance_frontier_boundary
254 * terminates when next_cut returns a "slice" where
255 * no vertices are physically permitted by the architecture
256 * linear_boundary and boolean_boundary updated to reflect this
257 */
258 3092 void MappingFrontier::advance_frontier_boundary(
259 const ArchitecturePtr& architecture) {
260 3092 bool boundary_updated = false;
261
2/2
✓ Branch 0 taken 3800 times.
✓ Branch 1 taken 3092 times.
 6892 do {
262 // next_cut.slice vertices in_edges from this->linear_boundary
263 6892 boundary_updated = false;
264 std::shared_ptr<unit_frontier_t> l_frontier_edges =
265 frontier_convert_vertport_to_edge(
266
1/2
✓ Branch 1 taken 6892 times.
✗ Branch 2 not taken.
 6892 this->circuit_, this->linear_boundary);
267
268 CutFrontier next_cut =
269
1/2
✓ Branch 3 taken 6892 times.
✗ Branch 4 not taken.
 13784 this->circuit_.next_cut(l_frontier_edges, this->boolean_boundary);
270 // For each vertex in a slice, if its physically permitted, update
271 // linear_boundary with quantum out edges from vertex (i.e.
272 // next_cut.u_frontier)
273 // update boolean_boundary in line
274
2/2
✓ Branch 6 taken 12516 times.
✓ Branch 7 taken 6892 times.
2/2
✓ Decision 'true' taken 12516 times.
✓ Decision 'false' taken 6892 times.
 19408 for (const Vertex& vert : *next_cut.slice) {
275 // for each boolean edge into vertex, collect associated Bit and port
276 // number n.b. a single Bit may have multiple "in bundles" to different
277 // vertices in the same cut
278 12516 std::map<Bit, port_t> bool_uid_port_set;
279
1/2
✓ Branch 1 taken 12516 times.
✗ Branch 2 not taken.
 12516 std::vector<EdgeVec> b_in_bundles = this->circuit_.get_b_in_bundles(vert);
280
2/2
✓ Branch 1 taken 26209 times.
✓ Branch 2 taken 12516 times.
2/2
✓ Decision 'true' taken 26209 times.
✓ Decision 'false' taken 12516 times.
 38725 for (unsigned i = 0; i < b_in_bundles.size(); i++) {
281
1/2
✓ Branch 2 taken 26209 times.
✗ Branch 3 not taken.
 26209 EdgeVec ev = b_in_bundles[i];
282
2/2
✓ Branch 1 taken 1932 times.
✓ Branch 2 taken 24277 times.
2/2
✓ Decision 'true' taken 1932 times.
✓ Decision 'false' taken 24277 times.
 26209 if (ev.size() > 0) {
283
1/2
✓ Branch 2 taken 1932 times.
✗ Branch 3 not taken.
 1932 bool_uid_port_set.insert(
284
1/2
✓ Branch 1 taken 1932 times.
✗ Branch 2 not taken.
 3864 {get_bit_from_bool_frontier(this->boolean_boundary, ev), i});
285 }
286 26209 }
287
288 // for each quantum edge into vertex, collect associated Qubit/Node
289 // don't collect port as this->linear_boundary holds this
290 // each UnitID will only have one quantum edge active
291 12516 std::vector<UnitID> l_uids; // linear unit id
292 12516 std::vector<Node> nodes; // quantum/node only
293 12516 for (const Edge& e :
294
3/4
✓ Branch 1 taken 12516 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 24260 times.
✓ Branch 9 taken 12516 times.
 49292 this->circuit_.get_in_edges_of_type(vert, EdgeType::Quantum)) {
295 UnitID uid = get_unitid_from_unit_frontier(
296 24260 this->linear_boundary,
297
3/6
✓ Branch 1 taken 24260 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 24260 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 24260 times.
✗ Branch 9 not taken.
 24260 {this->circuit_.source(e), this->circuit_.get_source_port(e)});
298
1/2
✓ Branch 1 taken 24260 times.
✗ Branch 2 not taken.
 24260 l_uids.push_back(uid);
299
2/4
✓ Branch 1 taken 24260 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 24260 times.
✗ Branch 5 not taken.
 24260 nodes.push_back(Node(uid));
300 36776 }
301
302 // for each classical edge store related UnitID in l_uids
303 // each Bit will only have one classical edge active
304 // n.b. some vertices may introduce new Bit to the boolean_boundary
305 // e.g. A Measurement result may be passed to a conditional as
306 // therefore, all Bit not in the Boolean boundary are also stored
307 // in case the operation does this and the this->boolean_boundary
308 // needs to be updated
309 12516 std::map<Bit, port_t> extra_bool_uid_port_set;
310 12516 for (const Edge& e :
311
3/4
✓ Branch 1 taken 12516 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 17 times.
✓ Branch 9 taken 12516 times.
 25049 this->circuit_.get_in_edges_of_type(vert, EdgeType::Classical)) {
312 // for updating linear boundary
313
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 port_t port_source = this->circuit_.get_source_port(e);
314 UnitID uid = get_unitid_from_unit_frontier(
315
2/4
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 17 times.
✗ Branch 6 not taken.
 17 this->linear_boundary, {this->circuit_.source(e), port_source});
316
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 l_uids.push_back(uid);
317
318 // for potentially adding new Bit to boolean boundary
319 // port_target makes it possible to track which "out bundle" corresponds
320 // to this Bit
321
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 port_t port_target = this->circuit_.get_target_port(e);
322
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 Bit bit = Bit(uid);
323
2/4
✓ Branch 2 taken 17 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 17 times.
✗ Branch 6 not taken.
1/2
✓ Decision 'true' taken 17 times.
✗ Decision 'false' not taken.
 17 if (bool_uid_port_set.find(bit) == bool_uid_port_set.end()) {
324
1/2
✓ Branch 2 taken 17 times.
✗ Branch 3 not taken.
 17 extra_bool_uid_port_set.insert({bit, port_target});
325 }
326 12533 }
327
328
1/2
✓ Branch 1 taken 12516 times.
✗ Branch 2 not taken.
 25032 if (nodes.size() == 0 ||
329
3/4
✓ Branch 1 taken 12516 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 4834 times.
✓ Branch 4 taken 7682 times.
 12516 this->valid_boundary_operation(
330
4/8
✓ Branch 1 taken 12516 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 12516 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 4834 times.
✓ Branch 7 taken 7682 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
 25032 architecture, this->circuit_.get_Op_ptr_from_Vertex(vert),
331 nodes)) {
332 // if no valid operation, boundary not updated and while loop terminates
333 4834 boundary_updated = true;
334 // update linear UnitID (Qubits&Quantum edges, Bits&Classical edges)
335
2/2
✓ Branch 4 taken 8842 times.
✓ Branch 5 taken 4834 times.
 13676 for (const UnitID& uid : l_uids) {
336 Edge replacement_edge =
337
2/4
✓ Branch 3 taken 8842 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 8842 times.
✗ Branch 7 not taken.
 8842 next_cut.u_frontier->get<TagKey>().find(uid)->second;
338
1/2
✓ Branch 1 taken 8842 times.
✗ Branch 2 not taken.
 8842 Vertex source_vertex = this->circuit_.source(replacement_edge);
339
1/2
✓ Branch 1 taken 8842 times.
✗ Branch 2 not taken.
 8842 port_t source_port = this->circuit_.get_source_port(replacement_edge);
340
2/4
✓ Branch 4 taken 8842 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 8842 times.
✗ Branch 8 not taken.
 17684 this->linear_boundary->replace(
341 8842 this->linear_boundary->get<TagKey>().find(uid),
342 {uid, {source_vertex, source_port}});
343 }
344 // update booleans
345 // n.b. its possible a boolean path terminates with an operation
346 // however, the port should be preserved so we can track the correct Bit
347 // {Bit, port_t}
348
2/2
✓ Branch 3 taken 1029 times.
✓ Branch 4 taken 4834 times.
 5863 for (auto it = bool_uid_port_set.begin(); it != bool_uid_port_set.end();
349 1029 ++it) {
350 std::vector<EdgeVec> out_bundles =
351
1/2
✓ Branch 1 taken 1029 times.
✗ Branch 2 not taken.
 1029 this->circuit_.get_b_out_bundles(vert);
352
353 1029 port_t port = it->second;
354 TKET_ASSERT(out_bundles.size() > port); // safe port indexing
355 // However, this Bit may have boolean values in other Vertices in
356 // slice therefore, we remove every edge from the vertex in_bundle for
357 // this port from the boolean_boundary and then insert these new edges
358 std::vector<EdgeVec> in_bundles =
359
1/2
✓ Branch 1 taken 1029 times.
✗ Branch 2 not taken.
 1029 this->circuit_.get_b_in_bundles(vert);
360
361 TKET_ASSERT(in_bundles.size() > port); // safe port indexing
362
1/2
✓ Branch 2 taken 1029 times.
✗ Branch 3 not taken.
 1029 EdgeVec in_bundle = in_bundles[port];
363 // Bit should be in boolean_boundary
364 1029 Bit bit = it->first;
365
1/2
✓ Branch 3 taken 1029 times.
✗ Branch 4 not taken.
 1029 auto jt = this->boolean_boundary->get<TagKey>().find(bit);
366 TKET_ASSERT(jt != this->boolean_boundary->get<TagKey>().end());
367 // construct a new EdgeVec object with replaced Edge and persisting
368 // Edge
369
370 1029 EdgeVec new_boolean_edges;
371
372
3/4
✓ Branch 1 taken 1029 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 59302 times.
✓ Branch 9 taken 1029 times.
 60331 for (const Edge& e : jt->second) {
373 // => edge isn't being replaced
374
1/2
✓ Branch 3 taken 59302 times.
✗ Branch 4 not taken.
 59302 if (std::find(in_bundle.begin(), in_bundle.end(), e) ==
375
2/2
✓ Branch 1 taken 58273 times.
✓ Branch 2 taken 1029 times.
 118604 in_bundle.end()) {
376
1/2
✓ Branch 1 taken 58273 times.
✗ Branch 2 not taken.
 58273 new_boolean_edges.push_back(e);
377 }
378 }
379 // add all new edges from out bundle to the boundary
380
1/2
✗ Branch 6 not taken.
✓ Branch 7 taken 1029 times.
 1029 for (const Edge& e : out_bundles[port]) {
381 ✗ new_boolean_edges.push_back(e);
382 }
383
384 // boolean no longer needed
385
2/2
✓ Branch 1 taken 19 times.
✓ Branch 2 taken 1010 times.
 1029 if (new_boolean_edges.size() == 0) {
386
1/2
✓ Branch 2 taken 19 times.
✗ Branch 3 not taken.
 19 this->boolean_boundary->erase(jt);
387 } else {
388 // replace boolean boundary
389
2/4
✓ Branch 2 taken 1010 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1010 times.
✗ Branch 6 not taken.
 1010 this->boolean_boundary->replace(jt, {bit, new_boolean_edges});
390 }
391 1029 }
392 // Some operations may spawn a Boolean wire not held in boolean_boundary
393 // this checks for any new wires and if true, adds to boolean_boundary
394 // {Bit, port_t}
395 4834 for (auto it = extra_bool_uid_port_set.begin();
396
2/2
✓ Branch 3 taken 17 times.
✓ Branch 4 taken 4834 times.
 4851 it != extra_bool_uid_port_set.end(); ++it) {
397 std::vector<EdgeVec> source_out =
398
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 this->circuit_.get_b_out_bundles(vert);
399 // If source_out has more bundles than port value, then we know
400 // it's been spawned (multiple could be spawned at same vertex)
401 17 port_t port = it->second;
402
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 if (source_out.size() > port) {
403
1/2
✓ Branch 2 taken 17 times.
✗ Branch 3 not taken.
 17 EdgeVec new_boolean_wire = source_out[port];
404 // add new edges to boolean_boundary
405 // note that a boolean cannot be spawned in multiple vertices
406 // as the incoming Bit wire is linear
407 // Measure always create a boolean, even if empty of edges
408 // => check size before adding
409
2/2
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 13 times.
 17 if (new_boolean_wire.size() > 0) {
410
2/4
✓ Branch 3 taken 4 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 4 times.
✗ Branch 7 not taken.
 4 this->boolean_boundary->insert({it->first, new_boolean_wire});
411 }
412 17 }
413 17 }
414 }
415 12516 }
416 6892 } while (boundary_updated);
417 3092 return;
418 }
419
420 74 EdgeVec convert_u_frontier_to_edges(const unit_frontier_t& u_frontier) {
421 74 EdgeVec edges;
422
5/8
✓ Branch 4 taken 294 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 294 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 368 times.
✗ Branch 11 not taken.
✓ Branch 12 taken 294 times.
✓ Branch 13 taken 74 times.
 368 for (const std::pair<UnitID, Edge>& pair : u_frontier.get<TagKey>()) {
423
1/2
✓ Branch 1 taken 294 times.
✗ Branch 2 not taken.
 294 edges.push_back(pair.second);
424 }
425 74 return edges;
426 }
427
428 23 Subcircuit MappingFrontier::get_frontier_subcircuit(
429 unsigned _max_subcircuit_depth, unsigned _max_subcircuit_size) const {
430 23 CutFrontier current_cut = this->circuit_.next_cut(
431
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 46 frontier_convert_vertport_to_edge(this->circuit_, this->linear_boundary),
432
1/2
✓ Branch 3 taken 23 times.
✗ Branch 4 not taken.
 69 this->boolean_boundary);
433
434 23 unsigned subcircuit_depth = 1;
435 VertexSet subcircuit_vertices(
436
1/2
✓ Branch 6 taken 23 times.
✗ Branch 7 not taken.
 23 current_cut.slice->begin(), current_cut.slice->end());
437 // add cuts of vertices to subcircuit_vertices until constraints met, or end
438 // of circuit reached
439 23 while (subcircuit_depth < _max_subcircuit_depth &&
440
8/8
✓ Branch 0 taken 61 times.
✓ Branch 1 taken 12 times.
✓ Branch 3 taken 60 times.
✓ Branch 4 taken 1 times.
✓ Branch 5 taken 50 times.
✓ Branch 6 taken 10 times.
✓ Branch 7 taken 50 times.
✓ Branch 8 taken 23 times.
 133 unsigned(subcircuit_vertices.size()) < _max_subcircuit_size &&
441 60 current_cut.slice->size() > 0) {
442 current_cut =
443
1/2
✓ Branch 3 taken 50 times.
✗ Branch 4 not taken.
 50 this->circuit_.next_cut(current_cut.u_frontier, current_cut.b_frontier);
444 50 subcircuit_depth++;
445
1/2
✓ Branch 5 taken 50 times.
✗ Branch 6 not taken.
 50 subcircuit_vertices.insert(
446 current_cut.slice->begin(), current_cut.slice->end());
447 }
448 TKET_ASSERT(subcircuit_vertices.size() != 0);
449 return Subcircuit(
450
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 46 convert_u_frontier_to_edges(*frontier_convert_vertport_to_edge(
451
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 this->circuit_, this->linear_boundary)),
452
1/2
✓ Branch 2 taken 23 times.
✗ Branch 3 not taken.
 46 convert_u_frontier_to_edges(*current_cut.u_frontier),
453
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 46 subcircuit_vertices);
454 23 }
455
456 279 UnitID MappingFrontier::get_qubit_from_circuit_uid(const UnitID& uid) {
457
1/2
✓ Branch 2 taken 279 times.
✗ Branch 3 not taken.
 279 auto it = this->bimaps_->initial.right.find(uid);
458
3/6
✓ Branch 2 taken 279 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 279 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 279 times.
 279 if (it == this->bimaps_->initial.right.end()) {
459 ✗ throw MappingFrontierError("UnitID not found in initial map.");
460 }
461
1/2
✓ Branch 1 taken 279 times.
✗ Branch 2 not taken.
 558 return it->second;
462 }
463
464 279 void MappingFrontier::update_bimaps(UnitID qubit, UnitID node) {
465 // Update initial map
466
1/2
✓ Branch 2 taken 279 times.
✗ Branch 3 not taken.
 279 auto init_it = this->bimaps_->initial.left.find(qubit);
467
3/6
✓ Branch 2 taken 279 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 279 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 279 times.
 279 if (init_it == this->bimaps_->initial.left.end())
468 ✗ throw MappingFrontierError("Qubit not found in initial map.");
469
1/2
✓ Branch 2 taken 279 times.
✗ Branch 3 not taken.
 279 this->bimaps_->initial.left.erase(init_it);
470
2/4
✓ Branch 2 taken 279 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 279 times.
✗ Branch 6 not taken.
 279 this->bimaps_->initial.left.insert({qubit, node});
471 // Update final map
472
1/2
✓ Branch 2 taken 279 times.
✗ Branch 3 not taken.
 279 auto final_it = this->bimaps_->final.left.find(qubit);
473
3/6
✓ Branch 2 taken 279 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 279 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 279 times.
 279 if (final_it == this->bimaps_->final.left.end())
474 ✗ throw MappingFrontierError("Qubit not found in final map.");
475
1/2
✓ Branch 2 taken 279 times.
✗ Branch 3 not taken.
 279 this->bimaps_->final.left.erase(final_it);
476
2/4
✓ Branch 2 taken 279 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 279 times.
✗ Branch 6 not taken.
 279 this->bimaps_->final.left.insert({qubit, node});
477 279 }
478
479 230 void MappingFrontier::update_linear_boundary_uids(
480 const unit_map_t& relabelled_uids) {
481
2/2
✓ Branch 5 taken 5681 times.
✓ Branch 6 taken 230 times.
 5911 for (const std::pair<const UnitID, UnitID>& label : relabelled_uids) {
482 // implies new labelling
483
3/4
✓ Branch 1 taken 5681 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 292 times.
✓ Branch 4 taken 5389 times.
 5681 if (label.first != label.second) {
484 // by type, label.first already assumed in circuit
485 // this condition means label.second also in circuit
486 // implies that a merging is done -> remove first qubit
487
488
2/4
✓ Branch 3 taken 292 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 292 times.
✗ Branch 7 not taken.
 292 if (this->linear_boundary->get<TagKey>().find(label.second) !=
489
2/2
✓ Branch 3 taken 14 times.
✓ Branch 4 taken 278 times.
 584 this->linear_boundary->get<TagKey>().end()) {
490 // erase, assume updated already
491
1/2
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
 14 this->linear_boundary->erase(label.first);
492 } else {
493 auto current_label_it =
494
1/2
✓ Branch 3 taken 278 times.
✗ Branch 4 not taken.
 278 this->linear_boundary->get<TagKey>().find(label.first);
495 // relabel "label.first" with "label.second"
496
1/2
✓ Branch 2 taken 278 times.
✗ Branch 3 not taken.
 556 this->linear_boundary->replace(
497
1/2
✓ Branch 1 taken 278 times.
✗ Branch 2 not taken.
 278 current_label_it, {label.second, current_label_it->second});
498
1/2
✓ Branch 3 taken 278 times.
✗ Branch 4 not taken.
 834 unit_map_t relabel = {label};
499
1/2
✓ Branch 1 taken 278 times.
✗ Branch 2 not taken.
 278 this->circuit_.rename_units(relabel);
500 278 }
501 }
502 }
503 230 }
504
505 9 void MappingFrontier::permute_subcircuit_q_out_hole(
506 const unit_map_t& final_permutation, Subcircuit& subcircuit) {
507 9 EdgeVec new_q_out_hole;
508 9 int i = 0;
509 // Change to iterate through final permutation first?
510
2/2
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 8 times.
 9 if (this->linear_boundary->size() != final_permutation.size()) {
511
2/4
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
 1 throw MappingFrontierError(
512 "Number of Qubits in mapping permutation does not match number of "
513 "Qubits in MappingFrontier boundary, for permuting Qubits as with "
514 2 "routed Subcircuit.");
515 }
516 8 for (const std::pair<UnitID, VertPort>& pair :
517
5/8
✓ Branch 5 taken 27 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 26 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 34 times.
✗ Branch 12 not taken.
✓ Branch 13 taken 27 times.
✓ Branch 14 taken 7 times.
 42 this->linear_boundary->get<TagKey>()) {
518
1/2
✓ Branch 1 taken 27 times.
✗ Branch 2 not taken.
 27 auto it = final_permutation.find(pair.first);
519
2/2
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 26 times.
 27 if (it == final_permutation.end()) {
520
2/4
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
 1 throw MappingFrontierError("Qubit in boundary not in permutation.");
521 }
522 26 std::pair<UnitID, UnitID> uid_pair = *it;
523
3/4
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 11 times.
✓ Branch 4 taken 15 times.
 26 if (uid_pair.first == uid_pair.second) {
524
1/2
✓ Branch 2 taken 11 times.
✗ Branch 3 not taken.
 11 new_q_out_hole.push_back(subcircuit.q_out_hole[i]);
525 } else {
526 15 int j = 0;
527 15 for (auto it = this->linear_boundary->get<TagKey>().begin();
528
2/4
✓ Branch 4 taken 31 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 31 times.
✗ Branch 7 not taken.
 31 it != this->linear_boundary->get<TagKey>().end(); ++it) {
529
4/6
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 31 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 15 times.
✓ Branch 7 taken 16 times.
 31 if (it->first == uid_pair.second) {
530
1/2
✓ Branch 2 taken 15 times.
✗ Branch 3 not taken.
 15 new_q_out_hole.push_back(subcircuit.q_out_hole[j]);
531 15 break;
532 }
533
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 j++;
534 }
535 }
536 26 i++;
537 26 }
538
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 subcircuit.q_out_hole = new_q_out_hole;
539 9 }
540
541 /**
542 * MappingFrontier::get_u_frontier_default_unit_map
543 * Map from default qubit register qubits to UnitIDs in linear_boundary
544 */
545 9 unit_map_t MappingFrontier::get_default_to_linear_boundary_unit_map() const {
546 9 unsigned i = 0;
547 9 unit_map_t default_to_u_frontier_map;
548 9 for (const std::pair<UnitID, VertPort>& pair :
549
4/6
✓ Branch 5 taken 29 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 38 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 29 times.
✓ Branch 11 taken 9 times.
 47 this->linear_boundary->get<TagKey>()) {
550
2/4
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 29 times.
✗ Branch 6 not taken.
 29 default_to_u_frontier_map.insert({Qubit(i), pair.first});
551
1/2
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
 29 i++;
552 }
553 9 return default_to_u_frontier_map;
554 }
555
556 5524 void MappingFrontier::set_linear_boundary(
557 const unit_vertport_frontier_t& new_boundary) {
558 5524 this->linear_boundary = std::make_shared<unit_vertport_frontier_t>();
559
5/8
✓ Branch 4 taken 111180 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 111180 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 116704 times.
✗ Branch 11 not taken.
✓ Branch 12 taken 111180 times.
✓ Branch 13 taken 5524 times.
 116704 for (const std::pair<UnitID, VertPort>& pair : new_boundary.get<TagKey>()) {
560
1/2
✓ Branch 2 taken 111180 times.
✗ Branch 3 not taken.
 111180 this->linear_boundary->insert(pair);
561 }
562 5524 }
563
564 /**
565 * add_swap
566 * Inserts an OpType::SWAP gate into the uid_0 and uid_1 edges held in
567 * linear_boundary This directly modifies circuit_ Updates linear_boundary to
568 * reflect new edges
569 */
570 2481 bool MappingFrontier::add_swap(const UnitID& uid_0, const UnitID& uid_1) {
571 // get iterators to linear_boundary uids
572
1/2
✓ Branch 2 taken 2481 times.
✗ Branch 3 not taken.
 2481 auto uid0_in_it = this->linear_boundary->find(uid_0);
573
1/2
✓ Branch 2 taken 2481 times.
✗ Branch 3 not taken.
 2481 auto uid1_in_it = this->linear_boundary->find(uid_1);
574
575 // Add Qubit if not in MappingFrontier boundary (i.e. not in circuit)
576
2/4
✓ Branch 3 taken 2481 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 2481 times.
 2481 if (uid0_in_it == this->linear_boundary->end()) {
577 ✗ this->add_ancilla(uid_0);
578 ✗ uid0_in_it = this->linear_boundary->find(uid_0);
579 }
580
3/4
✓ Branch 3 taken 2481 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 19 times.
✓ Branch 6 taken 2462 times.
 2481 if (uid1_in_it == this->linear_boundary->end()) {
581
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 this->add_ancilla(uid_1);
582
1/2
✓ Branch 2 taken 19 times.
✗ Branch 3 not taken.
 19 uid1_in_it = this->linear_boundary->find(uid_1);
583 }
584
585 // update held ancillas
586 // the location/id of the "ancilla node" changes when a SWAP occurs
587
1/2
✓ Branch 1 taken 2481 times.
✗ Branch 2 not taken.
 2481 Node n0 = Node(uid_0);
588
1/2
✓ Branch 1 taken 2481 times.
✗ Branch 2 not taken.
 2481 Node n1 = Node(uid_1);
589 bool uid0_ancilla =
590
1/2
✓ Branch 2 taken 2481 times.
✗ Branch 3 not taken.
 2481 this->ancilla_nodes_.find(n0) != this->ancilla_nodes_.end();
591 bool uid1_ancilla =
592
1/2
✓ Branch 2 taken 2481 times.
✗ Branch 3 not taken.
 2481 this->ancilla_nodes_.find(n1) != this->ancilla_nodes_.end();
593
594
3/4
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 2480 times.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 2481 if (uid0_ancilla && !uid1_ancilla) {
595
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 this->ancilla_nodes_.erase(n0);
596
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 this->ancilla_nodes_.insert(n1);
597 }
598
4/4
✓ Branch 0 taken 2480 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 28 times.
✓ Branch 3 taken 2452 times.
 2481 if (!uid0_ancilla && uid1_ancilla) {
599
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 this->ancilla_nodes_.erase(n1);
600
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 this->ancilla_nodes_.insert(n0);
601 }
602
603 // Get predecessor edges to SWAP insert location
604
1/2
✓ Branch 1 taken 2481 times.
✗ Branch 2 not taken.
 2481 VertPort vp0 = uid0_in_it->second;
605
1/2
✓ Branch 1 taken 2481 times.
✗ Branch 2 not taken.
 2481 VertPort vp1 = uid1_in_it->second;
606 EdgeVec predecessors = {
607
1/2
✓ Branch 1 taken 2481 times.
✗ Branch 2 not taken.
 2481 this->circuit_.get_nth_out_edge(vp0.first, vp0.second),
608
2/4
✓ Branch 1 taken 2481 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 2481 times.
✗ Branch 6 not taken.
 2481 this->circuit_.get_nth_out_edge(vp1.first, vp1.second)};
609
610 // If the immediate vertex before the new vertex is the same SWAP, this
611 // implies a rut has been hit In which case return false that SWAP can't be
612 // added Can safely do this check here after relabelling as adding/updating
613 // ancillas => fresh SWAP
614
1/2
✓ Branch 2 taken 2481 times.
✗ Branch 3 not taken.
 2481 Vertex source0 = this->circuit_.source(predecessors[0]);
615
1/2
✓ Branch 2 taken 2481 times.
✗ Branch 3 not taken.
 2481 Vertex source1 = this->circuit_.source(predecessors[1]);
616
2/2
✓ Branch 0 taken 163 times.
✓ Branch 1 taken 2318 times.
 2481 if (source0 == source1) {
617
3/4
✓ Branch 1 taken 163 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 9 times.
✓ Branch 4 taken 154 times.
 163 if (this->circuit_.get_OpType_from_Vertex(source0) == OpType::SWAP) {
618 9 return false;
619 }
620 }
621
622 // add SWAP vertex to circuit_ and rewire into predecessor
623
1/2
✓ Branch 2 taken 2472 times.
✗ Branch 3 not taken.
 2472 Vertex swap_v = this->circuit_.add_vertex(OpType::SWAP);
624
2/4
✓ Branch 2 taken 2472 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 2472 times.
✗ Branch 6 not taken.
 2472 this->circuit_.rewire(
625 swap_v, predecessors, {EdgeType::Quantum, EdgeType::Quantum});
626
627 // Update boundary to reflect new edges
628
1/2
✓ Branch 1 taken 2472 times.
✗ Branch 2 not taken.
 2472 EdgeVec successors = this->circuit_.get_all_out_edges(swap_v);
629
1/2
✓ Branch 2 taken 2472 times.
✗ Branch 3 not taken.
 2472 this->circuit_.dag[successors[0]].ports.first = 1;
630
1/2
✓ Branch 2 taken 2472 times.
✗ Branch 3 not taken.
 2472 this->circuit_.dag[successors[1]].ports.first = 0;
631
632
1/2
✓ Branch 3 taken 2472 times.
✗ Branch 4 not taken.
 4944 this->linear_boundary->replace(
633
1/2
✓ Branch 2 taken 2472 times.
✗ Branch 3 not taken.
 2472 uid0_in_it, {uid_0, {this->circuit_.source(successors[1]), 0}});
634
1/2
✓ Branch 3 taken 2472 times.
✗ Branch 4 not taken.
 4944 this->linear_boundary->replace(
635
1/2
✓ Branch 2 taken 2472 times.
✗ Branch 3 not taken.
 2472 uid1_in_it, {uid_1, {this->circuit_.source(successors[0]), 1}});
636
637 // update output vertices of quantum boundary of circuit to reflect changing
638 // qubit paths
639 auto uid0_circuit_boundary_it =
640
1/2
✓ Branch 2 taken 2472 times.
✗ Branch 3 not taken.
 2472 this->circuit_.boundary.get<TagID>().find(uid_0);
641 auto uid1_circuit_boundary_it =
642
1/2
✓ Branch 2 taken 2472 times.
✗ Branch 3 not taken.
 2472 this->circuit_.boundary.get<TagID>().find(uid_1);
643
644
1/2
✓ Branch 1 taken 2472 times.
✗ Branch 2 not taken.
 2472 Vertex uid0_out = uid0_circuit_boundary_it->out_;
645
1/2
✓ Branch 1 taken 2472 times.
✗ Branch 2 not taken.
 2472 Vertex uid1_out = uid1_circuit_boundary_it->out_;
646
1/2
✓ Branch 1 taken 2472 times.
✗ Branch 2 not taken.
 2472 Vertex uid0_in = uid0_circuit_boundary_it->in_;
647
1/2
✓ Branch 1 taken 2472 times.
✗ Branch 2 not taken.
 2472 Vertex uid1_in = uid1_circuit_boundary_it->in_;
648
649
1/2
✓ Branch 2 taken 2472 times.
✗ Branch 3 not taken.
 2472 this->circuit_.boundary.get<TagID>().erase(uid_0);
650
1/2
✓ Branch 2 taken 2472 times.
✗ Branch 3 not taken.
 2472 this->circuit_.boundary.get<TagID>().erase(uid_1);
651
652
1/2
✓ Branch 3 taken 2472 times.
✗ Branch 4 not taken.
 2472 this->circuit_.boundary.get<TagID>().insert({uid_0, uid0_in, uid1_out});
653
1/2
✓ Branch 3 taken 2472 times.
✗ Branch 4 not taken.
 2472 this->circuit_.boundary.get<TagID>().insert({uid_1, uid1_in, uid0_out});
654
655
1/2
✓ Branch 4 taken 2472 times.
✗ Branch 5 not taken.
 9888 std::map<Node, Node> final_map = {{n0, n1}, {n1, n0}};
656
657
1/2
✓ Branch 3 taken 2472 times.
✗ Branch 4 not taken.
 2472 update_maps(this->bimaps_, {}, final_map);
658 2472 return true;
659 2481 }
660
661 303 void MappingFrontier::add_bridge(
662 const UnitID& control, const UnitID& central, const UnitID& target) {
663 // get predecessors
664
1/2
✓ Branch 2 taken 303 times.
✗ Branch 3 not taken.
 303 auto control_in_it = this->linear_boundary->find(control);
665
1/2
✓ Branch 2 taken 303 times.
✗ Branch 3 not taken.
 303 auto central_in_it = this->linear_boundary->find(central);
666
1/2
✓ Branch 2 taken 303 times.
✗ Branch 3 not taken.
 303 auto target_in_it = this->linear_boundary->find(target);
667
668 // by virtue of method, control and target qubit will always be in BRIDGE.
669 // However, distances used to check BRIDGE and find PATH may use
670 // central qubit that is unallocated, in which add it.
671
3/4
✓ Branch 3 taken 303 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 2 times.
✓ Branch 6 taken 301 times.
 303 if (central_in_it == this->linear_boundary->end()) {
672
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 this->add_ancilla(central);
673
1/2
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
 2 central_in_it = this->linear_boundary->find(central);
674 }
675
676
1/2
✓ Branch 1 taken 303 times.
✗ Branch 2 not taken.
 303 VertPort vp_control = control_in_it->second;
677
1/2
✓ Branch 1 taken 303 times.
✗ Branch 2 not taken.
 303 VertPort vp_central = central_in_it->second;
678
1/2
✓ Branch 1 taken 303 times.
✗ Branch 2 not taken.
 303 VertPort vp_target = target_in_it->second;
679
680 EdgeVec predecessors = {
681
1/2
✓ Branch 1 taken 303 times.
✗ Branch 2 not taken.
 303 this->circuit_.get_nth_out_edge(vp_control.first, vp_control.second),
682
1/2
✓ Branch 1 taken 303 times.
✗ Branch 2 not taken.
 303 this->circuit_.get_nth_out_edge(vp_central.first, vp_central.second),
683
1/2
✓ Branch 1 taken 303 times.
✗ Branch 2 not taken.
 303 this->circuit_.get_nth_out_edge(vp_target.first, vp_target.second),
684
1/2
✓ Branch 2 taken 303 times.
✗ Branch 3 not taken.
 303 }; // get cx vertex
685 // this should be guaranteeds by pre-checks
686
1/2
✓ Branch 2 taken 303 times.
✗ Branch 3 not taken.
 303 Vertex cx_v = this->circuit_.target(predecessors[0]);
687 // add bridge
688
1/2
✓ Branch 2 taken 303 times.
✗ Branch 3 not taken.
 303 Vertex bridge_v = this->circuit_.add_vertex(OpType::BRIDGE);
689 // add bridge vertex to circuit
690
2/4
✓ Branch 2 taken 303 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 303 times.
✗ Branch 6 not taken.
 303 this->circuit_.rewire(
691 bridge_v, predecessors,
692 {EdgeType::Quantum, EdgeType::Quantum, EdgeType::Quantum});
693 // remove old cx vertex
694
1/2
✓ Branch 1 taken 303 times.
✗ Branch 2 not taken.
 303 this->circuit_.remove_vertex(
695 cx_v, Circuit::GraphRewiring::Yes, Circuit::VertexDeletion::Yes);
696 303 }
697
698 22 void MappingFrontier::add_ancilla(const UnitID& ancilla) {
699
1/2
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
 22 Qubit qb(ancilla);
700
1/2
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
 22 this->circuit_.add_qubit(qb);
701
2/4
✓ Branch 2 taken 22 times.
✗ Branch 3 not taken.
✓ Branch 7 taken 22 times.
✗ Branch 8 not taken.
 22 this->linear_boundary->insert({qb, {this->circuit_.get_in(qb), 0}});
702
703
2/4
✓ Branch 2 taken 22 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 22 times.
✗ Branch 6 not taken.
 22 this->bimaps_->initial.insert({qb, qb});
704
2/4
✓ Branch 2 taken 22 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 22 times.
✗ Branch 6 not taken.
 22 this->bimaps_->final.insert({qb, qb});
705
2/4
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 22 times.
✗ Branch 5 not taken.
 22 this->ancilla_nodes_.insert(Node(ancilla));
706 22 UnitID uid_ancilla(ancilla);
707
708 22 unit_map_t update_map;
709
1/2
✓ Branch 2 taken 22 times.
✗ Branch 3 not taken.
 22 update_map.insert({uid_ancilla, uid_ancilla});
710
711
1/2
✓ Branch 2 taken 22 times.
✗ Branch 3 not taken.
 22 update_maps(this->bimaps_, update_map, update_map);
712 22 }
713
714 14 void MappingFrontier::merge_ancilla(
715 const UnitID& merge, const UnitID& ancilla) {
716 // get output and input vertices
717
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 Vertex merge_v_in = this->circuit_.get_in(merge);
718
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 Vertex merge_v_out = this->circuit_.get_out(merge);
719
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 Vertex ancilla_v_out = this->circuit_.get_out(ancilla);
720 // find source vertex & port of merge_v_out
721 // output vertex, so can assume single edge
722
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 Edge merge_out_edge = this->circuit_.get_nth_out_edge(merge_v_in, 0);
723
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 Edge ancilla_in_edge = this->circuit_.get_nth_in_edge(ancilla_v_out, 0);
724 // Find port number
725
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 port_t merge_target_port = this->circuit_.get_target_port(merge_out_edge);
726
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 port_t ancilla_source_port = this->circuit_.get_source_port(ancilla_in_edge);
727 // Find vertices
728
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 Vertex merge_v_target = this->circuit_.target(merge_out_edge);
729
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 Vertex ancilla_v_source = this->circuit_.source(ancilla_in_edge);
730
731 // remove and replace edges
732
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 this->circuit_.remove_edge(merge_out_edge);
733
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 this->circuit_.remove_edge(ancilla_in_edge);
734
1/2
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
 14 this->circuit_.add_edge(
735 {ancilla_v_source, ancilla_source_port},
736 14 {merge_v_target, merge_target_port}, EdgeType::Quantum);
737
738 // instead of manually updating all boundaries, we change which output
739 // vertex the qubit paths to
740
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 Edge merge_in_edge = this->circuit_.get_nth_in_edge(merge_v_out, 0);
741
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 port_t merge_source_port = this->circuit_.get_source_port(merge_in_edge);
742
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 Vertex merge_v_source = this->circuit_.source(merge_in_edge);
743
744
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 this->circuit_.remove_edge(merge_in_edge);
745
1/2
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
 14 this->circuit_.add_edge(
746 ✗ {merge_v_source, merge_source_port}, {ancilla_v_out, 0},
747 14 EdgeType::Quantum);
748
749 // remove empty vertex wire, relabel dag vertices
750
2/4
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 14 times.
✗ Branch 6 not taken.
 14 this->circuit_.dag[merge_v_in].op = get_op_ptr(OpType::noop);
751
2/4
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 14 times.
✗ Branch 6 not taken.
 14 this->circuit_.dag[merge_v_out].op = get_op_ptr(OpType::noop);
752
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 this->circuit_.remove_vertex(
753 merge_v_in, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
754
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 this->circuit_.remove_vertex(
755 merge_v_out, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
756
757 // Can now just erase "merge" qubit from the circuit
758
1/2
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
 14 this->circuit_.boundary.get<TagID>().erase(merge);
759
760 // Update the qubit mappings
761 // let's call the arguments ancilla_node and merge_node
762 // e.g. before merge:
763 // initial := {ancilla_q:node_x, merge_q:some_uid}
764 // final := {ancilla_q:ancilla_node, merge_q:merge_node}
765 // e.g. after merge:
766 // initial := {merge_q:node_x}
767 // final := {merge_q:ancilla_node}
768 // Basically, in both qubit maps, erase the entry with qubit merge_q
769 // then replace the entry ancilla_q -> x with the merge_q -> x
770
771
1/2
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
 14 auto merge_it = this->bimaps_->initial.right.find(merge);
772 TKET_ASSERT(merge_it != this->bimaps_->initial.right.end());
773
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 UnitID merge_q = merge_it->second;
774
1/2
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
 14 this->bimaps_->initial.right.erase(merge_it);
775
1/2
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
 14 this->bimaps_->final.left.erase(merge_q);
776 // Find ancilla_q
777
1/2
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
 14 auto final_it = this->bimaps_->final.right.find(ancilla);
778
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 UnitID ancilla_q = final_it->second;
779 // Replace in final map
780
1/2
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
 14 this->bimaps_->final.right.erase(final_it);
781
2/4
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 14 times.
✗ Branch 6 not taken.
 14 this->bimaps_->final.left.insert({merge_q, ancilla});
782 // Replace in initial map
783
1/2
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
 14 auto init_it = this->bimaps_->initial.left.find(ancilla_q);
784
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 UnitID init_ancilla_node = init_it->second;
785
1/2
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
 14 this->bimaps_->initial.left.erase(init_it);
786
2/4
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 14 times.
✗ Branch 6 not taken.
 14 this->bimaps_->initial.left.insert({merge_q, init_ancilla_node});
787 14 }
788
789 12583 bool MappingFrontier::valid_boundary_operation(
790 const ArchitecturePtr& architecture, const Op_ptr& op,
791 const std::vector<Node>& uids) const {
792 // boxes are never allowed
793 12583 OpType ot = op->get_type();
794
2/2
✓ Branch 1 taken 18 times.
✓ Branch 2 taken 12565 times.
 12583 if (is_box_type(ot)) {
795 18 return false;
796 }
797
798
2/2
✓ Branch 0 taken 504 times.
✓ Branch 1 taken 12061 times.
 12565 if (ot == OpType::Conditional) {
799
1/2
✓ Branch 2 taken 504 times.
✗ Branch 3 not taken.
 504 Op_ptr cond_op_ptr = static_cast<const Conditional&>(*op).get_op();
800 // conditional boxes are never allowed, too
801 504 OpType ot = cond_op_ptr->get_type();
802
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 504 times.
 504 while (ot == OpType::Conditional) {
803 ✗ cond_op_ptr = static_cast<const Conditional&>(*op).get_op();
804 ✗ ot = cond_op_ptr->get_type();
805 ✗ if (is_box_type(ot)) {
806 ✗ return false;
807 }
808 }
809
1/2
✓ Branch 1 taken 504 times.
✗ Branch 2 not taken.
 504 }
810
811 // Barriers are allways allowed
812
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 12564 times.
 12565 if (ot == OpType::Barrier) {
813 1 return true;
814 }
815
816 // this currently allows unplaced single qubits gates
817 // this should be changes in the future
818
2/2
✓ Branch 1 taken 1147 times.
✓ Branch 2 taken 11417 times.
 12564 if (uids.size() == 1) {
819 1147 return true;
820 }
821
822 // allow two qubit gates only for placed and connected nodes
823
2/2
✓ Branch 1 taken 11114 times.
✓ Branch 2 taken 303 times.
 11417 if (uids.size() == 2) {
824 11114 bool n0 = architecture->node_exists(uids[0]);
825 11114 bool n1 = architecture->node_exists(uids[1]);
826
4/4
✓ Branch 0 taken 10975 times.
✓ Branch 1 taken 139 times.
✓ Branch 2 taken 10865 times.
✓ Branch 3 taken 110 times.
 11114 if (n0 && n1) {
827 10865 bool bde = architecture->bidirectional_edge_exists(uids[0], uids[1]);
828
2/2
✓ Branch 0 taken 3428 times.
✓ Branch 1 taken 7437 times.
 10865 if (bde) {
829 3428 return true;
830 }
831 }
832
3/6
✓ Branch 1 taken 303 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 303 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 303 times.
✗ Branch 6 not taken.
 303 } else if (uids.size() == 3 && ot == OpType::BRIDGE) {
833 bool con_0_exists =
834 303 architecture->bidirectional_edge_exists(uids[0], uids[1]);
835 bool con_1_exists =
836 303 architecture->bidirectional_edge_exists(uids[2], uids[1]);
837 303 if (architecture->node_exists(uids[0]) &&
838
1/2
✓ Branch 3 taken 303 times.
✗ Branch 4 not taken.
 303 architecture->node_exists(uids[1]) &&
839
5/10
✓ Branch 0 taken 303 times.
✗ Branch 1 not taken.
✓ Branch 5 taken 303 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 303 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 303 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 303 times.
✗ Branch 12 not taken.
 606 architecture->node_exists(uids[2]) && con_0_exists && con_1_exists) {
840 303 return true;
841 }
842 }
843
844 7686 return false;
845 }
846
847 } // namespace tket
848