GCC Code Coverage Report

Directory: ./
File: Transformations/ContextualReduction.cpp
Date: 2022-10-15 05:10:18
Warnings: 3 unchecked decisions!
Exec Total Coverage
Lines: 250 261 95.8%
Functions: 14 14 100.0%
Branches: 306 501 61.1%
Decisions: 77 86 89.5%
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 "ContextualReduction.hpp"
16
17 #include <algorithm>
18 #include <optional>
19 #include <sstream>
20 #include <stdexcept>
21 #include <tkassert/Assert.hpp>
22 #include <tklog/TketLog.hpp>
23
24 #include "Circuit/Circuit.hpp"
25 #include "Circuit/DAGDefs.hpp"
26 #include "Eigen/src/Core/Matrix.h"
27 #include "OpType/OpType.hpp"
28 #include "OpType/OpTypeInfo.hpp"
29 #include "Ops/ClassicalOps.hpp"
30 #include "Ops/OpPtr.hpp"
31 #include "Transform.hpp"
32 #include "Utils/HelperFunctions.hpp"
33 #include "Utils/UnitID.hpp"
34
35 namespace tket {
36
37 namespace Transforms {
38
39 2 Transform remove_discarded_ops() {
40 8 return Transform([](Circuit &circ) {
41 // We want to keep all vertices that have an Output or ClOutput in their
42 // causal future. Start by constructing this set, then remove the
43 // remainder.
44 8 VertexSet keep;
45
3/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 37 times.
✓ Branch 9 taken 8 times.
0/1
? Decision couldn't be analyzed.
 45 for (auto v_end : circ.all_outputs()) {
46
3/4
✓ Branch 1 taken 37 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 30 times.
✓ Branch 4 taken 7 times.
2/2
✓ Decision 'true' taken 30 times.
✓ Decision 'false' taken 7 times.
 37 if (circ.get_OpType_from_Vertex(v_end) != OpType::Discard) {
47 // Trace back from v, adding to keep-set. We can ignore vertices
48 // that are already in the keep-set.
49 30 VertexSet v_frontier;
50
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 keep.insert(v_end);
51
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 v_frontier.insert(v_end);
52
2/2
✓ Branch 1 taken 124 times.
✓ Branch 2 taken 30 times.
2/2
✓ Decision 'true' taken 124 times.
✓ Decision 'false' taken 30 times.
 154 while (!v_frontier.empty()) {
53 124 VertexSet new_v_frontier;
54
2/2
✓ Branch 5 taken 208 times.
✓ Branch 6 taken 124 times.
2/2
✓ Decision 'true' taken 208 times.
✓ Decision 'false' taken 124 times.
 332 for (auto v : v_frontier) {
55
3/4
✓ Branch 1 taken 208 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 234 times.
✓ Branch 9 taken 208 times.
0/1
? Decision couldn't be analyzed.
 442 for (const Vertex &v0 : circ.get_predecessors(v)) {
56
3/4
✓ Branch 2 taken 234 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 178 times.
✓ Branch 6 taken 56 times.
2/2
✓ Decision 'true' taken 178 times.
✓ Decision 'false' taken 56 times.
 234 if (keep.find(v0) == keep.end()) {
57
1/2
✓ Branch 1 taken 178 times.
✗ Branch 2 not taken.
 178 keep.insert(v0);
58
1/2
✓ Branch 1 taken 178 times.
✗ Branch 2 not taken.
 178 new_v_frontier.insert(v0);
59 }
60 208 }
61 }
62 124 v_frontier = std::move(new_v_frontier);
63 124 }
64 30 }
65 8 }
66 // Now remove all operations not in the keep-set.
67 8 VertexList to_remove;
68
7/8
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 218 times.
✓ Branch 6 taken 8 times.
✓ Branch 8 taken 218 times.
✓ Branch 9 taken 8 times.
✓ Branch 11 taken 8 times.
✓ Branch 12 taken 8 times.
 234 BGL_FORALL_VERTICES(v, circ.dag, DAG) {
69
3/4
✓ Branch 2 taken 218 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 10 times.
✓ Branch 6 taken 208 times.
2/2
✓ Decision 'true' taken 10 times.
✓ Decision 'false' taken 208 times.
 218 if (keep.find(v) == keep.end()) {
70
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 OpType optype = circ.get_OpType_from_Vertex(v);
71
7/10
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 8 times.
✓ Branch 4 taken 2 times.
✓ Branch 6 taken 8 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 8 times.
✓ Branch 10 taken 2 times.
✓ Branch 11 taken 8 times.
2/2
✓ Decision 'true' taken 2 times.
✓ Decision 'false' taken 8 times.
 10 if (is_gate_type(optype) || is_box_type(optype)) {
72
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 to_remove.push_back(v);
73 }
74 }
75 }
76
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 circ.remove_vertices(
77 to_remove, Circuit::GraphRewiring::Yes, Circuit::VertexDeletion::Yes);
78 16 return !to_remove.empty();
79
1/2
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
 10 });
80 }
81
82 99 static std::optional<Eigen::MatrixXcd> op_unitary(Op_ptr op) {
83 try {
84
2/2
✓ Branch 2 taken 66 times.
✓ Branch 3 taken 33 times.
 99 return op->get_unitary();
85
1/3
✗ Branch 0 not taken.
✓ Branch 1 taken 33 times.
✗ Branch 2 not taken.
 33 } catch (BadOpType &) {
86
1/2
✓ Branch 1 taken 33 times.
✗ Branch 2 not taken.
 33 std::stringstream ss;
87
3/6
✓ Branch 1 taken 33 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 33 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 33 times.
✗ Branch 9 not taken.
0/1
? Decision couldn't be analyzed.
 33 ss << "Attempting to compute unitary for invalid type: " << op->get_name();
88
3/6
✓ Branch 1 taken 33 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 33 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 33 times.
✗ Branch 9 not taken.
 33 tket_log()->warn(ss.str());
89 33 return std::nullopt;
90 33 } catch (SymbolsNotSupported &) {
91 ✗ std::stringstream ss;
92 ss << "Attempting to compute unitary for symbolic operation: "
93 ✗ << op->get_name();
94 ✗ tket_log()->warn(ss.str());
95 ✗ return std::nullopt;
96 }
97 // Any other exception is unexpected.
98 }
99
100 /**
101 * Return i s.t. |U[i,j]| = 1, if it exists. U is unitary, j a column index.
102 */
103 77 static std::optional<unsigned> unique_unit_row(
104 const Eigen::MatrixXcd U, unsigned j) {
105 77 unsigned n = U.rows();
106
1/2
✓ Branch 0 taken 123 times.
✗ Branch 1 not taken.
1/2
✓ Decision 'true' taken 123 times.
✗ Decision 'false' not taken.
 123 for (unsigned i = 0; i < n; i++) {
107
1/2
✓ Branch 1 taken 123 times.
✗ Branch 2 not taken.
 123 double a = std::abs(U(i, j));
108
2/2
✓ Branch 1 taken 45 times.
✓ Branch 2 taken 78 times.
2/2
✓ Decision 'true' taken 45 times.
✓ Decision 'false' taken 78 times.
 123 if (std::abs(a - 1) < EPS) {
109 45 return i;
110
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 46 times.
2/2
✓ Decision 'true' taken 32 times.
✓ Decision 'false' taken 46 times.
 78 } else if (a >= EPS) {
111 32 return std::nullopt;
112 }
113 }
114 // If we get here there is a logical error or numerical instability.
115 ✗ std::stringstream ss;
116 ✗ ss << "Not unitary:" << std::endl << U;
117 ✗ throw std::logic_error(ss.str());
118 }
119
120 /**
121 * Return the set of v in F all of whose quantum in-edges are in qvals.
122 */
123 50 static VertexSet known_inputs_only(
124 const Circuit &circ, const VertexSet &F,
125 const std::map<Edge, bool> &qvals) {
126 50 VertexSet v_frontier;
127
2/2
✓ Branch 5 taken 75 times.
✓ Branch 6 taken 50 times.
2/2
✓ Decision 'true' taken 75 times.
✓ Decision 'false' taken 50 times.
 125 for (const Vertex &v : F) {
128
1/2
✓ Branch 1 taken 75 times.
✗ Branch 2 not taken.
 75 EdgeVec v_q_inedges = circ.get_in_edges_of_type(v, EdgeType::Quantum);
129
3/4
✓ Branch 3 taken 75 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 66 times.
✓ Branch 6 taken 9 times.
2/2
✓ Decision 'true' taken 66 times.
✓ Decision 'false' taken 9 times.
 75 if (std::all_of(
130 v_q_inedges.begin(), v_q_inedges.end(),
131
1/2
✓ Branch 2 taken 96 times.
✗ Branch 3 not taken.
 96 [&qvals](const Edge &e) { return qvals.find(e) != qvals.end(); })) {
132
1/2
✓ Branch 1 taken 66 times.
✗ Branch 2 not taken.
 66 v_frontier.insert(v);
133 }
134 75 }
135 50 return v_frontier;
136 }
137
138 13 Transform simplify_initial(
139 AllowClassical allow_classical, CreateAllQubits create_all_qubits,
140 std::shared_ptr<const Circuit> xcirc) {
141 20 return Transform([allow_classical, create_all_qubits, xcirc](Circuit &circ) {
142
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 10 times.
2/2
✓ Decision 'true' taken 4 times.
✓ Decision 'false' taken 10 times.
 14 if (create_all_qubits == CreateAllQubits::Yes) {
143
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 circ.qubit_create_all();
144 }
145
146 // Find all Create and Reset vertices.
147 14 VertexSet zeroing_vertices;
148
7/8
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 289 times.
✓ Branch 6 taken 14 times.
✓ Branch 8 taken 289 times.
✓ Branch 9 taken 14 times.
✓ Branch 11 taken 14 times.
✓ Branch 12 taken 14 times.
 317 BGL_FORALL_VERTICES(v, circ.dag, DAG) {
149
1/2
✓ Branch 1 taken 289 times.
✗ Branch 2 not taken.
 289 OpType optype = circ.get_OpType_from_Vertex(v);
150
4/4
✓ Branch 0 taken 254 times.
✓ Branch 1 taken 35 times.
✓ Branch 2 taken 3 times.
✓ Branch 3 taken 251 times.
2/2
✓ Decision 'true' taken 38 times.
✓ Decision 'false' taken 251 times.
 289 if (optype == OpType::Create || optype == OpType::Reset) {
151
1/2
✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
 38 zeroing_vertices.insert(v);
152 }
153 }
154
155 // Partial map from quantum edges to values.
156 14 std::map<Edge, bool> qvals;
157
158 // Assign 0 values to all edges coming out of zeroing vertices, and
159 // construct the set of their target vertices.
160 14 VertexSet F;
161
2/2
✓ Branch 5 taken 38 times.
✓ Branch 6 taken 14 times.
2/2
✓ Decision 'true' taken 38 times.
✓ Decision 'false' taken 14 times.
 52 for (auto z : zeroing_vertices) {
162
1/2
✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
 38 EdgeVec z_outedges = circ.get_all_out_edges(z);
163 TKET_ASSERT(z_outedges.size() == 1);
164 38 Edge z_out = z_outedges[0];
165 TKET_ASSERT(circ.get_edgetype(z_out) == EdgeType::Quantum);
166
1/2
✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
 38 qvals[z_out] = false;
167
2/4
✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 38 times.
✗ Branch 5 not taken.
 38 F.insert(circ.target(z_out));
168 38 }
169
170 // Construct frontier of vertices with all-known input values.
171
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 VertexSet v_frontier = known_inputs_only(circ, F, qvals);
172
173 // Partial map from vertices to sequences of X gates to replace them.
174 14 std::map<Vertex, std::vector<bool>> reductions;
175
176 // Partial map from Measure vertices to bits to set after measure.
177 14 std::map<Vertex, bool> measurebits;
178
179
2/2
✓ Branch 1 taken 36 times.
✓ Branch 2 taken 14 times.
2/2
✓ Decision 'true' taken 36 times.
✓ Decision 'false' taken 14 times.
 50 while (!v_frontier.empty()) {
180 // Simplify vertices in the frontier that we can, and move it on.
181 36 F.clear();
182
2/2
✓ Branch 5 taken 66 times.
✓ Branch 6 taken 36 times.
2/2
✓ Decision 'true' taken 66 times.
✓ Decision 'false' taken 36 times.
 102 for (const Vertex &v : v_frontier) {
183 // If there are any Boolean inputs to v, skip it.
184
2/4
✓ Branch 1 taken 66 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 66 times.
2/2
✓ Decision 'true' taken 34 times.
✓ Decision 'false' taken 32 times.
 66 if (circ.n_in_edges_of_type(v, EdgeType::Boolean) != 0) {
185 34 continue;
186 }
187
188
1/2
✓ Branch 1 taken 66 times.
✗ Branch 2 not taken.
 66 Op_ptr op = circ.get_Op_ptr_from_Vertex(v);
189
1/2
✓ Branch 2 taken 66 times.
✗ Branch 3 not taken.
 66 std::optional<Eigen::MatrixXcd> U = op_unitary(op);
190 66 bool is_measure = (op->get_type() == OpType::Measure);
191
192
7/8
✓ Branch 1 taken 13 times.
✓ Branch 2 taken 53 times.
✓ Branch 3 taken 3 times.
✓ Branch 4 taken 10 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 3 times.
✓ Branch 7 taken 10 times.
✓ Branch 8 taken 56 times.
2/2
✓ Decision 'true' taken 10 times.
✓ Decision 'false' taken 56 times.
 66 if (!U && (!is_measure || allow_classical == AllowClassical::No)) {
193 10 continue;
194 }
195
196 // Compute input state.
197
1/2
✓ Branch 1 taken 56 times.
✗ Branch 2 not taken.
 56 EdgeVec v_q_inedges = circ.get_in_edges_of_type(v, EdgeType::Quantum);
198 56 unsigned n_q = v_q_inedges.size();
199
1/2
✓ Branch 2 taken 56 times.
✗ Branch 3 not taken.
 56 std::vector<bool> v_invals(n_q);
200
2/2
✓ Branch 0 taken 69 times.
✓ Branch 1 taken 56 times.
2/2
✓ Decision 'true' taken 69 times.
✓ Decision 'false' taken 56 times.
 125 for (unsigned i = 0; i < n_q; i++) {
201
2/4
✓ Branch 2 taken 69 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 69 times.
✗ Branch 6 not taken.
 69 v_invals[i] = qvals[v_q_inedges[i]];
202 }
203
204
2/2
✓ Branch 1 taken 53 times.
✓ Branch 2 taken 3 times.
2/2
✓ Decision 'true' taken 53 times.
✓ Decision 'false' taken 3 times.
 56 if (U) {
205 // Compute relevant column J of U.
206 53 unsigned J = 0, pow2 = 1u << n_q;
207
2/2
✓ Branch 0 taken 66 times.
✓ Branch 1 taken 53 times.
2/2
✓ Decision 'true' taken 66 times.
✓ Decision 'false' taken 53 times.
 119 for (unsigned i = 0; i < n_q; i++) {
208 66 pow2 >>= 1;
209
3/4
✓ Branch 1 taken 66 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 13 times.
✓ Branch 5 taken 53 times.
2/2
✓ Decision 'true' taken 13 times.
✓ Decision 'false' taken 53 times.
 66 if (v_invals[i]) {
210 13 J |= pow2;
211 }
212 }
213
214 // Check if there is a unique I s.t. |U(I,J)| == 1.
215
2/4
✓ Branch 2 taken 53 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 53 times.
✗ Branch 6 not taken.
 53 std::optional<unsigned> I = unique_unit_row(*U, J);
216
2/2
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 29 times.
2/2
✓ Decision 'true' taken 29 times.
✓ Decision 'false' taken 24 times.
 53 if (!I) continue;
217
218 // Convert I to a vector of bool
219
1/2
✓ Branch 2 taken 29 times.
✗ Branch 3 not taken.
 29 std::vector<bool> v_outvals(n_q);
220
2/2
✓ Branch 0 taken 42 times.
✓ Branch 1 taken 29 times.
2/2
✓ Decision 'true' taken 42 times.
✓ Decision 'false' taken 29 times.
 71 for (unsigned i = 0; i < n_q; i++) {
221
1/2
✓ Branch 2 taken 42 times.
✗ Branch 3 not taken.
 42 v_outvals[i] = (*I >> (n_q - 1 - i)) & 1;
222 }
223
224 // Label out-edges of v; construct equivalent X-gate rep.
225
1/2
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
 29 EdgeVec v_outedges = circ.get_all_out_edges(v);
226 TKET_ASSERT(v_outedges.size() == n_q);
227
1/2
✓ Branch 2 taken 29 times.
✗ Branch 3 not taken.
 29 std::vector<bool> x_gates(n_q);
228
2/2
✓ Branch 0 taken 42 times.
✓ Branch 1 taken 29 times.
2/2
✓ Decision 'true' taken 42 times.
✓ Decision 'false' taken 29 times.
 71 for (unsigned i = 0; i < n_q; i++) {
229
1/2
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
 42 bool outval = v_outvals[i];
230
1/2
✓ Branch 2 taken 42 times.
✗ Branch 3 not taken.
 42 qvals[v_outedges[i]] = outval;
231
2/4
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 42 times.
✗ Branch 6 not taken.
 42 x_gates[i] = v_invals[i] ^ outval;
232 }
233
234 // Record vertex for later replacement with X-gates.
235
2/4
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 29 times.
✗ Branch 5 not taken.
 29 reductions[v] = x_gates;
236
237 // Add all successors of v to potential next frontier F.
238
2/2
✓ Branch 4 taken 42 times.
✓ Branch 5 taken 29 times.
2/2
✓ Decision 'true' taken 42 times.
✓ Decision 'false' taken 29 times.
 71 for (const Edge &e : v_outedges) {
239
2/4
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 42 times.
✗ Branch 5 not taken.
 42 F.insert(circ.target(e));
240 }
241 29 } else {
242 TKET_ASSERT(allow_classical == AllowClassical::Yes);
243 TKET_ASSERT(n_q == 1);
244
2/4
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 3 times.
✗ Branch 6 not taken.
 3 measurebits[v] = v_invals[0];
245 }
246
8/8
✓ Branch 1 taken 32 times.
✓ Branch 2 taken 24 times.
✓ Branch 4 taken 32 times.
✓ Branch 5 taken 24 times.
✓ Branch 7 taken 32 times.
✓ Branch 8 taken 34 times.
✓ Branch 10 taken 32 times.
✓ Branch 11 taken 34 times.
 148 }
247
248 // Replace v_frontier with vertices from F having all-known inputs.
249
1/2
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
 36 v_frontier = known_inputs_only(circ, F, qvals);
250 }
251
252 // Perform substitutions.
253 14 VertexList bin;
254
2/2
✓ Branch 7 taken 29 times.
✓ Branch 8 taken 14 times.
2/2
✓ Decision 'true' taken 29 times.
✓ Decision 'false' taken 14 times.
 43 for (const auto &[v, x_gates] : reductions) {
255 29 unsigned n_q = x_gates.size();
256
1/2
✓ Branch 2 taken 29 times.
✗ Branch 3 not taken.
 29 Circuit xs_circ(n_q);
257
2/2
✓ Branch 0 taken 42 times.
✓ Branch 1 taken 29 times.
2/2
✓ Decision 'true' taken 42 times.
✓ Decision 'false' taken 29 times.
 71 for (unsigned i = 0; i < n_q; i++) {
258
3/4
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 17 times.
✓ Branch 4 taken 25 times.
2/2
✓ Decision 'true' taken 17 times.
✓ Decision 'false' taken 25 times.
 42 if (x_gates[i]) {
259
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 17 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 17 times.
 17 if (xcirc) {
260 ✗ unit_map_t qm;
261 ✗ qm.insert({Qubit(i), Qubit(0)});
262 ✗ xs_circ.append_with_map(*xcirc, qm);
263 ✗ } else {
264
2/4
✓ Branch 3 taken 17 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 17 times.
✗ Branch 7 not taken.
 17 xs_circ.add_op<unsigned>(OpType::X, {i});
265 }
266 }
267 }
268
1/2
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
 29 EdgeVec v_in_edges = circ.get_in_edges(v); // all Quantum
269
1/2
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
 29 EdgeVec v_out_edges = circ.get_all_out_edges(v); // all Quantum
270 TKET_ASSERT(v_in_edges.size() == n_q);
271 TKET_ASSERT(v_out_edges.size() == n_q);
272
2/4
✓ Branch 2 taken 29 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 29 times.
✗ Branch 6 not taken.
 58 Subcircuit subc{v_in_edges, v_out_edges, {v}};
273
1/2
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
 29 circ.substitute(xs_circ, subc, Circuit::VertexDeletion::No);
274
1/2
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
 29 bin.push_back(v);
275 29 }
276
2/2
✓ Branch 7 taken 3 times.
✓ Branch 8 taken 14 times.
2/2
✓ Decision 'true' taken 3 times.
✓ Decision 'false' taken 14 times.
 17 for (const auto &[v, bitval] : measurebits) {
277
1/2
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 3 Circuit newc(1, 1);
278 // Replace the measure with a set-bit.
279
1/2
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 3 std::vector<bool> values = {bitval};
280
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 Op_ptr setbitop = std::make_shared<SetBitsOp>(values);
281
5/10
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 3 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 3 times.
✗ Branch 10 not taken.
✓ Branch 13 taken 3 times.
✓ Branch 14 taken 3 times.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
 6 newc.add_op<Bit>(setbitop, {Bit(0)});
282
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 EdgeVec q_in_edges = circ.get_in_edges_of_type(v, EdgeType::Quantum);
283 TKET_ASSERT(q_in_edges.size() == 1);
284
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 EdgeVec q_out_edges = circ.get_out_edges_of_type(v, EdgeType::Quantum);
285 TKET_ASSERT(q_out_edges.size() == 1);
286
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 EdgeVec c_in_edges = circ.get_in_edges_of_type(v, EdgeType::Classical);
287 TKET_ASSERT(c_in_edges.size() == 1);
288
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 EdgeVec c_out_edges = circ.get_out_edges_of_type(v, EdgeType::Classical);
289 TKET_ASSERT(c_out_edges.size() == 1);
290
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 EdgeVec b_out_edges = circ.get_out_edges_of_type(v, EdgeType::Boolean);
291 Subcircuit subc{q_in_edges, q_out_edges, c_in_edges,
292
2/4
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 3 times.
✗ Branch 6 not taken.
 6 c_out_edges, b_out_edges, {v}};
293
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 circ.substitute(newc, subc, Circuit::VertexDeletion::No);
294
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 bin.push_back(v);
295 3 }
296 14 bool changed = !bin.empty();
297
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 circ.remove_vertices(
298 bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
299
300 14 return changed;
301
2/4
✓ Branch 2 taken 13 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 13 times.
✗ Branch 6 not taken.
 27 });
302 }
303
304 33 std::optional<std::shared_ptr<const ClassicalTransformOp>> classical_transform(
305 Op_ptr op) {
306
1/2
✓ Branch 2 taken 33 times.
✗ Branch 3 not taken.
 33 std::optional<Eigen::MatrixXcd> U = op_unitary(op);
307
2/2
✓ Branch 1 taken 20 times.
✓ Branch 2 taken 13 times.
2/2
✓ Decision 'true' taken 13 times.
✓ Decision 'false' taken 20 times.
 33 if (!U) return std::nullopt;
308
3/6
✓ Branch 2 taken 13 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 13 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 13 times.
✗ Branch 9 not taken.
 13 unsigned n = op->get_desc().n_qubits().value();
309 13 unsigned pow2n = 1u << n;
310 TKET_ASSERT(U->cols() == pow2n);
311
1/2
✓ Branch 2 taken 13 times.
✗ Branch 3 not taken.
 13 std::vector<uint32_t> values(pow2n);
312
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 5 times.
2/2
✓ Decision 'true' taken 24 times.
✓ Decision 'false' taken 5 times.
 29 for (uint32_t J = 0; J < pow2n; J++) {
313 // Look at the column U[*,J]. Is there a unique nonzero element?
314
2/4
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 24 times.
✗ Branch 6 not taken.
 24 std::optional<unsigned> I = unique_unit_row(*U, J);
315
2/2
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 16 times.
2/2
✓ Decision 'true' taken 16 times.
✓ Decision 'false' taken 8 times.
 24 if (!I) return std::nullopt;
316
2/4
✓ Branch 2 taken 16 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 16 times.
✗ Branch 6 not taken.
 16 values[reverse_bits(J, n)] = reverse_bits(*I, n);
317 }
318
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 return std::make_shared<ClassicalTransformOp>(n, values);
319 33 }
320
321 4 Transform simplify_measured() {
322 10 return Transform([](Circuit &circ) {
323 // First construct the set of all Measure vertices that are followed by
324 // Discard vertices (and no Boolean out-edges).
325 10 VertexSet M;
326
7/8
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 233 times.
✓ Branch 6 taken 10 times.
✓ Branch 8 taken 233 times.
✓ Branch 9 taken 10 times.
✓ Branch 11 taken 10 times.
✓ Branch 12 taken 10 times.
 253 BGL_FORALL_VERTICES(v, circ.dag, DAG) {
327
3/4
✓ Branch 1 taken 233 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 13 times.
✓ Branch 4 taken 220 times.
2/2
✓ Decision 'true' taken 13 times.
✓ Decision 'false' taken 220 times.
 233 if (circ.get_OpType_from_Vertex(v) == OpType::Measure) {
328
2/4
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 13 times.
✗ Branch 4 not taken.
1/2
✓ Decision 'true' taken 13 times.
✗ Decision 'false' not taken.
 13 if (circ.n_out_edges_of_type(v, EdgeType::Boolean) == 0) {
329
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 EdgeVec m_q_outs = circ.get_out_edges_of_type(v, EdgeType::Quantum);
330 TKET_ASSERT(m_q_outs.size() == 1);
331 13 Edge m_q_out = m_q_outs[0];
332
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 Vertex v1 = circ.target(m_q_out);
333
3/4
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 9 times.
✓ Branch 4 taken 4 times.
2/2
✓ Decision 'true' taken 9 times.
✓ Decision 'false' taken 4 times.
 13 if (circ.get_OpType_from_Vertex(v1) == OpType::Discard) {
334
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 M.insert(v);
335 }
336 13 }
337 }
338 }
339 10 bool changed = false;
340 bool carry_on;
341
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 10 times.
 14 do {
342 14 carry_on = false;
343 14 VertexList bin;
344 // Find all classical maps all of whose successors are in M
345
2/2
✓ Branch 5 taken 17 times.
✓ Branch 6 taken 14 times.
2/2
✓ Decision 'true' taken 17 times.
✓ Decision 'false' taken 14 times.
 31 for (const Vertex &v : M) {
346
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 VertexVec preds = circ.get_predecessors(v);
347
2/2
✓ Branch 5 taken 34 times.
✓ Branch 6 taken 17 times.
2/2
✓ Decision 'true' taken 34 times.
✓ Decision 'false' taken 17 times.
 51 for (const Vertex &v0 : preds) {
348 // Any Boolean inputs?
349
2/4
✓ Branch 1 taken 34 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 34 times.
2/2
✓ Decision 'true' taken 29 times.
✓ Decision 'false' taken 5 times.
 34 if (circ.n_in_edges_of_type(v0, EdgeType::Boolean) != 0) {
350 29 continue;
351 }
352 // No. Are all successors in M?
353
1/2
✓ Branch 1 taken 34 times.
✗ Branch 2 not taken.
 34 VertexVec succs = circ.get_successors(v0);
354
3/4
✓ Branch 3 taken 34 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 1 times.
✓ Branch 6 taken 33 times.
 34 if (std::any_of(succs.begin(), succs.end(), [&](const Vertex &u) {
355
1/2
✓ Branch 2 taken 38 times.
✗ Branch 3 not taken.
 38 return M.find(u) == M.end();
356 })) {
357 1 continue;
358 }
359 // Yes. Is it a classical map?
360
1/2
✓ Branch 1 taken 33 times.
✗ Branch 2 not taken.
 33 Op_ptr op = circ.get_Op_ptr_from_Vertex(v0);
361 std::optional<std::shared_ptr<const ClassicalTransformOp>> cm =
362
1/2
✓ Branch 2 taken 33 times.
✗ Branch 3 not taken.
 33 classical_transform(op);
363
2/2
✓ Branch 1 taken 28 times.
✓ Branch 2 taken 5 times.
 33 if (!cm) continue;
364 // Yes. Remove v0.
365 5 unsigned n_qb = succs.size();
366
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 circ.remove_vertex(
367 v0, Circuit::GraphRewiring::Yes, Circuit::VertexDeletion::No);
368
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 bin.push_back(v0);
369 // Insert *cm on the classical target wires.
370
1/2
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
 5 EdgeVec cl_edges(n_qb);
371
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 5 times.
 13 for (unsigned i = 0; i < n_qb; i++) {
372 EdgeVec m_c_outs =
373
1/2
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
 8 circ.get_out_edges_of_type(succs[i], EdgeType::Classical);
374 TKET_ASSERT(m_c_outs.size() == 1);
375 8 cl_edges[i] = m_c_outs[0];
376 8 }
377
1/2
✓ Branch 5 taken 5 times.
✗ Branch 6 not taken.
 10 Subcircuit cl_subc{{}, {}, cl_edges, cl_edges, {}, {}};
378
1/2
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
 5 Circuit cl_circ(0, n_qb);
379
1/2
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
 5 std::vector<unsigned> args(n_qb);
380 5 std::iota(args.begin(), args.end(), 0);
381
1/2
✓ Branch 4 taken 5 times.
✗ Branch 5 not taken.
 5 cl_circ.add_op<unsigned>(*cm, args);
382
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 circ.substitute(cl_circ, cl_subc, Circuit::VertexDeletion::No);
383 5 changed = true;
384 5 carry_on = true;
385
6/6
✓ Branch 5 taken 5 times.
✓ Branch 6 taken 28 times.
✓ Branch 8 taken 5 times.
✓ Branch 9 taken 28 times.
✓ Branch 11 taken 5 times.
✓ Branch 12 taken 29 times.
 90 }
386 17 }
387
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 circ.remove_vertices(
388 bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
389 14 } while (carry_on);
390 10 return changed;
391
1/2
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
 14 });
392 }
393
394 2 std::pair<Circuit, Circuit> separate_classical(const Circuit &circ) {
395 // Initialize the two circuits to return.
396
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 qubit_vector_t qubits = circ.all_qubits();
397
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 bit_vector_t bits = circ.all_bits();
398
2/4
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
 2 Circuit c0, c1;
399
2/2
✓ Branch 5 taken 5 times.
✓ Branch 6 taken 2 times.
 7 for (const Qubit &qb : qubits) {
400
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 c0.add_qubit(qb);
401 }
402
2/2
✓ Branch 5 taken 5 times.
✓ Branch 6 taken 2 times.
 7 for (const Bit &b : bits) {
403
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 c0.add_bit(b);
404
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 c1.add_bit(b);
405 }
406
407 // Get the command list.
408
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 std::vector<Command> cmds = circ.get_commands();
409
410 // Find the final Measure (or ClInput if no Measure) on each bit.
411
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 VertexVec c_in = circ.c_inputs();
412 2 unsigned n_bits = bits.size();
413 TKET_ASSERT(n_bits == c_in.size());
414 2 std::map<Bit, Vertex> final_vert_on_bit;
415
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 2 times.
 7 for (unsigned i = 0; i < n_bits; i++) {
416
1/2
✓ Branch 3 taken 5 times.
✗ Branch 4 not taken.
 5 final_vert_on_bit[bits[i]] = c_in[i];
417 }
418
2/2
✓ Branch 5 taken 11 times.
✓ Branch 6 taken 2 times.
 13 for (const Command &cmd : cmds) {
419 11 OpType optype = cmd.get_op_ptr()->get_type();
420
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 8 times.
 11 if (optype == OpType::Measure) {
421
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 bit_vector_t cmd_bits = cmd.get_bits();
422 TKET_ASSERT(cmd_bits.size() == 1);
423
1/2
✓ Branch 3 taken 3 times.
✗ Branch 4 not taken.
 3 final_vert_on_bit[cmd_bits[0]] = cmd.get_vertex();
424 3 }
425 }
426
427 // Construct the set of final vertices.
428 2 VertexSet final_verts;
429
2/2
✓ Branch 5 taken 5 times.
✓ Branch 6 taken 2 times.
 7 for (const Bit &b : bits) {
430
2/4
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 5 times.
✗ Branch 5 not taken.
 5 final_verts.insert(final_vert_on_bit[b]);
431 }
432
433 // Construct the set of vertices to go in c1.
434 // Initially include final_verts; later exclude them.
435
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 VertexSet c1_verts(final_verts);
436
2/2
✓ Branch 5 taken 11 times.
✓ Branch 6 taken 2 times.
 13 for (const Command &cmd : cmds) {
437 11 Vertex v = cmd.get_vertex();
438
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 VertexVec preds = circ.get_predecessors(v);
439
3/4
✓ Branch 3 taken 11 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 5 times.
✓ Branch 6 taken 6 times.
 11 if (std::all_of(preds.begin(), preds.end(), [&c1_verts](const Vertex &v) {
440
1/2
✓ Branch 2 taken 13 times.
✗ Branch 3 not taken.
 13 return c1_verts.find(v) != c1_verts.end();
441 })) {
442
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 c1_verts.insert(v);
443 }
444 11 }
445
2/2
✓ Branch 5 taken 5 times.
✓ Branch 6 taken 2 times.
 7 for (const Vertex &v : final_verts) {
446
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 c1_verts.erase(v);
447 }
448
449 // Step through the circuit, filling in c0 and c1.
450
2/2
✓ Branch 5 taken 11 times.
✓ Branch 6 taken 2 times.
 13 for (const Command &cmd : cmds) {
451 11 Op_ptr op = cmd.get_op_ptr();
452
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 unit_vector_t args = cmd.get_args();
453
3/4
✓ Branch 3 taken 11 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 6 times.
✓ Branch 7 taken 5 times.
 11 if (c1_verts.find(cmd.get_vertex()) == c1_verts.end()) {
454
1/2
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
 6 c0.add_op(op, args);
455 } else {
456
1/2
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
 5 c1.add_op(op, args);
457 }
458 11 }
459
460
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 4 return {c0, c1};
461 2 }
462
463 } // namespace Transforms
464
465 } // namespace tket
466