GCC Code Coverage Report

Directory: ./
File: ArchAwareSynth/SteinerForest.cpp
Date: 2022-10-15 05:10:18
Warnings: 9 unchecked decisions!
Exec Total Coverage
Lines: 269 273 98.5%
Functions: 18 18 100.0%
Branches: 248 410 60.5%
Decisions: 57 80 71.2%
Line Branch Decision Exec Source
1 // Copyright 2019-2022 Cambridge Quantum Computing
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "SteinerForest.hpp"
16
17 #include <algorithm>
18 #include <vector>
19
20 #include "Architecture/Architecture.hpp"
21 #include "SteinerTree.hpp"
22
23 namespace tket {
24 namespace aas {
25
26 157 ParityList parity_column_to_list(const std::vector<bool> &parity_column) {
27 157 ParityList parity_list;
28
2/2
✓ Branch 1 taken 859 times.
✓ Branch 2 taken 157 times.
2/2
✓ Decision 'true' taken 859 times.
✓ Decision 'false' taken 157 times.
 1016 for (unsigned i = 0; i != parity_column.size(); ++i) {
29
3/4
✓ Branch 1 taken 859 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 531 times.
✓ Branch 4 taken 328 times.
2/2
✓ Decision 'true' taken 531 times.
✓ Decision 'false' taken 328 times.
 859 if (parity_column[i]) {
30
1/2
✓ Branch 1 taken 531 times.
✗ Branch 2 not taken.
 531 parity_list.push_back(i);
31 }
32 }
33 157 return parity_list;
34 }
35
36 97 SteinerForest::SteinerForest(
37
2/4
✓ Branch 3 taken 97 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 97 times.
✗ Branch 7 not taken.
 97 const PathHandler &paths, const PhasePolyBox &phasepolybox) {
38 97 global_cost = 0;
39 97 unsigned id_counter = 0;
40 97 const PhasePolynomial &phasepoly = phasepolybox.get_phase_polynomial();
41 const MatrixXb &linear_fn_matrix_ppb =
42 97 phasepolybox.get_linear_transformation();
43 97 unsigned n_qubits = phasepolybox.get_n_qubits();
44
2/4
✓ Branch 2 taken 97 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 97 times.
✗ Branch 6 not taken.
 97 synth_circuit = Circuit(n_qubits);
45
1/2
✓ Branch 1 taken 97 times.
✗ Branch 2 not taken.
 97 linear_function = DiagMatrix(linear_fn_matrix_ppb);
46
47
2/2
✓ Branch 5 taken 157 times.
✓ Branch 6 taken 97 times.
2/2
✓ Decision 'true' taken 157 times.
✓ Decision 'false' taken 97 times.
 254 for (const auto &parity : phasepoly) {
48
1/2
✓ Branch 1 taken 157 times.
✗ Branch 2 not taken.
 157 ParityList parity_list = parity_column_to_list(parity.first);
49
1/2
✓ Branch 3 taken 157 times.
✗ Branch 4 not taken.
 157 SteinerTree tree(paths, parity_list, *parity_list.begin());
50 157 global_cost += tree.tree_cost;
51
1/2
✓ Branch 1 taken 157 times.
✗ Branch 2 not taken.
 157 std::pair<SteinerTree, Expr> parity_on_graph{tree, parity.second};
52
53
1/2
✓ Branch 1 taken 157 times.
✗ Branch 2 not taken.
 157 CostedTrees::iterator iter = current_trees.find(tree.tree_cost);
54
2/2
✓ Branch 2 taken 121 times.
✓ Branch 3 taken 36 times.
0/1
? Decision couldn't be analyzed.
 157 if (iter == current_trees.end())
55
6/12
✓ Branch 1 taken 121 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 121 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 121 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 121 times.
✗ Branch 12 not taken.
✓ Branch 16 taken 121 times.
✓ Branch 17 taken 121 times.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
 242 current_trees.insert({tree.tree_cost, {parity_on_graph}});
56 else
57
1/2
✓ Branch 2 taken 36 times.
✗ Branch 3 not taken.
 36 iter->second.push_back(parity_on_graph);
58
59 157 ++id_counter;
60 157 }
61 97 tree_count = id_counter;
62
63 97 CostedTrees new_trees;
64
2/2
✓ Branch 5 taken 121 times.
✓ Branch 6 taken 97 times.
2/2
✓ Decision 'true' taken 121 times.
✓ Decision 'false' taken 97 times.
 218 for (const auto &cost_trees : current_trees) {
65
3/4
✓ Branch 4 taken 157 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 157 times.
✓ Branch 9 taken 121 times.
0/1
? Decision couldn't be analyzed.
 278 for (auto tree_expr : cost_trees.second) {
66 /* If we come across a tree which has only 1 node, check that its
67 properties are correct
68 and remove it from the forest, leaving an Rz in the circuit. */
69
3/4
✓ Branch 1 taken 157 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 54 times.
✓ Branch 4 taken 103 times.
2/2
✓ Decision 'true' taken 54 times.
✓ Decision 'false' taken 103 times.
 157 if (tree_expr.first.fully_reduced()) {
70 54 unsigned qubit_id = UINT_MAX;
71
2/2
✓ Branch 5 taken 216 times.
✓ Branch 6 taken 54 times.
2/2
✓ Decision 'true' taken 216 times.
✓ Decision 'false' taken 54 times.
 270 for (SteinerNodeType q : tree_expr.first.node_types) {
72
2/2
✓ Branch 0 taken 54 times.
✓ Branch 1 taken 162 times.
2/2
✓ Decision 'true' taken 54 times.
✓ Decision 'false' taken 162 times.
 216 if (q == SteinerNodeType::Leaf) {
73
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 54 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 54 times.
 54 if (qubit_id != UINT_MAX) {
74 ✗ throw std::logic_error("Two nodes found to add the Rz");
75 } else {
76 54 qubit_id = tree_expr.first.root;
77 }
78 }
79 }
80
81
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 54 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 54 times.
 54 if (qubit_id == UINT_MAX) {
82 ✗ throw std::logic_error("No node found to add the Rz");
83 }
84
85
1/2
✓ Branch 2 taken 54 times.
✗ Branch 3 not taken.
 54 std::vector<unsigned> qubit{qubit_id};
86
87
1/2
✓ Branch 2 taken 54 times.
✗ Branch 3 not taken.
 54 synth_circuit.add_op(OpType::Rz, tree_expr.second, qubit);
88 54 --tree_count;
89 /* Otherwise, the tree stays in. */
90 54 } else {
91
1/2
✓ Branch 1 taken 103 times.
✗ Branch 2 not taken.
 103 CostedTrees::iterator iter = new_trees.find(tree_expr.first.tree_cost);
92
2/2
✓ Branch 2 taken 93 times.
✓ Branch 3 taken 10 times.
0/1
? Decision couldn't be analyzed.
 103 if (iter == new_trees.end())
93
6/12
✓ Branch 1 taken 93 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 93 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 93 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 93 times.
✗ Branch 12 not taken.
✓ Branch 16 taken 93 times.
✓ Branch 17 taken 93 times.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
 186 new_trees.insert({tree_expr.first.tree_cost, {tree_expr}});
94 else
95
1/2
✓ Branch 2 taken 10 times.
✗ Branch 3 not taken.
 10 iter->second.push_back(tree_expr);
96 103 unsigned cost_change = tree_expr.first.last_operation_cost;
97 103 global_cost += cost_change;
98 }
99 157 }
100 }
101
1/2
✓ Branch 1 taken 97 times.
✗ Branch 2 not taken.
 97 current_trees = new_trees;
102 97 }
103
104 1089 void SteinerForest::add_row_globally(unsigned i, unsigned j) {
105 /* CNOT with control j and target i. Which way round the indices are is a wee
106 * bit fiddly. */
107
1/2
✓ Branch 2 taken 1089 times.
✗ Branch 3 not taken.
 1089 std::vector<unsigned> qbs = {j, i};
108
1/2
✓ Branch 2 taken 1089 times.
✗ Branch 3 not taken.
 1089 synth_circuit.add_op(OpType::CX, qbs);
109
1/2
✓ Branch 1 taken 1089 times.
✗ Branch 2 not taken.
 1089 linear_function.col_add(
110 i, j); // prepend a CNOT to the linear reversible function
111
112 1089 CostedTrees new_trees;
113
114
2/2
✓ Branch 5 taken 1998 times.
✓ Branch 6 taken 1089 times.
2/2
✓ Decision 'true' taken 1998 times.
✓ Decision 'false' taken 1089 times.
 3087 for (const auto &cost_trees : current_trees) {
115
3/4
✓ Branch 4 taken 2134 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 2134 times.
✓ Branch 9 taken 1998 times.
0/1
? Decision couldn't be analyzed.
 4132 for (auto tree_expr : cost_trees.second) {
116
1/2
✓ Branch 1 taken 2134 times.
✗ Branch 2 not taken.
 2134 tree_expr.first.add_row(i, j);
117 /* If the tree has been fully reduced, remove it from the
118 forest */
119
3/4
✓ Branch 1 taken 2134 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 280 times.
✓ Branch 4 taken 1854 times.
2/2
✓ Decision 'true' taken 280 times.
✓ Decision 'false' taken 1854 times.
 2134 if (tree_expr.first.fully_reduced()) {
120
1/2
✓ Branch 2 taken 280 times.
✗ Branch 3 not taken.
 280 std::vector<unsigned> qubit{i};
121
1/2
✓ Branch 2 taken 280 times.
✗ Branch 3 not taken.
 280 synth_circuit.add_op(OpType::Rz, tree_expr.second, qubit);
122 280 --tree_count;
123 280 }
124 /* Otherwise, update the forest */
125 else {
126
1/2
✓ Branch 1 taken 1854 times.
✗ Branch 2 not taken.
 1854 CostedTrees::iterator iter = new_trees.find(tree_expr.first.tree_cost);
127
2/2
✓ Branch 2 taken 1759 times.
✓ Branch 3 taken 95 times.
0/1
? Decision couldn't be analyzed.
 1854 if (iter == new_trees.end())
128
6/12
✓ Branch 1 taken 1759 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 1759 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 1759 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 1759 times.
✗ Branch 12 not taken.
✓ Branch 16 taken 1759 times.
✓ Branch 17 taken 1759 times.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
 3518 new_trees.insert({tree_expr.first.tree_cost, {tree_expr}});
129 else
130
1/2
✓ Branch 2 taken 95 times.
✗ Branch 3 not taken.
 95 iter->second.push_back(tree_expr);
131 1854 unsigned cost_change = tree_expr.first.last_operation_cost;
132 1854 global_cost += cost_change;
133 }
134 2134 }
135 }
136
1/2
✓ Branch 1 taken 1089 times.
✗ Branch 2 not taken.
 1089 current_trees = new_trees;
137 1089 }
138
139 279 void SteinerForest::add_operation_list(const OperationList &oper_list) {
140
2/2
✓ Branch 5 taken 292 times.
✓ Branch 6 taken 279 times.
2/2
✓ Decision 'true' taken 292 times.
✓ Decision 'false' taken 279 times.
 571 for (const Operation &operation : oper_list) {
141
1/2
✓ Branch 1 taken 292 times.
✗ Branch 2 not taken.
 292 add_row_globally(operation.first, operation.second);
142 }
143 279 }
144
145 60 OperationList SteinerForest::operations_available_under_the_index(
146 const PathHandler &path, unsigned index) const {
147 60 OperationList operations;
148
2/2
✓ Branch 0 taken 162 times.
✓ Branch 1 taken 60 times.
2/2
✓ Decision 'true' taken 162 times.
✓ Decision 'false' taken 60 times.
 222 for (unsigned i = 0; i != index; ++i) {
149
1/2
✓ Branch 1 taken 162 times.
✗ Branch 2 not taken.
 162 CostedTrees::const_iterator iter = current_trees.find(i);
150
2/2
✓ Branch 2 taken 138 times.
✓ Branch 3 taken 24 times.
2/2
✓ Decision 'true' taken 48 times.
✓ Decision 'false' taken 114 times.
 162 if (iter == current_trees.end()) continue;
151
2/2
✓ Branch 5 taken 24 times.
✓ Branch 6 taken 24 times.
2/2
✓ Decision 'true' taken 24 times.
✓ Decision 'false' taken 24 times.
 48 for (const auto &tree_pair : iter->second) {
152 24 operations.splice(
153
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 48 operations.begin(), tree_pair.first.operations_available(path));
154 }
155 }
156 60 return operations;
157 }
158
159 2 OperationList SteinerForest::operations_available_at_index(
160 const PathHandler &path, unsigned index) const {
161 2 OperationList operations;
162
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 CostedTrees::const_iterator iter = current_trees.find(index);
163
1/2
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
0/1
? Decision couldn't be analyzed.
 2 if (iter != current_trees.end()) {
164
2/2
✓ Branch 5 taken 2 times.
✓ Branch 6 taken 2 times.
2/2
✓ Decision 'true' taken 2 times.
✓ Decision 'false' taken 2 times.
 4 for (const auto &tree_pair : iter->second) {
165 2 operations.splice(
166
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 4 operations.begin(), tree_pair.first.operations_available(path));
167 }
168 }
169 4 return operations;
170 }
171
172 278 OperationList SteinerForest::operations_available_at_min_costs(
173 const PathHandler &path) const {
174 278 OperationList operations;
175
176 // search in all trees with the minimal costs for operations
177
2/2
✓ Branch 7 taken 281 times.
✓ Branch 8 taken 278 times.
2/2
✓ Decision 'true' taken 281 times.
✓ Decision 'false' taken 278 times.
 559 for (const auto &tree_expr : current_trees.begin()->second) {
178
1/2
✓ Branch 1 taken 281 times.
✗ Branch 2 not taken.
 281 OperationList op_to_add = tree_expr.first.operations_available(path);
179
180
1/2
✓ Branch 5 taken 281 times.
✗ Branch 6 not taken.
 281 operations.insert(operations.end(), op_to_add.begin(), op_to_add.end());
181 281 }
182
183 278 return operations;
184 }
185
186 280 CostedOperations best_operations_lookahead(
187 const PathHandler &path, const SteinerForest &forest, unsigned lookahead) {
188
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 279 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 279 times.
 280 if (lookahead == 0) {
189
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 1 throw std::logic_error("Must look ahead at least one step");
190 }
191 279 CostedTrees::const_reverse_iterator r_iter = forest.current_trees.rbegin();
192
3/4
✓ Branch 2 taken 279 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 1 times.
✓ Branch 5 taken 278 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 278 times.
 279 if (r_iter == forest.current_trees.rend()) {
193
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 1 throw std::logic_error("Forest is empty");
194 }
195
196 OperationList operations_available =
197
1/2
✓ Branch 1 taken 278 times.
✗ Branch 2 not taken.
 278 forest.operations_available_at_min_costs(path);
198
199
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 278 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 278 times.
 278 if (operations_available.empty()) {
200 ✗ throw std::logic_error("Cannot find any operations");
201 }
202
203 // set up base case
204
1/2
✓ Branch 3 taken 278 times.
✗ Branch 4 not taken.
 278 OperationList ops{operations_available.front()};
205 CostedOperations costed_operations =
206
3/6
✓ Branch 1 taken 278 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 278 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 278 times.
✗ Branch 8 not taken.
 556 recursive_operation_search(path, forest, lookahead - 1, ops);
207 278 operations_available.pop_front();
208
209 278 for (OperationList::iterator op_iter = operations_available.begin();
210
2/2
✓ Branch 3 taken 442 times.
✓ Branch 4 taken 278 times.
 720 op_iter != operations_available.end(); ++op_iter) {
211
1/2
✓ Branch 2 taken 442 times.
✗ Branch 3 not taken.
 442 ops = {*op_iter};
212 CostedOperations candidate_operations =
213
3/6
✓ Branch 1 taken 442 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 442 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 442 times.
✗ Branch 8 not taken.
 884 recursive_operation_search(path, forest, lookahead - 1, ops);
214
215
4/4
✓ Branch 0 taken 409 times.
✓ Branch 1 taken 33 times.
✓ Branch 2 taken 33 times.
✓ Branch 3 taken 409 times.
2/2
✓ Decision 'true' taken 33 times.
✓ Decision 'false' taken 818 times.
 851 if ((candidate_operations.first < costed_operations.first) ||
216
3/4
✓ Branch 0 taken 360 times.
✓ Branch 1 taken 49 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 360 times.
 769 ((candidate_operations.first == costed_operations.first) &&
217 360 (candidate_operations.second.size() <
218 360 costed_operations.second.size()))) {
219 33 costed_operations = std::move(candidate_operations);
220 }
221 442 }
222
223 556 return costed_operations;
224 278 }
225
226 775 CostedOperations recursive_operation_search(
227 const PathHandler &path, SteinerForest forest, unsigned lookahead,
228 OperationList row_operations) {
229 775 CostedOperations costed_operations;
230 775 CostedOperations candidate_operations;
231
232
1/2
✓ Branch 1 taken 775 times.
✗ Branch 2 not taken.
 775 forest.add_row_globally(
233 775 row_operations.back().first, row_operations.back().second);
234
235
6/6
✓ Branch 0 taken 80 times.
✓ Branch 1 taken 695 times.
✓ Branch 3 taken 20 times.
✓ Branch 4 taken 60 times.
✓ Branch 5 taken 715 times.
✓ Branch 6 taken 60 times.
2/2
✓ Decision 'true' taken 715 times.
✓ Decision 'false' taken 60 times.
 775 if ((lookahead == 0) || (forest.current_trees.empty())) {
236
1/2
✓ Branch 1 taken 715 times.
✗ Branch 2 not taken.
 715 return {forest.global_cost, row_operations};
237 }
238 60 CostedTrees::const_reverse_iterator r_iter = forest.current_trees.rbegin();
239
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 unsigned index = r_iter->first;
240 OperationList operations_available =
241
1/2
✓ Branch 1 taken 60 times.
✗ Branch 2 not taken.
 60 forest.operations_available_under_the_index(path, index);
242
2/2
✓ Branch 1 taken 48 times.
✓ Branch 2 taken 12 times.
2/2
✓ Decision 'true' taken 48 times.
✓ Decision 'false' taken 12 times.
 60 if (operations_available.empty()) {
243
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 return {forest.global_cost, row_operations};
244 } else {
245
1/2
✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.
 12 row_operations.push_back(operations_available.front());
246 costed_operations =
247
3/6
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 12 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 12 times.
✗ Branch 8 not taken.
 12 recursive_operation_search(path, forest, lookahead - 1, row_operations);
248 12 row_operations.pop_back();
249 12 operations_available.pop_front();
250
251 12 for (OperationList::iterator op_iter = operations_available.begin();
252
2/2
✓ Branch 3 taken 42 times.
✓ Branch 4 taken 12 times.
 54 op_iter != operations_available.end(); ++op_iter) {
253
1/2
✓ Branch 2 taken 42 times.
✗ Branch 3 not taken.
 42 row_operations.push_back(*op_iter);
254
3/6
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 42 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 42 times.
✗ Branch 8 not taken.
 84 candidate_operations = recursive_operation_search(
255 42 path, forest, lookahead - 1, row_operations);
256
257 42 row_operations.pop_back();
258
259
4/4
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 6 times.
✓ Branch 3 taken 36 times.
2/2
✓ Decision 'true' taken 6 times.
✓ Decision 'false' taken 72 times.
 78 if ((candidate_operations.first < costed_operations.first) ||
260
3/4
✓ Branch 0 taken 23 times.
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 23 times.
 59 ((candidate_operations.first == costed_operations.first) &&
261 23 (candidate_operations.second.size() <
262 23 costed_operations.second.size()))) {
263 6 costed_operations = std::move(candidate_operations);
264 }
265 }
266 12 return costed_operations;
267 }
268 775 }
269
270 79 Circuit phase_poly_synthesis_int(
271 const Architecture &arch, const PhasePolyBox &phasepolybox,
272 unsigned lookahead, CNotSynthType cnottype) {
273
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 78 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 78 times.
 79 if (lookahead == 0)
274
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 throw std::logic_error(
275 "[AAS] the lookahead of the phase polynominal synthesis has to be "
276 2 "greater than 0");
277
278 78 CostedOperations best_operations;
279
280
1/2
✓ Branch 1 taken 78 times.
✗ Branch 2 not taken.
 78 PathHandler path(arch);
281
282
1/2
✓ Branch 1 taken 78 times.
✗ Branch 2 not taken.
 78 PathHandler acyclic_path = path.construct_acyclic_handler();
283
284
1/2
✓ Branch 1 taken 78 times.
✗ Branch 2 not taken.
 78 SteinerForest forest(acyclic_path, phasepolybox);
285
286
2/2
✓ Branch 1 taken 278 times.
✓ Branch 2 taken 78 times.
2/2
✓ Decision 'true' taken 278 times.
✓ Decision 'false' taken 78 times.
 356 while (!forest.current_trees.empty()) {
287 best_operations =
288
1/2
✓ Branch 1 taken 278 times.
✗ Branch 2 not taken.
 278 best_operations_lookahead(acyclic_path, forest, lookahead);
289
1/2
✓ Branch 1 taken 278 times.
✗ Branch 2 not taken.
 278 forest.add_operation_list(best_operations.second);
290 }
291
2/4
✓ Branch 2 taken 78 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 78 times.
✗ Branch 6 not taken.
 78 Circuit cnot_circ(path.get_size());
292
3/4
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 73 times.
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 78 switch (cnottype) {
293 2 case CNotSynthType::HamPath: {
294 cnot_circ =
295
2/4
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
 2 aas_CNOT_synth(forest.linear_function, path, CNotSynthType::HamPath);
296
297 // check if matrix is id, if not the result will be wrong
298 TKET_ASSERT(forest.linear_function.is_id());
299 2 break;
300 }
301 73 case CNotSynthType::Rec: {
302 Circuit resultofstep =
303
1/2
✓ Branch 1 taken 73 times.
✗ Branch 2 not taken.
 73 aas_CNOT_synth(forest.linear_function, path, CNotSynthType::Rec);
304
2/4
✓ Branch 1 taken 73 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 73 times.
✗ Branch 5 not taken.
 73 cnot_circ = cnot_circ >> resultofstep;
305
306 // check if matrix is id, if not the result will be wrong
307 TKET_ASSERT(forest.linear_function.is_id());
308 73 break;
309 73 }
310
1/1
✓ Decision 'true' taken 3 times.
 3 case CNotSynthType::SWAP: {
311
2/4
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3 times.
✗ Branch 5 not taken.
 3 cnot_circ = aas_CNOT_synth_SWAP(forest.linear_function, path);
312 // the check if the forest.linear_function is id is executed in the
313 // aas_CNOT_synth_SWAP function
314 3 break;
315 }
316
0/1
✗ Decision 'true' not taken.
 ✗ default: {
317 TKET_ASSERT(!"[AAS]: unknown type of cnot synth");
318 }
319 }
320
321
2/4
✓ Branch 1 taken 78 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 78 times.
✗ Branch 5 not taken.
 234 return forest.synth_circuit >> cnot_circ.dagger();
322 78 }
323
324 78 static PhasePolyBox make_placed_ppb(
325 const Architecture &arch, const PhasePolyBox &phasepolybox) {
326
2/4
✓ Branch 1 taken 78 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 78 times.
✗ Branch 6 not taken.
 78 Circuit circuit_ppb_place(*phasepolybox.to_circuit());
327
328
1/2
✓ Branch 2 taken 78 times.
✗ Branch 3 not taken.
 78 const std::string register_name = "surplus";
329
330
1/2
✓ Branch 1 taken 78 times.
✗ Branch 2 not taken.
 78 unsigned qb_counter = circuit_ppb_place.n_qubits();
331
3/4
✓ Branch 2 taken 87 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 9 times.
✓ Branch 5 taken 78 times.
0/1
? Decision couldn't be analyzed.
 87 while (arch.n_nodes() > circuit_ppb_place.n_qubits()) {
332
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 Qubit qb = Qubit(register_name, qb_counter);
333
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 circuit_ppb_place.add_qubit(qb);
334 9 ++qb_counter;
335 9 }
336
337 TKET_ASSERT(circuit_ppb_place.n_qubits() == arch.n_nodes());
338
339
1/2
✓ Branch 1 taken 78 times.
✗ Branch 2 not taken.
 78 qubit_vector_t q_vec_place = circuit_ppb_place.all_qubits();
340 78 std::map<Qubit, Node> qubit_to_nodes_place;
341 78 unsigned counter_place = 0;
342
343
2/2
✓ Branch 7 taken 456 times.
✓ Branch 8 taken 78 times.
2/2
✓ Decision 'true' taken 456 times.
✓ Decision 'false' taken 78 times.
 534 for (Node no_place : arch.nodes()) {
344
2/4
✓ Branch 1 taken 456 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 456 times.
✗ Branch 4 not taken.
1/2
✓ Decision 'true' taken 456 times.
✗ Decision 'false' not taken.
 456 if (counter_place < circuit_ppb_place.n_qubits()) {
345
1/2
✓ Branch 3 taken 456 times.
✗ Branch 4 not taken.
 456 qubit_to_nodes_place.insert({q_vec_place[counter_place], no_place});
346 456 ++counter_place;
347 }
348 456 }
349
350
1/2
✓ Branch 1 taken 78 times.
✗ Branch 2 not taken.
 78 circuit_ppb_place.rename_units(qubit_to_nodes_place);
351
352
1/2
✓ Branch 1 taken 78 times.
✗ Branch 2 not taken.
 156 return PhasePolyBox(circuit_ppb_place);
353 78 }
354
355 class PhasePolySynthesizer {
356 public:
357 78 PhasePolySynthesizer(
358 const Architecture &arch, const PhasePolyBox &phasepolybox,
359 unsigned lookahead, CNotSynthType cnottype)
360 78 : arch(arch),
361
1/2
✓ Branch 1 taken 78 times.
✗ Branch 2 not taken.
 78 placed_ppb(make_placed_ppb(arch, phasepolybox)),
362 78 lookahead(lookahead),
363 78 cnottype(cnottype) {}
364
365 78 Circuit get_result() {
366 78 return (cnottype == CNotSynthType::HamPath) ? get_result_using_hampath()
367
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 76 times.
 78 : get_result_standard();
368 }
369
370 private:
371 2 Circuit get_result_from_hampath(const std::vector<Node> &hampath) {
372 // maps from qubits/node to int
373 2 std::map<UnitID, UnitID> forward_contiguous_uids_q;
374 2 std::map<UnitID, UnitID> backward_contiguous_uids_n;
375 // extra map with node type needed for the creation of the architecture
376 2 std::map<UnitID, Node> unitid_to_int_nodes;
377
2/2
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 2 times.
2/2
✓ Decision 'true' taken 8 times.
✓ Decision 'false' taken 2 times.
 10 for (unsigned i = 0; i < hampath.size(); i++) {
378 8 UnitID qu_no = UnitID(hampath[i]);
379
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 Qubit q = Qubit(i);
380
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 Node n = Node(i);
381
1/2
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
 8 unitid_to_int_nodes.insert({qu_no, n});
382
1/2
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
 8 forward_contiguous_uids_q.insert({q, qu_no});
383
1/2
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
 8 backward_contiguous_uids_n.insert({qu_no, n});
384 8 }
385 // define new arcitecture
386 2 std::vector<Architecture::Connection> new_con;
387
3/4
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 9 taken 6 times.
✓ Branch 10 taken 2 times.
0/1
? Decision couldn't be analyzed.
 8 for (auto pair : arch.get_all_edges_vec()) {
388
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 new_con.push_back(
389
1/2
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
 6 {unitid_to_int_nodes[UnitID(pair.first)],
390
1/2
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
 12 unitid_to_int_nodes[UnitID(pair.second)]});
391 8 }
392
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 Architecture con_arch(new_con);
393 return make_result_from_con_arch(
394
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 4 con_arch, forward_contiguous_uids_q, backward_contiguous_uids_n);
395 2 }
396
397 2 Circuit get_result_using_hampath() {
398
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 1 times.
 2 std::vector<Node> hampath = find_hampath(arch); // using default timeout
399
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 Circuit c0 = get_result_from_hampath(hampath);
400 // Sometimes the reversed path gives a better circuit. Try both!
401
1/2
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
 1 std::reverse(hampath.begin(), hampath.end());
402
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 Circuit c1 = get_result_from_hampath(hampath);
403
4/8
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 1 times.
✓ Branch 9 taken 1 times.
✗ Branch 10 not taken.
 2 return (c0.depth() < c1.depth()) ? c0 : c1;
404 1 }
405
406 76 Circuit get_result_standard() {
407 // calculate iteration order
408
1/2
✓ Branch 1 taken 76 times.
✗ Branch 2 not taken.
 76 IterationOrder iter_order(arch);
409
1/2
✓ Branch 1 taken 76 times.
✗ Branch 2 not taken.
 76 std::vector<Node> node_order = iter_order.get_iterationorder();
410 // maps from qubits/node to int
411 76 std::map<UnitID, UnitID> forward_contiguous_uids_q;
412 76 std::map<UnitID, UnitID> backward_contiguous_uids_n;
413 // extra map with node type needed for the creation of the architecture
414 76 std::map<UnitID, Node> unitid_to_int_nodes;
415
2/2
✓ Branch 1 taken 437 times.
✓ Branch 2 taken 76 times.
2/2
✓ Decision 'true' taken 437 times.
✓ Decision 'false' taken 76 times.
 513 for (unsigned i = 0; i < node_order.size(); i++) {
416 // convert node to superclass type of qubit/node
417 437 UnitID qu_no = UnitID(node_order[i]);
418
1/2
✓ Branch 1 taken 437 times.
✗ Branch 2 not taken.
 437 Qubit q = Qubit(i);
419
1/2
✓ Branch 1 taken 437 times.
✗ Branch 2 not taken.
 437 Node n = Node(i);
420
1/2
✓ Branch 2 taken 437 times.
✗ Branch 3 not taken.
 437 forward_contiguous_uids_q.insert({q, qu_no});
421
1/2
✓ Branch 2 taken 437 times.
✗ Branch 3 not taken.
 437 backward_contiguous_uids_n.insert({qu_no, n});
422
1/2
✓ Branch 2 taken 437 times.
✗ Branch 3 not taken.
 437 unitid_to_int_nodes.insert({qu_no, n});
423 437 }
424 // define new arcitecture: include only the tree edges
425 76 std::vector<Architecture::Connection> new_con;
426
3/4
✓ Branch 1 taken 76 times.
✗ Branch 2 not taken.
✓ Branch 9 taken 361 times.
✓ Branch 10 taken 76 times.
0/1
? Decision couldn't be analyzed.
 437 for (auto pair : iter_order.get_edgelist()) {
427
1/2
✓ Branch 1 taken 361 times.
✗ Branch 2 not taken.
 361 new_con.push_back(
428
1/2
✓ Branch 2 taken 361 times.
✗ Branch 3 not taken.
 361 {unitid_to_int_nodes[UnitID(pair.first)],
429
1/2
✓ Branch 2 taken 361 times.
✗ Branch 3 not taken.
 722 unitid_to_int_nodes[UnitID(pair.second)]});
430 437 }
431
1/2
✓ Branch 1 taken 76 times.
✗ Branch 2 not taken.
 76 Architecture con_arch(new_con);
432 return make_result_from_con_arch(
433
1/2
✓ Branch 1 taken 76 times.
✗ Branch 2 not taken.
 152 con_arch, forward_contiguous_uids_q, backward_contiguous_uids_n);
434 76 }
435
436 78 Circuit make_result_from_con_arch(
437 const Architecture &con_arch,
438 const std::map<UnitID, UnitID> &forward_contiguous_uids_q,
439 const std::map<UnitID, UnitID> &backward_contiguous_uids_n) {
440 // define new phase poly box
441
2/4
✓ Branch 1 taken 78 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 78 times.
✗ Branch 6 not taken.
 78 Circuit circuit_ppb(*placed_ppb.to_circuit());
442 // the aas code is implemented under the assumption that all qubits in the
443 // circuit are named from 0 to n. The same assumption was made for the nodes
444 // of the architecture. To make sure that this condition is fulfilled the
445 // qubits in the circuit and the architecture are renamed. The new names are
446 // reverted at the end of the aas procedure. The qubits and the nodes have
447 // the same name in the input.
448
1/2
✓ Branch 1 taken 78 times.
✗ Branch 2 not taken.
 78 circuit_ppb.rename_units(backward_contiguous_uids_n);
449
1/2
✓ Branch 1 taken 78 times.
✗ Branch 2 not taken.
 78 PhasePolyBox new_ppb(circuit_ppb);
450 Circuit result =
451
1/2
✓ Branch 1 taken 78 times.
✗ Branch 2 not taken.
 78 phase_poly_synthesis_int(con_arch, new_ppb, lookahead, cnottype);
452
1/2
✓ Branch 1 taken 78 times.
✗ Branch 2 not taken.
 78 result.rename_units(forward_contiguous_uids_q);
453 156 return result;
454 78 }
455
456 Architecture arch;
457 PhasePolyBox placed_ppb;
458 unsigned lookahead;
459 CNotSynthType cnottype;
460 };
461
462 78 Circuit phase_poly_synthesis(
463 const Architecture &arch, const PhasePolyBox &phasepolybox,
464 unsigned lookahead, CNotSynthType cnottype) {
465
1/2
✓ Branch 1 taken 78 times.
✗ Branch 2 not taken.
 78 PhasePolySynthesizer pps(arch, phasepolybox, lookahead, cnottype);
466
2/2
✓ Branch 1 taken 77 times.
✓ Branch 2 taken 1 times.
 155 return pps.get_result();
467 78 }
468
469 } // namespace aas
470 } // namespace tket
471