GCC Code Coverage Report

Directory: ./
File: Transformations/PQPSquash.cpp
Date: 2022-10-15 05:10:18
Warnings: 3 unchecked decisions!
Exec Total Coverage
Lines: 236 248 95.2%
Functions: 16 17 94.1%
Branches: 307 494 62.1%
Decisions: 86 102 84.3%
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 "PQPSquash.hpp"
16
17 #include <memory>
18
19 #include "BasicOptimisation.hpp"
20 #include "Circuit/DAGDefs.hpp"
21 #include "Decomposition.hpp"
22 #include "Gate/Rotation.hpp"
23 #include "OpType/OpTypeInfo.hpp"
24 #include "Transform.hpp"
25 #include "Utils/Expression.hpp"
26
27 namespace tket {
28
29 namespace Transforms {
30
31 static bool fixup_angles(
32 Expr &angle_p1, Expr &angle_q, Expr &angle_p2, bool reversed = false);
33 static bool redundancy_removal(Circuit &circ);
34 static Rotation merge_rotations(
35 OpType r, const std::vector<Gate_ptr> &chain,
36 std::vector<Gate_ptr>::const_iterator &iter);
37
38 6357 PQPSquasher::PQPSquasher(OpType p, OpType q, bool smart_squash, bool reversed)
39 6357 : p_(p),
40 6357 q_(q),
41 6357 smart_squash_(smart_squash),
42 6357 reversed_(reversed),
43 6357 rotation_chain() {
44
7/8
✓ Branch 0 taken 6289 times.
✓ Branch 1 taken 68 times.
✓ Branch 2 taken 6283 times.
✓ Branch 3 taken 6 times.
✓ Branch 4 taken 6283 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 3167 times.
✓ Branch 7 taken 3190 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 6357 times.
 6357 if (!(p == OpType::Rx || p == OpType::Ry || p == OpType::Rz) ||
45
3/4
✓ Branch 0 taken 69 times.
✓ Branch 1 taken 3098 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 69 times.
 3167 !(q == OpType::Rx || q == OpType::Ry || q == OpType::Rz)) {
46 ✗ throw std::logic_error("Can only reduce chains of single qubit rotations");
47 }
48
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6357 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 6357 times.
 6357 if (p == q) {
49 ✗ throw std::logic_error(
50 "Requires two different bases to perform single qubit "
51 ✗ "rotations");
52 }
53 6357 }
54
55 403984 bool PQPSquasher::accepts(Gate_ptr gp) const {
56 403984 OpType type = gp->get_type();
57
4/4
✓ Branch 0 taken 122396 times.
✓ Branch 1 taken 281588 times.
✓ Branch 2 taken 122140 times.
✓ Branch 3 taken 256 times.
 403984 return type == p_ || type == q_;
58 }
59
60 201862 void PQPSquasher::append(Gate_ptr gp) {
61
2/4
✓ Branch 2 taken 201862 times.
✗ Branch 3 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 201862 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 201862 times.
 201862 if (!accepts(gp)) {
62 ✗ throw BadOpType("PQPSquasher: cannot append OpType", gp->get_type());
63 }
64 201862 rotation_chain.push_back(gp);
65 201862 }
66
67 37101 std::pair<Circuit, Gate_ptr> PQPSquasher::flush(
68 std::optional<Pauli> commutation_colour) const {
69 37101 bool commute_through = false;
70 37101 OpType p = p_, q = q_;
71
72
6/6
✓ Branch 0 taken 1076 times.
✓ Branch 1 taken 36025 times.
✓ Branch 3 taken 351 times.
✓ Branch 4 taken 725 times.
✓ Branch 5 taken 351 times.
✓ Branch 6 taken 36750 times.
2/2
✓ Decision 'true' taken 1053 times.
✓ Decision 'false' taken 36048 times.
 37101 if (smart_squash_ && commutation_colour.has_value()) {
73 // Using an arbitrary non-zero angle to obtain the commutation for p_/q_.
74
3/6
✓ Branch 1 taken 351 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 351 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 351 times.
✗ Branch 9 not taken.
 1053 Gate P(p_, {0.123}, 1);
75
3/6
✓ Branch 1 taken 351 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 351 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 351 times.
✗ Branch 9 not taken.
 1053 Gate Q(q_, {0.123}, 1);
76
3/4
✓ Branch 1 taken 351 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 161 times.
✓ Branch 4 taken 190 times.
2/2
✓ Decision 'true' taken 161 times.
✓ Decision 'false' taken 190 times.
 351 if (P.commutes_with_basis(commutation_colour, 0)) {
77 161 commute_through = true;
78
3/4
✓ Branch 1 taken 190 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 179 times.
✓ Branch 4 taken 11 times.
2/2
✓ Decision 'true' taken 179 times.
✓ Decision 'false' taken 11 times.
 190 } else if (Q.commutes_with_basis(commutation_colour, 0)) {
79 179 commute_through = true;
80 179 p = q_;
81 179 q = p_;
82 }
83 351 }
84
85 // Construct list of merged rotations
86 37101 std::list<Rotation> rots;
87 37101 auto iter = rotation_chain.cbegin();
88
2/2
✓ Branch 2 taken 93917 times.
✓ Branch 3 taken 37101 times.
2/2
✓ Decision 'true' taken 93917 times.
✓ Decision 'false' taken 37101 times.
 131018 while (iter != rotation_chain.cend()) {
89 // Merge next q rotations
90
2/4
✓ Branch 1 taken 93917 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 93917 times.
✗ Branch 5 not taken.
 93917 rots.push_back(merge_rotations(q, rotation_chain, iter));
91 // Merge next p rotations
92
2/4
✓ Branch 1 taken 93917 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 93917 times.
✗ Branch 5 not taken.
 93917 rots.push_back(merge_rotations(p, rotation_chain, iter));
93 }
94
95 // Perform any cancellations
96 37101 std::list<Rotation>::iterator r = rots.begin();
97
2/2
✓ Branch 2 taken 187834 times.
✓ Branch 3 taken 37101 times.
2/2
✓ Decision 'true' taken 187834 times.
✓ Decision 'false' taken 37101 times.
 224935 while (r != rots.end()) {
98
2/2
✓ Branch 2 taken 84132 times.
✓ Branch 3 taken 103702 times.
2/2
✓ Decision 'true' taken 84132 times.
✓ Decision 'false' taken 103702 times.
 187834 if (r->is_id()) {
99 84132 r = rots.erase(r);
100
6/6
✓ Branch 2 taken 19838 times.
✓ Branch 3 taken 64294 times.
✓ Branch 6 taken 13917 times.
✓ Branch 7 taken 5921 times.
✓ Branch 8 taken 13917 times.
✓ Branch 9 taken 70215 times.
2/2
✓ Decision 'true' taken 13917 times.
✓ Decision 'false' taken 70215 times.
 84132 if (r != rots.begin() && r != rots.end()) {
101
2/4
✓ Branch 1 taken 13917 times.
✗ Branch 2 not taken.
✓ Branch 6 taken 13917 times.
✗ Branch 7 not taken.
 13917 std::prev(r)->apply(*r);
102 13917 r = rots.erase(r);
103 13917 r--;
104 }
105 } else
106 103702 r++;
107 }
108
109 // Extract any P rotations from the beginning and end of the list
110
2/4
✓ Branch 1 taken 37101 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 37101 times.
✗ Branch 5 not taken.
 37101 Expr p1 = 0, p2 = 0;
111 37101 std::list<Rotation>::iterator i1 = rots.begin();
112
2/2
✓ Branch 2 taken 37055 times.
✓ Branch 3 taken 46 times.
2/2
✓ Decision 'true' taken 37055 times.
✓ Decision 'false' taken 46 times.
 37101 if (i1 != rots.end()) {
113
1/2
✓ Branch 2 taken 37055 times.
✗ Branch 3 not taken.
 37055 std::optional<Expr> a = i1->angle(p);
114
2/2
✓ Branch 1 taken 28061 times.
✓ Branch 2 taken 8994 times.
2/2
✓ Decision 'true' taken 28061 times.
✓ Decision 'false' taken 8994 times.
 37055 if (a) {
115
2/4
✓ Branch 1 taken 28061 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 28061 times.
✗ Branch 5 not taken.
 28061 p1 = a.value();
116 28061 rots.pop_front();
117 }
118 37055 }
119 37101 std::list<Rotation>::reverse_iterator i2 = rots.rbegin();
120
3/4
✓ Branch 2 taken 37101 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 27349 times.
✓ Branch 5 taken 9752 times.
2/2
✓ Decision 'true' taken 27349 times.
✓ Decision 'false' taken 9752 times.
 37101 if (i2 != rots.rend()) {
121
2/4
✓ Branch 1 taken 27349 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 27349 times.
✗ Branch 5 not taken.
 27349 std::optional<Expr> a = i2->angle(p);
122
2/2
✓ Branch 1 taken 21459 times.
✓ Branch 2 taken 5890 times.
2/2
✓ Decision 'true' taken 21459 times.
✓ Decision 'false' taken 5890 times.
 27349 if (a) {
123
2/4
✓ Branch 1 taken 21459 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 21459 times.
✗ Branch 5 not taken.
 21459 p2 = a.value();
124 21459 rots.pop_back();
125 }
126 27349 }
127
128 // Finish up:
129
1/2
✓ Branch 1 taken 37101 times.
✗ Branch 2 not taken.
 37101 Rotation R = {};
130
3/4
✓ Branch 4 taken 40265 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 40265 times.
✓ Branch 9 taken 37101 times.
0/1
? Decision couldn't be analyzed.
 77366 for (auto rot : rots) {
131
1/2
✓ Branch 1 taken 40265 times.
✗ Branch 2 not taken.
 40265 R.apply(rot);
132 40265 }
133
1/2
✓ Branch 1 taken 37101 times.
✗ Branch 2 not taken.
 37101 std::tuple<Expr, Expr, Expr> angles = R.to_pqp(p, q);
134
135
1/2
✓ Branch 2 taken 37101 times.
✗ Branch 3 not taken.
 37101 Expr angle_p1 = std::get<0>(angles) + p1;
136
1/2
✓ Branch 2 taken 37101 times.
✗ Branch 3 not taken.
 37101 Expr angle_q = std::get<1>(angles);
137
1/2
✓ Branch 2 taken 37101 times.
✗ Branch 3 not taken.
 37101 Expr angle_p2 = std::get<2>(angles) + p2;
138
1/2
✓ Branch 1 taken 37101 times.
✗ Branch 2 not taken.
 37101 fixup_angles(angle_p1, angle_q, angle_p2, reversed_);
139
140
1/2
✓ Branch 2 taken 37101 times.
✗ Branch 3 not taken.
 37101 Circuit replacement(1);
141 37101 Gate_ptr left_over_gate = nullptr;
142
3/4
✓ Branch 1 taken 37101 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 24660 times.
✓ Branch 4 taken 12441 times.
2/2
✓ Decision 'true' taken 24660 times.
✓ Decision 'false' taken 12441 times.
 37101 if (!equiv_0(angle_p1, 4)) {
143
10/12
✓ Branch 1 taken 24660 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 9559 times.
✓ Branch 4 taken 15101 times.
✓ Branch 6 taken 9559 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 9321 times.
✓ Branch 9 taken 238 times.
✓ Branch 10 taken 55 times.
✓ Branch 11 taken 9266 times.
✓ Branch 12 taken 55 times.
✓ Branch 13 taken 24605 times.
2/2
✓ Decision 'true' taken 110 times.
✓ Decision 'false' taken 24550 times.
 24660 if (equiv_0(angle_q, 4) && equiv_0(angle_p2, 4) && commute_through) {
144 left_over_gate =
145
5/10
✓ Branch 1 taken 55 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 55 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 55 times.
✗ Branch 9 not taken.
✓ Branch 14 taken 55 times.
✓ Branch 15 taken 55 times.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
 110 std::make_shared<Gate>(p, std::vector<Expr>{angle_p1}, 1);
146 } else {
147
2/4
✓ Branch 3 taken 24605 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 24605 times.
✗ Branch 7 not taken.
 24605 replacement.add_op<unsigned>(p, angle_p1, {0});
148 }
149 }
150
3/4
✓ Branch 1 taken 37101 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 26909 times.
✓ Branch 4 taken 10192 times.
2/2
✓ Decision 'true' taken 26909 times.
✓ Decision 'false' taken 10192 times.
 37101 if (!equiv_0(angle_q, 4)) {
151
2/4
✓ Branch 3 taken 26909 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 26909 times.
✗ Branch 7 not taken.
 26909 replacement.add_op<unsigned>(q, angle_q, {0});
152 }
153
3/4
✓ Branch 1 taken 37101 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 20724 times.
✓ Branch 4 taken 16377 times.
2/2
✓ Decision 'true' taken 20724 times.
✓ Decision 'false' taken 16377 times.
 37101 if (!equiv_0(angle_p2, 4)) {
154
2/2
✓ Branch 0 taken 86 times.
✓ Branch 1 taken 20638 times.
2/2
✓ Decision 'true' taken 172 times.
✓ Decision 'false' taken 20552 times.
 20724 if (commute_through) {
155 left_over_gate =
156
5/10
✓ Branch 1 taken 86 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 86 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 86 times.
✗ Branch 9 not taken.
✓ Branch 14 taken 86 times.
✓ Branch 15 taken 86 times.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
 172 std::make_shared<Gate>(p, std::vector<Expr>{angle_p2}, 1);
157 } else {
158
2/4
✓ Branch 3 taken 20638 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 20638 times.
✗ Branch 7 not taken.
 20638 replacement.add_op<unsigned>(p, angle_p2, {0});
159 }
160 }
161
1/2
✓ Branch 1 taken 37101 times.
✗ Branch 2 not taken.
 37101 redundancy_removal(replacement);
162
1/2
✓ Branch 1 taken 37101 times.
✗ Branch 2 not taken.
 74202 return {replacement, left_over_gate};
163 37101 }
164
165 63459 void PQPSquasher::clear() { rotation_chain.clear(); }
166
167 ✗ std::unique_ptr<AbstractSquasher> PQPSquasher::clone() const {
168 ✗ return std::make_unique<PQPSquasher>(*this);
169 }
170
171 187834 static Rotation merge_rotations(
172 OpType r, const std::vector<Gate_ptr> &chain,
173 std::vector<Gate_ptr>::const_iterator &iter) {
174
1/2
✓ Branch 1 taken 187834 times.
✗ Branch 2 not taken.
 187834 Expr total_angle(0);
175
2/2
✓ Branch 2 taken 349912 times.
✓ Branch 3 taken 39784 times.
2/2
✓ Decision 'true' taken 349912 times.
✓ Decision 'false' taken 39784 times.
 389696 while (iter != chain.end()) {
176 349912 const Gate_ptr rot_op = *iter;
177
2/2
✓ Branch 2 taken 148050 times.
✓ Branch 3 taken 201862 times.
2/2
✓ Decision 'true' taken 148050 times.
✓ Decision 'false' taken 201862 times.
 349912 if (rot_op->get_type() != r) {
178 148050 break;
179 }
180
2/4
✓ Branch 2 taken 201862 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 201862 times.
✗ Branch 7 not taken.
 201862 total_angle += rot_op->get_params()[0];
181 201862 iter++;
182
2/2
✓ Branch 1 taken 201862 times.
✓ Branch 2 taken 148050 times.
 349912 }
183
2/4
✓ Branch 1 taken 187834 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 187834 times.
✗ Branch 5 not taken.
 375668 return Rotation(r, total_angle);
184 187834 }
185
186 6346 static bool squash_to_pqp(
187 Circuit &circ, OpType q, OpType p, bool strict = false) {
188 6346 bool reverse = true;
189
1/2
✓ Branch 1 taken 6346 times.
✗ Branch 2 not taken.
 6346 auto squasher = std::make_unique<PQPSquasher>(p, q, !strict, reverse);
190
1/2
✓ Branch 4 taken 6346 times.
✗ Branch 5 not taken.
 12692 return SingleQubitSquash(std::move(squasher), circ, reverse).squash();
191 6346 }
192
193 24 Transform reduce_XZ_chains() {
194 40 return Transform([](Circuit &circ) {
195 40 return squash_to_pqp(circ, OpType::Rx, OpType::Rz);
196
1/2
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
 24 });
197 }
198
199 6141 Transform squash_1qb_to_pqp(const OpType &q, const OpType &p, bool strict) {
200 return Transform(
201
1/2
✓ Branch 2 taken 6141 times.
✗ Branch 3 not taken.
 12447 [=](Circuit &circ) { return squash_to_pqp(circ, q, p, strict); });
202 }
203
204 // To squash to TK1:
205 // - we first decompose to ZYZ. Doing this was found to reduce the size of
206 // symbolic expressions
207 // - we then redecompose to ZXZ, so that we can commute Rz or Rx rotation past
208 // multi-qubit gates (most usual multi-qb gates commute with X or Z)
209 // - Rz and Rx rotations can then be straight-forwardly combined into TK1s.
210 3020 Transform squash_1qb_to_tk1() {
211
1/2
✓ Branch 2 taken 3020 times.
✗ Branch 3 not taken.
 9060 return Transforms::decompose_ZY() >>
212
2/4
✓ Branch 1 taken 3020 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3020 times.
✗ Branch 5 not taken.
 9060 squash_1qb_to_pqp(OpType::Ry, OpType::Rz, true) >>
213
2/4
✓ Branch 1 taken 3020 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3020 times.
✗ Branch 5 not taken.
 9060 Transforms::decompose_ZX() >>
214
1/2
✓ Branch 1 taken 3020 times.
✗ Branch 2 not taken.
 6040 squash_1qb_to_pqp(OpType::Rx, OpType::Rz, true) >>
215
2/4
✓ Branch 1 taken 3020 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3020 times.
✗ Branch 5 not taken.
 9060 Transforms::decompose_ZXZ_to_TK1();
216 }
217
218 37101 static bool fixup_angles(
219 Expr &angle_p1, Expr &angle_q, Expr &angle_p2, bool reversed) {
220 37101 bool success = false;
221
2/2
✓ Branch 0 taken 37049 times.
✓ Branch 1 taken 52 times.
2/2
✓ Decision 'true' taken 37049 times.
✓ Decision 'false' taken 52 times.
 37101 if (reversed) {
222 37049 std::swap(angle_p1, angle_p2);
223
1/2
✓ Branch 2 taken 37049 times.
✗ Branch 3 not taken.
 37049 angle_p1 *= -1;
224
1/2
✓ Branch 2 taken 37049 times.
✗ Branch 3 not taken.
 37049 angle_q *= -1;
225
1/2
✓ Branch 2 taken 37049 times.
✗ Branch 3 not taken.
 37049 angle_p2 *= -1;
226 }
227
6/6
✓ Branch 1 taken 1864 times.
✓ Branch 2 taken 35237 times.
✓ Branch 4 taken 1689 times.
✓ Branch 5 taken 175 times.
✓ Branch 6 taken 1689 times.
✓ Branch 7 taken 35412 times.
2/2
✓ Decision 'true' taken 1689 times.
✓ Decision 'false' taken 35412 times.
 37101 if (equiv_val(angle_q, 1., 2) && !equiv_0(angle_p2, 4)) {
228 // Prefer --P(p1-p2)--Q(...)--P(0)--
229 // Only occurs if angle_q is pi or 3pi and angle_p2 is non-zero
230 1689 angle_p1 -= angle_p2;
231 1689 angle_p2 = 0;
232 1689 success = true;
233
2/2
✓ Branch 1 taken 1903 times.
✓ Branch 2 taken 33509 times.
2/2
✓ Decision 'true' taken 1903 times.
✓ Decision 'false' taken 33509 times.
 35412 } else if (equiv_val(angle_p2, 1., 4)) {
234 // Then prefer --P(p1+p2)--Q(-q)--P(0)--
235 // Only occurs if angle_p2 is pi
236
1/2
✓ Branch 2 taken 1903 times.
✗ Branch 3 not taken.
 1903 angle_p1 += 1;
237
1/2
✓ Branch 2 taken 1903 times.
✗ Branch 3 not taken.
 1903 angle_q *= -1;
238 1903 angle_p2 = 0;
239 1903 success = true;
240
2/2
✓ Branch 1 taken 562 times.
✓ Branch 2 taken 32947 times.
2/2
✓ Decision 'true' taken 562 times.
✓ Decision 'false' taken 32947 times.
 33509 } else if (equiv_val(angle_p2, 3., 4)) {
241 // Then prefer --P(p1+p2)--Q(-q)--P(0)--
242 // Only occurs if angle_p2 is 3pi
243
1/2
✓ Branch 2 taken 562 times.
✗ Branch 3 not taken.
 562 angle_p1 += 3;
244
1/2
✓ Branch 2 taken 562 times.
✗ Branch 3 not taken.
 562 angle_q *= -1;
245 562 angle_p2 = 0;
246 562 success = true;
247
6/6
✓ Branch 1 taken 3040 times.
✓ Branch 2 taken 29907 times.
✓ Branch 4 taken 1108 times.
✓ Branch 5 taken 1932 times.
✓ Branch 6 taken 1108 times.
✓ Branch 7 taken 31839 times.
2/2
✓ Decision 'true' taken 1108 times.
✓ Decision 'false' taken 31839 times.
 32947 } else if (equiv_val(angle_p1, 1., 4) && !equiv_0(angle_p2, 4)) {
248 // Then prefer --P(0)--Q(-q)--P(p1+p2)--
249 // Only occurs if angle_p1 is pi and angle_p2 is non-zero
250
1/2
✓ Branch 2 taken 1108 times.
✗ Branch 3 not taken.
 1108 angle_q *= -1;
251
1/2
✓ Branch 2 taken 1108 times.
✗ Branch 3 not taken.
 1108 angle_p2 += 1;
252 1108 angle_p1 = 0;
253 1108 success = true;
254
6/6
✓ Branch 1 taken 478 times.
✓ Branch 2 taken 31361 times.
✓ Branch 4 taken 253 times.
✓ Branch 5 taken 225 times.
✓ Branch 6 taken 253 times.
✓ Branch 7 taken 31586 times.
2/2
✓ Decision 'true' taken 253 times.
✓ Decision 'false' taken 31586 times.
 31839 } else if (equiv_val(angle_p1, 3., 4) && !equiv_0(angle_p2, 4)) {
255 // Then prefer --P(0)--Q(-q)--P(p1+p2)--
256 // Only occurs if angle_p1 is 3pi and angle_p2 is non-zero
257
1/2
✓ Branch 2 taken 253 times.
✗ Branch 3 not taken.
 253 angle_q *= -1;
258
1/2
✓ Branch 2 taken 253 times.
✗ Branch 3 not taken.
 253 angle_p2 += 3;
259 253 angle_p1 = 0;
260 253 success = true;
261 }
262
2/2
✓ Branch 0 taken 37049 times.
✓ Branch 1 taken 52 times.
2/2
✓ Decision 'true' taken 37049 times.
✓ Decision 'false' taken 52 times.
 37101 if (reversed) {
263 37049 std::swap(angle_p1, angle_p2);
264
1/2
✓ Branch 2 taken 37049 times.
✗ Branch 3 not taken.
 37049 angle_p1 *= -1;
265
1/2
✓ Branch 2 taken 37049 times.
✗ Branch 3 not taken.
 37049 angle_q *= -1;
266
1/2
✓ Branch 2 taken 37049 times.
✗ Branch 3 not taken.
 37049 angle_p2 *= -1;
267 }
268 37101 return success;
269 }
270
271 147290 static bool remove_redundancy(
272 Circuit &circ, const Vertex &vert, VertexList &bin,
273 std::set<IVertex> &new_affected_verts, IndexMap &im) {
274
1/2
✓ Branch 1 taken 147290 times.
✗ Branch 2 not taken.
 147290 const Op_ptr op = circ.get_Op_ptr_from_Vertex(vert);
275
1/2
✓ Branch 2 taken 147290 times.
✗ Branch 3 not taken.
 147290 const OpDesc desc = op->get_desc();
276
3/4
✓ Branch 1 taken 147290 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 74593 times.
✓ Branch 4 taken 72697 times.
2/2
✓ Decision 'true' taken 72697 times.
✓ Decision 'false' taken 74593 times.
 147290 if (!desc.is_gate()) return false;
277
7/10
✓ Branch 1 taken 72697 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 72532 times.
✓ Branch 4 taken 165 times.
✓ Branch 6 taken 72532 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 72532 times.
✓ Branch 10 taken 165 times.
✓ Branch 11 taken 72532 times.
2/2
✓ Decision 'true' taken 165 times.
✓ Decision 'false' taken 72532 times.
 72697 if (circ.n_out_edges(vert) == 0 || circ.n_in_edges(vert) == 0) {
278 165 return false; // either a boundary vert or we have already removed it
279 }
280
281 678 auto remove_single_vertex = [&bin, &circ, &new_affected_verts,
282 2712 &im](const Vertex &v_remove) {
283 678 bin.push_back(v_remove);
284
3/4
✓ Branch 1 taken 678 times.
✗ Branch 2 not taken.
✓ Branch 7 taken 678 times.
✓ Branch 8 taken 678 times.
0/1
? Decision couldn't be analyzed.
 1356 for (const Vertex &l : circ.get_predecessors(v_remove)) {
285
2/4
✓ Branch 1 taken 678 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 678 times.
✗ Branch 6 not taken.
 678 new_affected_verts.insert({im.at(l), l});
286 678 }
287 678 circ.remove_vertex(
288 v_remove, Circuit::GraphRewiring::Yes, Circuit::VertexDeletion::No);
289 678 };
290 // remove 0 angle rotations from circuit
291
1/2
✓ Branch 2 taken 72532 times.
✗ Branch 3 not taken.
 72532 std::optional<double> a = op->is_identity();
292
2/2
✓ Branch 1 taken 678 times.
✓ Branch 2 taken 71854 times.
2/2
✓ Decision 'true' taken 678 times.
✓ Decision 'false' taken 71854 times.
 72532 if (a) {
293
1/2
✓ Branch 1 taken 678 times.
✗ Branch 2 not taken.
 678 remove_single_vertex(vert);
294
3/6
✓ Branch 1 taken 678 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 678 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 678 times.
✗ Branch 8 not taken.
 678 circ.add_phase(a.value());
295 678 return true;
296
2/4
✓ Branch 1 taken 71854 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 71854 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 71854 times.
 71854 } else if (desc.type() == OpType::noop) {
297 // remove "noop" gates from circuit
298 ✗ remove_single_vertex(vert);
299 ✗ return true;
300 }
301
1/2
✓ Branch 1 taken 71854 times.
✗ Branch 2 not taken.
 71854 VertexVec kids = circ.get_successors(vert);
302
303 // if op is immediately followed by a z basis measurement on all qubits,
304 // remove
305
2/4
✓ Branch 1 taken 71854 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 71854 times.
✗ Branch 4 not taken.
1/2
✓ Decision 'true' taken 71854 times.
✗ Decision 'false' not taken.
 71854 if (circ.n_out_edges_of_type(vert, EdgeType::Classical) == 0) {
306 71854 bool z_followed_by_measures = true;
307
5/6
✓ Branch 1 taken 71854 times.
✓ Branch 2 taken 71854 times.
✓ Branch 3 taken 71854 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 71854 times.
✓ Branch 6 taken 71854 times.
0/1
? Decision couldn't be analyzed.
 143708 for (port_t port = 0; port < kids.size() && z_followed_by_measures;
308 port++) {
309
2/4
✓ Branch 2 taken 71854 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 71854 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 71854 times.
 71854 if (circ.get_OpType_from_Vertex(kids[port]) == OpType::Measure) {
310 ✗ z_followed_by_measures &=
311 ✗ circ.commutes_with_basis(vert, Pauli::Z, PortType::Source, port);
312 } else {
313 71854 z_followed_by_measures = false;
314 }
315 }
316
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 71854 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 71854 times.
 71854 if (z_followed_by_measures) {
317 ✗ remove_single_vertex(vert);
318 ✗ return true;
319 }
320 }
321
322 // check that both the vertex and its successor have each other and only each
323 // other
324
5/12
✓ Branch 1 taken 71854 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 71854 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 71854 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 71854 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 71854 times.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
1/2
✓ Decision 'true' taken 71854 times.
✗ Decision 'false' not taken.
 71854 if ((kids.size() == 1) && (circ.get_predecessors(kids[0]).size() == 1)) {
325 // check that the ports match up between vertices
326 71854 Vertex b = kids[0];
327
1/2
✓ Branch 1 taken 71854 times.
✗ Branch 2 not taken.
 71854 EdgeVec ins = circ.get_in_edges(b);
328
2/2
✓ Branch 5 taken 71854 times.
✓ Branch 6 taken 71854 times.
2/2
✓ Decision 'true' taken 71854 times.
✓ Decision 'false' taken 71854 times.
 143708 for (const Edge &in : ins) {
329
3/6
✓ Branch 1 taken 71854 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 71854 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 71854 times.
1/2
✓ Decision 'true' taken 71854 times.
✗ Decision 'false' not taken.
 71854 if (circ.get_source_port(in) != circ.get_target_port(in)) return false;
330 }
331
332 // check that the classical edges match up correctly
333
2/4
✓ Branch 1 taken 71854 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 71854 times.
1/2
✓ Decision 'true' taken 71854 times.
✗ Decision 'false' not taken.
 71854 if (circ.n_in_edges_of_type(vert, EdgeType::Boolean) != 0) return false;
334
335
1/2
✓ Branch 1 taken 71854 times.
✗ Branch 2 not taken.
 71854 const Op_ptr b_op = circ.get_Op_ptr_from_Vertex(b);
336
1/2
✓ Branch 2 taken 71854 times.
✗ Branch 3 not taken.
 71854 const OpDesc b_desc = b_op->get_desc();
337
338
3/4
✓ Branch 1 taken 71854 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 35001 times.
✓ Branch 4 taken 36853 times.
2/2
✓ Decision 'true' taken 35001 times.
✓ Decision 'false' taken 36853 times.
 71854 if (!b_desc.is_oneway()) {
339 // if A = B.dagger(), AB = I
340 // This method cannot detect matches between rotation gates.
341 // Rotation gates are covered by the rotation gate combiner, everything
342 // else in this.
343
4/6
✓ Branch 3 taken 35001 times.
✗ Branch 4 not taken.
✓ Branch 7 taken 35001 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 30 times.
✓ Branch 11 taken 34971 times.
2/2
✓ Decision 'true' taken 30 times.
✓ Decision 'false' taken 34971 times.
 35001 if (*b_op->dagger() == *op) {
344
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 bin.push_back(vert);
345
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 bin.push_back(b);
346
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 VertexVec last_verts = circ.get_predecessors(vert);
347
2/2
✓ Branch 4 taken 30 times.
✓ Branch 5 taken 30 times.
2/2
✓ Decision 'true' taken 30 times.
✓ Decision 'false' taken 30 times.
 60 for (const Vertex &l : last_verts) {
348
2/4
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 30 times.
✗ Branch 6 not taken.
 30 new_affected_verts.insert({im.at(l), l});
349 }
350
1/2
✓ Branch 2 taken 30 times.
✗ Branch 3 not taken.
 30 VertexList to_detach{vert, b};
351 // detached from circuit but not removed from graph
352
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 circ.remove_vertices(
353 to_detach, Circuit::GraphRewiring::Yes,
354 Circuit::VertexDeletion::No);
355 30 return true;
356
2/4
✓ Branch 3 taken 34971 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 34971 times.
✗ Branch 6 not taken.
2/2
✓ Decision 'true' taken 34971 times.
✓ Decision 'false' taken 30 times.
 35001 } else if (desc.is_rotation()) {
357 // combine two rotation gates together, then if the combined
358 // operation is the identity up to phase, remove from circuit
359
4/6
✓ Branch 1 taken 34971 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 34971 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 135 times.
✓ Branch 7 taken 34836 times.
2/2
✓ Decision 'true' taken 135 times.
✓ Decision 'false' taken 34836 times.
 34971 if (b_desc.type() == desc.type()) {
360
2/4
✓ Branch 2 taken 135 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 135 times.
✗ Branch 7 not taken.
 135 Expr expr1 = op->get_params()[0];
361
2/4
✓ Branch 2 taken 135 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 135 times.
✗ Branch 7 not taken.
 135 Expr expr2 = b_op->get_params()[0];
362
1/2
✓ Branch 1 taken 135 times.
✗ Branch 2 not taken.
 135 VertexVec last_verts = circ.get_predecessors(vert);
363
2/2
✓ Branch 4 taken 135 times.
✓ Branch 5 taken 135 times.
2/2
✓ Decision 'true' taken 135 times.
✓ Decision 'false' taken 135 times.
 270 for (const Vertex &l : last_verts) {
364
2/4
✓ Branch 1 taken 135 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 135 times.
✗ Branch 6 not taken.
 135 new_affected_verts.insert({im.at(l), l});
365 }
366
1/2
✓ Branch 1 taken 135 times.
✗ Branch 2 not taken.
 135 circ.remove_vertex(
367 b, Circuit::GraphRewiring::Yes, Circuit::VertexDeletion::No);
368
1/2
✓ Branch 1 taken 135 times.
✗ Branch 2 not taken.
 135 bin.push_back(b);
369
2/4
✓ Branch 1 taken 135 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 135 times.
✗ Branch 6 not taken.
 405 std::vector<Expr> params_new = {expr1 + expr2};
370
2/4
✓ Branch 2 taken 135 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 135 times.
✗ Branch 6 not taken.
 135 Op_ptr op_new = get_op_ptr(desc.type(), params_new, ins.size());
371
1/2
✓ Branch 2 taken 135 times.
✗ Branch 3 not taken.
 135 std::optional<double> a = op_new->is_identity();
372
2/2
✓ Branch 1 taken 42 times.
✓ Branch 2 taken 93 times.
2/2
✓ Decision 'true' taken 42 times.
✓ Decision 'false' taken 93 times.
 135 if (a) {
373
1/2
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
 42 bin.push_back(vert);
374
1/2
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
 42 circ.remove_vertex(
375 vert, Circuit::GraphRewiring::Yes, Circuit::VertexDeletion::No);
376
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.
 42 circ.add_phase(a.value());
377 } else {
378
2/4
✓ Branch 1 taken 93 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 93 times.
✗ Branch 6 not taken.
 93 new_affected_verts.insert({im[vert], vert});
379
1/2
✓ Branch 1 taken 93 times.
✗ Branch 2 not taken.
 93 circ.dag[vert].op = op_new;
380 }
381 135 return true;
382 135 }
383 }
384 }
385
6/6
✓ Branch 1 taken 71689 times.
✓ Branch 2 taken 165 times.
✓ Branch 4 taken 71689 times.
✓ Branch 5 taken 165 times.
✓ Branch 7 taken 71689 times.
✓ Branch 8 taken 165 times.
 72184 }
386 71689 return false;
387 147290 }
388
389 37101 static bool redundancy_removal(Circuit &circ) {
390 37101 bool success = false;
391 37101 bool found_redundancy = true;
392
1/2
✓ Branch 1 taken 37101 times.
✗ Branch 2 not taken.
 37101 IndexMap im = circ.index_map();
393 37101 std::set<IVertex> old_affected_verts;
394
7/8
✓ Branch 1 taken 37101 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 146354 times.
✓ Branch 5 taken 37101 times.
✓ Branch 7 taken 146354 times.
✓ Branch 8 taken 37101 times.
✓ Branch 10 taken 37101 times.
✓ Branch 11 taken 37101 times.
 220556 BGL_FORALL_VERTICES(v, circ.dag, DAG) {
395
2/4
✓ Branch 1 taken 146354 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 146354 times.
✗ Branch 6 not taken.
 146354 old_affected_verts.insert({im.at(v), v});
396 }
397 37101 VertexList bin;
398
2/2
✓ Branch 0 taken 37941 times.
✓ Branch 1 taken 37101 times.
2/2
✓ Decision 'true' taken 37941 times.
✓ Decision 'false' taken 37101 times.
 75042 while (found_redundancy) {
399 37941 std::set<IVertex> new_affected_verts;
400
2/2
✓ Branch 5 taken 147290 times.
✓ Branch 6 taken 37941 times.
2/2
✓ Decision 'true' taken 147290 times.
✓ Decision 'false' taken 37941 times.
 185231 for (const IVertex &p : old_affected_verts) {
401
1/2
✓ Branch 1 taken 147290 times.
✗ Branch 2 not taken.
 147290 remove_redundancy(circ, p.second, bin, new_affected_verts, im);
402 }
403 37941 found_redundancy = new_affected_verts.size() != 0;
404 37941 success |= found_redundancy;
405
1/2
✓ Branch 1 taken 37941 times.
✗ Branch 2 not taken.
 37941 old_affected_verts = new_affected_verts;
406 37941 }
407
1/2
✓ Branch 1 taken 37101 times.
✗ Branch 2 not taken.
 37101 circ.remove_vertices(
408 bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
409 37101 return success;
410 37101 }
411
412 } // namespace Transforms
413
414 } // namespace tket
415