GCC Code Coverage Report

Directory: ./
File: Placement/Qubit_Placement.cpp
Date: 2022-10-15 05:10:18
Warnings: 12 unchecked decisions!
Exec Total Coverage
Lines: 242 258 93.8%
Functions: 15 16 93.8%
Branches: 282 478 59.0%
Decisions: 67 100 67.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 //#define DEBUG
16 #include <algorithm>
17 #include <numeric>
18 #include <optional>
19 #include <queue>
20
21 #include "Architecture/Architecture.hpp"
22 #include "Graphs/Utils.hpp"
23 #include "Placement.hpp"
24
25 namespace tket {
26
27 61 std::set<Qubit> interacting_qbs(const Circuit& circ) {
28 61 std::set<Qubit> qbs;
29
3/4
✓ Branch 1 taken 61 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 1323 times.
✓ Branch 9 taken 61 times.
0/1
? Decision couldn't be analyzed.
 1384 for (const Qubit& qb : circ.all_qubits()) {
30
2/4
✓ Branch 1 taken 1323 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1323 times.
✗ Branch 5 not taken.
 1323 Edge e = circ.get_nth_out_edge(circ.get_in(qb), 0);
31
2/4
✓ Branch 1 taken 1323 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1323 times.
✗ Branch 5 not taken.
 1323 Vertex terminal = circ.target(circ.skip_irrelevant_edges(e));
32
3/4
✓ Branch 1 taken 1323 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1316 times.
✓ Branch 4 taken 7 times.
2/2
✓ Decision 'true' taken 1316 times.
✓ Decision 'false' taken 7 times.
 1323 if (!circ.detect_final_Op(terminal)) {
33
1/2
✓ Branch 1 taken 1316 times.
✗ Branch 2 not taken.
 1316 qbs.insert(qb);
34 }
35 61 }
36
37 61 return qbs;
38 }
39
40 61 PlacementFrontier::PlacementFrontier(const Circuit& _circ) : circ(_circ) {
41 61 VertexVec input_slice;
42
1/2
✓ Branch 1 taken 61 times.
✗ Branch 2 not taken.
 61 quantum_in_edges = std::make_shared<unit_frontier_t>();
43
1/2
✓ Branch 1 taken 61 times.
✗ Branch 2 not taken.
 61 boolean_in_edges = std::make_shared<b_frontier_t>();
44
45
3/4
✓ Branch 1 taken 61 times.
✗ Branch 2 not taken.
✓ Branch 7 taken 1323 times.
✓ Branch 8 taken 61 times.
0/1
? Decision couldn't be analyzed.
 1384 for (const Qubit& qb : circ.all_qubits()) {
46
1/2
✓ Branch 1 taken 1323 times.
✗ Branch 2 not taken.
 1323 Vertex input = circ.get_in(qb);
47
1/2
✓ Branch 1 taken 1323 times.
✗ Branch 2 not taken.
 1323 input_slice.push_back(input);
48
1/2
✓ Branch 1 taken 1323 times.
✗ Branch 2 not taken.
 1323 Edge candidate = circ.get_nth_out_edge(input, 0);
49
2/4
✓ Branch 2 taken 1323 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 1323 times.
✗ Branch 7 not taken.
 1323 quantum_in_edges->insert({qb, circ.skip_irrelevant_edges(candidate)});
50 61 }
51
3/4
✓ Branch 1 taken 61 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 9 times.
✓ Branch 9 taken 61 times.
0/1
? Decision couldn't be analyzed.
 70 for (const Bit& bit : circ.all_bits()) {
52
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 Vertex input = circ.get_in(bit);
53
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 EdgeVec candidates = circ.get_nth_b_out_bundle(input, 0);
54
2/4
✓ Branch 2 taken 9 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 9 times.
✗ Branch 6 not taken.
 9 boolean_in_edges->insert({bit, candidates});
55 70 }
56
57
1/2
✓ Branch 3 taken 61 times.
✗ Branch 4 not taken.
 122 CutFrontier next_cut = circ.next_cut(quantum_in_edges, boolean_in_edges);
58 61 slice = next_cut.slice;
59 61 quantum_out_edges = next_cut.u_frontier;
60 61 }
61
62 253 void PlacementFrontier::next_slicefrontier() {
63
1/2
✓ Branch 1 taken 253 times.
✗ Branch 2 not taken.
 253 quantum_in_edges = std::make_shared<unit_frontier_t>();
64
1/2
✓ Branch 1 taken 253 times.
✗ Branch 2 not taken.
 253 boolean_in_edges = std::make_shared<b_frontier_t>();
65
5/8
✓ Branch 5 taken 8611 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 8611 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 8864 times.
✗ Branch 12 not taken.
✓ Branch 13 taken 8611 times.
✓ Branch 14 taken 253 times.
0/1
? Decision couldn't be analyzed.
 8864 for (const std::pair<UnitID, Edge>& pair : quantum_out_edges->get<TagKey>()) {
66
1/2
✓ Branch 1 taken 8611 times.
✗ Branch 2 not taken.
 8611 Edge new_e = circ.skip_irrelevant_edges(pair.second);
67
1/2
✓ Branch 3 taken 8611 times.
✗ Branch 4 not taken.
 8611 quantum_in_edges->insert({pair.first, new_e});
68
1/2
✓ Branch 1 taken 8611 times.
✗ Branch 2 not taken.
 8611 Vertex targ = circ.target(new_e);
69 EdgeVec targ_classical_ins =
70
1/2
✓ Branch 1 taken 8611 times.
✗ Branch 2 not taken.
 8611 circ.get_in_edges_of_type(targ, EdgeType::Boolean);
71
2/4
✓ Branch 2 taken 8611 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 8611 times.
✗ Branch 6 not taken.
 17222 boolean_in_edges->insert(
72
3/6
✓ Branch 1 taken 8611 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 8611 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 8611 times.
✗ Branch 9 not taken.
 17222 {Bit("frontier_bit", pair.first.index()), targ_classical_ins});
73 8611 }
74
75
1/2
✓ Branch 3 taken 253 times.
✗ Branch 4 not taken.
 506 CutFrontier next_cut = circ.next_cut(quantum_in_edges, boolean_in_edges);
76 253 slice = next_cut.slice;
77 253 quantum_out_edges = next_cut.u_frontier;
78 253 }
79
80 52 QubitGraph monomorph_interaction_graph(
81 const Circuit& circ, const unsigned max_edges, unsigned depth_limit) {
82
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 std::set<Qubit> qubits_considered = interacting_qbs(circ);
83
84
2/4
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 52 times.
✗ Branch 5 not taken.
 52 QubitGraph q_graph(circ.all_qubits());
85
86
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 PlacementFrontier current_sf(circ);
87 52 unsigned count_edges = 0;
88 259 for (unsigned slice = 0;
89
2/2
✓ Branch 0 taken 224 times.
✓ Branch 1 taken 12 times.
 236 slice < depth_limit && count_edges < max_edges &&
90
7/8
✓ Branch 0 taken 236 times.
✓ Branch 1 taken 23 times.
✓ Branch 4 taken 207 times.
✓ Branch 5 taken 17 times.
✓ Branch 7 taken 207 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 207 times.
✓ Branch 10 taken 52 times.
 495 !current_sf.slice->empty() && qubits_considered.size() > 1;
91 slice++) {
92
2/2
✓ Branch 6 taken 249 times.
✓ Branch 7 taken 207 times.
2/2
✓ Decision 'true' taken 249 times.
✓ Decision 'false' taken 207 times.
 456 for (const Vertex& vert : *current_sf.slice) {
93
1/2
✓ Branch 1 taken 249 times.
✗ Branch 2 not taken.
 249 EdgeVec q_out_edges = circ.get_out_edges_of_type(vert, EdgeType::Quantum);
94
1/2
✓ Branch 1 taken 249 times.
✗ Branch 2 not taken.
 249 Qubit qb1;
95
1/2
✓ Branch 1 taken 249 times.
✗ Branch 2 not taken.
 249 Qubit qb2;
96 249 for (const std::pair<UnitID, Edge>& pair :
97
5/8
✓ Branch 5 taken 5606 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 5606 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 5855 times.
✗ Branch 12 not taken.
✓ Branch 13 taken 5606 times.
✓ Branch 14 taken 249 times.
 6104 current_sf.quantum_out_edges->get<TagKey>()) {
98
3/4
✓ Branch 2 taken 5606 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 249 times.
✓ Branch 5 taken 5357 times.
2/2
✓ Decision 'true' taken 249 times.
✓ Decision 'false' taken 5357 times.
 5606 if (pair.second == q_out_edges[0])
99
1/2
✓ Branch 1 taken 249 times.
✗ Branch 2 not taken.
 249 qb1 = Qubit(pair.first);
100
3/4
✓ Branch 2 taken 5357 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 249 times.
✓ Branch 5 taken 5108 times.
2/2
✓ Decision 'true' taken 249 times.
✓ Decision 'false' taken 5108 times.
 5357 else if (pair.second == q_out_edges[1])
101
1/2
✓ Branch 1 taken 249 times.
✗ Branch 2 not taken.
 249 qb2 = Qubit(pair.first);
102 }
103
8/10
✓ Branch 1 taken 249 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 215 times.
✓ Branch 4 taken 34 times.
✓ Branch 6 taken 215 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 207 times.
✓ Branch 9 taken 8 times.
✓ Branch 10 taken 207 times.
✓ Branch 11 taken 42 times.
2/2
✓ Decision 'true' taken 207 times.
✓ Decision 'false' taken 42 times.
 249 if (!q_graph.edge_exists(qb1, qb2) && !q_graph.edge_exists(qb2, qb1)) {
104
1/2
✓ Branch 1 taken 207 times.
✗ Branch 2 not taken.
 207 q_graph.add_connection(qb1, qb2, slice + 1);
105 207 count_edges++;
106 }
107 249 }
108
109
1/2
✓ Branch 1 taken 207 times.
✗ Branch 2 not taken.
 207 current_sf.next_slicefrontier();
110 }
111
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 q_graph.remove_stray_nodes();
112 104 return q_graph;
113 52 }
114
115 9 QubitGraph generate_interaction_graph(
116 const Circuit& circ, unsigned depth_limit) {
117
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 std::set<Qubit> qubits_considered = interacting_qbs(circ);
118
2/4
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 9 times.
✗ Branch 5 not taken.
 9 QubitGraph q_graph(circ.all_qubits());
119
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 PlacementFrontier current_sf(circ);
120
121
7/8
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 3 times.
✓ Branch 4 taken 46 times.
✓ Branch 5 taken 6 times.
✓ Branch 6 taken 46 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 46 times.
✓ Branch 9 taken 9 times.
0/1
? Decision couldn't be analyzed.
 101 for (unsigned slice = 0; slice < depth_limit && !current_sf.slice->empty() &&
122 46 qubits_considered.size() > 1;
123 slice++) {
124
2/2
✓ Branch 6 taken 62 times.
✓ Branch 7 taken 46 times.
2/2
✓ Decision 'true' taken 62 times.
✓ Decision 'false' taken 46 times.
 108 for (const Vertex& vert : *current_sf.slice) {
125
1/2
✓ Branch 1 taken 62 times.
✗ Branch 2 not taken.
 62 EdgeVec q_out_edges = circ.get_out_edges_of_type(vert, EdgeType::Quantum);
126
1/2
✓ Branch 1 taken 62 times.
✗ Branch 2 not taken.
 62 Qubit qb1;
127
1/2
✓ Branch 1 taken 62 times.
✗ Branch 2 not taken.
 62 Qubit qb2;
128 62 for (const std::pair<UnitID, Edge>& pair :
129
5/8
✓ Branch 5 taken 6394 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 6394 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 6456 times.
✗ Branch 12 not taken.
✓ Branch 13 taken 6394 times.
✓ Branch 14 taken 62 times.
 6518 current_sf.quantum_out_edges->get<TagKey>()) {
130
3/4
✓ Branch 2 taken 6394 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 62 times.
✓ Branch 5 taken 6332 times.
2/2
✓ Decision 'true' taken 62 times.
✓ Decision 'false' taken 6332 times.
 6394 if (pair.second == q_out_edges[0])
131
1/2
✓ Branch 1 taken 62 times.
✗ Branch 2 not taken.
 62 qb1 = Qubit(pair.first);
132
3/4
✓ Branch 2 taken 6332 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 62 times.
✓ Branch 5 taken 6270 times.
2/2
✓ Decision 'true' taken 62 times.
✓ Decision 'false' taken 6270 times.
 6332 else if (pair.second == q_out_edges[1])
133
1/2
✓ Branch 1 taken 62 times.
✗ Branch 2 not taken.
 62 qb2 = Qubit(pair.first);
134 }
135 const bool qb1_considered =
136
1/2
✓ Branch 2 taken 62 times.
✗ Branch 3 not taken.
 62 (qubits_considered.find(qb1) != qubits_considered.end());
137 const bool qb2_considered =
138
1/2
✓ Branch 2 taken 62 times.
✗ Branch 3 not taken.
 62 (qubits_considered.find(qb2) != qubits_considered.end());
139
8/10
✓ Branch 1 taken 62 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 62 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 35 times.
✓ Branch 6 taken 27 times.
✓ Branch 7 taken 13 times.
✓ Branch 8 taken 22 times.
✓ Branch 9 taken 40 times.
✓ Branch 10 taken 22 times.
2/2
✓ Decision 'true' taken 40 times.
✓ Decision 'false' taken 22 times.
 62 if ((qb2 != qb1) && (qb1_considered || qb2_considered)) {
140
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 27 times.
2/2
✓ Decision 'true' taken 13 times.
✓ Decision 'false' taken 27 times.
 40 if (!qb1_considered) {
141
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 qubits_considered.erase(qb2);
142
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 24 times.
2/2
✓ Decision 'true' taken 3 times.
✓ Decision 'false' taken 24 times.
 27 } else if (!qb2_considered) {
143
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 qubits_considered.erase(qb1);
144
2/4
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 24 times.
✗ Branch 4 not taken.
1/2
✓ Decision 'true' taken 24 times.
✗ Decision 'false' not taken.
 24 } else if (!q_graph.edge_exists(qb1, qb2)) {
145
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 const unsigned out1 = q_graph.get_degree(qb1);
146
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 const unsigned out2 = q_graph.get_degree(qb2);
147
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 q_graph.add_connection(qb1, qb2, slice + 1);
148
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
2/2
✓ Decision 'true' taken 12 times.
✓ Decision 'false' taken 12 times.
 24 if (out1 == 1) {
149
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 qubits_considered.erase(qb1);
150 }
151
2/2
✓ Branch 0 taken 9 times.
✓ Branch 1 taken 15 times.
2/2
✓ Decision 'true' taken 9 times.
✓ Decision 'false' taken 15 times.
 24 if (out2 == 1) {
152
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 qubits_considered.erase(qb2);
153 }
154 } else {
155 ✗ qubits_considered.erase(qb1);
156 ✗ qubits_considered.erase(qb2);
157 }
158 }
159 62 }
160
1/2
✓ Branch 1 taken 46 times.
✗ Branch 2 not taken.
 46 current_sf.next_slicefrontier();
161 }
162
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 q_graph.remove_stray_nodes();
163
164 18 return q_graph;
165 9 }
166
167 9 QubitLineList qubit_lines(const Circuit& circ) {
168
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 const QubitGraph q_graph = generate_interaction_graph(circ);
169
3/4
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 1 times.
✓ Branch 6 taken 8 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 8 times.
 9 if (q_graph.get_all_edges_vec().size() == 0) {
170 1 return {};
171 }
172 8 std::set<Qubit> all_qb;
173
3/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 472 times.
✓ Branch 9 taken 8 times.
0/1
? Decision couldn't be analyzed.
 480 for (const Qubit& qb : circ.all_qubits()) {
174
1/2
✓ Branch 1 taken 472 times.
✗ Branch 2 not taken.
 472 all_qb.insert(qb);
175 8 }
176 8 QubitLineList found_lines;
177 8 unsigned found_line_size = 0;
178
2/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
 8 QubitGraph::UndirectedConnGraph graph = q_graph.get_undirected_connectivity();
179 do {
180
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 auto u_line = graphs::longest_simple_path(graph);
181 16 QubitLine found;
182
2/4
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✓ Branch 6 taken 16 times.
✗ Branch 7 not taken.
 16 std::transform(
183 u_line.begin(), u_line.end(), std::back_inserter(found),
184 35 [&graph](auto v) -> Qubit { return graph[v]; });
185 16 found_line_size = found.size();
186
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 8 times.
2/2
✓ Decision 'true' taken 8 times.
✓ Decision 'false' taken 8 times.
 16 if (found_line_size > 1) {
187
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 found_lines.push_back(found);
188
2/2
✓ Branch 5 taken 27 times.
✓ Branch 6 taken 8 times.
2/2
✓ Decision 'true' taken 27 times.
✓ Decision 'false' taken 8 times.
 35 for (const auto& vertex : u_line) {
189
1/2
✓ Branch 1 taken 27 times.
✗ Branch 2 not taken.
 27 boost::clear_vertex(vertex, graph);
190 }
191
2/2
✓ Branch 6 taken 27 times.
✓ Branch 7 taken 8 times.
2/2
✓ Decision 'true' taken 27 times.
✓ Decision 'false' taken 8 times.
 35 for (Qubit q : found) {
192
1/2
✓ Branch 1 taken 27 times.
✗ Branch 2 not taken.
 27 all_qb.erase(q);
193 27 }
194 }
195
2/2
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 8 times.
2/2
✓ Decision 'true' taken 8 times.
✓ Decision 'false' taken 8 times.
 16 } while (found_line_size > 1);
196
197
3/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 472 times.
✓ Branch 9 taken 8 times.
0/1
? Decision couldn't be analyzed.
 480 for (const Qubit& qb : circ.all_qubits()) {
198
7/12
✓ Branch 2 taken 472 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 445 times.
✓ Branch 6 taken 27 times.
✓ Branch 10 taken 445 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 445 times.
✗ Branch 14 not taken.
✓ Branch 17 taken 445 times.
✓ Branch 18 taken 445 times.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
2/2
✓ Decision 'true' taken 8 times.
✓ Decision 'false' taken 909 times.
 917 if (all_qb.find(qb) != all_qb.end()) found_lines.push_back({qb});
199 8 }
200 8 return found_lines;
201 9 }
202
203 // remove a given number of nodes from the architecture, return a set of usable
204 // nodes (the remainder)
205 8 node_set_t best_nodes(Architecture& arc, unsigned n_remove) {
206
1/2
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
 8 node_set_t all_nodes = arc.nodes();
207 8 node_set_t bad_nodes;
208 // if there are nodes 'removed' already count them as bad nodes
209
2/2
✓ Branch 6 taken 473 times.
✓ Branch 7 taken 8 times.
2/2
✓ Decision 'true' taken 473 times.
✓ Decision 'false' taken 8 times.
 481 for (Node n : all_nodes) {
210
2/4
✓ Branch 1 taken 473 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 473 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 473 times.
 473 if (arc.get_degree(n) == 0) {
211 ✗ bad_nodes.insert(n);
212 ✗ n_remove--;
213 }
214 473 }
215
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 node_set_t removed_nodes = arc.remove_worst_nodes(n_remove);
216
1/2
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
 8 bad_nodes.insert(removed_nodes.begin(), removed_nodes.end());
217 8 node_set_t good_nodes; // keep track of nodes of architecture actually used
218
2/4
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
✓ Branch 9 taken 8 times.
✗ Branch 10 not taken.
 8 std::set_difference(
219 all_nodes.begin(), all_nodes.end(), bad_nodes.begin(), bad_nodes.end(),
220 std::inserter(good_nodes, good_nodes.begin()));
221 16 return good_nodes;
222 8 }
223
224 // map qubit lines to node lines, erasing qubit lines as it goes
225 8 qubit_mapping_t map_lines(
226 QubitLineList& qb_lines, const std::vector<node_vector_t>& node_lines) {
227 8 qubit_mapping_t outmap;
228
229 // go through all node lines
230
2/2
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 8 times.
2/2
✓ Decision 'true' taken 8 times.
✓ Decision 'false' taken 8 times.
 16 for (unsigned i = 0; i < node_lines.size(); i++) {
231
1/2
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
 8 node_vector_t node_lst = node_lines[i];
232
2/2
✓ Branch 4 taken 27 times.
✓ Branch 5 taken 8 times.
2/2
✓ Decision 'true' taken 27 times.
✓ Decision 'false' taken 8 times.
 35 for (const Node& node : node_lst) {
233
1/2
✓ Branch 5 taken 27 times.
✗ Branch 6 not taken.
 27 outmap.insert({*qb_lines[i].begin(), node});
234
1/2
✓ Branch 5 taken 27 times.
✗ Branch 6 not taken.
 27 qb_lines[i].erase(qb_lines[i].begin());
235 }
236 8 }
237 8 return outmap;
238 }
239
240 // trivially place qubit lines on to available nodes, return map
241 8 qubit_mapping_t place_qubit_lines(
242 const QubitLineList& qb_lines, node_set_t available_nodes) {
243 8 qubit_mapping_t outmap;
244
245 8 node_set_t::iterator node_it = available_nodes.begin();
246
2/2
✓ Branch 5 taken 8 times.
✓ Branch 6 taken 8 times.
2/2
✓ Decision 'true' taken 8 times.
✓ Decision 'false' taken 8 times.
 16 for (const QubitLine& line : qb_lines) {
247
1/2
✗ Branch 5 not taken.
✓ Branch 6 taken 8 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 8 times.
 8 for (const Qubit& qb : line) {
248
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (node_it == available_nodes.end()) {
249 ✗ throw ArchitectureInvalidity("Not enough nodes to place all qubits.");
250 }
251 ✗ outmap.insert({qb, *node_it});
252 ✗ ++node_it;
253 }
254 }
255 16 return outmap;
256 }
257
258 // Determine intial qubit placement by requesting lines of architecture to place
259 // lines of qubits on
260 8 qubit_mapping_t lines_on_arc(
261 Architecture arc, QubitLineList qb_lines, unsigned n_qubits) {
262 8 unsigned difference = arc.n_nodes() - n_qubits;
263 // sort from longest to shortest
264
1/2
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
 8 std::sort(qb_lines.begin(), qb_lines.end(), [](QubitLine x, QubitLine y) {
265 2429 return (x.size() > y.size());
266 });
267
268 // get rid of one qubit lines
269
5/6
✓ Branch 1 taken 453 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 445 times.
✓ Branch 6 taken 8 times.
✓ Branch 7 taken 445 times.
✓ Branch 8 taken 8 times.
0/1
? Decision couldn't be analyzed.
 453 while (!qb_lines.empty() && qb_lines.back().size() < 2) {
270 445 difference++;
271 445 qb_lines.pop_back();
272 }
273
274 // remove poorly connected nodes, up to the number not used by mapping
275
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 node_set_t unused_nodes = best_nodes(arc, difference);
276
277 // find lengths required
278 8 std::vector<unsigned> lengths;
279
2/2
✓ Branch 4 taken 8 times.
✓ Branch 5 taken 8 times.
2/2
✓ Decision 'true' taken 8 times.
✓ Decision 'false' taken 8 times.
 16 for (const QubitLine& line : qb_lines) {
280
1/2
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
 8 lengths.push_back(line.size());
281 }
282
283 // attempt to find lines of required length on architecture
284
2/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
 8 std::vector<node_vector_t> node_lines = arc.get_lines(lengths);
285
286 // map qubit lines to node lines to some extent
287
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 qubit_mapping_t outmap = map_lines(qb_lines, node_lines);
288
2/2
✓ Branch 3 taken 27 times.
✓ Branch 4 taken 8 times.
2/2
✓ Decision 'true' taken 27 times.
✓ Decision 'false' taken 8 times.
 35 for (qubit_mapping_t::iterator it = outmap.begin(); it != outmap.end();
289 27 ++it) {
290
1/2
✓ Branch 2 taken 27 times.
✗ Branch 3 not taken.
 27 unused_nodes.erase(it->second);
291 }
292 // map remain remaining qubit lines trivially
293
2/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
 8 qubit_mapping_t remainder_map = place_qubit_lines(qb_lines, unused_nodes);
294
1/2
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
 8 outmap.insert(remainder_map.begin(), remainder_map.end());
295
296 16 return outmap;
297 8 }
298
299 // Uses line placement method to produce a suitable qubit_mapping_t for initial
300 // placement Note that arc is passed by value, since this function modifies it.
301 ✗ qubit_mapping_t line_placement(const Circuit& circ, Architecture arc) {
302 ✗ QubitLineList qb_lines = qubit_lines(circ);
303
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (qb_lines.empty()) {
304 ✗ return qubit_mapping_t();
305 } else {
306 ✗ unsigned n_qb = circ.n_qubits();
307 ✗ return lines_on_arc(arc, qb_lines, n_qb);
308 }
309 }
310
311 // calculate a cost value for map being considered
312 1138 double Monomorpher::map_cost(const qubit_bimap_t& n_map) {
313 1138 double cost = 0.0;
314 1138 const int approx_depth = circ.n_gates() / circ.n_qubits() + 1;
315 // constants for scaling single qubit error
316 1138 constexpr double c1 = 0.5;
317 1138 constexpr double d1 = 1 - 1 / c1;
318
8/14
✓ Branch 1 taken 1138 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1138 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 4232 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 4232 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 4232 times.
✗ Branch 14 not taken.
✓ Branch 16 taken 5370 times.
✗ Branch 17 not taken.
✓ Branch 18 taken 4232 times.
✓ Branch 19 taken 1138 times.
0/1
? Decision couldn't be analyzed.
 5370 for (auto [qb, node] : n_map) {
319 // add fidelities of edges from node, weighted by if edge is used by
320 // interaction graph
321
1/2
✓ Branch 1 taken 4232 times.
✗ Branch 2 not taken.
 4232 node_set_t neighs = arc.get_neighbour_nodes(node);
322 4232 double edge_sum = 1.0;
323
2/2
✓ Branch 6 taken 13412 times.
✓ Branch 7 taken 4232 times.
2/2
✓ Decision 'true' taken 13412 times.
✓ Decision 'false' taken 4232 times.
 17644 for (Node nei : neighs) {
324 13412 double fwd_edge_weighting = 1.0, bck_edge_weighting = 1.0;
325 // check if neighbour node is mapped
326
1/2
✓ Branch 1 taken 13412 times.
✗ Branch 2 not taken.
 13412 r_const_iterator_t nei_qb_it = n_map.right.find(nei);
327
4/6
✓ Branch 1 taken 13412 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 13412 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 6640 times.
✓ Branch 7 taken 6772 times.
2/2
✓ Decision 'true' taken 6772 times.
✓ Decision 'false' taken 6640 times.
 13412 if (nei_qb_it == n_map.right.end()) continue;
328 // if ( nei_qb_it != n_map.end()){
329
2/4
✓ Branch 1 taken 6772 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 6772 times.
✗ Branch 5 not taken.
 6772 unsigned edge_val = q_graph.get_connection_weight(qb, nei_qb_it->second);
330 // check if either directed interaction exists
331 6188 auto place_interactions_boost = [&](unsigned edge_v) {
332 6188 return config.depth_limit - edge_v + 1;
333 6772 };
334 // if edge is used by interaction in mapping, weight edge higher
335
2/2
✓ Branch 0 taken 3094 times.
✓ Branch 1 taken 3678 times.
2/2
✓ Decision 'true' taken 3094 times.
✓ Decision 'false' taken 3678 times.
 6772 if (edge_val) {
336 3094 fwd_edge_weighting += place_interactions_boost(edge_val);
337 } else {
338
2/4
✓ Branch 1 taken 3678 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3678 times.
✗ Branch 5 not taken.
 3678 edge_val = q_graph.get_connection_weight(nei_qb_it->second, qb);
339
2/2
✓ Branch 0 taken 3094 times.
✓ Branch 1 taken 584 times.
2/2
✓ Decision 'true' taken 3094 times.
✓ Decision 'false' taken 584 times.
 3678 if (edge_val) {
340 3094 bck_edge_weighting += place_interactions_boost(edge_val);
341 }
342 }
343 // }
344
1/2
✓ Branch 2 taken 6772 times.
✗ Branch 3 not taken.
 6772 gate_error_t fwd_error = characterisation.get_error({node, nei});
345
1/2
✓ Branch 2 taken 6772 times.
✗ Branch 3 not taken.
 6772 gate_error_t bck_error = characterisation.get_error({nei, node});
346 6772 edge_sum += fwd_edge_weighting * (1.0 - fwd_error);
347 6772 edge_sum += bck_edge_weighting * (1.0 - bck_error);
348
2/2
✓ Branch 1 taken 6772 times.
✓ Branch 2 taken 6640 times.
 13412 }
349
350 // bigger edge sum -> smaller cost
351 4232 cost += 1.0 / (edge_sum);
352
353 // add error rate of node
354
1/2
✓ Branch 1 taken 4232 times.
✗ Branch 2 not taken.
 4232 gate_error_t single_error = characterisation.get_error(node);
355 4232 cost += d1 + 1.0 / ((1.0 - single_error) + c1);
356
1/2
✓ Branch 1 taken 4232 times.
✗ Branch 2 not taken.
 4232 readout_error_t readout_error = characterisation.get_readout_error(node);
357 4232 cost += (d1 + 1.0 / ((1.0 - readout_error) + c1)) / (approx_depth * 20);
358 // TODO add readout weighting to PlacementConfig?
359 4232 }
360
361 1138 return cost;
362 }
363
364 18 std::vector<MapCost> Monomorpher::place(unsigned max_return) {
365
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 18 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 18 times.
 18 if (max_return < 1)
366
0/1
? Decision couldn't be analyzed.
 ✗ throw PlacementError("Max return maps for place must be at least 1.");
367
1/2
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
 18 const unsigned interacting_nodes = q_graph.n_connected();
368
5/8
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 18 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 1 times.
✓ Branch 7 taken 17 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 18 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 19 times.
 19 if ((circ.n_gates() / circ.n_qubits()) >= config.arc_contraction_ratio &&
369
2/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
 1 circ.n_qubits() > 3) {
370 ✗ best_nodes(arc, arc.n_nodes() - interacting_nodes);
371 }
372
373 std::vector<qubit_bimap_t> potential_maps = monomorphism_edge_break(
374
2/2
✓ Branch 1 taken 17 times.
✓ Branch 2 taken 1 times.
 18 arc, q_graph, config.monomorphism_max_matches, config.timeout);
375 17 std::vector<MapCost> map_costs;
376
2/2
✓ Branch 1 taken 1138 times.
✓ Branch 2 taken 17 times.
2/2
✓ Decision 'true' taken 1138 times.
✓ Decision 'false' taken 17 times.
 1155 for (unsigned i = 0; i < potential_maps.size(); i++) {
377 1138 qubit_bimap_t& chosen = potential_maps[i];
378
1/2
✓ Branch 1 taken 1138 times.
✗ Branch 2 not taken.
 1138 double cost = map_cost(chosen);
379 1138 qubit_mapping_t converted_map;
380
7/12
✓ Branch 1 taken 1138 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1138 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 4232 times.
✗ Branch 8 not taken.
✓ Branch 11 taken 4232 times.
✗ Branch 12 not taken.
✓ Branch 14 taken 5370 times.
✗ Branch 15 not taken.
✓ Branch 16 taken 4232 times.
✓ Branch 17 taken 1138 times.
0/1
? Decision couldn't be analyzed.
 5370 for (auto [qb, node] : chosen.left) {
381
1/2
✓ Branch 1 taken 4232 times.
✗ Branch 2 not taken.
 4232 converted_map[qb] = node;
382 4232 }
383
2/4
✓ Branch 1 taken 1138 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1138 times.
✗ Branch 5 not taken.
 1138 map_costs.push_back({converted_map, cost});
384 1138 }
385
386 17 max_return = std::min(static_cast<unsigned>(map_costs.size()), max_return);
387
1/2
✓ Branch 4 taken 17 times.
✗ Branch 5 not taken.
 34 std::nth_element(
388 17 map_costs.begin(), map_costs.begin() + max_return - 1, map_costs.end());
389
1/2
✓ Branch 5 taken 17 times.
✗ Branch 6 not taken.
 17 const MapCost nth_map = *(map_costs.begin() + max_return - 1);
390 17 for (std::vector<MapCost>::iterator it = map_costs.begin();
391
2/2
✓ Branch 2 taken 1138 times.
✓ Branch 3 taken 17 times.
 1155 it != map_costs.end();) {
392
2/2
✓ Branch 2 taken 527 times.
✓ Branch 3 taken 611 times.
2/2
✓ Decision 'true' taken 527 times.
✓ Decision 'false' taken 611 times.
 1138 if (*it > nth_map) {
393
1/2
✓ Branch 2 taken 527 times.
✗ Branch 3 not taken.
 527 it = map_costs.erase(it);
394 } else {
395 611 ++it;
396 }
397 }
398
399
3/4
✓ Branch 1 taken 11 times.
✓ Branch 2 taken 6 times.
✓ Branch 4 taken 11 times.
✗ Branch 5 not taken.
0/1
? Decision couldn't be analyzed.
 17 if (max_return < map_costs.size()) map_costs.resize(max_return);
400 34 return map_costs;
401 17 }
402
403 } // namespace tket
404