GCC Code Coverage Report

Directory: ./
File: Transformations/Decomposition.cpp
Date: 2022-10-15 05:10:18
Warnings: 8 unchecked decisions!
Exec Total Coverage
Lines: 1048 1082 96.9%
Functions: 72 72 100.0%
Branches: 1413 2305 61.3%
Decisions: 333 385 86.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 "Decomposition.hpp"
16
17 #include <functional>
18 #include <optional>
19 // replace with c++20 <ranges> when available
20 #include <boost/range/adaptor/filtered.hpp>
21 #include <stdexcept>
22
23 #include "Architecture/Architecture.hpp"
24 #include "BasicOptimisation.hpp"
25 #include "Circuit/CircPool.hpp"
26 #include "Converters/PhasePoly.hpp"
27 #include "Gate/GatePtr.hpp"
28 #include "OpType/OpType.hpp"
29 #include "OpType/OpTypeFunctions.hpp"
30 #include "OpType/OpTypeInfo.hpp"
31 #include "Ops/OpPtr.hpp"
32 #include "OptimisationPass.hpp"
33 #include "PhasedXFrontier.hpp"
34 #include "Rebase.hpp"
35 #include "Replacement.hpp"
36 #include "Transform.hpp"
37 #include "Utils/Constants.hpp"
38 #include "Utils/Expression.hpp"
39 #include "Utils/MatrixAnalysis.hpp"
40
41 namespace tket {
42
43 namespace Transforms {
44
45 static bool convert_to_zxz(Circuit &circ);
46 static bool convert_to_zyz(Circuit &circ);
47 static bool convert_to_xyx(Circuit &circ);
48
49 /**
50 * Decompose all multi-qubit unitary gates into TK2 and single-qubit gates.
51 *
52 * This function does not decompose boxes.
53 */
54 193 static bool convert_multiqs_TK2(Circuit &circ) {
55 193 bool success = false;
56 193 VertexList bin;
57
7/8
✓ Branch 1 taken 193 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 9686 times.
✓ Branch 6 taken 193 times.
✓ Branch 8 taken 9686 times.
✓ Branch 9 taken 193 times.
✓ Branch 11 taken 193 times.
✓ Branch 12 taken 193 times.
 10072 BGL_FORALL_VERTICES(v, circ.dag, DAG) {
58
1/2
✓ Branch 1 taken 9686 times.
✗ Branch 2 not taken.
 9686 Op_ptr op = circ.get_Op_ptr_from_Vertex(v);
59 9686 OpType optype = op->get_type();
60
4/6
✓ Branch 1 taken 9686 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 8752 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 8749 times.
✓ Branch 7 taken 3 times.
2/2
✓ Decision 'true' taken 1116 times.
✓ Decision 'false' taken 17322 times.
 18438 if (is_gate_type(optype) && !is_projective_type(optype) &&
61
9/10
✓ Branch 0 taken 8752 times.
✓ Branch 1 taken 934 times.
✓ Branch 4 taken 8749 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 2359 times.
✓ Branch 7 taken 6390 times.
✓ Branch 8 taken 1116 times.
✓ Branch 9 taken 1243 times.
✓ Branch 10 taken 1116 times.
✓ Branch 11 taken 8570 times.
 18438 op->n_qubits() >= 2 && (optype != OpType::TK2)) {
62
1/2
✓ Branch 2 taken 1116 times.
✗ Branch 3 not taken.
 1116 Circuit in_circ = TK2_circ_from_multiq(op);
63 Subcircuit sub = {
64
4/8
✓ Branch 1 taken 1116 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1116 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 1116 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 1116 times.
✗ Branch 12 not taken.
 2232 {circ.get_in_edges(v)}, {circ.get_all_out_edges(v)}, {v}};
65
1/2
✓ Branch 1 taken 1116 times.
✗ Branch 2 not taken.
 1116 bin.push_back(v);
66
1/2
✓ Branch 1 taken 1116 times.
✗ Branch 2 not taken.
 1116 circ.substitute(in_circ, sub, Circuit::VertexDeletion::No);
67 1116 success = true;
68 1116 }
69 9686 }
70
1/2
✓ Branch 1 taken 193 times.
✗ Branch 2 not taken.
 193 circ.remove_vertices(
71 bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
72 193 return success;
73 193 }
74
75 /**
76 * Decompose all multi-qubit unitary gates into CX and single-qubit gates.
77 *
78 * This function does not decompose boxes.
79 */
80 331 static bool convert_multiqs_CX(Circuit &circ) {
81 331 bool success = false;
82 331 VertexList bin;
83
7/8
✓ Branch 1 taken 331 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 28258 times.
✓ Branch 6 taken 331 times.
✓ Branch 8 taken 28258 times.
✓ Branch 9 taken 331 times.
✓ Branch 11 taken 331 times.
✓ Branch 12 taken 331 times.
 28920 BGL_FORALL_VERTICES(v, circ.dag, DAG) {
84
1/2
✓ Branch 1 taken 28258 times.
✗ Branch 2 not taken.
 28258 Op_ptr op = circ.get_Op_ptr_from_Vertex(v);
85 28258 OpType optype = op->get_type();
86
4/6
✓ Branch 1 taken 28258 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 26001 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 25964 times.
✓ Branch 7 taken 37 times.
2/2
✓ Decision 'true' taken 754 times.
✓ Decision 'false' taken 53505 times.
 54259 if (is_gate_type(optype) && !is_projective_type(optype) &&
87
9/10
✓ Branch 0 taken 26001 times.
✓ Branch 1 taken 2257 times.
✓ Branch 4 taken 25964 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 6016 times.
✓ Branch 7 taken 19948 times.
✓ Branch 8 taken 754 times.
✓ Branch 9 taken 5262 times.
✓ Branch 10 taken 754 times.
✓ Branch 11 taken 27504 times.
 54259 op->n_qubits() >= 2 && (optype != OpType::CX)) {
88
1/2
✓ Branch 2 taken 754 times.
✗ Branch 3 not taken.
 754 Circuit in_circ = CX_circ_from_multiq(op);
89 Subcircuit sub = {
90
4/8
✓ Branch 1 taken 754 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 754 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 754 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 754 times.
✗ Branch 12 not taken.
 1508 {circ.get_in_edges(v)}, {circ.get_all_out_edges(v)}, {v}};
91
1/2
✓ Branch 1 taken 754 times.
✗ Branch 2 not taken.
 754 bin.push_back(v);
92
1/2
✓ Branch 1 taken 754 times.
✗ Branch 2 not taken.
 754 circ.substitute(in_circ, sub, Circuit::VertexDeletion::No);
93 754 success = true;
94 754 }
95 28258 }
96
1/2
✓ Branch 1 taken 331 times.
✗ Branch 2 not taken.
 331 circ.remove_vertices(
97 bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
98 331 return success;
99 331 }
100
101 3224 static bool convert_to_zxz(Circuit &circ) {
102 bool success =
103
3/6
✓ Branch 2 taken 3224 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 3224 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 3224 times.
✗ Branch 9 not taken.
 3224 (decompose_single_qubits_TK1() >> decompose_tk1_to_rzrx()).apply(circ);
104 3224 return success;
105 }
106
107 3097 static bool convert_to_zyz(Circuit &circ) {
108
7/14
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 3096 times.
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
✓ Branch 14 taken 1 times.
✗ Branch 15 not taken.
✓ Branch 17 taken 1 times.
✗ Branch 18 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
 3097 static const Expr half = SymEngine::div(Expr(1), Expr(2));
109
2/4
✓ Branch 1 taken 3097 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3097 times.
✗ Branch 5 not taken.
 3097 bool success = decompose_single_qubits_TK1().apply(circ);
110 3097 VertexList bin;
111
7/8
✓ Branch 1 taken 3097 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 148649 times.
✓ Branch 6 taken 3097 times.
✓ Branch 8 taken 148649 times.
✓ Branch 9 taken 3097 times.
✓ Branch 11 taken 3097 times.
✓ Branch 12 taken 3097 times.
 154843 BGL_FORALL_VERTICES(v, circ.dag, DAG) {
112
3/4
✓ Branch 1 taken 148649 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 15333 times.
✓ Branch 4 taken 133316 times.
2/2
✓ Decision 'true' taken 133316 times.
✓ Decision 'false' taken 15333 times.
 148649 if (circ.n_in_edges(v) != 1) continue;
113
1/2
✓ Branch 1 taken 133316 times.
✗ Branch 2 not taken.
 133316 const Op_ptr op = circ.get_Op_ptr_from_Vertex(v);
114
2/2
✓ Branch 2 taken 38216 times.
✓ Branch 3 taken 95100 times.
2/2
✓ Decision 'true' taken 38216 times.
✓ Decision 'false' taken 95100 times.
 133316 if (op->get_type() == OpType::TK1) {
115
1/2
✓ Branch 2 taken 38216 times.
✗ Branch 3 not taken.
 38216 std::vector<Expr> params = op->get_params();
116
1/2
✓ Branch 2 taken 38216 times.
✗ Branch 3 not taken.
 38216 Circuit replacement(1);
117
1/2
✓ Branch 2 taken 38216 times.
✗ Branch 3 not taken.
 38216 Expr a = params[2] + half;
118
1/2
✓ Branch 2 taken 38216 times.
✗ Branch 3 not taken.
 38216 Expr b = params[1];
119
1/2
✓ Branch 2 taken 38216 times.
✗ Branch 3 not taken.
 38216 Expr c = params[0] - half;
120
3/4
✓ Branch 1 taken 38216 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 34735 times.
✓ Branch 4 taken 3481 times.
2/2
✓ Decision 'true' taken 34735 times.
✓ Decision 'false' taken 3481 times.
 38216 if (!equiv_0(a, 4)) {
121
2/4
✓ Branch 3 taken 34735 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 34735 times.
✗ Branch 7 not taken.
 34735 replacement.add_op<unsigned>(OpType::Rz, a, {0});
122 }
123
3/4
✓ Branch 1 taken 38216 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 23336 times.
✓ Branch 4 taken 14880 times.
2/2
✓ Decision 'true' taken 23336 times.
✓ Decision 'false' taken 14880 times.
 38216 if (!equiv_0(b, 4)) {
124
2/4
✓ Branch 3 taken 23336 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 23336 times.
✗ Branch 7 not taken.
 23336 replacement.add_op<unsigned>(OpType::Ry, b, {0});
125 }
126
3/4
✓ Branch 1 taken 38216 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 32442 times.
✓ Branch 4 taken 5774 times.
2/2
✓ Decision 'true' taken 32442 times.
✓ Decision 'false' taken 5774 times.
 38216 if (!equiv_0(c, 4)) {
127
2/4
✓ Branch 3 taken 32442 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 32442 times.
✗ Branch 7 not taken.
 32442 replacement.add_op<unsigned>(OpType::Rz, c, {0});
128 }
129 Subcircuit sub = {
130
4/8
✓ Branch 1 taken 38216 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 38216 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 38216 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 38216 times.
✗ Branch 12 not taken.
 76432 {circ.get_in_edges(v)}, {circ.get_all_out_edges(v)}, {v}};
131
1/2
✓ Branch 1 taken 38216 times.
✗ Branch 2 not taken.
 38216 bin.push_back(v);
132
1/2
✓ Branch 1 taken 38216 times.
✗ Branch 2 not taken.
 38216 circ.substitute(replacement, sub, Circuit::VertexDeletion::No);
133 38216 success = true;
134 38216 }
135 133316 }
136
1/2
✓ Branch 1 taken 3097 times.
✗ Branch 2 not taken.
 3097 circ.remove_vertices(
137 bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
138 3097 return success;
139 3097 }
140
141 1 static bool convert_to_xyx(Circuit &circ) {
142
6/14
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
✓ Branch 14 taken 1 times.
✗ Branch 15 not taken.
✓ Branch 17 taken 1 times.
✗ Branch 18 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
 1 static const Expr half = SymEngine::div(Expr(1), Expr(2));
143
2/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
 1 bool success = decompose_single_qubits_TK1().apply(circ);
144 1 VertexList bin;
145
7/8
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 8 times.
✓ Branch 6 taken 1 times.
✓ Branch 8 taken 8 times.
✓ Branch 9 taken 1 times.
✓ Branch 11 taken 1 times.
✓ Branch 12 taken 1 times.
 10 BGL_FORALL_VERTICES(v, circ.dag, DAG) {
146
3/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 7 times.
2/2
✓ Decision 'true' taken 7 times.
✓ Decision 'false' taken 1 times.
 8 if (circ.n_in_edges(v) != 1) continue;
147
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 const Op_ptr op = circ.get_Op_ptr_from_Vertex(v);
148
2/2
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 6 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 6 times.
 7 if (op->get_type() == OpType::TK1) {
149
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 1 std::vector<Expr> params = op->get_params();
150
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 1 Circuit replacement(1);
151
2/4
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
 1 replacement.add_op<unsigned>(OpType::Ry, half, {0});
152
3/6
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
 1 replacement.add_op<unsigned>(OpType::Rx, params[2] + half, {0});
153
2/4
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
 1 replacement.add_op<unsigned>(OpType::Ry, params[1], {0});
154
3/6
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
 1 replacement.add_op<unsigned>(OpType::Rx, params[0] - half, {0});
155
3/6
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 1 times.
✗ Branch 10 not taken.
 1 replacement.add_op<unsigned>(OpType::Ry, -half, {0});
156
2/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
 1 remove_redundancies().apply(replacement);
157 Subcircuit sub = {
158
4/8
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 1 times.
✗ Branch 12 not taken.
 2 {circ.get_in_edges(v)}, {circ.get_all_out_edges(v)}, {v}};
159
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 bin.push_back(v);
160
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 circ.substitute(replacement, sub, Circuit::VertexDeletion::No);
161 1 success = true;
162 1 }
163 7 }
164
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 circ.remove_vertices(
165 bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
166 1 return success;
167 1 }
168
169 179 Transform decompose_multi_qubits_TK2() {
170
1/2
✓ Branch 2 taken 179 times.
✗ Branch 3 not taken.
 179 return Transform(convert_multiqs_TK2);
171 }
172
173
1/2
✓ Branch 2 taken 312 times.
✗ Branch 3 not taken.
 312 Transform decompose_multi_qubits_CX() { return Transform(convert_multiqs_CX); }
174
175 8894 static bool convert_singleqs_TK1(Circuit &circ) {
176 8894 bool success = false;
177 8894 VertexList bin;
178
7/8
✓ Branch 1 taken 8894 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 196669 times.
✓ Branch 6 taken 8893 times.
✓ Branch 8 taken 196669 times.
✓ Branch 9 taken 8893 times.
✓ Branch 11 taken 8893 times.
✓ Branch 12 taken 8894 times.
 214456 BGL_FORALL_VERTICES(v, circ.dag, DAG) {
179
1/2
✓ Branch 1 taken 196669 times.
✗ Branch 2 not taken.
 196669 Op_ptr op = circ.get_Op_ptr_from_Vertex(v);
180 196669 OpType optype = op->get_type();
181
4/6
✓ Branch 1 taken 196669 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 172594 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 172460 times.
✓ Branch 7 taken 134 times.
2/2
✓ Decision 'true' taken 122136 times.
✓ Decision 'false' taken 247127 times.
 369263 if (is_gate_type(optype) && !is_projective_type(optype) &&
182
9/10
✓ Branch 0 taken 172594 times.
✓ Branch 1 taken 24075 times.
✓ Branch 4 taken 172460 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 150568 times.
✓ Branch 7 taken 21892 times.
✓ Branch 8 taken 61068 times.
✓ Branch 9 taken 89500 times.
✓ Branch 10 taken 61068 times.
✓ Branch 11 taken 135601 times.
 369263 op->n_qubits() == 1 && optype != OpType::TK1) {
183
2/4
✓ Branch 2 taken 61068 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 61068 times.
✗ Branch 7 not taken.
 122136 std::vector<Expr> tk1_angs = as_gate_ptr(op)->get_tk1_angles();
184
1/2
✓ Branch 2 taken 61068 times.
✗ Branch 3 not taken.
 61068 Circuit rep(1);
185
8/16
✓ Branch 3 taken 61068 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 61068 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 61068 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 61068 times.
✗ Branch 13 not taken.
✓ Branch 16 taken 61068 times.
✗ Branch 17 not taken.
✓ Branch 19 taken 61068 times.
✗ Branch 20 not taken.
✓ Branch 23 taken 183204 times.
✓ Branch 24 taken 61068 times.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
 427476 rep.add_op<unsigned>(
186 183204 OpType::TK1, {tk1_angs[0], tk1_angs[1], tk1_angs[2]}, {0});
187
1/2
✓ Branch 1 taken 61068 times.
✗ Branch 2 not taken.
 61068 circ.substitute(rep, v, Circuit::VertexDeletion::No);
188
2/4
✓ Branch 2 taken 61068 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 61068 times.
✗ Branch 6 not taken.
 61068 circ.add_phase(tk1_angs[3]);
189
1/2
✓ Branch 1 taken 61068 times.
✗ Branch 2 not taken.
 61068 bin.push_back(v);
190 61068 success = true;
191 61068 }
192 196669 }
193
1/2
✓ Branch 1 taken 8894 times.
✗ Branch 2 not taken.
 8894 circ.remove_vertices(
194 bin, Circuit::GraphRewiring::Yes, Circuit::VertexDeletion::Yes);
195 8894 return success;
196 8894 }
197
198 8893 Transform decompose_single_qubits_TK1() {
199
1/2
✓ Branch 2 taken 8893 times.
✗ Branch 3 not taken.
 8893 return Transform(convert_singleqs_TK1);
200 }
201
202 5 Transform decompose_ZYZ_to_TK1() {
203 5 return Transform([](Circuit &circ) {
204 5 bool success = false;
205
4/8
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 4 times.
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
 5 static const Expr zero(0);
206
7/14
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 4 times.
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
✓ Branch 14 taken 1 times.
✗ Branch 15 not taken.
✓ Branch 17 taken 1 times.
✗ Branch 18 not taken.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
 5 static const Expr half = SymEngine::div(Expr(1), Expr(2));
207 5 VertexList bin;
208
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 VertexVec inputs = circ.q_inputs();
209
2/2
✓ Branch 4 taken 7 times.
✓ Branch 5 taken 5 times.
2/2
✓ Decision 'true' taken 7 times.
✓ Decision 'false' taken 5 times.
 12 for (VertexVec::iterator i = inputs.begin(); i != inputs.end(); ++i) {
210
1/2
✓ Branch 2 taken 7 times.
✗ Branch 3 not taken.
 7 Edge e = circ.get_nth_out_edge(*i, 0);
211
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 Vertex v = circ.target(e);
212
4/6
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 32 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 25 times.
✓ Branch 7 taken 7 times.
0/1
? Decision couldn't be analyzed.
 32 while (!is_final_q_type(circ.get_OpType_from_Vertex(v))) {
213
3/4
✓ Branch 1 taken 25 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 9 times.
✓ Branch 4 taken 16 times.
2/2
✓ Decision 'true' taken 9 times.
✓ Decision 'false' taken 16 times.
 25 if (circ.get_OpType_from_Vertex(v) == OpType::Rz) {
214
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 const Op_ptr v_g = circ.get_Op_ptr_from_Vertex(v);
215
2/4
✓ Branch 2 taken 9 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 9 times.
✗ Branch 7 not taken.
 9 Expr angle_1 = v_g->get_params()[0];
216
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 Edge e1 = circ.get_next_edge(v, e);
217
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 Vertex v2 = circ.target(e1);
218
3/4
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 3 times.
✓ Branch 4 taken 6 times.
2/2
✓ Decision 'true' taken 3 times.
✓ Decision 'false' taken 6 times.
 9 if (circ.get_OpType_from_Vertex(v2) == OpType::Ry) {
219
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 const Op_ptr v2_g = circ.get_Op_ptr_from_Vertex(v2);
220
2/4
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 3 times.
✗ Branch 7 not taken.
 3 Expr angle_2 = v2_g->get_params()[0];
221
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 Edge e2 = circ.get_next_edge(v2, e1);
222
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 Vertex v3 = circ.target(e2);
223
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 bin.push_back(v2);
224
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 circ.remove_vertex(
225 v2, Circuit::GraphRewiring::Yes, Circuit::VertexDeletion::No);
226
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 Expr angle_3 = zero;
227
3/4
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 2 times.
✓ Branch 4 taken 1 times.
2/2
✓ Decision 'true' taken 2 times.
✓ Decision 'false' taken 1 times.
 3 if (circ.get_OpType_from_Vertex(v3) == OpType::Rz) {
228
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 const Op_ptr v3_g = circ.get_Op_ptr_from_Vertex(v3);
229
2/4
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
 2 angle_3 = v3_g->get_params()[0];
230
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 circ.remove_vertex(
231 v3, Circuit::GraphRewiring::Yes, Circuit::VertexDeletion::No);
232
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 bin.push_back(v3);
233 2 }
234 std::vector<Expr> new_params = {
235
4/8
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 3 times.
✗ Branch 8 not taken.
✓ Branch 11 taken 3 times.
✗ Branch 12 not taken.
 15 angle_3 + half, angle_2, angle_1 - half};
236
3/6
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 3 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 3 times.
✗ Branch 9 not taken.
 3 circ.dag[v] = {get_op_ptr(OpType::TK1, new_params)};
237 3 } else {
238
9/18
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 6 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 6 times.
✗ Branch 8 not taken.
✓ Branch 11 taken 6 times.
✗ Branch 12 not taken.
✓ Branch 14 taken 6 times.
✗ Branch 15 not taken.
✓ Branch 18 taken 6 times.
✗ Branch 19 not taken.
✓ Branch 21 taken 6 times.
✗ Branch 22 not taken.
✓ Branch 29 taken 18 times.
✓ Branch 30 taken 6 times.
✗ Branch 37 not taken.
✗ Branch 38 not taken.
 24 circ.dag[v] = {get_op_ptr(OpType::TK1, {zero, zero, angle_1})};
239 }
240
3/4
✓ Branch 3 taken 16 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 6 times.
✓ Branch 6 taken 10 times.
2/2
✓ Decision 'true' taken 6 times.
✓ Decision 'false' taken 19 times.
 25 } else if (circ.get_OpType_from_Vertex(v) == OpType::Ry) {
241
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 const Op_ptr v_g = circ.get_Op_ptr_from_Vertex(v);
242
2/4
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 6 times.
✗ Branch 7 not taken.
 6 Expr angle_2 = v_g->get_params()[0];
243
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 Expr angle_3 = zero;
244
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 Edge e1 = circ.get_next_edge(v, e);
245
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 Vertex v2 = circ.target(e1);
246
3/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 5 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 5 times.
 6 if (circ.get_OpType_from_Vertex(v2) == OpType::Rz) {
247
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 const Op_ptr v2_g = circ.get_Op_ptr_from_Vertex(v2);
248
2/4
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
 1 angle_3 = v2_g->get_params()[0];
249
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 circ.remove_vertex(
250 v2, Circuit::GraphRewiring::Yes, Circuit::VertexDeletion::No);
251
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 bin.push_back(v2);
252 1 }
253
4/8
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 6 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 6 times.
✗ Branch 8 not taken.
✓ Branch 11 taken 6 times.
✗ Branch 12 not taken.
 30 std::vector<Expr> new_params = {angle_3 + half, angle_2, -half};
254
3/6
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 6 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 6 times.
✗ Branch 9 not taken.
 6 circ.dag[v] = {get_op_ptr(OpType::TK1, new_params)};
255 6 }
256
1/2
✓ Branch 1 taken 25 times.
✗ Branch 2 not taken.
 25 e = circ.get_next_edge(v, e);
257
1/2
✓ Branch 1 taken 25 times.
✗ Branch 2 not taken.
 25 v = circ.target(e);
258 }
259 }
260
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 circ.remove_vertices(
261 bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
262 5 return success;
263
1/2
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
 10 });
264 }
265
266 17927 static Circuit tk1_angles_to_circ(Expr a, Expr b, Expr c) {
267
1/2
✓ Branch 2 taken 17927 times.
✗ Branch 3 not taken.
 17927 Circuit circ(1);
268
269
1/2
✓ Branch 1 taken 17927 times.
✗ Branch 2 not taken.
 17927 std::optional<double> ea = eval_expr(a);
270
1/2
✓ Branch 1 taken 17927 times.
✗ Branch 2 not taken.
 17927 std::optional<double> eb = eval_expr(b);
271
1/2
✓ Branch 1 taken 17927 times.
✗ Branch 2 not taken.
 17927 std::optional<double> ec = eval_expr(c);
272
273 // Remove global phases
274
6/6
✓ Branch 1 taken 17858 times.
✓ Branch 2 taken 69 times.
✓ Branch 4 taken 359 times.
✓ Branch 5 taken 17499 times.
✓ Branch 6 taken 359 times.
✓ Branch 7 taken 17568 times.
2/2
✓ Decision 'true' taken 359 times.
✓ Decision 'false' taken 17568 times.
 17927 if (ea && *ea >= 2) {
275
2/4
✓ Branch 1 taken 359 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 359 times.
✗ Branch 5 not taken.
 359 a -= 2;
276
2/4
✓ Branch 1 taken 359 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 359 times.
✗ Branch 5 not taken.
 359 circ.add_phase(1);
277 }
278
6/6
✓ Branch 1 taken 17870 times.
✓ Branch 2 taken 57 times.
✓ Branch 4 taken 74 times.
✓ Branch 5 taken 17796 times.
✓ Branch 6 taken 74 times.
✓ Branch 7 taken 17853 times.
2/2
✓ Decision 'true' taken 74 times.
✓ Decision 'false' taken 17853 times.
 17927 if (eb && *eb >= 2) {
279
2/4
✓ Branch 1 taken 74 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 74 times.
✗ Branch 5 not taken.
 74 b -= 2;
280
2/4
✓ Branch 1 taken 74 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 74 times.
✗ Branch 5 not taken.
 74 circ.add_phase(1);
281 }
282
6/6
✓ Branch 1 taken 17872 times.
✓ Branch 2 taken 55 times.
✓ Branch 4 taken 326 times.
✓ Branch 5 taken 17546 times.
✓ Branch 6 taken 326 times.
✓ Branch 7 taken 17601 times.
2/2
✓ Decision 'true' taken 326 times.
✓ Decision 'false' taken 17601 times.
 17927 if (ec && *ec >= 2) {
283
2/4
✓ Branch 1 taken 326 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 326 times.
✗ Branch 5 not taken.
 326 c -= 2;
284
2/4
✓ Branch 1 taken 326 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 326 times.
✗ Branch 5 not taken.
 326 circ.add_phase(1);
285 }
286
287
6/14
✓ Branch 1 taken 17927 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 3966 times.
✓ Branch 4 taken 13961 times.
✓ Branch 6 taken 3966 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 3966 times.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✓ Branch 15 taken 17927 times.
✗ Branch 16 not taken.
0/1
? Decision couldn't be analyzed.
 17927 if (!equiv_0(a, 2) || !equiv_0(b, 2) || !equiv_0(c, 2)) {
288
8/16
✓ Branch 3 taken 17927 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 17927 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 17927 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 17927 times.
✗ Branch 13 not taken.
✓ Branch 16 taken 17927 times.
✗ Branch 17 not taken.
✓ Branch 19 taken 17927 times.
✗ Branch 20 not taken.
✓ Branch 23 taken 53781 times.
✓ Branch 24 taken 17927 times.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
 71708 circ.add_op<unsigned>(OpType::TK1, {c, b, a}, {0});
289 }
290
291 35854 return circ;
292 }
293
294 3026 Transform decompose_ZXZ_to_TK1() {
295 3103 return Transform([](Circuit &circ) {
296 3103 bool success = false;
297 3103 VertexList bin;
298
1/2
✓ Branch 1 taken 3103 times.
✗ Branch 2 not taken.
 3103 VertexVec inputs = circ.q_inputs();
299
2/2
✓ Branch 4 taken 4500 times.
✓ Branch 5 taken 3103 times.
2/2
✓ Decision 'true' taken 4500 times.
✓ Decision 'false' taken 3103 times.
 7603 for (VertexVec::iterator i = inputs.begin(); i != inputs.end(); ++i) {
300
1/2
✓ Branch 2 taken 4500 times.
✗ Branch 3 not taken.
 4500 Edge e = circ.get_nth_out_edge(*i, 0);
301
1/2
✓ Branch 1 taken 4500 times.
✗ Branch 2 not taken.
 4500 Vertex v = circ.target(e);
302 // Angles for current TK1
303
1/2
✓ Branch 1 taken 4500 times.
✗ Branch 2 not taken.
 4500 std::array<Expr, 3> curr_angles;
304 // Index from 0 <= curr_ind <= 2 into `curr_angles` collecting TK1 angles
305 4500 unsigned curr_ind = 0;
306 // The beginning edge of a sequence of Rx and Rz gates
307 4500 std::optional<Edge> first_edge;
308 // Vertices of the Rx/Rz sequence. Empty iff first_edge == std::nullopt
309 4500 VertexSet curr_vs;
310 while (true) {
311
1/2
✓ Branch 1 taken 59923 times.
✗ Branch 2 not taken.
 59923 Op_ptr op = circ.get_Op_ptr_from_Vertex(v);
312 59923 bool repeat_loop = false;
313 59923 bool substitute_vertex = false;
314 TKET_ASSERT(curr_ind < 3);
315
3/3
✓ Branch 2 taken 20830 times.
✓ Branch 3 taken 12986 times.
✓ Branch 4 taken 26107 times.
 59923 switch (op->get_type()) {
316
1/1
✓ Decision 'true' taken 20830 times.
 20830 case OpType::Rz: {
317
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 20829 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 20829 times.
 20830 if (curr_ind == 1) {
318
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 curr_angles[curr_ind++] = 0;
319 }
320 TKET_ASSERT(op->get_params().size() == 1);
321
3/6
✓ Branch 2 taken 20830 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 20830 times.
✗ Branch 6 not taken.
✓ Branch 9 taken 20830 times.
✗ Branch 10 not taken.
 20830 curr_angles[curr_ind++] = op->get_params().at(0);
322 20830 substitute_vertex = true;
323 20830 break;
324 }
325
1/1
✓ Decision 'true' taken 12986 times.
 12986 case OpType::Rx: {
326
2/2
✓ Branch 0 taken 3967 times.
✓ Branch 1 taken 9019 times.
2/2
✓ Decision 'true' taken 3967 times.
✓ Decision 'false' taken 9019 times.
 12986 if (curr_ind != 1) {
327
1/2
✓ Branch 1 taken 3967 times.
✗ Branch 2 not taken.
 3967 curr_angles[curr_ind++] = 0;
328 }
329 TKET_ASSERT(op->get_params().size() == 1);
330
2/2
✓ Branch 0 taken 12985 times.
✓ Branch 1 taken 1 times.
2/2
✓ Decision 'true' taken 12985 times.
✓ Decision 'false' taken 1 times.
 12986 if (curr_ind < 3) {
331
3/6
✓ Branch 2 taken 12985 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 12985 times.
✗ Branch 6 not taken.
✓ Branch 9 taken 12985 times.
✗ Branch 10 not taken.
 12985 curr_angles[curr_ind++] = op->get_params().at(0);
332 12985 substitute_vertex = true;
333 } else {
334 1 repeat_loop = true;
335 }
336 12986 break;
337 }
338
1/1
✓ Decision 'true' taken 87255 times.
 26107 default: {
339
2/2
✓ Branch 0 taken 61148 times.
✓ Branch 1 taken 26107 times.
2/2
✓ Decision 'true' taken 61148 times.
✓ Decision 'false' taken 26107 times.
 87255 while (curr_ind < 3) {
340
1/2
✓ Branch 1 taken 61148 times.
✗ Branch 2 not taken.
 61148 curr_angles[curr_ind++] = 0;
341 }
342 }
343 }
344
2/2
✓ Branch 0 taken 33815 times.
✓ Branch 1 taken 26108 times.
2/2
✓ Decision 'true' taken 33815 times.
✓ Decision 'false' taken 26108 times.
 59923 if (substitute_vertex) {
345
1/2
✓ Branch 1 taken 33815 times.
✗ Branch 2 not taken.
 33815 curr_vs.insert(v);
346
2/2
✓ Branch 1 taken 17927 times.
✓ Branch 2 taken 15888 times.
2/2
✓ Decision 'true' taken 17927 times.
✓ Decision 'false' taken 15888 times.
 33815 if (!first_edge) {
347 17927 first_edge = e;
348 }
349 }
350 // Substitute sequence of RzRxRz with TK1
351 32977 auto substitute = [&]() {
352
2/2
✓ Branch 1 taken 17927 times.
✓ Branch 2 taken 15050 times.
2/2
✓ Decision 'true' taken 17927 times.
✓ Decision 'false' taken 15050 times.
 32977 if (first_edge) {
353 17927 success = true;
354 Circuit sub = tk1_angles_to_circ(
355
4/8
✓ Branch 2 taken 17927 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 17927 times.
✗ Branch 7 not taken.
✓ Branch 10 taken 17927 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 17927 times.
✗ Branch 14 not taken.
 35854 curr_angles[0], curr_angles[1], curr_angles[2]);
356
3/6
✓ Branch 3 taken 17927 times.
✗ Branch 4 not taken.
✓ Branch 7 taken 17927 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 17927 times.
✗ Branch 11 not taken.
 35854 Subcircuit hole{{*first_edge}, {e}, curr_vs};
357 // Backup
358
1/2
✓ Branch 1 taken 17927 times.
✗ Branch 2 not taken.
 17927 port_t backup_p = circ.get_target_port(e);
359 // Substitute
360
1/2
✓ Branch 1 taken 17927 times.
✗ Branch 2 not taken.
 17927 circ.substitute(sub, hole, Circuit::VertexDeletion::No);
361 // Restore
362
1/2
✓ Branch 1 taken 17927 times.
✗ Branch 2 not taken.
 17927 e = circ.get_nth_in_edge(v, backup_p);
363 // Reset all tracking variables
364
1/2
✓ Branch 5 taken 17927 times.
✗ Branch 6 not taken.
 17927 bin.insert(bin.end(), curr_vs.begin(), curr_vs.end());
365
1/2
✓ Branch 3 taken 17927 times.
✗ Branch 4 not taken.
 17927 std::fill(curr_angles.begin(), curr_angles.end(), 0);
366 17927 curr_vs.clear();
367 17927 first_edge.reset();
368 17927 }
369 32977 curr_ind = 0;
370 32977 };
371 // Depending on `substitute_vertex`, we either place the TK1 before
372 // moving the edge forward or after
373
4/4
✓ Branch 0 taken 32977 times.
✓ Branch 1 taken 26946 times.
✓ Branch 2 taken 26108 times.
✓ Branch 3 taken 6869 times.
2/2
✓ Decision 'true' taken 26108 times.
✓ Decision 'false' taken 33815 times.
 59923 if (curr_ind == 3 && !substitute_vertex) {
374
1/2
✓ Branch 1 taken 26108 times.
✗ Branch 2 not taken.
 26108 substitute();
375 }
376
3/4
✓ Branch 3 taken 59923 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 4500 times.
✓ Branch 6 taken 55423 times.
2/2
✓ Decision 'true' taken 4500 times.
✓ Decision 'false' taken 55423 times.
 59923 if (is_final_q_type(op->get_type())) {
377 TKET_ASSERT(!substitute_vertex);
378 4500 break;
379 }
380
2/2
✓ Branch 0 taken 55422 times.
✓ Branch 1 taken 1 times.
2/2
✓ Decision 'true' taken 55422 times.
✓ Decision 'false' taken 1 times.
 55423 if (!repeat_loop) {
381 // Move edge forward
382
1/2
✓ Branch 1 taken 55422 times.
✗ Branch 2 not taken.
 55422 e = circ.get_next_edge(v, e);
383
1/2
✓ Branch 1 taken 55422 times.
✗ Branch 2 not taken.
 55422 v = circ.target(e);
384 }
385
3/4
✓ Branch 0 taken 6869 times.
✓ Branch 1 taken 48554 times.
✓ Branch 2 taken 6869 times.
✗ Branch 3 not taken.
2/2
✓ Decision 'true' taken 6869 times.
✓ Decision 'false' taken 48554 times.
 55423 if (curr_ind == 3 && substitute_vertex) {
386
1/2
✓ Branch 1 taken 6869 times.
✗ Branch 2 not taken.
 6869 substitute();
387 }
388
2/2
✓ Branch 1 taken 55423 times.
✓ Branch 2 taken 4500 times.
 115346 }
389 4500 }
390
1/2
✓ Branch 1 taken 3103 times.
✗ Branch 2 not taken.
 3103 circ.remove_vertices(
391 bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
392 3103 return success;
393
1/2
✓ Branch 2 taken 3026 times.
✗ Branch 3 not taken.
 6129 });
394 }
395
396
1/2
✓ Branch 2 taken 3147 times.
✗ Branch 3 not taken.
 3147 Transform decompose_ZX() { return Transform(convert_to_zxz); }
397
398
1/2
✓ Branch 2 taken 3020 times.
✗ Branch 3 not taken.
 3020 Transform decompose_ZY() { return Transform(convert_to_zyz); }
399
400
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 1 Transform decompose_XY() { return Transform(convert_to_xyx); }
401
402 3274 Transform decompose_tk1_to_rzrx() {
403 3274 return Transform([](Circuit &circ) {
404 3274 bool success = false;
405
1/2
✓ Branch 1 taken 3274 times.
✗ Branch 2 not taken.
 3274 auto [it, end] = boost::vertices(circ.dag);
406
2/2
✓ Branch 1 taken 167611 times.
✓ Branch 2 taken 3274 times.
2/2
✓ Decision 'true' taken 167611 times.
✓ Decision 'false' taken 3274 times.
 170885 for (auto next = it; it != end; it = next) {
407 167611 ++next;
408
3/4
✓ Branch 2 taken 167611 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 37026 times.
✓ Branch 5 taken 130585 times.
2/2
✓ Decision 'true' taken 37026 times.
✓ Decision 'false' taken 130585 times.
 167611 if (circ.get_OpType_from_Vertex(*it) == OpType::TK1) {
409 37026 success = true;
410
1/2
✓ Branch 2 taken 37026 times.
✗ Branch 3 not taken.
 37026 const Op_ptr g = circ.get_Op_ptr_from_Vertex(*it);
411
1/2
✓ Branch 2 taken 37026 times.
✗ Branch 3 not taken.
 37026 const std::vector<Expr> &params = g->get_params();
412 Circuit newcirc =
413
1/2
✓ Branch 4 taken 37026 times.
✗ Branch 5 not taken.
 37026 CircPool::tk1_to_rzrx(params[0], params[1], params[2]);
414 Subcircuit sc = {
415
4/8
✓ Branch 2 taken 37026 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 37026 times.
✗ Branch 7 not taken.
✓ Branch 11 taken 37026 times.
✗ Branch 12 not taken.
✓ Branch 14 taken 37026 times.
✗ Branch 15 not taken.
 74052 {circ.get_in_edges(*it)}, {circ.get_all_out_edges(*it)}, {*it}};
416
1/2
✓ Branch 1 taken 37026 times.
✗ Branch 2 not taken.
 37026 circ.substitute(newcirc, sc, Circuit::VertexDeletion::Yes);
417 37026 }
418 }
419 3274 return success;
420
1/2
✓ Branch 2 taken 3274 times.
✗ Branch 3 not taken.
 3274 });
421 }
422
423 13 Transform decompose_CX_to_ECR() {
424 13 return Transform([](Circuit &circ) {
425 13 bool success = false;
426
1/2
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 13 auto [i, end] = boost::vertices(circ.dag);
427
2/2
✓ Branch 1 taken 423 times.
✓ Branch 2 taken 13 times.
2/2
✓ Decision 'true' taken 423 times.
✓ Decision 'false' taken 13 times.
 436 for (auto next = i; i != end; i = next) {
428 423 ++next;
429
3/4
✓ Branch 2 taken 423 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 48 times.
✓ Branch 5 taken 375 times.
2/2
✓ Decision 'true' taken 48 times.
✓ Decision 'false' taken 375 times.
 423 if (circ.get_OpType_from_Vertex(*i) == OpType::CX) {
430 48 success = true;
431
4/8
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 48 times.
✗ Branch 7 not taken.
✓ Branch 11 taken 48 times.
✗ Branch 12 not taken.
✓ Branch 14 taken 48 times.
✗ Branch 15 not taken.
 96 Subcircuit sub{circ.get_in_edges(*i), circ.get_all_out_edges(*i), {*i}};
432
2/4
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 48 times.
✗ Branch 5 not taken.
 48 circ.substitute(
433 CircPool::CX_using_ECR(), sub, Circuit::VertexDeletion::Yes);
434 48 }
435 }
436 13 return success;
437
1/2
✓ Branch 2 taken 13 times.
✗ Branch 3 not taken.
 13 });
438 }
439
440 44 Transform decompose_CX_to_HQS2() {
441 44 return Transform([](Circuit &circ) {
442 44 bool success = false;
443 44 VertexList bin;
444
7/8
✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 1225 times.
✓ Branch 6 taken 44 times.
✓ Branch 8 taken 1225 times.
✓ Branch 9 taken 44 times.
✓ Branch 11 taken 44 times.
✓ Branch 12 taken 44 times.
 1313 BGL_FORALL_VERTICES(v, circ.dag, DAG) {
445
3/4
✓ Branch 1 taken 1225 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 98 times.
✓ Branch 4 taken 1127 times.
2/2
✓ Decision 'true' taken 98 times.
✓ Decision 'false' taken 1127 times.
 1225 if (circ.get_OpType_from_Vertex(v) == OpType::CX) {
446 98 success = true;
447
1/2
✓ Branch 1 taken 98 times.
✗ Branch 2 not taken.
 98 bin.push_back(v);
448
3/6
✓ Branch 1 taken 98 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 98 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 98 times.
✗ Branch 9 not taken.
 196 Subcircuit sub = {circ.get_in_edges(v), circ.get_all_out_edges(v)};
449
2/4
✓ Branch 1 taken 98 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 98 times.
✗ Branch 5 not taken.
 98 circ.substitute(
450 CircPool::CX_using_ZZMax(), sub, Circuit::VertexDeletion::No);
451 98 }
452 }
453
1/2
✓ Branch 1 taken 44 times.
✗ Branch 2 not taken.
 44 circ.remove_vertices(
454 bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
455 44 return success;
456
1/2
✓ Branch 2 taken 44 times.
✗ Branch 3 not taken.
 88 });
457 }
458
459 /* --Rz(a)--Rx(b)--R(c)-- => --Rz(a+c)--PhasedX(b,c)-- */
460 14 Transform decompose_ZX_to_HQS1() {
461 14 return Transform([](Circuit &circ) {
462 14 bool success = false;
463 14 VertexList to_bin;
464
7/8
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 299 times.
✓ Branch 6 taken 14 times.
✓ Branch 8 taken 299 times.
✓ Branch 9 taken 14 times.
✓ Branch 11 taken 14 times.
✓ Branch 12 taken 14 times.
 327 BGL_FORALL_VERTICES(v, circ.dag, DAG) {
465
3/4
✓ Branch 1 taken 299 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 86 times.
✓ Branch 4 taken 213 times.
2/2
✓ Decision 'true' taken 86 times.
✓ Decision 'false' taken 213 times.
 299 if (circ.get_OpType_from_Vertex(v) == OpType::Rx) {
466 86 success = true;
467
1/2
✓ Branch 1 taken 86 times.
✗ Branch 2 not taken.
 86 const Op_ptr g = circ.get_Op_ptr_from_Vertex(v);
468
2/4
✓ Branch 2 taken 86 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 86 times.
✗ Branch 7 not taken.
 86 Expr theta = g->get_params()[0];
469
1/2
✓ Branch 1 taken 86 times.
✗ Branch 2 not taken.
 86 Vertex prev_vert = *circ.get_predecessors(v).begin();
470
1/2
✓ Branch 1 taken 86 times.
✗ Branch 2 not taken.
 86 Vertex next_vert = *circ.get_successors(v).begin();
471
5/6
✓ Branch 1 taken 86 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 26 times.
✓ Branch 4 taken 60 times.
✓ Branch 5 taken 9 times.
✓ Branch 6 taken 77 times.
2/2
✓ Decision 'true' taken 9 times.
✓ Decision 'false' taken 103 times.
 112 if (circ.get_OpType_from_Vertex(prev_vert) == OpType::Rz &&
472
3/4
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 9 times.
✓ Branch 4 taken 17 times.
 26 circ.get_OpType_from_Vertex(next_vert) == OpType::Rz) {
473
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 const Op_ptr prev_g = circ.get_Op_ptr_from_Vertex(prev_vert);
474
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 const Op_ptr next_g = circ.get_Op_ptr_from_Vertex(next_vert);
475
2/4
✓ Branch 2 taken 9 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 9 times.
✗ Branch 7 not taken.
 9 Expr phi = next_g->get_params()[0];
476
3/6
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 9 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 9 times.
✗ Branch 9 not taken.
 36 std::vector<Expr> params{theta, phi};
477
2/4
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 9 times.
✗ Branch 5 not taken.
 9 circ.dag[v].op = get_op_ptr(OpType::PhasedX, params);
478
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 circ.remove_vertex(
479 next_vert, Circuit::GraphRewiring::Yes,
480 Circuit::VertexDeletion::No);
481
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 to_bin.push_back(next_vert);
482
2/4
✓ Branch 2 taken 9 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 9 times.
✗ Branch 7 not taken.
 9 Expr new_param = prev_g->get_params()[0] + phi;
483
2/4
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 9 times.
✗ Branch 5 not taken.
 9 circ.dag[prev_vert].op = get_op_ptr(OpType::Rz, new_param);
484 9 } else {
485 // if no Rz, initialise a PhasedX op with theta=Rx.params[0],phi=0
486
1/2
✓ Branch 1 taken 77 times.
✗ Branch 2 not taken.
 77 Expr phi(0);
487
3/6
✓ Branch 1 taken 77 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 77 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 77 times.
✗ Branch 9 not taken.
 308 std::vector<Expr> params{theta, phi};
488
2/4
✓ Branch 1 taken 77 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 77 times.
✗ Branch 5 not taken.
 77 circ.dag[v].op = get_op_ptr(OpType::PhasedX, params);
489 77 }
490 86 }
491 }
492
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 14 circ.remove_vertices(
493 to_bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
494
2/4
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 14 times.
✗ Branch 5 not taken.
 14 remove_redundancies().apply(circ);
495 14 return success;
496
1/2
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
 28 });
497 }
498
499 // Decompose CX into MolmerSorensen as:
500 // ---C--- -V-S-|-H-
501 // | --> XX(pi/4)
502 // ---X--- -----|-Vdg-
503 11 Transform decompose_MolmerSorensen() {
504 11 return Transform([](Circuit &circ) {
505 11 bool success = false;
506 11 VertexList bin;
507
7/8
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 588 times.
✓ Branch 6 taken 11 times.
✓ Branch 8 taken 588 times.
✓ Branch 9 taken 11 times.
✓ Branch 11 taken 11 times.
✓ Branch 12 taken 11 times.
 610 BGL_FORALL_VERTICES(v, circ.dag, DAG) {
508
3/4
✓ Branch 1 taken 588 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 541 times.
✓ Branch 4 taken 47 times.
2/2
✓ Decision 'true' taken 47 times.
✓ Decision 'false' taken 542 times.
 589 if (circ.get_OpType_from_Vertex(v) != OpType::CX) continue;
509
1/2
✓ Branch 1 taken 47 times.
✗ Branch 2 not taken.
 47 EdgeVec outs = circ.get_all_out_edges(v);
510
2/2
✓ Branch 1 taken 46 times.
✓ Branch 2 taken 1 times.
2/2
✓ Decision 'true' taken 46 times.
✓ Decision 'false' taken 1 times.
 47 if (outs.size() == 2) {
511
1/2
✓ Branch 2 taken 46 times.
✗ Branch 3 not taken.
 46 Vertex next = circ.target(outs[0]);
512 // Is the next operation equivalent to an Rx, up to phase?
513
1/2
✓ Branch 1 taken 46 times.
✗ Branch 2 not taken.
 46 Op_ptr next_g = circ.get_Op_ptr_from_Vertex(next);
514 46 OpType next_type = next_g->get_type();
515
8/10
✓ Branch 1 taken 46 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 10 times.
✓ Branch 4 taken 36 times.
✓ Branch 6 taken 10 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 8 times.
✓ Branch 9 taken 2 times.
✓ Branch 10 taken 8 times.
✓ Branch 11 taken 38 times.
2/2
✓ Decision 'true' taken 16 times.
✓ Decision 'false' taken 30 times.
 46 if (is_single_qubit_type(next_type) && !is_projective_type(next_type)) {
516
2/4
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 8 times.
✗ Branch 7 not taken.
 16 std::vector<Expr> angles = as_gate_ptr(next_g)->get_tk1_angles();
517
5/10
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 8 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 8 times.
✗ Branch 11 not taken.
✓ Branch 12 taken 8 times.
✗ Branch 13 not taken.
1/2
✓ Decision 'true' taken 8 times.
✗ Decision 'false' not taken.
 8 if (equiv_0(angles[0], 2) && equiv_0(angles[2], 2)) {
518
1/2
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
 8 Expr angle = angles[1];
519
1/2
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
 8 Expr phase = angles[3];
520
2/8
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 8 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
1/2
✓ Decision 'true' taken 8 times.
✗ Decision 'false' not taken.
 8 if (!equiv_0(angles[0], 4)) phase += 1;
521
2/8
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 8 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
1/2
✓ Decision 'true' taken 8 times.
✗ Decision 'false' not taken.
 8 if (!equiv_0(angles[2], 4)) phase += 1;
522
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 Edge next_e = circ.get_nth_out_edge(next, 0);
523
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 Vertex last = circ.target(next_e);
524
3/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 7 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 8 times.
 9 if (circ.get_OpType_from_Vertex(last) == OpType::CX &&
525
5/8
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 1 times.
✓ Branch 10 taken 7 times.
 9 circ.get_nth_in_edge(last, 1) == outs[1]) {
526 // Recognise exp(-i XX * angle * pi/2)
527
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 const Op_ptr op_ptr = get_op_ptr(OpType::XXPhase, angle);
528
2/4
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
 1 circ.dag[v] = {op_ptr};
529
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 bin.push_back(next);
530
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 circ.remove_vertex(
531 next, Circuit::GraphRewiring::Yes,
532 Circuit::VertexDeletion::No);
533
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 bin.push_back(last);
534
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 circ.remove_vertex(
535 last, Circuit::GraphRewiring::Yes,
536 Circuit::VertexDeletion::No);
537
2/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
 1 circ.add_phase(phase);
538 1 success = true;
539 1 continue;
540 1 }
541
4/4
✓ Branch 1 taken 7 times.
✓ Branch 2 taken 1 times.
✓ Branch 4 taken 7 times.
✓ Branch 5 taken 1 times.
 9 }
542
2/2
✓ Branch 1 taken 7 times.
✓ Branch 2 taken 1 times.
 8 }
543 // Replace remaining CX gates
544
3/6
✓ Branch 1 taken 45 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 45 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 45 times.
✗ Branch 9 not taken.
 90 Subcircuit sub = {{circ.get_in_edges(v)}, {outs}, {v}};
545
1/2
✓ Branch 1 taken 45 times.
✗ Branch 2 not taken.
 45 bin.push_back(v);
546
2/4
✓ Branch 1 taken 45 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 45 times.
✗ Branch 5 not taken.
 45 circ.substitute(
547 CircPool::CX_using_XXPhase_1(), sub, Circuit::VertexDeletion::No);
548 45 success = true;
549
2/2
✓ Branch 2 taken 45 times.
✓ Branch 3 taken 1 times.
 46 }
550
2/2
✓ Branch 1 taken 46 times.
✓ Branch 2 taken 1 times.
 47 }
551
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 circ.remove_vertices(
552 bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
553 11 return success;
554
1/2
✓ Branch 2 taken 11 times.
✗ Branch 3 not taken.
 22 });
555 }
556
557 88 static double get_ZZPhase_fidelity(
558 const std::array<double, 3> &k, unsigned nb_cx) {
559
4/4
✓ Branch 0 taken 36 times.
✓ Branch 1 taken 36 times.
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 8 times.
 88 switch (nb_cx) {
560
1/1
✓ Decision 'true' taken 36 times.
 36 case 0:
561 36 return trace_fidelity(k[0], k[1], k[2]);
562
1/1
✓ Decision 'true' taken 36 times.
 36 case 1:
563 36 return trace_fidelity(0, k[1], k[2]);
564
1/1
✓ Decision 'true' taken 8 times.
 8 case 2:
565 8 return trace_fidelity(0, 0, k[2]);
566
1/1
✓ Decision 'true' taken 8 times.
 8 default:
567 8 return 1.;
568 }
569 }
570
571 /** Given TK2 angles, computes the fidelity that can be achieved using
572 * nb_cx CX gates.
573 *
574 * @param k The TK2 angles.
575 * @param nb_cx The number of CX gates to be used for decomposition.
576 * @return The fidelity.
577 */
578 1048 static double get_CX_fidelity(const std::array<double, 3> &k, unsigned nb_cx) {
579 TKET_ASSERT(nb_cx < 4);
580 1048 auto [a, b, c] = k;
581
582 // gate fidelity achievable with 0,...,3 cnots
583 // this is fully determined by the information content k and is optimal
584 // see PhysRevA 71.062331 (2005) for more details on this
585
4/4
✓ Branch 0 taken 262 times.
✓ Branch 1 taken 262 times.
✓ Branch 2 taken 262 times.
✓ Branch 3 taken 262 times.
 1048 switch (nb_cx) {
586
1/1
✓ Decision 'true' taken 262 times.
 262 case 0:
587
1/2
✓ Branch 1 taken 262 times.
✗ Branch 2 not taken.
 262 return trace_fidelity(a, b, c);
588
1/1
✓ Decision 'true' taken 262 times.
 262 case 1:
589
1/2
✓ Branch 1 taken 262 times.
✗ Branch 2 not taken.
 262 return trace_fidelity(0.5 - a, b, c);
590
1/1
✓ Decision 'true' taken 262 times.
 262 case 2:
591
1/2
✓ Branch 1 taken 262 times.
✗ Branch 2 not taken.
 262 return trace_fidelity(0, 0, c);
592
1/1
✓ Decision 'true' taken 262 times.
 262 default:
593 262 return 1.;
594 }
595 }
596
597 // Try to decompose a TK2 gate using different gate sets, find the one with
598 // the highest fidelity.
599 // If no fidelities are provided, (best_optype, n_gates) is left unchanged.
600 270 static double best_noise_aware_decomposition(
601 const std::array<double, 3> &angles, const TwoQbFidelities &fid,
602 OpType &best_optype, unsigned &n_gates) {
603 270 double max_fid = 0.;
604
605 // Try decomposition using CX or equivalent gates.
606 270 double cx_fid = std::max(
607
3/4
✓ Branch 0 taken 180 times.
✓ Branch 1 taken 90 times.
✓ Branch 3 taken 180 times.
✗ Branch 4 not taken.
 270 fid.CX_fidelity ? fid.CX_fidelity.value() : 0.,
608
2/2
✓ Branch 1 taken 53 times.
✓ Branch 2 taken 217 times.
 270 fid.ZZMax_fidelity ? fid.ZZMax_fidelity.value() : 0.);
609 270 bool zzmax_is_better = false;
610
2/2
✓ Branch 0 taken 39 times.
✓ Branch 1 taken 231 times.
2/2
✓ Decision 'true' taken 39 times.
✓ Decision 'false' taken 231 times.
 270 if (cx_fid < EPS) {
611
2/2
✓ Branch 1 taken 31 times.
✓ Branch 2 taken 8 times.
2/2
✓ Decision 'true' taken 31 times.
✓ Decision 'false' taken 8 times.
 39 if (!fid.ZZPhase_fidelity) {
612 // No fidelity is defined, so default to CX
613 31 cx_fid = 1.;
614 }
615 } else {
616 231 zzmax_is_better = fid.CX_fidelity < fid.ZZMax_fidelity;
617 }
618
2/2
✓ Branch 0 taken 262 times.
✓ Branch 1 taken 8 times.
0/1
? Decision couldn't be analyzed.
 270 if (cx_fid > EPS) {
619
2/2
✓ Branch 0 taken 1048 times.
✓ Branch 1 taken 262 times.
2/2
✓ Decision 'true' taken 1048 times.
✓ Decision 'false' taken 262 times.
 1310 for (unsigned n_cx = 0; n_cx <= 3; ++n_cx) {
620 1048 double ncx_fid = get_CX_fidelity(angles, n_cx) * pow(cx_fid, n_cx);
621
2/2
✓ Branch 0 taken 735 times.
✓ Branch 1 taken 313 times.
2/2
✓ Decision 'true' taken 735 times.
✓ Decision 'false' taken 313 times.
 1048 if (ncx_fid > max_fid) {
622 735 max_fid = ncx_fid;
623
2/2
✓ Branch 0 taken 158 times.
✓ Branch 1 taken 577 times.
 735 best_optype = zzmax_is_better ? OpType::ZZMax : OpType::CX;
624 735 n_gates = n_cx;
625 }
626 }
627 }
628
629 // Try decomposition using ZZPhase(α)
630
2/2
✓ Branch 1 taken 36 times.
✓ Branch 2 taken 234 times.
2/2
✓ Decision 'true' taken 36 times.
✓ Decision 'false' taken 234 times.
 270 if (fid.ZZPhase_fidelity) {
631 36 double zz_fid = 1.;
632 // If ZZMax is available, ZZPhase is only interesting when used once.
633 // (two ZZPhase can always be written using two ZZmax)
634
2/2
✓ Branch 1 taken 28 times.
✓ Branch 2 taken 8 times.
 36 unsigned max_nzz = fid.ZZMax_fidelity ? 1 : 3;
635
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 36 times.
2/2
✓ Decision 'true' taken 88 times.
✓ Decision 'false' taken 36 times.
 124 for (unsigned n_zz = 0; n_zz <= max_nzz; ++n_zz) {
636
2/2
✓ Branch 0 taken 52 times.
✓ Branch 1 taken 36 times.
2/2
✓ Decision 'true' taken 52 times.
✓ Decision 'false' taken 36 times.
 88 if (n_zz > 0) {
637 52 double gate_fid = (*fid.ZZPhase_fidelity)(angles[n_zz - 1]);
638
2/4
✓ Branch 0 taken 52 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 52 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 52 times.
 52 if (gate_fid < 0 || gate_fid > 1) {
639 ✗ throw std::domain_error(
640 ✗ "ZZPhase_fidelity returned a value outside of [0, 1].");
641 }
642 52 zz_fid *= gate_fid;
643 }
644 88 double nzz_fid = get_ZZPhase_fidelity(angles, n_zz) * zz_fid;
645 // Use ZZPhase if fidelity is greater or it is equal but uses fewer gates
646
2/2
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 28 times.
2/2
✓ Decision 'true' taken 29 times.
✓ Decision 'false' taken 59 times.
 88 if (nzz_fid - max_fid > EPS ||
647
4/4
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 48 times.
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 11 times.
 60 (nzz_fid - max_fid > -EPS && n_zz < n_gates)) {
648 29 max_fid = nzz_fid;
649 29 best_optype = OpType::ZZPhase;
650 29 n_gates = n_zz;
651 }
652 }
653 }
654
655 270 return max_fid;
656 }
657
658 // Try to decompose a TK2 gate exactly using different gate sets.
659 // The fidelities are used as an indication of which gate set is usable, but
660 // the actual values of the fidelities will be ignored.
661 //
662 // Relies on default values of best_optype and n_gates if no optimisation can be
663 // performed.
664 40 static void best_exact_decomposition(
665 const std::array<Expr, 3> &angles, const TwoQbFidelities &fid,
666 OpType &best_optype, unsigned &n_gates) {
667 // Prefer CX/ZZMax when possible.
668
6/6
✓ Branch 1 taken 32 times.
✓ Branch 2 taken 8 times.
✓ Branch 4 taken 16 times.
✓ Branch 5 taken 16 times.
✓ Branch 6 taken 24 times.
✓ Branch 7 taken 16 times.
2/2
✓ Decision 'true' taken 24 times.
✓ Decision 'false' taken 16 times.
 40 if (fid.CX_fidelity || fid.ZZMax_fidelity) {
669 bool zzmax_is_better =
670
3/4
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 16 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 8 times.
 24 !fid.CX_fidelity || fid.CX_fidelity < fid.ZZMax_fidelity;
671
2/2
✓ Branch 0 taken 16 times.
✓ Branch 1 taken 8 times.
 24 best_optype = zzmax_is_better ? OpType::ZZMax : OpType::CX;
672
2/2
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 8 times.
2/2
✓ Decision 'true' taken 8 times.
✓ Decision 'false' taken 8 times.
 16 } else if (fid.ZZPhase_fidelity) {
673 // Only ZZPhase has fidelity, so use ZZPhase.
674 8 best_optype = OpType::ZZPhase;
675 }
676
677
4/4
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 16 times.
✓ Branch 2 taken 16 times.
✓ Branch 3 taken 8 times.
2/2
✓ Decision 'true' taken 32 times.
✓ Decision 'false' taken 8 times.
 40 if (best_optype == OpType::CX || best_optype == OpType::ZZMax) {
678 // Reduce n_gates if possible.
679
2/2
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 24 times.
2/2
✓ Decision 'true' taken 8 times.
✓ Decision 'false' taken 24 times.
 32 if (equiv_0(angles[2], 4)) {
680 8 n_gates = 2;
681 }
682
1/2
✓ Branch 0 taken 8 times.
✗ Branch 1 not taken.
1/2
✓ Decision 'true' taken 8 times.
✗ Decision 'false' not taken.
 8 } else if (best_optype == OpType::ZZPhase) {
683 // Reduce n_gates if possible.
684
2/2
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 6 times.
2/2
✓ Decision 'true' taken 2 times.
✓ Decision 'false' taken 6 times.
 8 if (equiv_0(angles[2], 4)) {
685 2 n_gates = 2;
686
2/2
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 1 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 1 times.
 2 if (equiv_0(angles[1], 4)) {
687 1 n_gates = 1;
688 }
689 }
690 }
691
692 // Finally, handle the only case where ZZPhase is preferable over ZZMax.
693
8/8
✓ Branch 1 taken 16 times.
✓ Branch 2 taken 24 times.
✓ Branch 5 taken 4 times.
✓ Branch 6 taken 12 times.
✓ Branch 9 taken 2 times.
✓ Branch 10 taken 2 times.
✓ Branch 11 taken 1 times.
✓ Branch 12 taken 39 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 41 times.
 42 if (fid.ZZPhase_fidelity && equiv_0(angles[2], 4) && equiv_0(angles[1], 4) &&
694
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
 2 n_gates > 1) {
695 1 n_gates = 1;
696 1 best_optype = OpType::ZZPhase;
697 }
698 40 }
699
700 /**
701 * @brief TK2 expressed (approximately) as CX/ZZMax or ZZPhase.
702 *
703 * This is the core logic of how to decompose a TK2 gate into other two-qubit
704 * gates, taking hardware fidelities into account for optimal approximate
705 * decompositions.
706 *
707 * Decomposes to whatever gate type has non-nullopt fidelity. If there are
708 * multiple options, choose the best one. Defaults to CX if no fidelities are
709 * provided.
710 *
711 * Symbolic parameters are supported. In that case, decompositions are exact.
712 *
713 * @param angles The TK2 parameters
714 * @param fid The two-qubit gate fidelities
715 * @param allow_swaps Whether implicit swaps are allowed.
716 * @return Circuit TK2-equivalent circuit
717 */
718 186 static Circuit TK2_replacement(
719 std::array<Expr, 3> angles, const TwoQbFidelities &fid, bool allow_swaps) {
720
3/4
✓ Branch 1 taken 186 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 4 times.
✓ Branch 4 taken 182 times.
2/2
✓ Decision 'true' taken 4 times.
✓ Decision 'false' taken 182 times.
 186 if (!in_weyl_chamber(angles)) {
721
1/2
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
 4 throw std::domain_error("TK2 params are not normalised to Weyl chamber.");
722 }
723 182 OpType best_optype = OpType::CX; // default to using CX
724 182 unsigned n_gates = 3; // default to 3x CX
725 182 bool implicit_swap = false; // default to no implicit swap
726
727 // Only used when allow_swaps == true.
728
2/4
✓ Branch 1 taken 182 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 182 times.
✗ Branch 5 not taken.
 182 Circuit pre, post;
729
1/2
✓ Branch 1 taken 182 times.
✗ Branch 2 not taken.
 182 std::array<Expr, 3> angles_swapped;
730
2/2
✓ Branch 0 taken 128 times.
✓ Branch 1 taken 54 times.
2/2
✓ Decision 'true' taken 128 times.
✓ Decision 'false' taken 54 times.
 182 if (allow_swaps) {
731 // Swapped circuit
732
1/2
✓ Branch 2 taken 128 times.
✗ Branch 3 not taken.
 128 Circuit swap_circ(2);
733
1/2
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
 128 angles_swapped = angles;
734
2/2
✓ Branch 0 taken 384 times.
✓ Branch 1 taken 128 times.
2/2
✓ Decision 'true' taken 384 times.
✓ Decision 'false' taken 128 times.
 512 for (unsigned i = 0; i < 3; ++i) {
735
2/4
✓ Branch 1 taken 384 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 384 times.
✗ Branch 6 not taken.
 384 angles_swapped[i] += 0.5;
736 }
737
4/8
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 128 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 128 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 128 times.
✗ Branch 11 not taken.
 512 std::tie(pre, angles_swapped, post) = normalise_TK2_angles(
738
1/2
✓ Branch 4 taken 128 times.
✗ Branch 5 not taken.
 512 angles_swapped[0], angles_swapped[1], angles_swapped[2]);
739
2/4
✓ Branch 1 taken 128 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 128 times.
✗ Branch 5 not taken.
 128 pre.add_phase(0.25);
740 128 }
741
742 // Try to evaluate exprs to doubles.
743 std::array<double, 3> angles_eval;
744 std::array<double, 3> angles_eval_swapped;
745 182 unsigned last_angle = 0;
746
2/2
✓ Branch 0 taken 506 times.
✓ Branch 1 taken 162 times.
2/2
✓ Decision 'true' taken 506 times.
✓ Decision 'false' taken 162 times.
 668 for (; last_angle < 3; ++last_angle) {
747
1/2
✓ Branch 2 taken 506 times.
✗ Branch 3 not taken.
 506 std::optional<double> eval = eval_expr_mod(angles[last_angle]);
748
2/2
✓ Branch 1 taken 486 times.
✓ Branch 2 taken 20 times.
2/2
✓ Decision 'true' taken 486 times.
✓ Decision 'false' taken 20 times.
 506 if (eval) {
749 486 angles_eval[last_angle] = *eval;
750 } else {
751 20 break;
752 }
753
2/2
✓ Branch 0 taken 324 times.
✓ Branch 1 taken 162 times.
2/2
✓ Decision 'true' taken 324 times.
✓ Decision 'false' taken 162 times.
 486 if (allow_swaps) {
754
1/2
✓ Branch 2 taken 324 times.
✗ Branch 3 not taken.
 324 eval = eval_expr_mod(angles_swapped[last_angle]);
755 TKET_ASSERT(eval);
756 324 angles_eval_swapped[last_angle] = *eval;
757 }
758 }
759
760
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 162 times.
2/2
✓ Decision 'true' taken 20 times.
✓ Decision 'false' taken 162 times.
 182 if (last_angle <= 2) {
761 // Not all angles could be resolved numerically.
762 // For symbolic angles, we can only provide an exact decomposition.
763
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 best_exact_decomposition(angles, fid, best_optype, n_gates);
764
1/2
✓ Branch 0 taken 20 times.
✗ Branch 1 not taken.
1/2
✓ Decision 'true' taken 20 times.
✗ Decision 'false' not taken.
 20 if (allow_swaps) {
765 20 OpType best_optype_swapped = OpType::CX; // default to using CX
766 20 unsigned n_gates_swapped = 3; // default to 3x CX
767
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 best_exact_decomposition(
768 angles_swapped, fid, best_optype_swapped, n_gates_swapped);
769
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 20 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 20 times.
 20 if (n_gates_swapped < n_gates) {
770 ✗ n_gates = n_gates_swapped;
771 ✗ best_optype = best_optype_swapped;
772 ✗ angles = angles_swapped;
773 ✗ implicit_swap = true;
774 }
775 }
776 } else {
777 // For non-symbolic angles, we can find the optimal number of gates
778 // using the gate fidelities provided.
779 double max_fid =
780
1/2
✓ Branch 1 taken 162 times.
✗ Branch 2 not taken.
 162 best_noise_aware_decomposition(angles_eval, fid, best_optype, n_gates);
781
2/2
✓ Branch 0 taken 108 times.
✓ Branch 1 taken 54 times.
2/2
✓ Decision 'true' taken 108 times.
✓ Decision 'false' taken 54 times.
 162 if (allow_swaps) {
782 108 OpType best_optype_swapped = OpType::CX; // default to using CX
783 108 unsigned n_gates_swapped = 3; // default to 3x CX
784
1/2
✓ Branch 1 taken 108 times.
✗ Branch 2 not taken.
 108 double max_fid_swapped = best_noise_aware_decomposition(
785 angles_eval_swapped, fid, best_optype_swapped, n_gates_swapped);
786
2/2
✓ Branch 0 taken 106 times.
✓ Branch 1 taken 2 times.
2/2
✓ Decision 'true' taken 28 times.
✓ Decision 'false' taken 80 times.
 108 if (max_fid_swapped > max_fid ||
787
3/4
✓ Branch 0 taken 106 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 26 times.
✓ Branch 3 taken 80 times.
 106 ((max_fid_swapped - max_fid) < EPS && n_gates_swapped < n_gates)) {
788 28 n_gates = n_gates_swapped;
789 28 best_optype = best_optype_swapped;
790
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 angles = angles_swapped;
791 28 implicit_swap = true;
792 }
793 }
794 }
795
796 // Build circuit for substitution.
797
1/2
✓ Branch 2 taken 182 times.
✗ Branch 3 not taken.
 182 Circuit sub(2);
798
2/3
✓ Branch 0 taken 169 times.
✓ Branch 1 taken 13 times.
✗ Branch 2 not taken.
 182 switch (best_optype) {
799 169 case OpType::ZZMax:
800 case OpType::CX: {
801
4/5
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 51 times.
✓ Branch 2 taken 73 times.
✓ Branch 3 taken 24 times.
✗ Branch 4 not taken.
 169 switch (n_gates) {
802
1/1
✓ Decision 'true' taken 21 times.
 21 case 0:
803 21 break;
804
1/1
✓ Decision 'true' taken 51 times.
 51 case 1: {
805
2/4
✓ Branch 1 taken 51 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 51 times.
✗ Branch 5 not taken.
 51 sub.append(CircPool::approx_TK2_using_1xCX());
806 51 break;
807 }
808
1/1
✓ Decision 'true' taken 73 times.
 73 case 2: {
809
2/4
✓ Branch 3 taken 73 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 73 times.
✗ Branch 7 not taken.
 73 sub.append(CircPool::approx_TK2_using_2xCX(angles[0], angles[1]));
810 73 break;
811 }
812
1/1
✓ Decision 'true' taken 24 times.
 24 case 3: {
813
2/4
✓ Branch 4 taken 24 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 24 times.
✗ Branch 8 not taken.
 24 sub.append(CircPool::TK2_using_3xCX(angles[0], angles[1], angles[2]));
814 24 break;
815 }
816
0/1
✗ Decision 'true' not taken.
 ✗ default:
817 TKET_ASSERT(!"Number of CX invalid in decompose_TK2");
818 }
819
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 137 times.
2/2
✓ Decision 'true' taken 32 times.
✓ Decision 'false' taken 137 times.
 169 if (best_optype == OpType::ZZMax) {
820
2/4
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 32 times.
✗ Branch 5 not taken.
 32 decompose_CX_to_HQS2().apply(sub);
821 }
822 169 break;
823 }
824
1/1
✓ Decision 'true' taken 13 times.
 13 case OpType::ZZPhase: {
825
4/5
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 7 times.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 3 times.
✗ Branch 4 not taken.
 13 switch (n_gates) {
826
1/1
✓ Decision 'true' taken 1 times.
 1 case 0:
827 1 break;
828
1/1
✓ Decision 'true' taken 7 times.
 7 case 1: {
829
2/4
✓ Branch 2 taken 7 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 7 times.
✗ Branch 6 not taken.
 7 sub.append(CircPool::approx_TK2_using_1xZZPhase(angles[0]));
830 7 break;
831 }
832
1/1
✓ Decision 'true' taken 2 times.
 2 case 2: {
833
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 sub.append(
834
1/2
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
 4 CircPool::approx_TK2_using_2xZZPhase(angles[0], angles[1]));
835 2 break;
836 }
837
1/1
✓ Decision 'true' taken 3 times.
 3 case 3: {
838
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 sub.append(
839
1/2
✓ Branch 4 taken 3 times.
✗ Branch 5 not taken.
 6 CircPool::TK2_using_ZZPhase(angles[0], angles[1], angles[2]));
840 3 break;
841 }
842
0/1
✗ Decision 'true' not taken.
 ✗ default:
843 TKET_ASSERT(!"Number of ZZPhase invalid in decompose_TK2");
844 }
845 13 break;
846 }
847
0/1
✗ Decision 'true' not taken.
 ✗ default:
848 ✗ throw BadOpType(
849 ✗ "Unrecognised target OpType in decompose_TK2", best_optype);
850 }
851
852
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 154 times.
2/2
✓ Decision 'true' taken 28 times.
✓ Decision 'false' taken 154 times.
 182 if (implicit_swap) {
853
1/2
✓ Branch 2 taken 28 times.
✗ Branch 3 not taken.
 28 Circuit swap(2);
854
2/4
✓ Branch 3 taken 28 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 28 times.
✗ Branch 7 not taken.
 28 swap.add_op<unsigned>(OpType::SWAP, {0, 1});
855
4/8
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 28 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 28 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 28 times.
✗ Branch 11 not taken.
 28 sub = pre >> sub >> post >> swap;
856
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 sub.replace_SWAPs();
857 28 }
858
859 364 return sub;
860 182 }
861
862 122 Transform decompose_TK2(bool allow_swaps) {
863
1/2
✓ Branch 1 taken 122 times.
✗ Branch 2 not taken.
 122 return decompose_TK2({}, allow_swaps);
864 }
865
866 392 Transform decompose_TK2(const TwoQbFidelities &fid, bool allow_swaps) {
867
2/2
✓ Branch 1 taken 37 times.
✓ Branch 2 taken 355 times.
2/2
✓ Decision 'true' taken 37 times.
✓ Decision 'false' taken 355 times.
 392 if (fid.ZZMax_fidelity) {
868
3/6
✓ Branch 1 taken 37 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 37 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 37 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 37 times.
 37 if (*fid.ZZMax_fidelity < 0 || *fid.ZZMax_fidelity > 1) {
869 ✗ throw std::domain_error("ZZMax fidelity must be between 0 and 1.");
870 }
871 }
872
2/2
✓ Branch 1 taken 217 times.
✓ Branch 2 taken 175 times.
2/2
✓ Decision 'true' taken 217 times.
✓ Decision 'false' taken 175 times.
 392 if (fid.CX_fidelity) {
873
3/6
✓ Branch 1 taken 217 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 217 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 217 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 217 times.
 217 if (*fid.CX_fidelity < 0 || *fid.CX_fidelity > 1) {
874 ✗ throw std::domain_error("CX fidelity must be between 0 and 1.");
875 }
876 }
877
6/6
✓ Branch 1 taken 37 times.
✓ Branch 2 taken 355 times.
✓ Branch 4 taken 18 times.
✓ Branch 5 taken 19 times.
✓ Branch 6 taken 18 times.
✓ Branch 7 taken 374 times.
2/2
✓ Decision 'true' taken 18 times.
✓ Decision 'false' taken 374 times.
 392 if (fid.ZZMax_fidelity && fid.ZZPhase_fidelity) {
878
1/2
✗ Branch 3 not taken.
✓ Branch 4 taken 18 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 18 times.
 18 if (*fid.ZZMax_fidelity < (*fid.ZZPhase_fidelity)(.5)) {
879 ✗ throw std::domain_error(
880 "The ZZMax fidelity cannot be smaller than the ZZPhase(0.5) "
881 ✗ "fidelity");
882 }
883 }
884 578 return Transform([fid, allow_swaps](Circuit &circ) {
885 392 bool success = false;
886
887 392 VertexList bin;
888
7/8
✓ Branch 1 taken 392 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 12106 times.
✓ Branch 6 taken 388 times.
✓ Branch 8 taken 12106 times.
✓ Branch 9 taken 388 times.
✓ Branch 11 taken 392 times.
✓ Branch 12 taken 388 times.
 12882 BGL_FORALL_VERTICES(v, circ.dag, DAG) {
889
3/4
✓ Branch 1 taken 12106 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 11920 times.
✓ Branch 4 taken 186 times.
2/2
✓ Decision 'true' taken 186 times.
✓ Decision 'false' taken 11920 times.
 12106 if (circ.get_OpType_from_Vertex(v) != OpType::TK2) continue;
890
891 186 success = true;
892
2/4
✓ Branch 1 taken 186 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 186 times.
✗ Branch 6 not taken.
 186 auto params = circ.get_Op_ptr_from_Vertex(v)->get_params();
893 TKET_ASSERT(params.size() == 3);
894
3/6
✓ Branch 2 taken 186 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 186 times.
✗ Branch 7 not taken.
✓ Branch 10 taken 186 times.
✗ Branch 11 not taken.
 186 std::array<Expr, 3> angles{params[0], params[1], params[2]};
895
896
3/4
✓ Branch 1 taken 186 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 182 times.
✓ Branch 5 taken 4 times.
 190 Circuit sub = TK2_replacement(angles, fid, allow_swaps);
897
1/2
✓ Branch 1 taken 182 times.
✗ Branch 2 not taken.
 182 bin.push_back(v);
898
1/2
✓ Branch 1 taken 182 times.
✗ Branch 2 not taken.
 182 circ.substitute(sub, v, Circuit::VertexDeletion::No);
899 190 }
900
1/2
✓ Branch 1 taken 388 times.
✗ Branch 2 not taken.
 388 circ.remove_vertices(
901 bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
902
903 388 return success;
904
2/4
✓ Branch 2 taken 392 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 392 times.
✗ Branch 6 not taken.
 784 });
905 }
906
907 11 Transform decompose_ZZPhase() {
908 11 return Transform([](Circuit &circ) {
909
2/4
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 11 times.
✗ Branch 5 not taken.
 11 bool success = decompose_PhaseGadgets().apply(circ);
910 11 VertexList bin;
911
7/8
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 138 times.
✓ Branch 6 taken 11 times.
✓ Branch 8 taken 138 times.
✓ Branch 9 taken 11 times.
✓ Branch 11 taken 11 times.
✓ Branch 12 taken 11 times.
 160 BGL_FORALL_VERTICES(v, circ.dag, DAG) {
912
5/6
✓ Branch 1 taken 138 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 3 times.
✓ Branch 4 taken 3 times.
✓ Branch 5 taken 3 times.
✓ Branch 6 taken 129 times.
 138 switch (circ.get_OpType_from_Vertex(v)) {
913
1/1
✓ Decision 'true' taken 3 times.
 3 case OpType::PhaseGadget: {
914 3 success = true;
915
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 const Op_ptr g = circ.get_Op_ptr_from_Vertex(v);
916 TKET_ASSERT(g->get_params().size() == 1);
917
4/8
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 3 times.
✗ Branch 7 not taken.
✓ Branch 10 taken 3 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 3 times.
✗ Branch 14 not taken.
 3 circ.dag[v] = {get_op_ptr(OpType::ZZPhase, g->get_params()[0])};
918 3 break;
919 3 }
920
1/1
✓ Decision 'true' taken 3 times.
 3 case OpType::XXPhase: {
921 3 success = true;
922
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 const Op_ptr g = circ.get_Op_ptr_from_Vertex(v);
923 TKET_ASSERT(g->get_params().size() == 1);
924
2/4
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 3 times.
✗ Branch 7 not taken.
 3 Circuit sub = CircPool::XXPhase_using_ZZPhase(g->get_params()[0]);
925
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 circ.substitute(sub, v, Circuit::VertexDeletion::No);
926
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 bin.push_back(v);
927 3 break;
928 3 }
929
1/1
✓ Decision 'true' taken 3 times.
 3 case OpType::YYPhase: {
930 3 success = true;
931
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 const Op_ptr g = circ.get_Op_ptr_from_Vertex(v);
932 TKET_ASSERT(g->get_params().size() == 1);
933
2/4
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 3 times.
✗ Branch 7 not taken.
 3 Circuit sub = CircPool::YYPhase_using_ZZPhase(g->get_params()[0]);
934
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 circ.substitute(sub, v, Circuit::VertexDeletion::No);
935
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 bin.push_back(v);
936 3 break;
937 3 }
938
1/1
✓ Decision 'true' taken 129 times.
 129 default:
939 129 break;
940 }
941 }
942
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 circ.remove_vertices(
943 bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
944 11 return success;
945
1/2
✓ Branch 2 taken 11 times.
✗ Branch 3 not taken.
 22 });
946 }
947
948 /**
949 * Specification of a sequence of Clifford gates and a phase
950 *
951 * The order of the gates is (Z)(X)(S)(V)(S). Each int is 1 or 0 representing
952 * the presence or absence of the corresponding gate.
953 */
954 typedef struct {
955 int Z0;
956 int X1;
957 int S2;
958 int V3;
959 int S4;
960 double p;
961 } std_cliff_spec_t;
962
963 /**
964 * The (i,j,k) entry in this table represents TK1(i/2, j/2, k/2).
965 *
966 * Where there is more than one decomposition the number of gates is minimized.
967 */
968 static const std_cliff_spec_t tk1_table[4][4][4] = {
969 {
970 {
971 {0, 0, 0, 0, 0, 0.0},
972 {0, 0, 0, 0, 1, -0.25},
973 {1, 0, 0, 0, 0, -0.5},
974 {1, 0, 0, 0, 1, -0.75},
975 },
976 {
977 {0, 0, 0, 1, 0, 0.0},
978 {0, 0, 1, 1, 0, -0.25},
979 {1, 0, 0, 1, 0, -0.5},
980 {1, 0, 1, 1, 0, -0.75},
981 },
982 {
983 {0, 1, 0, 0, 0, -0.5},
984 {1, 1, 0, 0, 1, 0.75},
985 {1, 1, 0, 0, 0, 1.0},
986 {0, 1, 0, 0, 1, 0.25},
987 },
988 {
989 {0, 1, 0, 1, 0, -0.5},
990 {1, 1, 1, 1, 0, 0.75},
991 {1, 1, 0, 1, 0, 1.0},
992 {0, 1, 1, 1, 0, 0.25},
993 },
994 },
995 {
996 {
997 {0, 0, 0, 0, 1, -0.25},
998 {1, 0, 0, 0, 0, -0.5},
999 {1, 0, 0, 0, 1, -0.75},
1000 {0, 0, 0, 0, 0, -1.0},
1001 },
1002 {
1003 {0, 0, 0, 1, 1, -0.25},
1004 {0, 0, 1, 1, 1, -0.5},
1005 {1, 0, 0, 1, 1, -0.75},
1006 {1, 0, 1, 1, 1, -1.0},
1007 },
1008 {
1009 {0, 1, 0, 0, 1, -0.75},
1010 {0, 1, 0, 0, 0, -0.5},
1011 {1, 1, 0, 0, 1, 0.75},
1012 {1, 1, 0, 0, 0, 1.0},
1013 },
1014 {
1015 {0, 1, 0, 1, 1, -0.75},
1016 {1, 1, 1, 1, 1, 0.5},
1017 {1, 1, 0, 1, 1, 0.75},
1018 {0, 1, 1, 1, 1, 0.0},
1019 },
1020 },
1021 {
1022 {
1023 {1, 0, 0, 0, 0, -0.5},
1024 {1, 0, 0, 0, 1, -0.75},
1025 {0, 0, 0, 0, 0, -1.0},
1026 {0, 0, 0, 0, 1, 0.75},
1027 },
1028 {
1029 {1, 1, 0, 1, 0, 0.0},
1030 {0, 1, 1, 1, 0, -0.75},
1031 {0, 1, 0, 1, 0, -0.5},
1032 {1, 1, 1, 1, 0, 0.75},
1033 },
1034 {
1035 {1, 1, 0, 0, 0, 0.0},
1036 {0, 1, 0, 0, 1, -0.75},
1037 {0, 1, 0, 0, 0, -0.5},
1038 {1, 1, 0, 0, 1, 0.75},
1039 },
1040 {
1041 {1, 0, 0, 1, 0, 0.5},
1042 {1, 0, 1, 1, 0, 0.25},
1043 {0, 0, 0, 1, 0, 0.0},
1044 {0, 0, 1, 1, 0, -0.25},
1045 },
1046 },
1047 {
1048 {
1049 {1, 0, 0, 0, 1, -0.75},
1050 {0, 0, 0, 0, 0, -1.0},
1051 {0, 0, 0, 0, 1, 0.75},
1052 {1, 0, 0, 0, 0, 0.5},
1053 },
1054 {
1055 {1, 1, 0, 1, 1, -0.25},
1056 {0, 1, 1, 1, 1, -1.0},
1057 {0, 1, 0, 1, 1, -0.75},
1058 {1, 1, 1, 1, 1, 0.5},
1059 },
1060 {
1061 {1, 1, 0, 0, 1, -0.25},
1062 {1, 1, 0, 0, 0, 0.0},
1063 {0, 1, 0, 0, 1, -0.75},
1064 {0, 1, 0, 0, 0, -0.5},
1065 },
1066 {
1067 {1, 0, 0, 1, 1, 0.25},
1068 {1, 0, 1, 1, 1, 0.0},
1069 {0, 0, 0, 1, 1, -0.25},
1070 {0, 0, 1, 1, 1, -0.5},
1071 },
1072 },
1073 };
1074
1075 /**
1076 * Clifford circuit equivalent to TK1(i/2, j/2, k/2)
1077 *
1078 * @pre 0 <= i, j, k < 8
1079 * @post circuit consists of V, S, X and Z gates only, in order (Z)(X)(S)(V)(S)
1080 */
1081 4834 static Circuit clifford_from_tk1(int i, int j, int k) {
1082 4834 std_cliff_spec_t spec = tk1_table[i % 4][j % 4][k % 4];
1083
2/2
✓ Branch 0 taken 34 times.
✓ Branch 1 taken 4800 times.
1/2
✓ Decision 'true' taken 4834 times.
✗ Decision 'false' not taken.
 4834 if (i >= 4) spec.p += 1;
1084
2/2
✓ Branch 0 taken 923 times.
✓ Branch 1 taken 3911 times.
1/2
✓ Decision 'true' taken 4834 times.
✗ Decision 'false' not taken.
 4834 if (j >= 4) spec.p += 1;
1085
2/2
✓ Branch 0 taken 950 times.
✓ Branch 1 taken 3884 times.
1/2
✓ Decision 'true' taken 4834 times.
✗ Decision 'false' not taken.
 4834 if (k >= 4) spec.p += 1;
1086
1087
1/2
✓ Branch 2 taken 4834 times.
✗ Branch 3 not taken.
 4834 Circuit c(1);
1088
2/2
✓ Branch 0 taken 1120 times.
✓ Branch 1 taken 3714 times.
2/2
✓ Decision 'true' taken 1120 times.
✓ Decision 'false' taken 3714 times.
 4834 if (spec.Z0) {
1089
2/4
✓ Branch 3 taken 1120 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 1120 times.
✗ Branch 7 not taken.
 1120 c.add_op<unsigned>(OpType::Z, {0});
1090 }
1091
2/2
✓ Branch 0 taken 1924 times.
✓ Branch 1 taken 2910 times.
2/2
✓ Decision 'true' taken 1924 times.
✓ Decision 'false' taken 2910 times.
 4834 if (spec.X1) {
1092
2/4
✓ Branch 3 taken 1924 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 1924 times.
✗ Branch 7 not taken.
 1924 c.add_op<unsigned>(OpType::X, {0});
1093 }
1094
2/2
✓ Branch 0 taken 1322 times.
✓ Branch 1 taken 3512 times.
2/2
✓ Decision 'true' taken 1322 times.
✓ Decision 'false' taken 3512 times.
 4834 if (spec.S2) {
1095
2/4
✓ Branch 3 taken 1322 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 1322 times.
✗ Branch 7 not taken.
 1322 c.add_op<unsigned>(OpType::S, {0});
1096 }
1097
2/2
✓ Branch 0 taken 3610 times.
✓ Branch 1 taken 1224 times.
2/2
✓ Decision 'true' taken 3610 times.
✓ Decision 'false' taken 1224 times.
 4834 if (spec.V3) {
1098
2/4
✓ Branch 3 taken 3610 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 3610 times.
✗ Branch 7 not taken.
 3610 c.add_op<unsigned>(OpType::V, {0});
1099 }
1100
2/2
✓ Branch 0 taken 2132 times.
✓ Branch 1 taken 2702 times.
2/2
✓ Decision 'true' taken 2132 times.
✓ Decision 'false' taken 2702 times.
 4834 if (spec.S4) {
1101
2/4
✓ Branch 3 taken 2132 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2132 times.
✗ Branch 7 not taken.
 2132 c.add_op<unsigned>(OpType::S, {0});
1102 }
1103
2/4
✓ Branch 1 taken 4834 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4834 times.
✗ Branch 5 not taken.
 4834 c.add_phase(spec.p);
1104
1105 9668 return c;
1106 }
1107
1108 2954 Transform decompose_cliffords_std() {
1109 2957 return Transform([](Circuit &circ) {
1110 2957 bool success = false;
1111 2957 VertexList bin;
1112
7/8
✓ Branch 1 taken 2957 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 29878 times.
✓ Branch 6 taken 2957 times.
✓ Branch 8 taken 29878 times.
✓ Branch 9 taken 2957 times.
✓ Branch 11 taken 2957 times.
✓ Branch 12 taken 2957 times.
 35792 BGL_FORALL_VERTICES(v, circ.dag, DAG) {
1113
1/2
✓ Branch 1 taken 29878 times.
✗ Branch 2 not taken.
 29878 Op_ptr op = circ.get_Op_ptr_from_Vertex(v);
1114 29878 OpType type = op->get_type();
1115
6/6
✓ Branch 0 taken 20916 times.
✓ Branch 1 taken 4319 times.
✓ Branch 2 taken 18590 times.
✓ Branch 3 taken 2326 times.
✓ Branch 4 taken 17206 times.
✓ Branch 5 taken 1384 times.
2/2
✓ Decision 'true' taken 9668 times.
✓ Decision 'false' taken 15567 times.
 25235 if (type != OpType::V && type != OpType::S && type != OpType::X &&
1116
7/8
✓ Branch 0 taken 25235 times.
✓ Branch 1 taken 4643 times.
✓ Branch 3 taken 17206 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 7809 times.
✓ Branch 6 taken 9397 times.
✓ Branch 7 taken 4834 times.
✓ Branch 8 taken 25044 times.
 62922 type != OpType::Z && is_single_qubit_unitary_type(type) &&
1117
3/4
✓ Branch 2 taken 7809 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 4834 times.
✓ Branch 5 taken 2975 times.
 7809 op->is_clifford()) {
1118
2/4
✓ Branch 2 taken 4834 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 4834 times.
✗ Branch 7 not taken.
 9668 std::vector<Expr> tk1_param_exprs = as_gate_ptr(op)->get_tk1_angles();
1119 4834 bool all_reduced = true;
1120 4834 bool all_roundable = true;
1121
1/2
✓ Branch 2 taken 4834 times.
✗ Branch 3 not taken.
 4834 std::vector<int> iangles(3);
1122
2/2
✓ Branch 0 taken 14502 times.
✓ Branch 1 taken 4834 times.
2/2
✓ Decision 'true' taken 14502 times.
✓ Decision 'false' taken 4834 times.
 19336 for (int i = 0; i < 3; i++) {
1123
1/2
✓ Branch 2 taken 14502 times.
✗ Branch 3 not taken.
 14502 std::optional<double> reduced = eval_expr_mod(tk1_param_exprs[i], 4);
1124
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 14502 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 14502 times.
 14502 if (!reduced)
1125 ✗ all_reduced = false;
1126 else {
1127
1/2
✓ Branch 1 taken 14502 times.
✗ Branch 2 not taken.
 14502 double angle = 2 * reduced.value(); // > 0
1128 14502 iangles[i] = int(angle + 0.5); // nearest integer
1129
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 14502 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 14502 times.
 14502 if (std::abs(angle - iangles[i]) >= EPS) {
1130 ✗ all_roundable = false;
1131 }
1132 14502 iangles[i] %= 8; // 8 --> 0
1133 }
1134 }
1135
2/4
✓ Branch 0 taken 4834 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 4834 times.
1/2
✓ Decision 'true' taken 4834 times.
✗ Decision 'false' not taken.
 4834 if (!(all_reduced && all_roundable)) continue;
1136 Circuit replacement =
1137
1/2
✓ Branch 4 taken 4834 times.
✗ Branch 5 not taken.
 4834 clifford_from_tk1(iangles[0], iangles[1], iangles[2]);
1138 Subcircuit sub = {
1139
4/8
✓ Branch 1 taken 4834 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4834 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 4834 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 4834 times.
✗ Branch 12 not taken.
 9668 {circ.get_in_edges(v)}, {circ.get_all_out_edges(v)}, {v}};
1140
1/2
✓ Branch 1 taken 4834 times.
✗ Branch 2 not taken.
 4834 bin.push_back(v);
1141
1/2
✓ Branch 1 taken 4834 times.
✗ Branch 2 not taken.
 4834 circ.substitute(replacement, sub, Circuit::VertexDeletion::No);
1142
2/4
✓ Branch 2 taken 4834 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 4834 times.
✗ Branch 6 not taken.
 4834 circ.add_phase(tk1_param_exprs[3]);
1143 4834 success = true;
1144
9/12
✓ Branch 3 taken 4834 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 4834 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 235 times.
✓ Branch 9 taken 24809 times.
✓ Branch 12 taken 235 times.
✗ Branch 13 not taken.
✓ Branch 14 taken 225 times.
✓ Branch 15 taken 10 times.
✓ Branch 16 taken 225 times.
✓ Branch 17 taken 24819 times.
2/2
✓ Decision 'true' taken 225 times.
✓ Decision 'false' taken 29653 times.
 29878 } else if (type == OpType::TK2 && op->is_clifford()) {
1145
1/2
✓ Branch 2 taken 225 times.
✗ Branch 3 not taken.
 225 auto params = op->get_params();
1146 TKET_ASSERT(params.size() == 3);
1147 // TODO: Maybe handle TK2 gates natively within clifford_simp?
1148 Circuit replacement =
1149
1/2
✓ Branch 4 taken 225 times.
✗ Branch 5 not taken.
 225 CircPool::TK2_using_CX(params[0], params[1], params[2]);
1150
2/4
✓ Branch 1 taken 225 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 225 times.
✗ Branch 5 not taken.
 225 decompose_cliffords_std().apply(replacement);
1151
1/2
✓ Branch 1 taken 225 times.
✗ Branch 2 not taken.
 225 bin.push_back(v);
1152
1/2
✓ Branch 1 taken 225 times.
✗ Branch 2 not taken.
 225 circ.substitute(replacement, v, Circuit::VertexDeletion::No);
1153 225 success = true;
1154 225 }
1155
1/2
✓ Branch 1 taken 29878 times.
✗ Branch 2 not taken.
 29878 }
1156
1/2
✓ Branch 1 taken 2957 times.
✗ Branch 2 not taken.
 2957 circ.remove_vertices(
1157 bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
1158 2957 return success;
1159
1/2
✓ Branch 2 taken 2954 times.
✗ Branch 3 not taken.
 5911 });
1160 }
1161
1162 11 Transform decompose_ZX_to_cliffords() {
1163 11 return Transform([](Circuit &circ) {
1164 11 bool success = false;
1165 11 VertexList bin;
1166
7/8
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 455 times.
✓ Branch 6 taken 11 times.
✓ Branch 8 taken 455 times.
✓ Branch 9 taken 11 times.
✓ Branch 11 taken 11 times.
✓ Branch 12 taken 11 times.
 477 BGL_FORALL_VERTICES(v, circ.dag, DAG) {
1167
1/2
✓ Branch 1 taken 455 times.
✗ Branch 2 not taken.
 455 const Op_ptr op_ptr = circ.get_Op_ptr_from_Vertex(v);
1168
6/6
✓ Branch 2 taken 245 times.
✓ Branch 3 taken 210 times.
✓ Branch 4 taken 105 times.
✓ Branch 5 taken 140 times.
✓ Branch 6 taken 315 times.
✓ Branch 7 taken 140 times.
2/2
✓ Decision 'true' taken 315 times.
✓ Decision 'false' taken 385 times.
 700 if (op_ptr->get_type() == OpType::Rz ||
1169 245 op_ptr->get_type() == OpType::Rx) {
1170
2/4
✓ Branch 2 taken 315 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 315 times.
✗ Branch 7 not taken.
 315 Expr param = op_ptr->get_params()[0];
1171
1/2
✓ Branch 1 taken 315 times.
✗ Branch 2 not taken.
 315 std::optional<double> reduced = eval_expr_mod(param, 4);
1172 315 bool roundable = false;
1173 315 int iangle = 0;
1174
2/2
✓ Branch 1 taken 313 times.
✓ Branch 2 taken 2 times.
2/2
✓ Decision 'true' taken 313 times.
✓ Decision 'false' taken 2 times.
 315 if (reduced) {
1175
1/2
✓ Branch 1 taken 313 times.
✗ Branch 2 not taken.
 313 double angle = 2 * reduced.value(); // >= 0
1176 313 iangle = int(angle + 0.5); // nearest integer
1177 313 iangle %= 8; // {0,1,2,3,4,5,6,7}
1178 313 roundable = (std::abs(angle - iangle) < EPS);
1179 }
1180
2/2
✓ Branch 0 taken 299 times.
✓ Branch 1 taken 16 times.
2/2
✓ Decision 'true' taken 299 times.
✓ Decision 'false' taken 16 times.
 315 if (roundable) {
1181 299 bool is_rz = op_ptr->get_type() == OpType::Rz;
1182
4/5
✓ Branch 0 taken 156 times.
✓ Branch 1 taken 110 times.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 29 times.
✗ Branch 4 not taken.
 299 switch (iangle % 4) {
1183
1/1
✓ Decision 'true' taken 156 times.
 156 case 0: {
1184
1/2
✓ Branch 1 taken 156 times.
✗ Branch 2 not taken.
 156 bin.push_back(v);
1185
1/2
✓ Branch 1 taken 156 times.
✗ Branch 2 not taken.
 156 circ.remove_vertex(
1186 v, Circuit::GraphRewiring::Yes, Circuit::VertexDeletion::No);
1187 156 break;
1188 }
1189
1/1
✓ Decision 'true' taken 110 times.
 110 case 1: {
1190
2/2
✓ Branch 0 taken 55 times.
✓ Branch 1 taken 55 times.
2/2
✓ Decision 'true' taken 55 times.
✓ Decision 'false' taken 55 times.
 110 if (is_rz) {
1191
3/6
✓ Branch 2 taken 55 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 55 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 55 times.
✗ Branch 10 not taken.
 55 circ.dag[v] = {get_op_ptr(OpType::S)};
1192
2/4
✓ Branch 1 taken 55 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 55 times.
✗ Branch 5 not taken.
 55 circ.add_phase(-0.25);
1193 } else {
1194
3/6
✓ Branch 2 taken 55 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 55 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 55 times.
✗ Branch 10 not taken.
 55 circ.dag[v] = {get_op_ptr(OpType::V)};
1195 }
1196 110 break;
1197 }
1198
1/1
✓ Decision 'true' taken 4 times.
 4 case 2: {
1199
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2 times.
2/2
✓ Decision 'true' taken 2 times.
✓ Decision 'false' taken 2 times.
 4 if (is_rz) {
1200
3/6
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 2 times.
✗ Branch 10 not taken.
 2 circ.dag[v] = {get_op_ptr(OpType::Z)};
1201 } else {
1202
3/6
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 2 times.
✗ Branch 10 not taken.
 2 circ.dag[v] = {get_op_ptr(OpType::X)};
1203 }
1204
2/4
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
 4 circ.add_phase(-0.5);
1205 4 break;
1206 }
1207
1/1
✓ Decision 'true' taken 29 times.
 29 case 3: {
1208
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 28 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 28 times.
 29 if (is_rz) {
1209
3/6
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 1 times.
✗ Branch 10 not taken.
 1 circ.dag[v] = {get_op_ptr(OpType::Sdg)};
1210
2/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
 1 circ.add_phase(-0.75);
1211 } else {
1212
3/6
✓ Branch 2 taken 28 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 28 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 28 times.
✗ Branch 10 not taken.
 28 circ.dag[v] = {get_op_ptr(OpType::Vdg)};
1213
2/4
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 28 times.
✗ Branch 5 not taken.
 28 circ.add_phase(1);
1214 }
1215 29 break;
1216 }
1217 }
1218
4/6
✓ Branch 0 taken 11 times.
✓ Branch 1 taken 288 times.
✓ Branch 3 taken 11 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 11 times.
✗ Branch 7 not taken.
1/2
✓ Decision 'true' taken 299 times.
✗ Decision 'false' not taken.
 299 if (iangle >= 4) circ.add_phase(1);
1219 299 success = true;
1220 }
1221 315 }
1222 455 }
1223
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 circ.remove_vertices(
1224 bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
1225 11 return success;
1226
1/2
✓ Branch 2 taken 11 times.
✗ Branch 3 not taken.
 22 });
1227 }
1228
1229 23 Transform decompose_PhaseGadgets() {
1230 23 return Transform([](Circuit &circ) {
1231 23 bool success = false;
1232 23 VertexList big_bin;
1233
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 auto [it, end] = boost::vertices(circ.dag);
1234
2/2
✓ Branch 1 taken 453 times.
✓ Branch 2 taken 23 times.
2/2
✓ Decision 'true' taken 453 times.
✓ Decision 'false' taken 23 times.
 476 for (auto next = it; it != end; it = next) {
1235 453 ++next;
1236
5/6
✓ Branch 2 taken 453 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 125 times.
✓ Branch 5 taken 328 times.
✓ Branch 6 taken 105 times.
✓ Branch 7 taken 348 times.
2/2
✓ Decision 'true' taken 105 times.
✓ Decision 'false' taken 473 times.
 578 if (circ.get_OpType_from_Vertex(*it) == OpType::CX &&
1237
3/4
✓ Branch 2 taken 125 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 105 times.
✓ Branch 5 taken 20 times.
 125 circ.n_out_edges(*it) == 2) {
1238
1/2
✓ Branch 2 taken 105 times.
✗ Branch 3 not taken.
 105 EdgeVec outs = circ.get_all_out_edges(*it);
1239
1/2
✓ Branch 2 taken 105 times.
✗ Branch 3 not taken.
 105 Vertex next_v = circ.target(outs[1]);
1240
1/2
✓ Branch 1 taken 105 times.
✗ Branch 2 not taken.
 105 Op_ptr g = circ.get_Op_ptr_from_Vertex(next_v);
1241 105 OpType type = g->get_type();
1242
5/6
✓ Branch 0 taken 100 times.
✓ Branch 1 taken 5 times.
✓ Branch 2 taken 100 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 42 times.
✓ Branch 5 taken 58 times.
2/2
✓ Decision 'true' taken 22 times.
✓ Decision 'false' taken 125 times.
 147 if (type == OpType::Rz || type == OpType::U1 ||
1243
8/12
✓ Branch 2 taken 42 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 42 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 17 times.
✓ Branch 9 taken 25 times.
✓ Branch 10 taken 42 times.
✓ Branch 11 taken 63 times.
✓ Branch 13 taken 22 times.
✓ Branch 14 taken 83 times.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
 147 (type == OpType::TK1 && equiv_0(g->get_params()[1]))) {
1244
1/2
✓ Branch 2 taken 22 times.
✗ Branch 3 not taken.
 22 Vertex last_v = circ.get_next_pair(next_v, outs[1]).first;
1245
3/4
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 19 times.
✓ Branch 4 taken 3 times.
2/2
✓ Decision 'true' taken 18 times.
✓ Decision 'false' taken 23 times.
 41 if (circ.get_OpType_from_Vertex(last_v) == OpType::CX &&
1246
6/8
✓ Branch 2 taken 19 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 19 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 18 times.
✓ Branch 8 taken 1 times.
✓ Branch 9 taken 18 times.
✓ Branch 10 taken 4 times.
 41 circ.get_nth_in_edge(last_v, 0) == outs[0]) {
1247
1/2
✓ Branch 2 taken 18 times.
✗ Branch 3 not taken.
 18 VertexList bin = {next_v, last_v};
1248
1/2
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
 18 big_bin.push_back(next_v);
1249
1/2
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
 18 big_bin.push_back(last_v);
1250
1/2
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
 18 circ.remove_vertices(
1251 bin, Circuit::GraphRewiring::Yes, Circuit::VertexDeletion::No);
1252
2/4
✓ Branch 2 taken 18 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 18 times.
✗ Branch 7 not taken.
 18 Expr t = g->get_params()[0];
1253
2/2
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 5 times.
2/2
✓ Decision 'true' taken 13 times.
✓ Decision 'false' taken 5 times.
 18 if (type == OpType::TK1) {
1254
2/4
✓ Branch 2 taken 13 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 13 times.
✗ Branch 7 not taken.
 13 t += g->get_params()[2];
1255 }
1256
3/6
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 18 times.
✗ Branch 6 not taken.
✓ Branch 9 taken 18 times.
✗ Branch 10 not taken.
 18 circ.dag[*it] = {get_op_ptr(OpType::PhaseGadget, {t}, 2)};
1257
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 18 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 18 times.
 18 if (type == OpType::U1) {
1258 ✗ circ.add_phase(t / 2);
1259 18 } else if (
1260
8/14
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 5 times.
✓ Branch 4 taken 13 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 13 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✓ Branch 11 taken 13 times.
✓ Branch 12 taken 13 times.
✓ Branch 13 taken 5 times.
✗ Branch 15 not taken.
✓ Branch 16 taken 18 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
 18 type == OpType::TK1 && equiv_val(g->get_params()[1], 2, 4)) {
1261 ✗ circ.add_phase(1);
1262 }
1263 18 success = true;
1264 18 }
1265 }
1266
2/2
✓ Branch 0 taken 50 times.
✓ Branch 1 taken 55 times.
2/2
✓ Decision 'true' taken 50 times.
✓ Decision 'false' taken 55 times.
 105 if (type == OpType::CX) {
1267
3/4
✓ Branch 2 taken 50 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 18 times.
✓ Branch 5 taken 32 times.
2/2
✓ Decision 'true' taken 18 times.
✓ Decision 'false' taken 32 times.
 50 if (circ.get_target_port(outs[1]) == 1) {
1268
2/4
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 18 times.
✗ Branch 5 not taken.
 18 Vertex rx = circ.source(circ.get_nth_in_edge(next_v, 0));
1269
3/4
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 2 times.
✓ Branch 4 taken 16 times.
2/2
✓ Decision 'true' taken 2 times.
✓ Decision 'false' taken 16 times.
 18 if (circ.get_OpType_from_Vertex(rx) == OpType::Rx) {
1270
2/4
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
1/2
✓ Decision 'true' taken 2 times.
✗ Decision 'false' not taken.
 2 if (rx == circ.target(outs[0])) {
1271
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 const Op_ptr rx_g = (circ.get_Op_ptr_from_Vertex(rx));
1272
1/2
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
 2 VertexList bin = {rx, next_v};
1273
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 big_bin.push_back(next_v);
1274
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 big_bin.push_back(rx);
1275
1/2
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
 2 Circuit replacement(2);
1276
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 circ.remove_vertices(
1277 bin, Circuit::GraphRewiring::Yes,
1278 Circuit::VertexDeletion::No);
1279
2/4
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
 2 replacement.add_op<unsigned>(OpType::H, {0});
1280
2/4
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
 2 replacement.add_op<unsigned>(OpType::H, {1});
1281
2/4
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
 6 replacement.add_op<unsigned>(
1282
1/2
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
 4 OpType::PhaseGadget, rx_g->get_params()[0], {0, 1});
1283
2/4
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
 2 replacement.add_op<unsigned>(OpType::H, {0});
1284
2/4
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
 2 replacement.add_op<unsigned>(OpType::H, {1});
1285 Subcircuit sub = {
1286
4/8
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 11 taken 2 times.
✗ Branch 12 not taken.
✓ Branch 14 taken 2 times.
✗ Branch 15 not taken.
 4 circ.get_in_edges(*it), circ.get_all_out_edges(*it), {*it}};
1287
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 circ.substitute(replacement, sub, Circuit::VertexDeletion::Yes);
1288 2 success = true;
1289 2 }
1290 }
1291 }
1292 }
1293 105 }
1294 }
1295
1/2
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
 23 circ.remove_vertices(
1296 big_bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
1297 23 return success;
1298
1/2
✓ Branch 2 taken 23 times.
✗ Branch 3 not taken.
 46 });
1299 }
1300
1301 8 Transform decomp_boxes() {
1302
1/2
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
 20 return Transform([](Circuit &circ) { return circ.decompose_boxes(); });
1303 }
1304
1305 27 Transform compose_phase_poly_boxes(const unsigned min_size) {
1306 26 return Transform([=](Circuit &circ) {
1307 // replace wireswaps with three CX
1308
3/4
✓ Branch 1 taken 45 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 19 times.
✓ Branch 4 taken 26 times.
0/1
? Decision couldn't be analyzed.
 45 while (circ.has_implicit_wireswaps()) {
1309
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 qubit_map_t perm = circ.implicit_qubit_permutation();
1310
1/2
✓ Branch 5 taken 49 times.
✗ Branch 6 not taken.
1/2
✓ Decision 'true' taken 49 times.
✗ Decision 'false' not taken.
 49 for (const std::pair<const Qubit, Qubit> &pair : perm) {
1311
3/4
✓ Branch 1 taken 49 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 19 times.
✓ Branch 4 taken 30 times.
2/2
✓ Decision 'true' taken 19 times.
✓ Decision 'false' taken 30 times.
 49 if (pair.first != pair.second) {
1312
1/2
✓ Branch 3 taken 19 times.
✗ Branch 4 not taken.
 19 circ.replace_implicit_wire_swap(pair.first, pair.second);
1313 19 break;
1314 }
1315 }
1316 19 }
1317
1318
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 CircToPhasePolyConversion conv = CircToPhasePolyConversion(circ, min_size);
1319
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 conv.convert();
1320
2/4
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 26 times.
✗ Branch 5 not taken.
 26 circ = conv.get_circuit();
1321 26 return true;
1322
1/2
✓ Branch 2 taken 27 times.
✗ Branch 3 not taken.
 53 });
1323 }
1324
1325 3 Transform decompose_SWAP(const Circuit &replacement_circuit) {
1326 3 return Transform([=](Circuit &circ) {
1327
1/4
✗ Branch 1 not taken.
✓ Branch 2 taken 3 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
1/2
✓ Decision 'true' taken 3 times.
✗ Decision 'false' not taken.
 3 if (!replacement_circuit.is_simple()) throw SimpleOnly();
1328
2/4
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 3 times.
✗ Branch 6 not taken.
 3 return circ.substitute_all(replacement_circuit, get_op_ptr(OpType::SWAP));
1329
2/4
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 3 times.
✗ Branch 6 not taken.
 3 });
1330 }
1331
1332 44 static void swap_sub(
1333 Circuit &circ, const Circuit &swap_circ_1, const Circuit &swap_circ_2,
1334 Subcircuit &sub, const std::pair<port_t, port_t> &port_comp) {
1335 44 std::pair<port_t, port_t> comp = {0, 1};
1336 // Ports only come in 2 cases, {0,1} or {1,0}. if {0,1} (first case),
1337 // swap_circ_1 leaves a CX{0,1} next to current CX{0,1}, if not we can
1338 // assume second case.
1339
2/2
✓ Branch 1 taken 28 times.
✓ Branch 2 taken 16 times.
2/2
✓ Decision 'true' taken 28 times.
✓ Decision 'false' taken 16 times.
 44 if (port_comp == comp)
1340
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 circ.substitute(swap_circ_1, sub, Circuit::VertexDeletion::Yes);
1341 else
1342
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 circ.substitute(swap_circ_2, sub, Circuit::VertexDeletion::Yes);
1343 44 }
1344
1345 33 Transform decompose_SWAP_to_CX(const Architecture &arc) {
1346 // Note that the default argument will be out of scope at call-time!
1347 // => we replace the default empty Architecture with nullptr
1348 // we need to keep arc as a pointer as there is no such thing as
1349 // optional references in std
1350
2/2
✓ Branch 1 taken 16 times.
✓ Branch 2 taken 17 times.
 33 const Architecture *arc_ptr = arc.n_nodes() ? &arc : nullptr;
1351 1184 return Transform([arc_ptr](Circuit &circ) {
1352 29 bool success = false;
1353 29 std::vector<std::pair<Vertex, bool>> bin;
1354
5/8
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3043 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 3072 times.
✗ Branch 8 not taken.
✓ Branch 11 taken 3043 times.
✓ Branch 12 taken 29 times.
0/1
? Decision couldn't be analyzed.
 3072 for (Circuit::CommandIterator it = circ.begin(); it != circ.end(); ++it) {
1355
2/2
✓ Branch 5 taken 917 times.
✓ Branch 6 taken 2126 times.
2/2
✓ Decision 'true' taken 917 times.
✓ Decision 'false' taken 2126 times.
 3043 if (it->get_op_ptr()->get_type() == OpType::SWAP) {
1356
1/2
✓ Branch 2 taken 917 times.
✗ Branch 3 not taken.
 917 unit_vector_t qbs = it->get_args();
1357
1/2
✓ Branch 4 taken 917 times.
✗ Branch 5 not taken.
 917 node_vector_t nodes = {qbs.begin(), qbs.end()};
1358
3/4
✓ Branch 2 taken 122 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 58 times.
✓ Branch 5 taken 64 times.
2/2
✓ Decision 'true' taken 31 times.
✓ Decision 'false' taken 91 times.
 122 if (arc_ptr != nullptr && arc_ptr->node_exists(nodes[0]) &&
1359
6/8
✓ Branch 0 taken 122 times.
✓ Branch 1 taken 795 times.
✓ Branch 4 taken 58 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 58 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 31 times.
✓ Branch 9 taken 886 times.
 1097 arc_ptr->node_exists(nodes[1]) &&
1360
3/4
✓ Branch 3 taken 58 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 31 times.
✓ Branch 6 taken 27 times.
 58 arc_ptr->edge_exists(nodes[1], nodes[0])) {
1361
1/2
✓ Branch 3 taken 31 times.
✗ Branch 4 not taken.
 31 bin.push_back({it.get_vertex(), true});
1362 } else {
1363
1/2
✓ Branch 3 taken 886 times.
✗ Branch 4 not taken.
 886 bin.push_back({it.get_vertex(), false});
1364 }
1365 917 }
1366 29 }
1367
1368
2/2
✓ Branch 5 taken 917 times.
✓ Branch 6 taken 29 times.
2/2
✓ Decision 'true' taken 917 times.
✓ Decision 'false' taken 29 times.
 946 for (std::pair<Vertex, bool> v : bin) {
1369 917 success = true;
1370 // Get predecessor vertices and successor vertices and find subcircuit
1371 // for replacement
1372
1/2
✓ Branch 1 taken 917 times.
✗ Branch 2 not taken.
 917 VertexVec preds = circ.get_predecessors(v.first);
1373
1/2
✓ Branch 1 taken 917 times.
✗ Branch 2 not taken.
 917 VertexVec succs = circ.get_successors(v.first);
1374
1/2
✓ Branch 1 taken 917 times.
✗ Branch 2 not taken.
 917 EdgeVec in_edges = circ.get_in_edges(v.first);
1375
1/2
✓ Branch 1 taken 917 times.
✗ Branch 2 not taken.
 917 EdgeVec out_edges = circ.get_all_out_edges(v.first);
1376
2/4
✓ Branch 2 taken 917 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 917 times.
✗ Branch 6 not taken.
 1834 Subcircuit sub = {in_edges, out_edges, {v.first}};
1377
1378
4/4
✓ Branch 1 taken 40 times.
✓ Branch 2 taken 877 times.
✓ Branch 3 taken 38 times.
✓ Branch 4 taken 879 times.
2/2
✓ Decision 'true' taken 38 times.
✓ Decision 'false' taken 919 times.
 957 if (preds.size() == 1 &&
1379
3/4
✓ Branch 2 taken 40 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 38 times.
✓ Branch 5 taken 2 times.
 40 circ.get_OpType_from_Vertex(preds[0]) == OpType::CX) {
1380 // if conditions requires that there is a CX gate before SWAP
1381
3/6
✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 38 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 38 times.
✗ Branch 8 not taken.
 38 swap_sub(
1382 circ, CircPool::SWAP_using_CX_0(), CircPool::SWAP_using_CX_1(), sub,
1383
1/2
✓ Branch 2 taken 38 times.
✗ Branch 3 not taken.
 38 {circ.get_source_port(in_edges[0]),
1384
1/2
✓ Branch 2 taken 38 times.
✗ Branch 3 not taken.
 76 circ.get_source_port(in_edges[1])});
1385 879 } else if (
1386
4/4
✓ Branch 1 taken 11 times.
✓ Branch 2 taken 868 times.
✓ Branch 3 taken 6 times.
✓ Branch 4 taken 873 times.
 890 succs.size() == 1 &&
1387
3/4
✓ Branch 2 taken 11 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 6 times.
✓ Branch 5 taken 5 times.
 11 circ.get_OpType_from_Vertex(succs[0]) == OpType::CX) {
1388 // if no CX gate before SWAP, check after.
1389
3/6
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 6 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 6 times.
✗ Branch 8 not taken.
 6 swap_sub(
1390 circ, CircPool::SWAP_using_CX_0(), CircPool::SWAP_using_CX_1(), sub,
1391
1/2
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
 6 {circ.get_target_port(out_edges[0]),
1392
1/2
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
 12 circ.get_target_port(out_edges[1])});
1393
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 845 times.
2/2
✓ Decision 'true' taken 28 times.
✓ Decision 'false' taken 845 times.
 873 } else if (v.second) {
1394 // We assume in general that a CX gate saving is desired over H gate
1395 // savings. If SWAP doesn't lend itself to annihlation though, the
1396 // SWAP is inserted to reduce number of H gates added in a 'directed'
1397 // CX decomposition. SWAP_using_CX_1 is added if the backwards
1398 // direction is available on the architecture
1399
2/4
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 28 times.
✗ Branch 5 not taken.
 28 circ.substitute(
1400 CircPool::SWAP_using_CX_1(), sub, Circuit::VertexDeletion::Yes);
1401 } else {
1402 // SWAP_using_CX_0 is added as a default option
1403
2/4
✓ Branch 1 taken 845 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 845 times.
✗ Branch 5 not taken.
 845 circ.substitute(
1404 CircPool::SWAP_using_CX_0(), sub, Circuit::VertexDeletion::Yes);
1405 }
1406 917 }
1407 29 return success;
1408
1/2
✓ Branch 2 taken 33 times.
✗ Branch 3 not taken.
 62 });
1409 }
1410
1411 18 Transform decompose_BRIDGE_to_CX() {
1412 15 return Transform([](Circuit &circ) {
1413 15 bool success = false;
1414 // Collect all BRIDGE type vertices
1415 15 std::vector<std::pair<Vertex, bool>> bin;
1416
7/8
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 2589 times.
✓ Branch 6 taken 15 times.
✓ Branch 8 taken 2589 times.
✓ Branch 9 taken 15 times.
✓ Branch 11 taken 15 times.
✓ Branch 12 taken 15 times.
 2619 BGL_FORALL_VERTICES(v, circ.dag, DAG) {
1417
3/4
✓ Branch 1 taken 2589 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 44 times.
✓ Branch 4 taken 2545 times.
2/2
✓ Decision 'true' taken 44 times.
✓ Decision 'false' taken 2545 times.
 2589 if (circ.get_OpType_from_Vertex(v) == OpType::BRIDGE) {
1418
1/2
✓ Branch 2 taken 44 times.
✗ Branch 3 not taken.
 44 bin.push_back({v, false});
1419 }
1420
3/4
✓ Branch 1 taken 2589 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 295 times.
✓ Branch 4 taken 2294 times.
2/2
✓ Decision 'true' taken 295 times.
✓ Decision 'false' taken 2294 times.
 2589 if (circ.get_OpType_from_Vertex(v) == OpType::Conditional) {
1421 const Conditional &b =
1422
1/2
✓ Branch 1 taken 295 times.
✗ Branch 2 not taken.
 295 static_cast<const Conditional &>(*circ.get_Op_ptr_from_Vertex(v));
1423
3/4
✓ Branch 1 taken 295 times.
✗ Branch 2 not taken.
✓ Branch 6 taken 1 times.
✓ Branch 7 taken 294 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 294 times.
 295 if (b.get_op()->get_type() == OpType::BRIDGE) {
1424
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 1 bin.push_back({v, true});
1425 }
1426 }
1427 }
1428
1429 auto BRIDGE_sub =
1430 90 [&circ](std::pair<Vertex, bool> &candidate, Circuit BRIDGE_circ) {
1431
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 44 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 44 times.
 45 if (candidate.second)
1432
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 circ.substitute_conditional(
1433 1 BRIDGE_circ, candidate.first, Circuit::VertexDeletion::Yes);
1434 else
1435 44 circ.substitute(
1436 44 BRIDGE_circ, candidate.first, Circuit::VertexDeletion::Yes);
1437 45 };
1438
1439
2/2
✓ Branch 5 taken 45 times.
✓ Branch 6 taken 15 times.
2/2
✓ Decision 'true' taken 45 times.
✓ Decision 'false' taken 15 times.
 60 for (std::pair<Vertex, bool> v : bin) {
1440 // Get predecessor vertices and successor vertices and find subcircuit
1441 // for replacement
1442 45 success = true;
1443
1/2
✓ Branch 1 taken 45 times.
✗ Branch 2 not taken.
 45 VertexVec preds = circ.get_predecessors(v.first);
1444
1/2
✓ Branch 1 taken 45 times.
✗ Branch 2 not taken.
 45 VertexVec succs = circ.get_successors(v.first);
1445
1/2
✓ Branch 1 taken 45 times.
✗ Branch 2 not taken.
 45 EdgeVec in_edges = circ.get_in_edges(v.first);
1446
1/2
✓ Branch 1 taken 45 times.
✗ Branch 2 not taken.
 45 EdgeVec out_edges = circ.get_all_out_edges(v.first);
1447
2/4
✓ Branch 2 taken 45 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 45 times.
✗ Branch 6 not taken.
 90 Subcircuit sub = {in_edges, out_edges, {v.first}};
1448
1449 45 bool done = false;
1450
2/2
✓ Branch 1 taken 10 times.
✓ Branch 2 taken 35 times.
2/2
✓ Decision 'true' taken 20 times.
✓ Decision 'false' taken 25 times.
 45 if (preds.size() < 3) { // Implies some predecessor vertices are in a
1451 // multi-qubit op together
1452 VertexVec comps = {
1453
2/4
✓ Branch 2 taken 10 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 10 times.
✗ Branch 6 not taken.
 20 circ.source(in_edges[0]), circ.source(in_edges[1]),
1454
2/4
✓ Branch 3 taken 10 times.
✗ Branch 4 not taken.
✓ Branch 7 taken 10 times.
✗ Branch 8 not taken.
 20 circ.source(in_edges[2])};
1455
2/2
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 2 times.
2/2
✓ Decision 'true' taken 8 times.
✓ Decision 'false' taken 12 times.
 20 if (comps[0] ==
1456 10 comps[1]) { // First two qubits in BRIDGE in multi-qubit op
1457
3/6
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 8 times.
✗ Branch 8 not taken.
 8 BRIDGE_sub(v, CircPool::BRIDGE_using_CX_0());
1458 8 done = true;
1459
1/2
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
1/2
✓ Decision 'true' taken 2 times.
✗ Decision 'false' not taken.
 2 } else if (comps[2] == comps[1]) { // Second two qubits in BRIDGE in
1460 // multi-qubit op together before
1461 // BRIDGE
1462
3/6
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 2 times.
✗ Branch 8 not taken.
 2 BRIDGE_sub(v, CircPool::BRIDGE_using_CX_1());
1463 2 done = true;
1464 }
1465 10 }
1466
6/6
✓ Branch 1 taken 13 times.
✓ Branch 2 taken 32 times.
✓ Branch 3 taken 12 times.
✓ Branch 4 taken 1 times.
✓ Branch 5 taken 12 times.
✓ Branch 6 taken 33 times.
2/2
✓ Decision 'true' taken 24 times.
✓ Decision 'false' taken 21 times.
 45 if (succs.size() < 3 && !done) { // Implies some successor vertices are
1467 // in a multiq-ubit op together
1468 VertexVec comps = {
1469
2/4
✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 12 times.
✗ Branch 6 not taken.
 24 circ.target(out_edges[0]), circ.target(out_edges[1]),
1470
2/4
✓ Branch 3 taken 12 times.
✗ Branch 4 not taken.
✓ Branch 7 taken 12 times.
✗ Branch 8 not taken.
 24 circ.target(out_edges[2])};
1471
2/2
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 4 times.
2/2
✓ Decision 'true' taken 8 times.
✓ Decision 'false' taken 4 times.
 12 if (comps[0] == comps[1]) { // First two qubits in BRIDGE in
1472 // multi-qubit op together before BRIDGE
1473
3/6
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 8 times.
✗ Branch 8 not taken.
 8 BRIDGE_sub(v, CircPool::BRIDGE_using_CX_1());
1474 8 done = true;
1475
1/2
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
1/2
✓ Decision 'true' taken 4 times.
✗ Decision 'false' not taken.
 4 } else if (comps[2] == comps[1]) { // Second two qubits in BRIDGE in
1476 // multi-qubit op together before
1477 // BRIDGE
1478
3/6
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 4 times.
✗ Branch 8 not taken.
 4 BRIDGE_sub(v, CircPool::BRIDGE_using_CX_0());
1479 4 done = true;
1480 }
1481 12 }
1482
2/2
✓ Branch 0 taken 23 times.
✓ Branch 1 taken 22 times.
2/2
✓ Decision 'true' taken 23 times.
✓ Decision 'false' taken 22 times.
 45 if (!done) { // default decomposition
1483
3/6
✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 23 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 23 times.
✗ Branch 8 not taken.
 23 BRIDGE_sub(v, CircPool::BRIDGE_using_CX_1());
1484 }
1485 45 }
1486 15 return success;
1487
1/2
✓ Branch 2 taken 18 times.
✗ Branch 3 not taken.
 33 });
1488 }
1489
1490 14 Transform decompose_CX_directed(const Architecture &arc) {
1491 10 return Transform([arc](Circuit &circ) {
1492 10 bool success = false;
1493 // Collect all CX type vertices
1494 10 std::vector<std::pair<Vertex, bool>> bin;
1495
5/8
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1228 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1238 times.
✗ Branch 8 not taken.
✓ Branch 11 taken 1228 times.
✓ Branch 12 taken 10 times.
0/1
? Decision couldn't be analyzed.
 1238 for (Circuit::CommandIterator it = circ.begin(); it != circ.end(); ++it) {
1496
2/2
✓ Branch 5 taken 1198 times.
✓ Branch 6 taken 30 times.
2/2
✓ Decision 'true' taken 1198 times.
✓ Decision 'false' taken 30 times.
 1228 if (it->get_op_ptr()->get_type() == OpType::CX) {
1497
1/2
✓ Branch 2 taken 1198 times.
✗ Branch 3 not taken.
 1198 unit_vector_t qbs = it->get_args();
1498
1/2
✓ Branch 4 taken 1198 times.
✗ Branch 5 not taken.
 1198 node_vector_t nodes = {qbs.begin(), qbs.end()};
1499
5/6
✓ Branch 3 taken 1198 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 607 times.
✓ Branch 6 taken 591 times.
✓ Branch 7 taken 607 times.
✓ Branch 8 taken 591 times.
2/2
✓ Decision 'true' taken 607 times.
✓ Decision 'false' taken 1198 times.
 1805 if (!arc.edge_exists(nodes[0], nodes[1]) &&
1500
2/4
✓ Branch 3 taken 607 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 607 times.
✗ Branch 6 not taken.
 607 arc.edge_exists(nodes[1], nodes[0])) {
1501 // Implies CX gate is valid, and needs flipping to respect
1502 // Architecture
1503
1/2
✓ Branch 3 taken 607 times.
✗ Branch 4 not taken.
 607 bin.push_back({it.get_vertex(), false});
1504 }
1505 1198 }
1506
2/2
✓ Branch 5 taken 2 times.
✓ Branch 6 taken 1226 times.
2/2
✓ Decision 'true' taken 2 times.
✓ Decision 'false' taken 1226 times.
 1228 if (it->get_op_ptr()->get_type() == OpType::Conditional) {
1507 const Conditional &b =
1508 2 static_cast<const Conditional &>(*it->get_op_ptr());
1509
2/4
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
1/2
✓ Decision 'true' taken 2 times.
✗ Decision 'false' not taken.
 2 if (b.get_op()->get_type() == OpType::CX) {
1510
1/2
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
 2 qubit_vector_t qbs = it->get_qubits();
1511
1/2
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
 2 node_vector_t nodes = {qbs.begin(), qbs.end()};
1512
5/6
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 1 times.
✓ Branch 6 taken 1 times.
✓ Branch 7 taken 1 times.
✓ Branch 8 taken 1 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 2 times.
 3 if (!arc.edge_exists(nodes[0], nodes[1]) &&
1513
2/4
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
 1 arc.edge_exists(nodes[1], nodes[0])) {
1514 // Implies CX gate is valid, and needs flipping to respect
1515 // Architecture
1516
1/2
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
 1 bin.push_back({it.get_vertex(), true});
1517 }
1518 2 }
1519
2/4
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 2 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 2 times.
 2 if (b.get_op()->get_type() == OpType::CircBox) {
1520 ✗ qubit_vector_t qbs = it->get_qubits();
1521 std::shared_ptr<const Box> box_ptr =
1522 ✗ std::dynamic_pointer_cast<const Box>(b.get_op());
1523 ✗ qubit_vector_t all_qubits = box_ptr->to_circuit().get()->all_qubits();
1524
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (all_qubits.size() != 3)
1525 ✗ throw std::logic_error("Box being opened not a BRIDGE gate.");
1526 std::map<Qubit, Qubit> rmap = {
1527 ✗ {all_qubits[0], qbs[0]},
1528 ✗ {all_qubits[1], qbs[1]},
1529 ✗ {all_qubits[2], qbs[2]}};
1530 ✗ box_ptr->to_circuit()->rename_units(rmap);
1531 ✗ decompose_CX_directed(arc).apply(*box_ptr->to_circuit());
1532 }
1533 }
1534 10 }
1535
2/2
✓ Branch 4 taken 608 times.
✓ Branch 5 taken 10 times.
2/2
✓ Decision 'true' taken 608 times.
✓ Decision 'false' taken 10 times.
 618 for (std::pair<Vertex, bool> v : bin) {
1536
2/2
✓ Branch 0 taken 607 times.
✓ Branch 1 taken 1 times.
2/2
✓ Decision 'true' taken 607 times.
✓ Decision 'false' taken 1 times.
 608 if (!v.second) {
1537 Subcircuit sub = {
1538
1/2
✓ Branch 1 taken 607 times.
✗ Branch 2 not taken.
 607 circ.get_in_edges(v.first),
1539
1/2
✓ Branch 1 taken 607 times.
✗ Branch 2 not taken.
 1214 circ.get_all_out_edges(v.first),
1540
2/4
✓ Branch 2 taken 607 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 607 times.
✗ Branch 6 not taken.
 1214 {v.first}};
1541
2/4
✓ Branch 1 taken 607 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 607 times.
✗ Branch 5 not taken.
 607 circ.substitute(
1542 CircPool::CX_using_flipped_CX(), sub, Circuit::VertexDeletion::Yes);
1543 607 }
1544
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 607 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 607 times.
 608 if (v.second) {
1545
3/6
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
 1 circ.substitute_conditional(
1546 CircPool::CX_using_flipped_CX(), v.first,
1547 Circuit::VertexDeletion::Yes);
1548 }
1549 608 success = true;
1550 }
1551 10 return success;
1552
2/4
✓ Branch 2 taken 14 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 14 times.
✗ Branch 6 not taken.
 24 });
1553 }
1554
1555 38 Transform decompose_NPhasedX() {
1556 38 return Transform([](Circuit &circ) {
1557 38 VertexList bin;
1558 38 bool success = false;
1559
1560
7/8
✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 522 times.
✓ Branch 6 taken 38 times.
✓ Branch 8 taken 522 times.
✓ Branch 9 taken 38 times.
✓ Branch 11 taken 38 times.
✓ Branch 12 taken 38 times.
 598 BGL_FORALL_VERTICES(v, circ.dag, DAG) {
1561
3/4
✓ Branch 1 taken 522 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 63 times.
✓ Branch 4 taken 459 times.
2/2
✓ Decision 'true' taken 63 times.
✓ Decision 'false' taken 459 times.
 522 if (circ.get_OpType_from_Vertex(v) == OpType::NPhasedX) {
1562
2/4
✓ Branch 1 taken 63 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 63 times.
✗ Branch 5 not taken.
 63 Gate_ptr g = as_gate_ptr(circ.get_Op_ptr_from_Vertex(v));
1563
1/2
✓ Branch 2 taken 63 times.
✗ Branch 3 not taken.
 63 unsigned n = g->n_qubits();
1564
1/2
✓ Branch 2 taken 63 times.
✗ Branch 3 not taken.
 63 Circuit sub(n);
1565
1566
2/2
✓ Branch 0 taken 149 times.
✓ Branch 1 taken 63 times.
2/2
✓ Decision 'true' taken 149 times.
✓ Decision 'false' taken 63 times.
 212 for (unsigned i = 0; i < n; ++i) {
1567
3/6
✓ Branch 3 taken 149 times.
✗ Branch 4 not taken.
✓ Branch 7 taken 149 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 149 times.
✗ Branch 11 not taken.
 149 sub.add_op<unsigned>(OpType::PhasedX, g->get_params(), {i});
1568 }
1569
1/2
✓ Branch 1 taken 63 times.
✗ Branch 2 not taken.
 63 circ.substitute(sub, v, Circuit::VertexDeletion::No);
1570
1/2
✓ Branch 1 taken 63 times.
✗ Branch 2 not taken.
 63 bin.push_back(v);
1571 63 success = true;
1572 63 }
1573 }
1574
1/2
✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
 38 circ.remove_vertices(
1575 bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
1576 38 return success;
1577
1/2
✓ Branch 2 taken 38 times.
✗ Branch 3 not taken.
 76 });
1578 }
1579
1580 ///////////////////////////////
1581 // GlobalisePhasedX //
1582 ///////////////////////////////
1583
1584 static unsigned n_distinct_beta(const Circuit &circ, const OptVertexVec &gates);
1585 template <typename T>
1586 static bool all_equal(const std::vector<T> &vs);
1587
1588 // Any PhasedX or NPhasedX gate is replaced by an NPhasedX that is global
1589 45 Transform globalise_PhasedX(bool squash) {
1590 // The key bit: choose the decomposition strategy depending on the current
1591 // beta angles.
1592 //
1593 // Given the set of PhasedX gates to synthesise, choose which decomposition
1594 // strategy. Valid strategies are 0, 1, 2, corresponding to the number of
1595 // NPhasedX gates to be inserted.
1596 //
1597 // The current strategy is rather simple: it chooses to insert a single
1598 // NPhasedX whenever it would solve the current problem and there are further
1599 // PhasedX left (meaning that the rest of the computation can be deferred till
1600 // later), otherwise inserts 2x PhasedX.
1601 37 auto choose_strategy = [](const PhasedXFrontier &frontier, unsigned n_target,
1602 unsigned n_all) {
1603
2/4
✓ Branch 0 taken 37 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 37 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 37 times.
 37 if (n_all == 0 || n_target == 0) {
1604 ✗ return 0;
1605 }
1606
4/4
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 24 times.
✓ Branch 2 taken 5 times.
✓ Branch 3 taken 8 times.
2/2
✓ Decision 'true' taken 5 times.
✓ Decision 'false' taken 32 times.
 37 if (n_target == 1 && n_all == 1) {
1607 5 return 1;
1608 }
1609
6/6
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 24 times.
✓ Branch 3 taken 6 times.
✓ Branch 4 taken 2 times.
✓ Branch 5 taken 6 times.
✓ Branch 6 taken 26 times.
2/2
✓ Decision 'true' taken 6 times.
✓ Decision 'false' taken 26 times.
 32 if (n_target == 1 && frontier.are_phasedx_left()) {
1610 6 return 1;
1611 }
1612 26 return 2;
1613 };
1614
1615 // the actual transform
1616 301 return Transform([squash, choose_strategy](Circuit &circ) {
1617 // if we squash, we start by removing all NPhasedX gates
1618
2/2
✓ Branch 0 taken 25 times.
✓ Branch 1 taken 20 times.
2/2
✓ Decision 'true' taken 25 times.
✓ Decision 'false' taken 20 times.
 45 if (squash) {
1619
2/4
✓ Branch 1 taken 25 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 25 times.
✗ Branch 5 not taken.
 25 Transforms::decompose_NPhasedX().apply(circ);
1620 }
1621
1622
2/4
✓ Branch 2 taken 45 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 45 times.
✗ Branch 6 not taken.
 45 std::vector<unsigned> range_qbs(circ.n_qubits());
1623 45 std::iota(range_qbs.begin(), range_qbs.end(), 0);
1624
1/2
✓ Branch 1 taken 45 times.
✗ Branch 2 not taken.
 45 PhasedXFrontier frontier(circ);
1625
1626 // find a total ordering of boundary gates (aka non-NPhasedX multi-qb gates)
1627 707 auto is_boundary = [&circ](Vertex v) {
1628
1/2
✓ Branch 1 taken 707 times.
✗ Branch 2 not taken.
 707 Op_ptr op = circ.get_Op_ptr_from_Vertex(v);
1629
1/2
✓ Branch 2 taken 707 times.
✗ Branch 3 not taken.
 1414 return PhasedXFrontier::is_interval_boundary(op);
1630 707 };
1631 // get a lexicographic ordering of boundary vertices
1632
1/2
✓ Branch 1 taken 45 times.
✗ Branch 2 not taken.
 45 auto vertices_in_order = circ.vertices_in_order();
1633
2/4
✓ Branch 1 taken 45 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 45 times.
✗ Branch 5 not taken.
 45 auto r = vertices_in_order | boost::adaptors::filtered(is_boundary);
1634
3/6
✓ Branch 2 taken 45 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 45 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 45 times.
✗ Branch 9 not taken.
 90 OptVertexVec boundary_gates(r.begin(), r.end());
1635 // Add sentinel to process the gates after last boundary_gate.
1636 // This is required to force flush the frontier after the last multi-qubit
1637 // gate.
1638 45 OptVertex optv;
1639
1/2
✓ Branch 1 taken 45 times.
✗ Branch 2 not taken.
 45 boundary_gates.push_back(optv);
1640
1641 // whether transform is successful (always true if squash=true)
1642 45 bool success = squash;
1643
1644 // Loop through each multi-qb gate.
1645 // At each iteration, decide how to decompose the single-qb gates
1646 // immediately preceding the current multi-qb gate into global gates.
1647 //
1648 // The rationale: defer any computation until just before the next multi-qb
1649 // gate. At that point, the single-qb gates on the qubits where the multi-qb
1650 // gate is acting HAVE TO be decomposed. Figure out how to do that and take
1651 // care of the garbage you might have created on other qubits at a later
1652 // point.
1653
1654
2/2
✓ Branch 5 taken 97 times.
✓ Branch 6 taken 45 times.
2/2
✓ Decision 'true' taken 97 times.
✓ Decision 'false' taken 45 times.
 142 for (OptVertex v : boundary_gates) {
1655 // the qubits whose intervals must be decomposed into global gates
1656 97 std::set<unsigned> curr_qubits;
1657 while (true) {
1658
2/2
✓ Branch 1 taken 95 times.
✓ Branch 2 taken 87 times.
2/2
✓ Decision 'true' taken 95 times.
✓ Decision 'false' taken 87 times.
 182 if (v) {
1659
1/2
✓ Branch 2 taken 95 times.
✗ Branch 3 not taken.
 95 curr_qubits = frontier.qubits_ending_in(*v);
1660 } else {
1661 87 curr_qubits.clear();
1662
3/4
✓ Branch 1 taken 343 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 256 times.
✓ Branch 4 taken 87 times.
0/1
? Decision couldn't be analyzed.
 343 for (unsigned i = 0; i < circ.n_qubits(); ++i) {
1663
1/2
✓ Branch 2 taken 256 times.
✗ Branch 3 not taken.
 256 curr_qubits.insert(curr_qubits.end(), i);
1664 }
1665 }
1666
2/2
✓ Branch 0 taken 90 times.
✓ Branch 1 taken 92 times.
2/2
✓ Decision 'true' taken 90 times.
✓ Decision 'false' taken 92 times.
 182 if (squash) {
1667
1/2
✓ Branch 1 taken 90 times.
✗ Branch 2 not taken.
 90 frontier.squash_intervals();
1668 }
1669
1/2
✓ Branch 1 taken 182 times.
✗ Branch 2 not taken.
 182 OptVertexVec all_phasedx = frontier.get_all_beta_vertices();
1670 182 OptVertexVec curr_phasedx;
1671
2/2
✓ Branch 5 taken 446 times.
✓ Branch 6 taken 182 times.
2/2
✓ Decision 'true' taken 446 times.
✓ Decision 'false' taken 182 times.
 628 for (unsigned q : curr_qubits) {
1672
1/2
✓ Branch 2 taken 446 times.
✗ Branch 3 not taken.
 446 curr_phasedx.push_back(all_phasedx[q]);
1673 }
1674
1675
3/4
✓ Branch 1 taken 182 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 97 times.
✓ Branch 4 taken 85 times.
2/2
✓ Decision 'true' taken 97 times.
✓ Decision 'false' taken 85 times.
 182 if (all_nullopt(curr_phasedx)) {
1676 // there is nothing to decompose anymore, move to next boundary_gate
1677 97 break;
1678 }
1679
3/4
✓ Branch 1 taken 85 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 11 times.
✓ Branch 4 taken 74 times.
2/2
✓ Decision 'true' taken 11 times.
✓ Decision 'false' taken 74 times.
 85 if (all_equal(all_phasedx)) {
1680 // this is already a global NPhasedX gate, leave untouched
1681
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 frontier.skip_global_gates(1);
1682 11 continue;
1683 }
1684
1685 // find best decomposition strategy
1686
1/2
✓ Branch 1 taken 74 times.
✗ Branch 2 not taken.
 74 unsigned n_curr_betas = n_distinct_beta(circ, curr_phasedx);
1687
1/2
✓ Branch 1 taken 74 times.
✗ Branch 2 not taken.
 74 unsigned n_all_betas = n_distinct_beta(circ, all_phasedx);
1688 unsigned strategy;
1689
2/2
✓ Branch 0 taken 37 times.
✓ Branch 1 taken 37 times.
2/2
✓ Decision 'true' taken 37 times.
✓ Decision 'false' taken 37 times.
 74 if (squash) {
1690
1/2
✓ Branch 1 taken 37 times.
✗ Branch 2 not taken.
 37 strategy = choose_strategy(frontier, n_curr_betas, n_all_betas);
1691 } else {
1692 // if we don't squash we decompose each NPhasedX with 2x global
1693 37 strategy = 2;
1694 }
1695
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 11 times.
✓ Branch 2 taken 63 times.
✗ Branch 3 not taken.
 74 switch (strategy) {
1696
0/1
✗ Decision 'true' not taken.
 ✗ case 0:
1697 // do nothing
1698 ✗ break;
1699
0/1
✗ Decision 'true' not taken.
 11 case 1:
1700 // insert one single global NPhasedX
1701 TKET_ASSERT(curr_qubits.size() > 0);
1702
1/2
✓ Branch 3 taken 11 times.
✗ Branch 4 not taken.
 11 frontier.insert_1_phasedx(*(curr_qubits.begin()));
1703 11 success = true;
1704 11 break;
1705
0/1
✗ Decision 'true' not taken.
 63 case 2:
1706 // insert two global NPhasedX
1707
1/2
✓ Branch 1 taken 63 times.
✗ Branch 2 not taken.
 63 frontier.insert_2_phasedx();
1708 63 success = true;
1709 63 break;
1710
0/1
✗ Decision 'true' not taken.
 ✗ default:
1711 TKET_ASSERT(!"Invalid strategy in replace_non_global_phasedx");
1712 }
1713
6/6
✓ Branch 1 taken 74 times.
✓ Branch 2 taken 97 times.
✓ Branch 3 taken 11 times.
✓ Branch 5 taken 74 times.
✓ Branch 6 taken 97 times.
✓ Branch 7 taken 11 times.
 375 }
1714
2/2
✓ Branch 1 taken 52 times.
✓ Branch 2 taken 45 times.
2/2
✓ Decision 'true' taken 52 times.
✓ Decision 'false' taken 45 times.
 97 if (v) {
1715
1/2
✓ Branch 2 taken 52 times.
✗ Branch 3 not taken.
 52 frontier.next_multiqb(*v);
1716 }
1717 97 }
1718 TKET_ASSERT(frontier.is_finished());
1719
1720
2/4
✓ Branch 1 taken 45 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 45 times.
✗ Branch 5 not taken.
 45 success |= absorb_Rz_NPhasedX().apply(circ);
1721
1722 45 return success;
1723
1/2
✓ Branch 2 taken 45 times.
✗ Branch 3 not taken.
 90 });
1724 }
1725
1726 // The number of distinct beta angles in `gates`.
1727 //
1728 // Performs O(n^2) pairwise equivalence comparisons between expressions to
1729 // handle symbolic variables and floating point errors
1730 148 unsigned n_distinct_beta(const Circuit &circ, const OptVertexVec &gates) {
1731 148 std::vector<Expr> vals;
1732
1733 // collect all epxressions
1734
2/2
✓ Branch 5 taken 436 times.
✓ Branch 6 taken 148 times.
2/2
✓ Decision 'true' taken 436 times.
✓ Decision 'false' taken 148 times.
 584 for (OptVertex v : gates) {
1735
2/2
✓ Branch 1 taken 304 times.
✓ Branch 2 taken 132 times.
0/1
? Decision couldn't be analyzed.
 436 if (v) {
1736
3/6
✓ Branch 2 taken 304 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 304 times.
✗ Branch 7 not taken.
✓ Branch 10 taken 304 times.
✗ Branch 11 not taken.
 608 Expr angle = circ.get_Op_ptr_from_Vertex(*v)->get_params()[0];
1737
1/2
✓ Branch 1 taken 304 times.
✗ Branch 2 not taken.
 304 vals.push_back(angle);
1738 304 } else {
1739
2/4
✓ Branch 1 taken 132 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 132 times.
✗ Branch 5 not taken.
 132 vals.push_back(0.);
1740 }
1741 }
1742
1743 148 unsigned n_distinct = 0;
1744
1745 // perform pairwise equivalence checks
1746
2/2
✓ Branch 1 taken 436 times.
✓ Branch 2 taken 148 times.
2/2
✓ Decision 'true' taken 436 times.
✓ Decision 'false' taken 148 times.
 584 for (unsigned i = 0; i < vals.size(); ++i) {
1747 436 bool is_unique = true;
1748
2/2
✓ Branch 1 taken 358 times.
✓ Branch 2 taken 284 times.
2/2
✓ Decision 'true' taken 358 times.
✓ Decision 'false' taken 284 times.
 642 for (unsigned j = i + 1; j < vals.size(); ++j) {
1749
3/4
✓ Branch 3 taken 358 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 152 times.
✓ Branch 6 taken 206 times.
2/2
✓ Decision 'true' taken 152 times.
✓ Decision 'false' taken 206 times.
 358 if (equiv_expr(vals[i], vals[j])) {
1750 152 is_unique = false;
1751 152 break;
1752 }
1753 }
1754 436 n_distinct += is_unique;
1755 }
1756 148 return n_distinct;
1757 148 }
1758
1759 template <typename T>
1760 85 bool all_equal(const std::vector<T> &vs) {
1761
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 85 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 85 times.
 85 if (vs.empty()) {
1762 ✗ return true;
1763 }
1764 85 T front = vs.front();
1765
2/2
✓ Branch 5 taken 214 times.
✓ Branch 6 taken 11 times.
2/2
✓ Decision 'true' taken 214 times.
✓ Decision 'false' taken 11 times.
 225 for (auto v : vs) {
1766
2/2
✓ Branch 1 taken 74 times.
✓ Branch 2 taken 140 times.
2/2
✓ Decision 'true' taken 74 times.
✓ Decision 'false' taken 140 times.
 214 if (front != v) {
1767 74 return false;
1768 }
1769 }
1770 11 return true;
1771 }
1772
1773 /* naive decomposition - there are cases we can do better if we can eg. ignore
1774 * phase */
1775 15 Transform decomp_CCX() {
1776 15 return Transform([](Circuit &circ) {
1777
1/2
✓ Branch 2 taken 15 times.
✗ Branch 3 not taken.
 15 const Op_ptr ccx = get_op_ptr(OpType::CCX);
1778
2/4
✓ Branch 2 taken 15 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 15 times.
✗ Branch 6 not taken.
 30 return circ.substitute_all(CircPool::CCX_normal_decomp(), ccx);
1779
1/2
✓ Branch 2 taken 15 times.
✗ Branch 3 not taken.
 30 });
1780 }
1781
1782 10 Transform decomp_controlled_Rys() {
1783 10 return Transform([](Circuit &circ) {
1784
2/4
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 10 times.
✗ Branch 5 not taken.
 10 bool success = decomp_CCX().apply(circ);
1785
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 auto [vit, vend] = boost::vertices(circ.dag);
1786
2/2
✓ Branch 1 taken 100 times.
✓ Branch 2 taken 9 times.
2/2
✓ Decision 'true' taken 100 times.
✓ Decision 'false' taken 9 times.
 109 for (auto next = vit; vit != vend; vit = next) {
1787 100 ++next;
1788 100 Vertex v = *vit;
1789
1/2
✓ Branch 1 taken 100 times.
✗ Branch 2 not taken.
 100 const Op_ptr op = circ.get_Op_ptr_from_Vertex(v);
1790
1/2
✓ Branch 1 taken 100 times.
✗ Branch 2 not taken.
 100 unsigned arity = circ.n_in_edges(v);
1791
2/2
✓ Branch 2 taken 9 times.
✓ Branch 3 taken 91 times.
2/2
✓ Decision 'true' taken 9 times.
✓ Decision 'false' taken 91 times.
 100 if (op->get_type() == OpType::CnRy) {
1792 9 success = true;
1793
2/2
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 1 times.
 10 Circuit rep = CircPool::CnRy_normal_decomp(op, arity);
1794
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 EdgeVec inedges = circ.get_in_edges(v);
1795
3/6
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 8 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 8 times.
✗ Branch 9 not taken.
 16 Subcircuit final_sub{inedges, circ.get_all_out_edges(v), {v}};
1796
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 circ.substitute(rep, final_sub, Circuit::VertexDeletion::Yes);
1797 8 }
1798 100 }
1799 9 return success;
1800
1/2
✓ Branch 2 taken 10 times.
✗ Branch 3 not taken.
 10 });
1801 }
1802
1803 3 Transform decomp_arbitrary_controlled_gates() {
1804 static const std::set<OpType> cn_gate_set = {
1805
4/8
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 2 times.
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
 3 OpType::CCX, OpType::CnX, OpType::CnRy, OpType::CnZ, OpType::CnY};
1806 3 std::set<OpType> all_gates;
1807
2/4
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 3 times.
✗ Branch 6 not taken.
 6 std::copy(
1808
2/4
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 3 times.
✗ Branch 6 not taken.
 3 all_gate_types().begin(), all_gate_types().end(),
1809 std::inserter(all_gates, all_gates.end()));
1810 3 OpTypeSet allowed_gate_set;
1811
2/4
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
✓ Branch 9 taken 3 times.
✗ Branch 10 not taken.
 3 std::set_difference(
1812 all_gates.begin(), all_gates.end(), cn_gate_set.begin(),
1813 cn_gate_set.end(),
1814 std::inserter(allowed_gate_set, allowed_gate_set.begin()));
1815
2/4
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 3 times.
✗ Branch 6 not taken.
 6 return rebase_factory(allowed_gate_set, CircPool::CX(), CircPool::tk1_to_tk1);
1816 3 }
1817
1818 } // namespace Transforms
1819
1820 } // namespace tket
1821