GCC Code Coverage Report

Directory: ./
File: Circuit/ControlledGates.cpp
Date: 2022-10-15 05:10:18
Warnings: 10 unchecked decisions!
Exec Total Coverage
Lines: 638 681 93.7%
Functions: 20 20 100.0%
Branches: 937 1737 53.9%
Decisions: 229 286 80.1%
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 <math.h>
16
17 #include <numeric>
18 #include <optional>
19
20 #include "Circuit/CircPool.hpp"
21 #include "Circuit/CircUtils.hpp"
22 #include "Circuit/DAGDefs.hpp"
23 #include "Gate/GatePtr.hpp"
24 #include "Gate/Rotation.hpp"
25 #include "OpType/OpType.hpp"
26 #include "Utils/EigenConfig.hpp"
27 #include "Utils/HelperFunctions.hpp"
28
29 namespace tket {
30
31 namespace CircPool {
32
33 /* all of these methods are from https://arxiv.org/pdf/quant-ph/9503016.pdf
34 or
35 https://algassert.com/circuits/2015/06/05/Constructing-Large-Controlled-Nots.html
36 */
37
38 typedef std::vector<std::pair<Edge, Vertex>>
39 candidate_t; // each CnX candidate to decompose needs a spare wire to put
40 // some extra controls on
41
42 static Circuit lemma72(unsigned control_m); // rule lemma 7.2
43 static void lemma73(
44 Circuit& circ, const std::pair<Edge, Vertex>& pairy); // rule lemma 7.3
45
46 // `n` = size of incrementer, circuit returned is of size `n+1`
47 /* this is slightly less efficient than perhaps it could be -- asymptotically it
48 is still good. In an ideal world, this would decompose the incrementers
49 smarter for the "even" case */
50 16 Circuit incrementer_borrow_1_qubit(unsigned n) {
51 16 bool is_odd = n % 2;
52
1/2
✓ Branch 2 taken 16 times.
✗ Branch 3 not taken.
 16 Circuit circ(n + 1);
53
2/2
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 9 times.
2/2
✓ Decision 'true' taken 7 times.
✓ Decision 'false' taken 9 times.
 16 if (n < 6) {
54
5/8
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 5 times.
✓ Branch 5 taken 2 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 2 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 2 times.
✗ Branch 12 not taken.
1/2
✓ Decision 'true' taken 7 times.
✗ Decision 'false' not taken.
 7 if (n > 4) circ.append_qubits(C4X_normal_decomp(), {0, 1, 2, 3, 4});
55
5/8
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 4 times.
✓ Branch 5 taken 3 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 3 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 3 times.
✗ Branch 12 not taken.
1/2
✓ Decision 'true' taken 7 times.
✗ Decision 'false' not taken.
 7 if (n > 3) circ.append_qubits(C3X_normal_decomp(), {0, 1, 2, 3});
56
4/6
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 3 times.
✓ Branch 5 taken 4 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 4 times.
✗ Branch 9 not taken.
1/2
✓ Decision 'true' taken 7 times.
✗ Decision 'false' not taken.
 7 if (n > 2) circ.add_op<unsigned>(OpType::CCX, {0, 1, 2});
57
4/6
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 2 times.
✓ Branch 5 taken 5 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 5 times.
✗ Branch 9 not taken.
1/2
✓ Decision 'true' taken 7 times.
✗ Decision 'false' not taken.
 7 if (n > 1) circ.add_op<unsigned>(OpType::CX, {0, 1});
58
4/6
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 1 times.
✓ Branch 5 taken 6 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 6 times.
✗ Branch 9 not taken.
1/2
✓ Decision 'true' taken 7 times.
✗ Decision 'false' not taken.
 7 if (n > 0) circ.add_op<unsigned>(OpType::X, {0});
59 7 return circ;
60 }
61 unsigned j;
62 unsigned k;
63 // j is bottom qubits, k is top qubits
64 // k + j = n + 1 (total no. of qbs)
65
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 5 times.
2/2
✓ Decision 'true' taken 4 times.
✓ Decision 'false' taken 5 times.
 9 if (is_odd) {
66 /* if the number of bits we are incrementing is odd, we can just split the
67 incrementer in 2 and use the `incrementer_borrow_n_qubits` method twice */
68 4 j = (n + 1) / 2, k = (n + 1) / 2;
69 } else {
70 /* otherwise, we will also have to pull out a cnx */
71 5 j = n / 2 + 1, k = n / 2;
72 }
73
74
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 Circuit top_incrementer = incrementer_borrow_n_qubits(k);
75
1/2
✓ Branch 2 taken 9 times.
✗ Branch 3 not taken.
 9 std::vector<unsigned> top_qbs(2 * k);
76
2/2
✓ Branch 0 taken 37 times.
✓ Branch 1 taken 9 times.
2/2
✓ Decision 'true' taken 37 times.
✓ Decision 'false' taken 9 times.
 46 for (unsigned i = 0; i != k; ++i) {
77 37 top_qbs[2 * i] = i + k; // borrowed qubits
78 37 top_qbs[2 * i + 1] = i; // qbs we are trying to increment
79 }
80
81
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 Circuit cnx_top;
82 9 std::vector<unsigned> cnx1_qbs;
83
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 7 times.
2/2
✓ Decision 'true' taken 2 times.
✓ Decision 'false' taken 7 times.
 9 if (k == 3) { // code is unreachable if k<3
84
2/4
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
 2 cnx_top = C3X_normal_decomp();
85
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 cnx1_qbs = {0, 1, 2, n};
86
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 3 times.
2/2
✓ Decision 'true' taken 4 times.
✓ Decision 'false' taken 3 times.
 7 } else if (k == 4) {
87
2/4
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
 4 cnx_top = C4X_normal_decomp();
88
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 cnx1_qbs = {0, 1, 2, 3, n};
89 } else {
90
2/4
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3 times.
✗ Branch 5 not taken.
 3 cnx_top = lemma72(k); // k controls on cnx
91 3 cnx1_qbs.resize(
92
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 2 * k - 2); // size of replacement using borrowed qbs = 2*k-1
93 3 std::iota(cnx1_qbs.begin(), cnx1_qbs.end(), 0);
94
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 cnx1_qbs.push_back(n); // target is last qubit
95 }
96
97
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 Circuit bottom_incrementer;
98 9 std::vector<unsigned> bot_qbs;
99
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 5 times.
2/2
✓ Decision 'true' taken 4 times.
✓ Decision 'false' taken 5 times.
 9 if (is_odd) {
100
2/4
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
 4 bottom_incrementer = incrementer_borrow_n_qubits(j);
101
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 bot_qbs.resize(2 * j);
102
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 4 times.
2/2
✓ Decision 'true' taken 18 times.
✓ Decision 'false' taken 4 times.
 22 for (unsigned i = 0; i != j; ++i) {
103 18 bot_qbs[2 * i] = i; // 0,2,4...n-1 //borrowed qubits
104
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 4 times.
2/2
✓ Decision 'true' taken 14 times.
✓ Decision 'false' taken 4 times.
 18 if (i != 0)
105 14 bot_qbs[2 * i + 1] =
106 14 i + j -
107 1; // 3,5...n //other qbs we are actually trying to increment
108 }
109 4 bot_qbs[1] = n; // incremented qubit 0 in incrementer is bottom one
110 } else {
111
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 3 times.
2/2
✓ Decision 'true' taken 2 times.
✓ Decision 'false' taken 3 times.
 5 if (j == 4) { // code is unreachable if j<4
112
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 bottom_incrementer.add_blank_wires(4);
113
3/6
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 2 times.
✗ Branch 10 not taken.
 2 bottom_incrementer.append_qubits(C3X_normal_decomp(), {0, 1, 2, 3});
114
2/4
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
 2 bottom_incrementer.add_op<unsigned>(OpType::CCX, {0, 1, 2});
115
2/4
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
 2 bottom_incrementer.add_op<unsigned>(OpType::CX, {0, 1});
116
2/4
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
 2 bottom_incrementer.add_op<unsigned>(OpType::X, {0});
117
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 bot_qbs = {n, n - 3, n - 2, n - 1};
118
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 1 times.
2/2
✓ Decision 'true' taken 2 times.
✓ Decision 'false' taken 1 times.
 3 } else if (j == 5) {
119
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 bottom_incrementer.add_blank_wires(5);
120
3/6
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 2 times.
✗ Branch 10 not taken.
 2 bottom_incrementer.append_qubits(C4X_normal_decomp(), {0, 1, 2, 3, 4});
121
3/6
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 2 times.
✗ Branch 10 not taken.
 2 bottom_incrementer.append_qubits(C3X_normal_decomp(), {0, 1, 2, 3});
122
2/4
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
 2 bottom_incrementer.add_op<unsigned>(OpType::CCX, {0, 1, 2});
123
2/4
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
 2 bottom_incrementer.add_op<unsigned>(OpType::CX, {0, 1});
124
2/4
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
 2 bottom_incrementer.add_op<unsigned>(OpType::X, {0});
125
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 bot_qbs = {n, n - 4, n - 3, n - 2, n - 1};
126 } else {
127 // insert peeled-out cnx
128
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 Circuit cnx_bot = lemma72(j - 1);
129 std::vector<unsigned> cnx2_qbs(
130
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 1 2 * j - 3); // lemma 7.2 uses 2j-3 qubits for a (j-1)-controlled X
131
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 1 times.
2/2
✓ Decision 'true' taken 4 times.
✓ Decision 'false' taken 1 times.
 5 for (unsigned i = 0; i < j - 2; ++i) {
132 4 cnx2_qbs[i] = k + i;
133 }
134 1 cnx2_qbs[j - 2] = n; // replace the last control
135
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 1 times.
2/2
✓ Decision 'true' taken 3 times.
✓ Decision 'false' taken 1 times.
 4 for (unsigned i = 0; i < j - 3; ++i) {
136 3 cnx2_qbs[j + i - 1] = i;
137 }
138 1 cnx2_qbs[2 * j - 4] = n - 1; // the target of the peeled out cnx
139
140
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 1 circ.append_qubits(cnx_bot, cnx2_qbs);
141
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 2 bottom_incrementer = incrementer_borrow_n_qubits(
142
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 j - 1); // insert incrementer over remaining qubits
143
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 bot_qbs.resize(2 * j - 2);
144
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 1 times.
2/2
✓ Decision 'true' taken 5 times.
✓ Decision 'false' taken 1 times.
 6 for (unsigned i = 0; i != j - 1; ++i) {
145 5 bot_qbs[2 * i] = i; // 0,2,4...n-1 //borrowed qubits
146
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 1 times.
2/2
✓ Decision 'true' taken 4 times.
✓ Decision 'false' taken 1 times.
 5 if (i != 0)
147 4 bot_qbs[2 * i + 1] =
148 4 i + k -
149 1; // 3,5...n //other qbs we are actually trying to increment
150 }
151 1 bot_qbs[1] = n; // incremented qubit 0 in incrementer is bottom one
152 1 }
153 }
154
155
1/2
✓ Branch 2 taken 9 times.
✗ Branch 3 not taken.
 9 circ.append_qubits(bottom_incrementer, bot_qbs);
156
2/4
✓ Branch 3 taken 9 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 9 times.
✗ Branch 7 not taken.
 9 circ.add_op<unsigned>(
157 OpType::X,
158 {n}); // to convert controlled-incrementer to larger incrementer
159
4/6
✓ Branch 3 taken 33 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 33 times.
✗ Branch 7 not taken.
✓ Branch 11 taken 33 times.
✓ Branch 12 taken 9 times.
0/1
? Decision couldn't be analyzed.
 42 for (unsigned i = k; i != n; ++i) circ.add_op<unsigned>(OpType::CX, {n, i});
160
1/2
✓ Branch 2 taken 9 times.
✗ Branch 3 not taken.
 9 circ.append_qubits(cnx_top, cnx1_qbs);
161
4/4
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 4 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 8 times.
 9 if (!is_odd && j > 5) {
162 // insert peeled-out cnx
163
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 Circuit cnx_bot = lemma72(j - 1);
164
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 1 std::vector<unsigned> cnx2_qbs(2 * j - 3);
165
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 1 times.
2/2
✓ Decision 'true' taken 5 times.
✓ Decision 'false' taken 1 times.
 6 for (unsigned i = 0; i < j - 1; ++i) {
166 5 cnx2_qbs[i] = k + i;
167 }
168 1 cnx2_qbs[j - 2] = n; // the last control
169
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 1 times.
2/2
✓ Decision 'true' taken 3 times.
✓ Decision 'false' taken 1 times.
 4 for (unsigned i = 0; i < j - 3; ++i) {
170 3 cnx2_qbs[j + i - 1] = i;
171 }
172 1 cnx2_qbs[2 * j - 4] = n - 1; // the target of the peeled out cnx
173
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 1 circ.append_qubits(cnx_bot, cnx2_qbs);
174 1 }
175
1/2
✓ Branch 2 taken 9 times.
✗ Branch 3 not taken.
 9 circ.append_qubits(bottom_incrementer, bot_qbs);
176
2/4
✓ Branch 3 taken 9 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 9 times.
✗ Branch 7 not taken.
 9 circ.add_op<unsigned>(OpType::X, {n});
177
1/2
✓ Branch 2 taken 9 times.
✗ Branch 3 not taken.
 9 circ.append_qubits(cnx_top, cnx1_qbs);
178
4/6
✓ Branch 3 taken 33 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 33 times.
✗ Branch 7 not taken.
✓ Branch 11 taken 33 times.
✓ Branch 12 taken 9 times.
0/1
? Decision couldn't be analyzed.
 42 for (unsigned i = k; i != n; ++i) circ.add_op<unsigned>(OpType::CX, {n, i});
179
1/2
✓ Branch 2 taken 9 times.
✗ Branch 3 not taken.
 9 circ.append_qubits(top_incrementer, top_qbs);
180 9 return circ;
181 9 }
182
183 // an optimised version of
184 // https://algassert.com/circuits/2015/06/12/Constructing-Large-Increment-Gates.html
185 /* every second qubit (0,2,4...) is a borrowed qubit */
186 27 Circuit incrementer_borrow_n_qubits(unsigned n) {
187 27 const unsigned N = 2 * n;
188
1/2
✓ Branch 2 taken 27 times.
✗ Branch 3 not taken.
 27 Circuit circ(N);
189 /* deal with small cases where borrowing qubits is unnecessary */
190
2/2
✓ Branch 0 taken 23 times.
✓ Branch 1 taken 4 times.
2/2
✓ Decision 'true' taken 23 times.
✓ Decision 'false' taken 4 times.
 27 if (n < 6) {
191
5/8
✓ Branch 0 taken 7 times.
✓ Branch 1 taken 16 times.
✓ Branch 5 taken 7 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 7 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 7 times.
✗ Branch 12 not taken.
1/2
✓ Decision 'true' taken 23 times.
✗ Decision 'false' not taken.
 23 if (n > 4) circ.append_qubits(C4X_normal_decomp(), {1, 3, 5, 7, 9});
192
5/8
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 9 times.
✓ Branch 5 taken 14 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 14 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 14 times.
✗ Branch 12 not taken.
1/2
✓ Decision 'true' taken 23 times.
✗ Decision 'false' not taken.
 23 if (n > 3) circ.append_qubits(C3X_normal_decomp(), {1, 3, 5, 7});
193
4/6
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 3 times.
✓ Branch 5 taken 20 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 20 times.
✗ Branch 9 not taken.
1/2
✓ Decision 'true' taken 23 times.
✗ Decision 'false' not taken.
 23 if (n > 2) circ.add_op<unsigned>(OpType::CCX, {1, 3, 5});
194
4/6
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 2 times.
✓ Branch 5 taken 21 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 21 times.
✗ Branch 9 not taken.
1/2
✓ Decision 'true' taken 23 times.
✗ Decision 'false' not taken.
 23 if (n > 1) circ.add_op<unsigned>(OpType::CX, {1, 3});
195
4/6
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 1 times.
✓ Branch 5 taken 22 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 22 times.
✗ Branch 9 not taken.
1/2
✓ Decision 'true' taken 23 times.
✗ Decision 'false' not taken.
 23 if (n > 0) circ.add_op<unsigned>(OpType::X, {1});
196 23 return circ;
197 }
198
199
2/2
✓ Branch 0 taken 56 times.
✓ Branch 1 taken 4 times.
2/2
✓ Decision 'true' taken 56 times.
✓ Decision 'false' taken 4 times.
 60 for (unsigned i = 1; i < N; ++i) {
200
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 26 times.
2/2
✓ Decision 'true' taken 30 times.
✓ Decision 'false' taken 26 times.
 56 if (i % 2)
201
2/4
✓ Branch 3 taken 30 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 30 times.
✗ Branch 7 not taken.
 30 circ.add_op<unsigned>(OpType::CX, {0, i});
202 else
203
2/4
✓ Branch 3 taken 26 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 26 times.
✗ Branch 7 not taken.
 26 circ.add_op<unsigned>(OpType::X, {i});
204 }
205
206
2/4
✓ Branch 3 taken 4 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 4 times.
✗ Branch 7 not taken.
 4 circ.add_op<unsigned>(OpType::X, {N - 1});
207
208
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 4 times.
2/2
✓ Decision 'true' taken 26 times.
✓ Decision 'false' taken 4 times.
 30 for (unsigned i = 2; i < N; ++(++i)) {
209
1/2
✓ Branch 2 taken 26 times.
✗ Branch 3 not taken.
 26 std::vector<unsigned> ladder_down_qbs = {i - 2, i - 1, i};
210
2/4
✓ Branch 2 taken 26 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 26 times.
✗ Branch 6 not taken.
 26 circ.append_qubits(ladder_down(), ladder_down_qbs);
211 26 }
212
2/4
✓ Branch 3 taken 4 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 4 times.
✗ Branch 7 not taken.
 4 circ.add_op<unsigned>(OpType::CX, {N - 2, N - 1});
213
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 4 times.
2/2
✓ Decision 'true' taken 26 times.
✓ Decision 'false' taken 4 times.
 30 for (unsigned i = N - 2; i > 1; --(--i)) {
214
1/2
✓ Branch 2 taken 26 times.
✗ Branch 3 not taken.
 26 std::vector<unsigned> tof_up_qbs = {i - 2, i - 1, i};
215
1/2
✓ Branch 2 taken 26 times.
✗ Branch 3 not taken.
 26 circ.add_op<unsigned>(OpType::CCX, tof_up_qbs);
216 26 }
217
218
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 4 times.
2/2
✓ Decision 'true' taken 26 times.
✓ Decision 'false' taken 4 times.
 30 for (unsigned i = 2; i < N; ++(++i)) {
219
1/2
✓ Branch 2 taken 26 times.
✗ Branch 3 not taken.
 26 std::vector<unsigned> ladder_down_2_qbs = {i - 2, i - 1, i};
220
2/4
✓ Branch 2 taken 26 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 26 times.
✗ Branch 6 not taken.
 26 circ.append_qubits(ladder_down_2(), ladder_down_2_qbs);
221 26 }
222
2/4
✓ Branch 3 taken 4 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 4 times.
✗ Branch 7 not taken.
 4 circ.add_op<unsigned>(OpType::CX, {N - 2, N - 1});
223
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 4 times.
2/2
✓ Decision 'true' taken 26 times.
✓ Decision 'false' taken 4 times.
 30 for (unsigned i = N - 2; i > 1; --(--i)) {
224
1/2
✓ Branch 2 taken 26 times.
✗ Branch 3 not taken.
 26 std::vector<unsigned> ladder_up_qbs = {i - 2, i - 1, i};
225
2/4
✓ Branch 2 taken 26 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 26 times.
✗ Branch 6 not taken.
 26 circ.append_qubits(ladder_up(), ladder_up_qbs);
226 26 }
227
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 4 times.
2/2
✓ Decision 'true' taken 30 times.
✓ Decision 'false' taken 4 times.
 34 for (unsigned i = 1; i < N; ++(++i))
228
2/4
✓ Branch 3 taken 30 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 30 times.
✗ Branch 7 not taken.
 30 circ.add_op<unsigned>(OpType::CX, {0, i});
229 4 return circ;
230 }
231
232 // decompose CnX gate using
233 // https://algassert.com/circuits/2015/06/22/Using-Quantum-Gates-instead-of-Ancilla-Bits.html
234 // `n` = no. of controls
235 26 Circuit CnX_normal_decomp(unsigned n) {
236 /* handle low qb edge cases */
237 bool insert_c4xs; // dictate whether to add C4Xs or n>4 controlled Xs
238 // when bootstrapping
239
6/7
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 3 times.
✓ Branch 3 taken 9 times.
✓ Branch 4 taken 7 times.
✓ Branch 5 taken 1 times.
✓ Branch 6 taken 4 times.
 26 switch (n) {
240
0/1
✗ Decision 'true' not taken.
 ✗ case 0: {
241 ✗ return X();
242 }
243
1/1
✓ Decision 'true' taken 2 times.
 2 case 1: {
244
2/4
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
 2 return CX();
245 }
246
1/1
✓ Decision 'true' taken 3 times.
 3 case 2: {
247
2/4
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3 times.
✗ Branch 5 not taken.
 3 return CCX_normal_decomp();
248 }
249
1/1
✓ Decision 'true' taken 9 times.
 9 case 3: {
250
2/4
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 9 times.
✗ Branch 5 not taken.
 9 return C3X_normal_decomp();
251 }
252
1/1
✓ Decision 'true' taken 7 times.
 7 case 4: {
253
2/4
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 7 times.
✗ Branch 5 not taken.
 7 return C4X_normal_decomp();
254 }
255
1/1
✓ Decision 'true' taken 1 times.
 1 case 5: {
256 1 insert_c4xs = true;
257 1 break;
258 }
259
1/1
✓ Decision 'true' taken 4 times.
 4 default: {
260 4 insert_c4xs = false;
261 4 break;
262 }
263 }
264
265
1/2
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
 10 Circuit circ(n + 1);
266
1/2
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
 10 std::vector<unsigned> cnx_qbs(n - 1);
267 5 std::iota(cnx_qbs.begin(), cnx_qbs.end(), 0);
268
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 cnx_qbs.push_back(n);
269 // first, bootstrap an ancilla qubit
270
2/4
✓ Branch 3 taken 5 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 5 times.
✗ Branch 7 not taken.
 5 circ.add_op<unsigned>(OpType::H, {n});
271 Vertex cnx1;
272
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 4 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 4 times.
 5 if (insert_c4xs)
273
2/4
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
 1 circ.append_qubits(C4X_normal_decomp(), {cnx_qbs});
274 else {
275
1/2
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
 4 cnx1 = circ.add_op<unsigned>(
276 OpType::CnX,
277 {cnx_qbs}); /* the CnXs can be decomposed using lemma 7.3 */
278 }
279
2/4
✓ Branch 3 taken 5 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 5 times.
✗ Branch 7 not taken.
 5 circ.add_op<unsigned>(OpType::Tdg, {n});
280
2/4
✓ Branch 3 taken 5 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 5 times.
✗ Branch 7 not taken.
 5 Vertex cx = circ.add_op<unsigned>(OpType::CX, {n - 1, n});
281
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 1 times.
2/2
✓ Decision 'true' taken 4 times.
✓ Decision 'false' taken 1 times.
 5 if (!insert_c4xs) {
282
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 Edge e1 = circ.get_nth_in_edge(cx, 0);
283
1/2
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
 4 lemma73(circ, {e1, cnx1}); // replace first CnX using lemma 7.3
284 }
285
2/4
✓ Branch 3 taken 5 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 5 times.
✗ Branch 7 not taken.
 5 circ.add_op<unsigned>(OpType::T, {n});
286 Vertex cnx2;
287
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 4 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 4 times.
 5 if (insert_c4xs)
288
2/4
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
 1 circ.append_qubits(C4X_normal_decomp(), {cnx_qbs});
289 else {
290
1/2
✓ Branch 2 taken 4 times.
✗ Branch 3 not taken.
 4 cnx2 = circ.add_op<unsigned>(OpType::CnX, {cnx_qbs});
291 }
292
2/4
✓ Branch 3 taken 5 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 5 times.
✗ Branch 7 not taken.
 5 circ.add_op<unsigned>(OpType::Tdg, {n});
293
2/4
✓ Branch 3 taken 5 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 5 times.
✗ Branch 7 not taken.
 5 cx = circ.add_op<unsigned>(OpType::CX, {n - 1, n});
294
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 Edge e2 = circ.get_nth_in_edge(cx, 0);
295
3/4
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 1 times.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
1/2
✓ Decision 'true' taken 5 times.
✗ Decision 'false' not taken.
 5 if (!insert_c4xs) lemma73(circ, {e2, cnx2});
296
2/4
✓ Branch 3 taken 5 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 5 times.
✗ Branch 7 not taken.
 5 circ.add_op<unsigned>(OpType::T, {n});
297
2/4
✓ Branch 3 taken 5 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 5 times.
✗ Branch 7 not taken.
 5 circ.add_op<unsigned>(OpType::H, {n});
298
299 // add incremented shift pattern
300
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 10 Circuit incrementer = incrementer_borrow_1_qubit(n);
301
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 circ.append(incrementer);
302
303 // z rotation layer #1
304
1/2
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
 10 std::vector<Op_ptr> z_rots(n);
305 5 double angle = -0.25;
306
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 5 times.
2/2
✓ Decision 'true' taken 30 times.
✓ Decision 'false' taken 5 times.
 35 for (unsigned i = 0; i < n - 1; ++i) {
307 30 unsigned m = n - 1 - i;
308
2/4
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 30 times.
✗ Branch 5 not taken.
 30 z_rots[i] = get_op_ptr(OpType::Rz, angle);
309
2/4
✓ Branch 3 taken 30 times.
✗ Branch 4 not taken.
✓ Branch 7 taken 30 times.
✗ Branch 8 not taken.
 30 circ.add_op<unsigned>(z_rots[i], {m});
310 30 angle /= 2;
311 }
312
313 // decremented shift pattern
314
2/2
✓ Branch 0 taken 35 times.
✓ Branch 1 taken 5 times.
2/2
✓ Decision 'true' taken 35 times.
✓ Decision 'false' taken 5 times.
 40 for (unsigned i = 0; i < n; ++i) {
315
2/4
✓ Branch 3 taken 35 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 35 times.
✗ Branch 7 not taken.
 35 circ.add_op<unsigned>(OpType::X, {i});
316 }
317
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 circ.append(incrementer);
318
2/2
✓ Branch 0 taken 35 times.
✓ Branch 1 taken 5 times.
2/2
✓ Decision 'true' taken 35 times.
✓ Decision 'false' taken 5 times.
 40 for (unsigned i = 0; i < n; ++i) {
319
2/4
✓ Branch 3 taken 35 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 35 times.
✗ Branch 7 not taken.
 35 circ.add_op<unsigned>(OpType::X, {i});
320 }
321
322 // z rotation layer #2
323
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 5 times.
2/2
✓ Decision 'true' taken 30 times.
✓ Decision 'false' taken 5 times.
 35 for (unsigned i = 0; i < n - 1; ++i) {
324 30 unsigned m = n - 1 - i;
325
2/4
✓ Branch 3 taken 30 times.
✗ Branch 4 not taken.
✓ Branch 7 taken 30 times.
✗ Branch 8 not taken.
 30 Expr ang = z_rots[i]->get_params()[0];
326
4/8
✓ Branch 3 taken 30 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 30 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 30 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 30 times.
✗ Branch 13 not taken.
 30 circ.add_op<unsigned>(get_op_ptr(OpType::Rz, -ang), {m});
327 30 }
328
2/4
✓ Branch 3 taken 5 times.
✗ Branch 4 not taken.
✓ Branch 7 taken 5 times.
✗ Branch 8 not taken.
 10 Expr ang = z_rots[n - 2]->get_params()[0];
329
4/8
✓ Branch 3 taken 5 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 5 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 5 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 5 times.
✗ Branch 13 not taken.
 5 circ.add_op<unsigned>(get_op_ptr(OpType::Rz, -ang), {0});
330
331
1/2
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
 10 const Op_ptr ccx = get_op_ptr(OpType::CCX);
332
2/4
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 5 times.
✗ Branch 6 not taken.
 5 circ.substitute_all(CCX_normal_decomp(), ccx);
333
334
2/4
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 5 times.
✗ Branch 6 not taken.
 5 circ.add_phase(std::pow(0.5, n + 1));
335
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 return circ;
336 }
337
338 // unsigned -> which column the change is in
339 19478 static unsigned find_first_differing_val(
340 const std::deque<bool>& d1, const std::deque<bool>& d2) {
341 19478 unsigned N = d1.size();
342
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 19478 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 19478 times.
 19478 if (N != d2.size())
343 ✗ throw ControlDecompError(
344 "Error in `find_first_differing_val`: Deques are of differing "
345 ✗ "sizes");
346
1/2
✓ Branch 0 taken 35411 times.
✗ Branch 1 not taken.
1/2
✓ Decision 'true' taken 35411 times.
✗ Decision 'false' not taken.
 35411 for (unsigned i = 0; i < N; ++i) {
347
2/2
✓ Branch 2 taken 19478 times.
✓ Branch 3 taken 15933 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 35411 times.
 35411 if (d1[i] != d2[i]) return i;
348 }
349 ✗ throw ControlDecompError(
350 ✗ "Error in `find_first_differing_val`: No change between deques");
351 }
352
353 // optimal decomposition of CnRy and CnZ for 2 < n < 8 according to 1995
354 // paper... can do better with ZH calculus?
355 1517 static Circuit lemma71(
356 unsigned arity, const Circuit& v_rep, const Circuit& v_dg_rep) {
357 1517 unsigned m_controls = arity - 1;
358
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1517 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 1517 times.
 1517 if (m_controls < 2)
359 ✗ throw Unsupported(
360 "No point using Lemma 7.1 to decompose a gate with less than 2 "
361 ✗ "controls");
362
363
1/2
✓ Branch 1 taken 1517 times.
✗ Branch 2 not taken.
 1517 GrayCode gc = gen_graycode(m_controls);
364
365
1/2
✓ Branch 2 taken 1517 times.
✗ Branch 3 not taken.
 1517 Circuit rep(arity);
366
367 1517 unsigned control_qb = 0;
368 1517 unsigned last = 0;
369
4/8
✓ Branch 4 taken 1517 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1517 times.
✗ Branch 8 not taken.
✓ Branch 11 taken 3034 times.
✓ Branch 12 taken 1517 times.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
 6068 rep.append_with_map(
370
4/8
✓ Branch 1 taken 1517 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1517 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1517 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 1517 times.
✗ Branch 11 not taken.
 4551 v_rep, {{Qubit(0), Qubit(0)}, {Qubit(1), Qubit(m_controls)}});
371 // we ignore the 0...0 term, and the first one is always trivial
372 // so start from 2
373
2/2
✓ Branch 1 taken 19478 times.
✓ Branch 2 taken 1517 times.
2/2
✓ Decision 'true' taken 19478 times.
✓ Decision 'false' taken 1517 times.
 20995 for (unsigned i = 2; i < gc.size(); ++i) {
374
1/2
✓ Branch 3 taken 19478 times.
✗ Branch 4 not taken.
 19478 unsigned change = find_first_differing_val(gc[i], gc[i - 1]);
375
2/2
✓ Branch 2 taken 69454 times.
✓ Branch 3 taken 19478 times.
2/2
✓ Decision 'true' taken 69454 times.
✓ Decision 'false' taken 19478 times.
 88932 for (unsigned j = 1; j < gc[i].size(); ++j) {
376
2/2
✓ Branch 2 taken 38272 times.
✓ Branch 3 taken 31182 times.
2/2
✓ Decision 'true' taken 19478 times.
✓ Decision 'false' taken 49976 times.
 69454 if (gc[i][j] == 1) last = j;
377 }
378
2/2
✓ Branch 0 taken 15933 times.
✓ Branch 1 taken 3545 times.
2/2
✓ Decision 'true' taken 15933 times.
✓ Decision 'false' taken 3545 times.
 19478 if (change < control_qb) {
379
2/4
✓ Branch 3 taken 15933 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 15933 times.
✗ Branch 7 not taken.
 15933 rep.add_op<unsigned>(OpType::CX, {change, control_qb});
380 }
381
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 19478 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 19478 times.
 19478 if (change == control_qb) {
382 ✗ throw ControlDecompError("Error in graycode iteration");
383 }
384
2/2
✓ Branch 0 taken 3545 times.
✓ Branch 1 taken 15933 times.
2/2
✓ Decision 'true' taken 3545 times.
✓ Decision 'false' taken 15933 times.
 19478 if (change > control_qb) {
385
2/4
✓ Branch 3 taken 3545 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 3545 times.
✗ Branch 7 not taken.
 3545 rep.add_op<unsigned>(OpType::CX, {control_qb, change});
386 }
387
388
2/2
✓ Branch 0 taken 9739 times.
✓ Branch 1 taken 9739 times.
0/1
? Decision couldn't be analyzed.
 19478 if ((i % 2) == 0) {
389
4/8
✓ Branch 4 taken 9739 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 9739 times.
✗ Branch 8 not taken.
✓ Branch 11 taken 19478 times.
✓ Branch 12 taken 9739 times.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
 38956 rep.append_with_map(
390
4/8
✓ Branch 1 taken 9739 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 9739 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 9739 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 9739 times.
✗ Branch 11 not taken.
 29217 v_dg_rep, {{Qubit(0), Qubit(last)}, {Qubit(1), Qubit(m_controls)}});
391 } else
392
4/8
✓ Branch 4 taken 9739 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 9739 times.
✗ Branch 8 not taken.
✓ Branch 11 taken 19478 times.
✓ Branch 12 taken 9739 times.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
 38956 rep.append_with_map(
393
4/8
✓ Branch 1 taken 9739 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 9739 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 9739 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 9739 times.
✗ Branch 11 not taken.
 29217 v_rep, {{Qubit(0), Qubit(last)}, {Qubit(1), Qubit(m_controls)}});
394 19478 control_qb = last;
395 }
396
1/2
✓ Branch 1 taken 1517 times.
✗ Branch 2 not taken.
 1517 auto [vit, vend] = boost::vertices(rep.dag);
397 1517 VertexSet bin;
398
2/2
✓ Branch 1 taken 170632 times.
✓ Branch 2 taken 1517 times.
2/2
✓ Decision 'true' taken 170632 times.
✓ Decision 'false' taken 1517 times.
 172149 for (auto next = vit; vit != vend; vit = next) {
399 170632 ++next;
400 170632 Vertex v = *vit;
401
2/4
✓ Branch 1 taken 170632 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 170632 times.
✗ Branch 4 not taken.
1/2
✓ Decision 'true' taken 170632 times.
✗ Decision 'false' not taken.
 170632 if (!bin.contains(v)) {
402
1/2
✓ Branch 1 taken 170632 times.
✗ Branch 2 not taken.
 170632 Op_ptr op = rep.get_Op_ptr_from_Vertex(v);
403 170632 OpType optype = op->get_type();
404
7/8
✓ Branch 1 taken 170632 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 82463 times.
✓ Branch 4 taken 88169 times.
✓ Branch 5 taken 20995 times.
✓ Branch 6 taken 61468 times.
✓ Branch 7 taken 20995 times.
✓ Branch 8 taken 149637 times.
2/2
✓ Decision 'true' taken 41990 times.
✓ Decision 'false' taken 128642 times.
 170632 if (is_multi_qubit_type(optype) && optype != OpType::CX) {
405
2/4
✓ Branch 2 taken 20995 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 20995 times.
✗ Branch 6 not taken.
 41990 Circuit replacement = with_CX(as_gate_ptr(op));
406
1/2
✓ Branch 1 taken 20995 times.
✗ Branch 2 not taken.
 20995 rep.substitute(replacement, v, Circuit::VertexDeletion::No);
407
1/2
✓ Branch 1 taken 20995 times.
✗ Branch 2 not taken.
 20995 bin.insert(v);
408 20995 }
409 170632 }
410 }
411
1/2
✓ Branch 1 taken 1517 times.
✗ Branch 2 not taken.
 1517 rep.remove_vertices(
412 bin, Circuit::GraphRewiring::No, Circuit::VertexDeletion::Yes);
413 3034 return rep;
414 1517 }
415
416 //`control_m` = number of controls
417 61 static Circuit lemma72(unsigned control_m) {
418
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 61 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 61 times.
 61 if (control_m < 3)
419 ✗ throw Unsupported(
420 ✗ "Cannot decompose a gate with " + std::to_string(control_m) +
421 ✗ " controls using Lemma 7.2");
422 61 const unsigned n = 2 * control_m - 1;
423
424
1/2
✓ Branch 2 taken 61 times.
✗ Branch 3 not taken.
 61 Circuit ccx_circ(n);
425 61 unsigned diff = n - control_m;
426
2/2
✓ Branch 0 taken 89 times.
✓ Branch 1 taken 61 times.
2/2
✓ Decision 'true' taken 89 times.
✓ Decision 'false' taken 61 times.
 150 for (unsigned i = control_m - 1; i > 1; --i) {
427
2/4
✓ Branch 3 taken 89 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 89 times.
✗ Branch 7 not taken.
 89 ccx_circ.add_op<unsigned>(OpType::CCX, {i, i + diff - 1, i + diff});
428 }
429
2/4
✓ Branch 3 taken 61 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 61 times.
✗ Branch 7 not taken.
 61 ccx_circ.add_op<unsigned>(OpType::CCX, {0, 1, control_m});
430
2/2
✓ Branch 0 taken 89 times.
✓ Branch 1 taken 61 times.
2/2
✓ Decision 'true' taken 89 times.
✓ Decision 'false' taken 61 times.
 150 for (unsigned i = 2; i < control_m; ++i) {
431
2/4
✓ Branch 3 taken 89 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 89 times.
✗ Branch 7 not taken.
 89 ccx_circ.add_op<unsigned>(OpType::CCX, {i, i + diff - 1, i + diff});
432 }
433
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 61 times.
2/2
✓ Decision 'true' taken 28 times.
✓ Decision 'false' taken 61 times.
 89 for (unsigned i = control_m - 2; i > 1; --i) {
434
2/4
✓ Branch 3 taken 28 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 28 times.
✗ Branch 7 not taken.
 28 ccx_circ.add_op<unsigned>(OpType::CCX, {i, i + diff - 1, i + diff});
435 }
436
2/4
✓ Branch 3 taken 61 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 61 times.
✗ Branch 7 not taken.
 61 ccx_circ.add_op<unsigned>(OpType::CCX, {0, 1, control_m});
437
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 61 times.
2/2
✓ Decision 'true' taken 28 times.
✓ Decision 'false' taken 61 times.
 89 for (unsigned i = 2; i < control_m - 1; ++i) {
438
2/4
✓ Branch 3 taken 28 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 28 times.
✗ Branch 7 not taken.
 28 ccx_circ.add_op<unsigned>(OpType::CCX, {i, i + diff - 1, i + diff});
439 }
440
2/4
✓ Branch 1 taken 61 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 61 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 61 times.
 61 if (ccx_circ.count_gates(OpType::CCX) != 4 * (control_m - 2))
441 ✗ throw ControlDecompError("Error in Lemma 7.2: CCX gate count is incorrect");
442 61 return ccx_circ;
443 }
444
445 /* this is specifically for performing corollary 7.4 via lemma 7.3 & lemma 7.2 -
446 * optimal decomp of a CnX gate */
447 /* for corollary 7.4, n >= 7 */
448 // this is a decomposition of a CnX gate using one dirty ancilla
449 48 static void lemma73(Circuit& circ, const std::pair<Edge, Vertex>& pairy) {
450 48 Vertex original_cnx = pairy.second;
451 48 Edge original_spare_edge = pairy.first;
452
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 EdgeVec in_edges = circ.get_in_edges(original_cnx);
453 const unsigned N =
454 48 in_edges.size() + 1; // number of qubits in new circuit to replace
455
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 48 times.
 48 if (N < 5)
456 ✗ throw Unsupported(
457 ✗ "Lemma 7.3 cannot decompose CnX with n = " + std::to_string(N - 1));
458
459
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 EdgeVec out_edges = circ.get_all_out_edges(original_cnx);
460
461
1/2
✓ Branch 6 taken 48 times.
✗ Branch 7 not taken.
 48 in_edges.insert(in_edges.begin() + in_edges.size() - 1, original_spare_edge);
462
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 out_edges.insert(
463 48 out_edges.begin() + out_edges.size() - 1, original_spare_edge);
464
465
2/4
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 48 times.
✗ Branch 6 not taken.
 96 Subcircuit to_delete{in_edges, out_edges, {original_cnx}};
466 48 bool odd_N = N % 2;
467 48 unsigned m1 = (N + 1) / 2; // number of controls on the first type of CnX
468 48 unsigned m2 = N - m1 - 1; // number of controls on the second type of CnX
469
470 // make new circuit to substitute later
471
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 Circuit new_circ(N);
472
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 const Op_ptr cnx_op1 = get_op_ptr(OpType::CnX, std::vector<Expr>{}, m1 + 1);
473
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 const Op_ptr cnx_op2 = get_op_ptr(OpType::CnX, std::vector<Expr>{}, m2 + 1);
474
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 std::vector<unsigned> qbs_m1(m1 + 1);
475 48 std::iota(qbs_m1.begin(), qbs_m1.begin() + m1, 0);
476 48 qbs_m1[m1] = N - 1;
477
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 std::vector<unsigned> qbs_m2(m2 + 1);
478 48 std::iota(qbs_m2.begin(), qbs_m2.end(), N - (m2 + 1));
479
480 // add ladder of CnXs to the correct qubits
481
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 Vertex a = new_circ.add_op<unsigned>(cnx_op1, qbs_m1);
482
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 Vertex b = new_circ.add_op<unsigned>(cnx_op2, qbs_m2);
483
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 Vertex c = new_circ.add_op<unsigned>(cnx_op1, qbs_m1);
484
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 Vertex d = new_circ.add_op<unsigned>(cnx_op2, qbs_m2);
485
486 /* first, replace vertex a, putting circuit at back of new_circ */
487
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
 48 unsigned cutsize = odd_N ? N : N - 1;
488
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 EdgeVec cut1(cutsize);
489
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 VertexVec out_verts = new_circ.q_outputs();
490
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
0/1
? Decision couldn't be analyzed.
 48 if (odd_N) {
491
2/2
✓ Branch 0 taken 92 times.
✓ Branch 1 taken 24 times.
2/2
✓ Decision 'true' taken 92 times.
✓ Decision 'false' taken 24 times.
 116 for (unsigned i = 0; i < N - 2; ++i)
492
1/2
✓ Branch 2 taken 92 times.
✗ Branch 3 not taken.
 92 cut1[i] = new_circ.get_nth_in_edge(out_verts[i], 0);
493
1/2
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
 24 cut1[N - 2] = new_circ.get_nth_in_edge(out_verts[N - 1], 0);
494
1/2
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
 24 cut1[N - 1] = new_circ.get_nth_in_edge(out_verts[N - 2], 0);
495 } else {
496
2/2
✓ Branch 0 taken 132 times.
✓ Branch 1 taken 24 times.
2/2
✓ Decision 'true' taken 132 times.
✓ Decision 'false' taken 24 times.
 156 for (unsigned i = 0; i < cutsize; ++i)
497
1/2
✓ Branch 2 taken 132 times.
✗ Branch 3 not taken.
 132 cut1[i] = new_circ.get_nth_in_edge(out_verts[i], 0);
498 }
499
500
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 Circuit a_replacement;
501
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 48 times.
 48 if (m1 == 1) {
502 ✗ a_replacement = CX();
503
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 48 times.
 48 } else if (m1 == 2) {
504 ✗ a_replacement = CCX();
505 } else
506
2/4
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 48 times.
✗ Branch 5 not taken.
 48 a_replacement = lemma72(m1); // returns circuit of size 2*m1 - 1
507
1/2
✓ Branch 3 taken 48 times.
✗ Branch 4 not taken.
 48 new_circ.cut_insert(a_replacement, cut1);
508
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 new_circ.remove_vertex(
509 a, Circuit::GraphRewiring::Yes, Circuit::VertexDeletion::Yes);
510
511 48 VertexSet normal_decomp_vertices;
512
513
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 Circuit b_replacement;
514
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 30 times.
2/2
✓ Decision 'true' taken 18 times.
✓ Decision 'false' taken 30 times.
 48 if (m2 == 1) {
515
2/4
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 18 times.
✗ Branch 5 not taken.
 18 b_replacement = CX();
516
2/2
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 8 times.
2/2
✓ Decision 'true' taken 22 times.
✓ Decision 'false' taken 8 times.
 30 } else if (m2 == 2) {
517
2/4
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 22 times.
✗ Branch 5 not taken.
 22 b_replacement = CCX();
518 } else
519
2/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
 8 b_replacement = lemma72(m2); // returns circuit of size 2*m2 - 1
520
521
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 unsigned b_qubits = b_replacement.n_qubits();
522
523 // reassign cut to back of circuit
524
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 EdgeVec frontier(N);
525
2/2
✓ Branch 0 taken 296 times.
✓ Branch 1 taken 48 times.
2/2
✓ Decision 'true' taken 296 times.
✓ Decision 'false' taken 48 times.
 344 for (unsigned i = 0; i < N; ++i)
526
1/2
✓ Branch 2 taken 296 times.
✗ Branch 3 not taken.
 296 frontier[i] = new_circ.get_nth_in_edge(out_verts[i], 0);
527
528
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 EdgeVec cut2(b_qubits);
529
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 48 times.
2/2
✓ Decision 'true' taken 88 times.
✓ Decision 'false' taken 48 times.
 136 for (unsigned i = N - m2 - 1; i < N - 1; ++i)
530 88 cut2[i - (N - m2 - 1)] =
531 88 frontier[i]; // N-1 - (N-m2-1) = m2 (all the controls)
532
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 48 times.
2/2
✓ Decision 'true' taken 10 times.
✓ Decision 'false' taken 48 times.
 58 for (unsigned i = 0; i < b_qubits - (m2 + 1); ++i)
533 10 cut2[i + m2] = frontier[i]; // empty wires
534 48 cut2[b_qubits - 1] = frontier[N - 1]; // target
535
536
1/2
✓ Branch 3 taken 48 times.
✗ Branch 4 not taken.
 48 new_circ.cut_insert(b_replacement, cut2);
537
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 new_circ.remove_vertex(
538 b, Circuit::GraphRewiring::Yes, Circuit::VertexDeletion::Yes);
539 48 Vertex last_path = out_verts[N - 1];
540
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 Edge init_back_edge = new_circ.get_nth_in_edge(last_path, 0);
541
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 Vertex init_back_path = new_circ.source(init_back_edge);
542
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 normal_decomp_vertices.insert(init_back_path);
543
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 init_back_edge = new_circ.get_last_edge(init_back_path, init_back_edge);
544
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 init_back_path = new_circ.source(init_back_edge);
545
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 OpType backstop = new_circ.get_OpType_from_Vertex(init_back_path);
546
7/8
✓ Branch 0 taken 60 times.
✓ Branch 1 taken 28 times.
✓ Branch 3 taken 60 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 40 times.
✓ Branch 6 taken 20 times.
✓ Branch 7 taken 40 times.
✓ Branch 8 taken 48 times.
0/1
? Decision couldn't be analyzed.
 88 while ((backstop != OpType::CCX) && !is_initial_q_type(backstop)) {
547
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 init_back_edge = new_circ.get_last_edge(init_back_path, init_back_edge);
548
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 init_back_path = new_circ.source(init_back_edge);
549
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 backstop = new_circ.get_OpType_from_Vertex(init_back_path);
550 }
551
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 normal_decomp_vertices.insert(init_back_path);
552 /* now, replace vertex c */
553
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 EdgeVec cut3(cutsize);
554
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 24 times.
0/1
? Decision couldn't be analyzed.
 48 if (odd_N) {
555
2/2
✓ Branch 0 taken 92 times.
✓ Branch 1 taken 24 times.
2/2
✓ Decision 'true' taken 92 times.
✓ Decision 'false' taken 24 times.
 116 for (unsigned i = 0; i < N - 2; ++i)
556
1/2
✓ Branch 2 taken 92 times.
✗ Branch 3 not taken.
 92 cut3[i] = new_circ.get_nth_in_edge(out_verts[i], 0);
557
1/2
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
 24 cut3[N - 2] = new_circ.get_nth_in_edge(out_verts[N - 1], 0);
558
1/2
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
 24 cut3[N - 1] = new_circ.get_nth_in_edge(out_verts[N - 2], 0);
559 } else
560
2/2
✓ Branch 0 taken 132 times.
✓ Branch 1 taken 24 times.
2/2
✓ Decision 'true' taken 132 times.
✓ Decision 'false' taken 24 times.
 156 for (unsigned i = 0; i < cutsize; ++i)
561
1/2
✓ Branch 2 taken 132 times.
✗ Branch 3 not taken.
 132 cut3[i] = new_circ.get_nth_in_edge(out_verts[i], 0);
562
563
1/2
✓ Branch 3 taken 48 times.
✗ Branch 4 not taken.
 48 new_circ.cut_insert(a_replacement, cut3);
564
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 new_circ.remove_vertex(
565 c, Circuit::GraphRewiring::Yes, Circuit::VertexDeletion::Yes);
566
567 /* now, replace vertex d */
568
2/2
✓ Branch 0 taken 296 times.
✓ Branch 1 taken 48 times.
2/2
✓ Decision 'true' taken 296 times.
✓ Decision 'false' taken 48 times.
 344 for (unsigned i = 0; i < N; ++i)
569
1/2
✓ Branch 2 taken 296 times.
✗ Branch 3 not taken.
 296 frontier[i] = new_circ.get_nth_in_edge(out_verts[i], 0);
570
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 EdgeVec cut4(b_qubits);
571
2/2
✓ Branch 0 taken 88 times.
✓ Branch 1 taken 48 times.
2/2
✓ Decision 'true' taken 88 times.
✓ Decision 'false' taken 48 times.
 136 for (unsigned i = N - m2 - 1; i < N - 1; ++i)
572 88 cut4[i - (N - m2 - 1)] =
573 88 frontier[i]; // N-1 - (N-m2-1) = m2 (all the controls)
574
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 48 times.
2/2
✓ Decision 'true' taken 10 times.
✓ Decision 'false' taken 48 times.
 58 for (unsigned i = 0; i < b_qubits - (m2 + 1); ++i)
575 10 cut4[i + m2] = frontier[i]; // empty wires
576 48 cut4[b_qubits - 1] = frontier[N - 1]; // target
577
578
1/2
✓ Branch 3 taken 48 times.
✗ Branch 4 not taken.
 48 new_circ.cut_insert(b_replacement, cut4);
579
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 new_circ.remove_vertex(
580 d, Circuit::GraphRewiring::Yes, Circuit::VertexDeletion::Yes);
581
582 48 last_path = out_verts[N - 1];
583
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 init_back_edge = new_circ.get_nth_in_edge(last_path, 0);
584
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 init_back_path = new_circ.source(init_back_edge);
585
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 normal_decomp_vertices.insert(init_back_path);
586
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 init_back_edge = new_circ.get_last_edge(init_back_path, init_back_edge);
587
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 init_back_path = new_circ.source(init_back_edge);
588
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 backstop = new_circ.get_OpType_from_Vertex(init_back_path);
589
2/8
✗ Branch 0 not taken.
✓ Branch 1 taken 48 times.
✗ Branch 3 not taken.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 48 times.
0/1
? Decision couldn't be analyzed.
 48 while ((backstop != OpType::CCX) && !is_initial_q_type(backstop)) {
590 ✗ init_back_edge = new_circ.get_last_edge(init_back_path, init_back_edge);
591 ✗ init_back_path = new_circ.source(init_back_edge);
592 ✗ backstop = new_circ.get_OpType_from_Vertex(init_back_path);
593 }
594
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 normal_decomp_vertices.insert(init_back_path);
595
596
6/10
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 40 times.
✓ Branch 5 taken 8 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 8 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 48 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 48 times.
 48 if (m1 > 2 && m2 > 2 && (new_circ.count_gates(OpType::CCX) != 8 * N - 40))
597 ✗ throw ControlDecompError("Error in Lemma 7.3: CCX gate count is incorrect");
598 /* now, replace CCXs with either CX circuit modulo phase shift or just typical
599 * Toffoli decomposition */
600
601
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 auto [vit, vend] = boost::vertices(new_circ.dag);
602
2/2
✓ Branch 1 taken 6644 times.
✓ Branch 2 taken 48 times.
2/2
✓ Decision 'true' taken 6644 times.
✓ Decision 'false' taken 48 times.
 6692 for (auto next = vit; vit != vend; vit = next) {
603 6644 ++next;
604
3/4
✓ Branch 2 taken 6644 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 636 times.
✓ Branch 5 taken 6008 times.
2/2
✓ Decision 'true' taken 636 times.
✓ Decision 'false' taken 6008 times.
 6644 if (new_circ.get_OpType_from_Vertex(*vit) == OpType::CCX) {
605 Subcircuit sub{
606
1/2
✓ Branch 2 taken 636 times.
✗ Branch 3 not taken.
 636 new_circ.get_in_edges(*vit),
607
1/2
✓ Branch 2 taken 636 times.
✗ Branch 3 not taken.
 1272 new_circ.get_all_out_edges(*vit),
608
2/4
✓ Branch 3 taken 636 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 636 times.
✗ Branch 7 not taken.
 1272 {*vit}};
609
3/4
✓ Branch 3 taken 636 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 520 times.
✓ Branch 7 taken 116 times.
2/2
✓ Decision 'true' taken 520 times.
✓ Decision 'false' taken 116 times.
 636 if (normal_decomp_vertices.find(*vit) == normal_decomp_vertices.end()) {
610
2/4
✓ Branch 1 taken 520 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 520 times.
✗ Branch 5 not taken.
 520 new_circ.substitute(
611 CCX_modulo_phase_shift(), sub, Circuit::VertexDeletion::Yes);
612 } else {
613
2/4
✓ Branch 1 taken 116 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 116 times.
✗ Branch 5 not taken.
 116 new_circ.substitute(
614 CCX_normal_decomp(), sub, Circuit::VertexDeletion::Yes);
615 }
616 636 }
617 }
618
6/10
✓ Branch 0 taken 48 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 8 times.
✓ Branch 3 taken 40 times.
✓ Branch 5 taken 8 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 8 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 48 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 48 times.
 48 if (m1 > 2 && m2 > 2 && new_circ.count_gates(OpType::CX) != 24 * N - 108)
619 ✗ throw ControlDecompError("Error in Lemma 7.3: CX gate count is incorrect");
620
621
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 circ.substitute(new_circ, to_delete, Circuit::VertexDeletion::Yes);
622 48 }
623
624 // N must be >= 3
625 // Assume the unitary is not identity
626 // Linear decomposition for multi-controlled special unitaries
627 42 static void lemma79(
628 Circuit& replacement, unsigned N, const Expr& alpha, const Expr& theta,
629 const Expr& beta, candidate_t& CCX_candidates) {
630
1/2
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
 42 replacement.add_blank_wires(N);
631
632 // Add Controlled C
633
4/6
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 42 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 12 times.
✓ Branch 8 taken 30 times.
0/1
? Decision couldn't be analyzed.
 42 if (!equiv_0(beta - alpha, 8)) {
634
2/4
✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 12 times.
✗ Branch 6 not taken.
 48 replacement.add_op<unsigned>(
635
3/6
✓ Branch 2 taken 12 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 12 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 12 times.
✗ Branch 9 not taken.
 36 OpType::CRz, {(beta - alpha) / 2.}, {N - 2, N - 1});
636 }
637 // Add the first CnX
638
1/2
✓ Branch 2 taken 42 times.
✗ Branch 3 not taken.
 42 std::vector<unsigned> cnx_qbs(N - 1);
639 42 std::iota(cnx_qbs.begin(), --cnx_qbs.end(), 0);
640 42 cnx_qbs[N - 2] = N - 1;
641
1/2
✓ Branch 2 taken 42 times.
✗ Branch 3 not taken.
 42 const Op_ptr cnx = get_op_ptr(OpType::CnX, std::vector<Expr>{}, N - 1);
642
1/2
✓ Branch 2 taken 42 times.
✗ Branch 3 not taken.
 42 Vertex firstCnX = replacement.add_op<unsigned>(cnx, cnx_qbs);
643
644 // Add Controlled B
645 42 VertexVec vBs;
646
4/6
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 42 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 20 times.
✓ Branch 8 taken 22 times.
0/1
? Decision couldn't be analyzed.
 42 if (!equiv_0(alpha + beta, 8)) {
647
2/4
✓ Branch 2 taken 20 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 20 times.
✗ Branch 6 not taken.
 80 Vertex vB1 = replacement.add_op<unsigned>(
648
4/8
✓ Branch 2 taken 20 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 20 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 20 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 20 times.
✗ Branch 12 not taken.
 60 OpType::CRz, {(-alpha - beta) / 2.}, {N - 2, N - 1});
649
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 vBs.push_back(vB1);
650 }
651
3/4
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 38 times.
✓ Branch 4 taken 4 times.
0/1
? Decision couldn't be analyzed.
 42 if (!equiv_0(theta, 8)) {
652
2/4
✓ Branch 2 taken 38 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 38 times.
✗ Branch 6 not taken.
 152 Vertex vB2 = replacement.add_op<unsigned>(
653
3/6
✓ Branch 2 taken 38 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 38 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 38 times.
✗ Branch 9 not taken.
 114 OpType::CRy, {-theta / 2.}, {N - 2, N - 1});
654
1/2
✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
 38 vBs.push_back(vB2);
655 }
656 // At least one of vB1 and vB2 should be set, otherwise it implies that the
657 // SU(2) is identity
658
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 42 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 42 times.
 42 if (vBs.empty()) {
659 ✗ throw ControlDecompError(
660 ✗ "Unknown error in Lemma 7.9: identity not rejected");
661 }
662
663 // Add the second CnX
664
1/2
✓ Branch 2 taken 42 times.
✗ Branch 3 not taken.
 42 Vertex secondCnX = replacement.add_op<unsigned>(cnx, cnx_qbs);
665
666 // Add Controlled A
667
3/4
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 38 times.
✓ Branch 4 taken 4 times.
2/2
✓ Decision 'true' taken 38 times.
✓ Decision 'false' taken 4 times.
 42 if (!equiv_0(theta, 8)) {
668
4/8
✓ Branch 3 taken 38 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 38 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 38 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 38 times.
✗ Branch 13 not taken.
 38 replacement.add_op<unsigned>(OpType::CRy, {theta / 2.}, {N - 2, N - 1});
669 }
670
3/4
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 20 times.
✓ Branch 4 taken 22 times.
2/2
✓ Decision 'true' taken 20 times.
✓ Decision 'false' taken 22 times.
 42 if (!equiv_0(alpha, 4)) {
671
2/4
✓ Branch 3 taken 20 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 20 times.
✗ Branch 7 not taken.
 20 replacement.add_op<unsigned>(OpType::CRz, {alpha}, {N - 2, N - 1});
672 }
673
1/2
✓ Branch 2 taken 42 times.
✗ Branch 3 not taken.
 42 Edge first_e = replacement.get_nth_in_edge(vBs[0], 0);
674
1/2
✓ Branch 2 taken 42 times.
✗ Branch 3 not taken.
 42 Edge second_e = replacement.get_nth_out_edge(vBs.back(), 0);
675
1/2
✓ Branch 2 taken 42 times.
✗ Branch 3 not taken.
 42 CCX_candidates.push_back({first_e, firstCnX});
676
1/2
✓ Branch 2 taken 42 times.
✗ Branch 3 not taken.
 42 CCX_candidates.push_back({second_e, secondCnX});
677 42 }
678
679 2713 static Circuit CU_to_CU3(const Eigen::Matrix2cd& u) {
680
1/2
✓ Branch 2 taken 2713 times.
✗ Branch 3 not taken.
 2713 Circuit c(2);
681
1/2
✓ Branch 1 taken 2713 times.
✗ Branch 2 not taken.
 2713 std::vector<double> tk1_angles = tk1_angles_from_unitary(u);
682
1/2
✓ Branch 2 taken 2713 times.
✗ Branch 3 not taken.
 2713 Expr theta = tk1_angles[1];
683
1/2
✓ Branch 2 taken 2713 times.
✗ Branch 3 not taken.
 2713 Expr phi = tk1_angles[0] - 0.5;
684
1/2
✓ Branch 2 taken 2713 times.
✗ Branch 3 not taken.
 2713 Expr lambda = tk1_angles[2] + 0.5;
685
1/2
✓ Branch 4 taken 2713 times.
✗ Branch 5 not taken.
 2713 Expr t = tk1_angles[3] - 0.5 * (tk1_angles[0] + tk1_angles[2]);
686
2/4
✓ Branch 3 taken 2713 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2713 times.
✗ Branch 7 not taken.
 2713 c.add_op<unsigned>(OpType::U1, t, {0});
687
8/16
✓ Branch 3 taken 2713 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2713 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 2713 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 2713 times.
✗ Branch 13 not taken.
✓ Branch 16 taken 2713 times.
✗ Branch 17 not taken.
✓ Branch 19 taken 2713 times.
✗ Branch 20 not taken.
✓ Branch 23 taken 8139 times.
✓ Branch 24 taken 2713 times.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
 10852 c.add_op<unsigned>(OpType::CU3, {theta, phi, lambda}, {0, 1});
688
1/2
✓ Branch 1 taken 2713 times.
✗ Branch 2 not taken.
 2713 c.remove_noops();
689 5426 return c;
690 2713 }
691
692 500 Circuit CnU_gray_code_decomp(unsigned n, const Eigen::Matrix2cd& u) {
693
2/2
✓ Branch 0 taken 100 times.
✓ Branch 1 taken 400 times.
2/2
✓ Decision 'true' taken 100 times.
✓ Decision 'false' taken 400 times.
 500 if (n == 0) {
694 // Synthesise U using tk1 and phase
695
1/2
✓ Branch 2 taken 100 times.
✗ Branch 3 not taken.
 100 Circuit cnu_circ(1);
696
1/2
✓ Branch 1 taken 100 times.
✗ Branch 2 not taken.
 100 std::vector<double> tk1_angles = tk1_angles_from_unitary(u);
697
8/16
✓ Branch 3 taken 100 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 100 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 100 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 100 times.
✗ Branch 13 not taken.
✓ Branch 16 taken 100 times.
✗ Branch 17 not taken.
✓ Branch 19 taken 100 times.
✗ Branch 20 not taken.
✓ Branch 23 taken 300 times.
✓ Branch 24 taken 100 times.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
 700 cnu_circ.add_op<unsigned>(
698 300 OpType::TK1, {tk1_angles[0], tk1_angles[1], tk1_angles[2]}, {0});
699
2/4
✓ Branch 2 taken 100 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 100 times.
✗ Branch 6 not taken.
 100 cnu_circ.add_phase(tk1_angles[3]);
700
1/2
✓ Branch 1 taken 100 times.
✗ Branch 2 not taken.
 100 return cnu_circ;
701 100 }
702
2/2
✓ Branch 0 taken 100 times.
✓ Branch 1 taken 300 times.
2/2
✓ Decision 'true' taken 100 times.
✓ Decision 'false' taken 300 times.
 400 if (n == 1) {
703
1/2
✓ Branch 1 taken 100 times.
✗ Branch 2 not taken.
 100 return CU_to_CU3(u);
704 }
705
706
1/2
✓ Branch 1 taken 300 times.
✗ Branch 2 not taken.
 300 Eigen::Matrix2cd v_matrix = nth_root(u, 1 << (n - 1));
707
2/4
✓ Branch 1 taken 300 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 300 times.
✗ Branch 5 not taken.
 300 Eigen::Matrix2cd v_matrix_dag = v_matrix.adjoint();
708
1/2
✓ Branch 1 taken 300 times.
✗ Branch 2 not taken.
 300 Circuit v_rep = CU_to_CU3(v_matrix);
709
1/2
✓ Branch 1 taken 300 times.
✗ Branch 2 not taken.
 300 Circuit v_dg_rep = CU_to_CU3(v_matrix_dag);
710
1/2
✓ Branch 1 taken 300 times.
✗ Branch 2 not taken.
 300 return lemma71(n + 1, v_rep, v_dg_rep);
711 300 }
712
713 2017 Circuit CnU_gray_code_decomp(unsigned n, const Gate_ptr& gate) {
714 static const std::map<OpType, OpType> cu_type_map = {
715 {OpType::Rx, OpType::CRx},
716 {OpType::Ry, OpType::CRy},
717 {OpType::Rz, OpType::CRz},
718
4/8
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 2016 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.
 2017 {OpType::U1, OpType::CU1}};
719
720
1/2
✓ Branch 3 taken 2017 times.
✗ Branch 4 not taken.
 2017 auto it = cu_type_map.find(gate->get_type());
721
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 2017 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 2017 times.
 2017 if (it == cu_type_map.end()) {
722 ✗ throw Unsupported(
723 ✗ "The implementation currently only supports Rx, Ry, Rz, U1");
724 }
725
726 2017 const OpType& cu_type = it->second;
727
728
2/2
✓ Branch 0 taken 400 times.
✓ Branch 1 taken 1617 times.
2/2
✓ Decision 'true' taken 400 times.
✓ Decision 'false' taken 1617 times.
 2017 if (n == 0) {
729
1/2
✓ Branch 2 taken 400 times.
✗ Branch 3 not taken.
 400 Circuit cnu_circ(1);
730
2/4
✓ Branch 3 taken 400 times.
✗ Branch 4 not taken.
✓ Branch 7 taken 400 times.
✗ Branch 8 not taken.
 400 cnu_circ.add_op<unsigned>(gate, {0});
731
1/2
✓ Branch 1 taken 400 times.
✗ Branch 2 not taken.
 400 return cnu_circ;
732 400 }
733
734
2/4
✓ Branch 2 taken 1617 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 1617 times.
✗ Branch 7 not taken.
 1617 Expr angle = gate->get_params()[0];
735
2/2
✓ Branch 0 taken 400 times.
✓ Branch 1 taken 1217 times.
2/2
✓ Decision 'true' taken 400 times.
✓ Decision 'false' taken 1217 times.
 1617 if (n == 1) {
736
1/2
✓ Branch 2 taken 400 times.
✗ Branch 3 not taken.
 400 Circuit cnu_circ(2);
737
2/4
✓ Branch 3 taken 400 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 400 times.
✗ Branch 7 not taken.
 400 cnu_circ.add_op<unsigned>(cu_type, angle, {0, 1});
738
1/2
✓ Branch 1 taken 400 times.
✗ Branch 2 not taken.
 400 return cnu_circ;
739 400 }
740
1/2
✓ Branch 1 taken 1217 times.
✗ Branch 2 not taken.
 1217 Expr param;
741
1/2
✓ Branch 1 taken 1217 times.
✗ Branch 2 not taken.
 1217 std::optional<double> reduced = eval_expr_mod(angle, 4);
742
2/2
✓ Branch 1 taken 1216 times.
✓ Branch 2 taken 1 times.
2/2
✓ Decision 'true' taken 1216 times.
✓ Decision 'false' taken 1 times.
 1217 if (reduced)
743
2/4
✓ Branch 1 taken 1216 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1216 times.
✗ Branch 5 not taken.
 1216 param = reduced.value();
744 else
745
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 param = angle;
746
747
2/4
✓ Branch 1 taken 1217 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1217 times.
✗ Branch 5 not taken.
 1217 param = param / (1 << (n - 1));
748
1/2
✓ Branch 2 taken 1217 times.
✗ Branch 3 not taken.
 1217 Circuit v_rep(2);
749
1/2
✓ Branch 2 taken 1217 times.
✗ Branch 3 not taken.
 1217 Circuit v_dg_rep(2);
750
2/4
✓ Branch 3 taken 1217 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 1217 times.
✗ Branch 7 not taken.
 1217 v_rep.add_op<unsigned>(cu_type, param, {0, 1});
751
3/6
✓ Branch 3 taken 1217 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 1217 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 1217 times.
✗ Branch 10 not taken.
 1217 v_dg_rep.add_op<unsigned>(cu_type, -param, {0, 1});
752
1/2
✓ Branch 1 taken 1217 times.
✗ Branch 2 not taken.
 1217 return lemma71(n + 1, v_rep, v_dg_rep);
753 1617 }
754
755 20 Circuit CnRy_normal_decomp(const Op_ptr op, unsigned arity) {
756
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 20 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 20 times.
 20 if (op->get_type() != OpType::CnRy) {
757 ✗ throw CircuitInvalidity("Operation not CnRy");
758 }
759
1/2
✓ Branch 2 taken 20 times.
✗ Branch 3 not taken.
 20 OpDesc desc = op->get_desc();
760
2/4
✓ Branch 2 taken 20 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 20 times.
✗ Branch 7 not taken.
 20 Expr angle = op->get_params()[0];
761
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 Circuit rep;
762
4/5
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 14 times.
✓ Branch 4 taken 1 times.
 20 switch (arity) {
763
1/1
✓ Decision 'true' taken 1 times.
 1 case 0: {
764
2/4
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
 1 throw CircuitInvalidity("Circuit has a CnRy with no in edges!");
765 }
766
0/1
✗ Decision 'true' not taken.
 ✗ case 1: {
767 ✗ rep.add_blank_wires(1);
768 ✗ rep.add_op<unsigned>(OpType::Ry, angle, {0});
769 ✗ break;
770 }
771
1/1
✓ Decision 'true' taken 4 times.
 4 case 2: {
772
2/4
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
 4 rep = CircPool::CRy_using_CX(angle);
773 4 break;
774 }
775 14 case 3:
776 case 4:
777 case 5:
778 case 6:
779 case 7:
780 case 8: {
781
1/2
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 28 rep = CnU_gray_code_decomp(
782
3/6
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 14 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 14 times.
✗ Branch 8 not taken.
 42 arity - 1, as_gate_ptr(get_op_ptr(OpType::Ry, angle)));
783 14 break;
784 }
785
1/1
✓ Decision 'true' taken 1 times.
 1 default: {
786
4/8
✓ 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.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
 1 rep = CnSU2_linear_decomp(arity - 1, 0., angle, 0.);
787
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 auto [x, xend] = boost::vertices(rep.dag);
788
2/2
✓ Branch 1 taken 540 times.
✓ Branch 2 taken 1 times.
2/2
✓ Decision 'true' taken 540 times.
✓ Decision 'false' taken 1 times.
 541 for (auto xnext = x; x != xend; x = xnext) {
789 540 ++xnext;
790
1/2
✓ Branch 2 taken 540 times.
✗ Branch 3 not taken.
 540 OpType type = rep.get_OpType_from_Vertex(*x);
791
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 538 times.
2/2
✓ Decision 'true' taken 4 times.
✓ Decision 'false' taken 536 times.
 540 if (type == OpType::CRy) {
792
3/6
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 2 times.
✗ Branch 7 not taken.
✓ Branch 10 taken 2 times.
✗ Branch 11 not taken.
 4 Expr x_angle = rep.get_Op_ptr_from_Vertex(*x)->get_params()[0];
793
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 Circuit new_circ = CircPool::CRy_using_CX(x_angle);
794
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 Subcircuit sub{rep.get_in_edges(*x), rep.get_all_out_edges(*x), {*x}};
795
1/2
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
 2 rep.substitute(new_circ, sub, Circuit::VertexDeletion::Yes);
796
1/2
✗ Branch 3 not taken.
✓ Branch 4 taken 538 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 540 times.
 540 } else if (type == OpType::CRz) {
797 ✗ throw ControlDecompError(
798 ✗ "Error in Lemma 7.9: Y rotation isn't recognized");
799 }
800 }
801 1 break;
802 }
803 }
804 38 return rep;
805 22 }
806
807 // decompose CnX gate using lemma 7.1
808 // `n` = no. of controls
809 8 Circuit CnX_gray_decomp(unsigned n) {
810
6/6
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 1 times.
✓ Branch 5 taken 3 times.
 8 switch (n) {
811
1/1
✓ Decision 'true' taken 1 times.
 1 case 0: {
812 1 return X();
813 }
814
1/1
✓ Decision 'true' taken 1 times.
 1 case 1: {
815 1 return CX();
816 }
817
1/1
✓ Decision 'true' taken 1 times.
 1 case 2: {
818 1 return CCX_normal_decomp();
819 }
820
1/1
✓ Decision 'true' taken 1 times.
 1 case 3: {
821 1 return C3X_normal_decomp();
822 }
823
1/1
✓ Decision 'true' taken 1 times.
 1 case 4: {
824 1 return C4X_normal_decomp();
825 }
826
1/1
✓ Decision 'true' taken 3 times.
 3 default: {
827
1/2
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 3 Circuit circ(n + 1);
828
2/4
✓ Branch 3 taken 3 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 3 times.
✗ Branch 7 not taken.
 3 circ.add_op<unsigned>(OpType::H, {n});
829
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 circ.append(
830
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 10 taken 3 times.
✗ Branch 11 not taken.
 6 CnU_gray_code_decomp(n, as_gate_ptr(get_op_ptr(OpType::U1, 1.0))));
831
2/4
✓ Branch 3 taken 3 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 3 times.
✗ Branch 7 not taken.
 3 circ.add_op<unsigned>(OpType::H, {n});
832
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 return circ;
833 3 }
834 }
835 }
836
837 2013 static void add_cu_using_cu3(
838 const unsigned& ctrl, const unsigned& trgt, Circuit& circ,
839 const Eigen::Matrix2cd& u) {
840 2013 unit_map_t unit_map;
841
3/6
✓ Branch 1 taken 2013 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2013 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 2013 times.
✗ Branch 9 not taken.
 2013 unit_map.insert({Qubit(0), Qubit(ctrl)});
842
3/6
✓ Branch 1 taken 2013 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2013 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 2013 times.
✗ Branch 9 not taken.
 2013 unit_map.insert({Qubit(1), Qubit(trgt)});
843
1/2
✓ Branch 1 taken 2013 times.
✗ Branch 2 not taken.
 2013 Circuit cnu_circ = CU_to_CU3(u);
844
1/2
✓ Branch 1 taken 2013 times.
✗ Branch 2 not taken.
 2013 circ.append_with_map(cnu_circ, unit_map);
845 2013 }
846
847 // Add pn to qubits {1,...,n}, assume n > 1
848 1026 static void add_pn(Circuit& circ, unsigned n, bool inverse) {
849 TKET_ASSERT(n > 1);
850 // pn is self commute
851
2/2
✓ Branch 0 taken 2006 times.
✓ Branch 1 taken 1026 times.
2/2
✓ Decision 'true' taken 2006 times.
✓ Decision 'false' taken 1026 times.
 3032 for (unsigned i = 2; i < n + 1; i++) {
852 2006 int d = 1 << (n - i + 1);
853
2/2
✓ Branch 0 taken 1003 times.
✓ Branch 1 taken 1003 times.
 2006 d = inverse ? -1 * d : d;
854
3/6
✓ Branch 3 taken 2006 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 2006 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 2006 times.
✗ Branch 10 not taken.
 2006 circ.add_op<unsigned>(OpType::CRx, (double)1 / d, {i - 1, n});
855 }
856 1026 }
857
858 // Add pn(u) to qubits {1,...,n}, assume n > 1
859 642 static void add_pn_unitary(
860 Circuit& circ, const Eigen::Matrix2cd& u, unsigned n, bool inverse) {
861 TKET_ASSERT(n > 1);
862 // pn_(u) is self commute
863
2/2
✓ Branch 0 taken 1572 times.
✓ Branch 1 taken 642 times.
2/2
✓ Decision 'true' taken 1572 times.
✓ Decision 'false' taken 642 times.
 2214 for (unsigned i = 2; i < n + 1; i++) {
864
1/2
✓ Branch 1 taken 1572 times.
✗ Branch 2 not taken.
 1572 Eigen::Matrix2cd m = nth_root(u, 1 << (n - i + 1));
865
3/4
✓ Branch 0 taken 786 times.
✓ Branch 1 taken 786 times.
✓ Branch 3 taken 786 times.
✗ Branch 4 not taken.
1/2
✓ Decision 'true' taken 1572 times.
✗ Decision 'false' not taken.
 1572 if (inverse) m.adjointInPlace();
866
1/2
✓ Branch 1 taken 1572 times.
✗ Branch 2 not taken.
 1572 add_cu_using_cu3(i - 1, n, circ, m);
867 }
868 642 }
869
870 // Add an incrementer without toggling the least significant bit
871 // Apply to qubits {0,...,n-1}, assume n > 1
872 341 static void add_qn(Circuit& circ, unsigned n) {
873 TKET_ASSERT(n > 1);
874
2/2
✓ Branch 0 taken 513 times.
✓ Branch 1 taken 341 times.
2/2
✓ Decision 'true' taken 513 times.
✓ Decision 'false' taken 341 times.
 854 for (unsigned i = n - 1; i > 1; i--) {
875 513 int d = 1 << (i - 1);
876 513 add_pn(circ, i, false);
877
3/6
✓ Branch 3 taken 513 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 513 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 513 times.
✗ Branch 10 not taken.
 513 circ.add_op<unsigned>(OpType::CRx, (double)1 / d, {0, i});
878 }
879
3/6
✓ Branch 3 taken 341 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 341 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 341 times.
✗ Branch 10 not taken.
 341 circ.add_op<unsigned>(OpType::CRx, 1, {0, 1});
880
2/2
✓ Branch 0 taken 513 times.
✓ Branch 1 taken 341 times.
2/2
✓ Decision 'true' taken 513 times.
✓ Decision 'false' taken 341 times.
 854 for (unsigned i = 2; i < n; i++) {
881 513 add_pn(circ, i, true);
882 }
883 341 }
884
885 // https://arxiv.org/abs/2203.11882 Equation 5
886 344 Circuit incrementer_linear_depth(unsigned n, bool lsb) {
887
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 343 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 343 times.
 344 if (n == 0) {
888
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 return Circuit();
889 }
890
1/2
✓ Branch 2 taken 343 times.
✗ Branch 3 not taken.
 343 Circuit circ(n);
891
2/2
✓ Branch 0 taken 341 times.
✓ Branch 1 taken 2 times.
2/2
✓ Decision 'true' taken 341 times.
✓ Decision 'false' taken 2 times.
 343 if (n > 1) {
892
1/2
✓ Branch 1 taken 341 times.
✗ Branch 2 not taken.
 341 add_qn(circ, n);
893 }
894
2/2
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 321 times.
2/2
✓ Decision 'true' taken 22 times.
✓ Decision 'false' taken 321 times.
 343 if (lsb) {
895 // Some optimisations might have better handlings for X gates
896 // so use X instead of Rx(1)
897
2/4
✓ Branch 3 taken 22 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 22 times.
✗ Branch 7 not taken.
 22 circ.add_op<unsigned>(OpType::X, {0});
898
2/4
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 22 times.
✗ Branch 5 not taken.
 22 circ.add_phase(-0.5);
899 }
900
1/2
✓ Branch 1 taken 343 times.
✗ Branch 2 not taken.
 343 return circ;
901 343 }
902
903 // https://arxiv.org/abs/2203.11882 Equation 3
904 549 Circuit CnU_linear_depth_decomp(unsigned n, const Eigen::Matrix2cd& u) {
905
3/6
✓ Branch 1 taken 549 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 549 times.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 549 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 549 times.
 549 if (!is_unitary(u)) {
906 ✗ throw CircuitInvalidity(
907 ✗ "Matrix for the controlled operation must be unitary");
908 }
909
1/2
✓ Branch 2 taken 549 times.
✗ Branch 3 not taken.
 549 Circuit circ(n + 1);
910
911
2/2
✓ Branch 0 taken 108 times.
✓ Branch 1 taken 441 times.
2/2
✓ Decision 'true' taken 108 times.
✓ Decision 'false' taken 441 times.
 549 if (n == 0) {
912 // Synthesis U using tk1 and phase
913
1/2
✓ Branch 1 taken 108 times.
✗ Branch 2 not taken.
 108 std::vector<double> tk1_angles = tk1_angles_from_unitary(u);
914
8/16
✓ Branch 3 taken 108 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 108 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 108 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 108 times.
✗ Branch 13 not taken.
✓ Branch 16 taken 108 times.
✗ Branch 17 not taken.
✓ Branch 19 taken 108 times.
✗ Branch 20 not taken.
✓ Branch 23 taken 324 times.
✓ Branch 24 taken 108 times.
✗ Branch 31 not taken.
✗ Branch 32 not taken.
 756 circ.add_op<unsigned>(
915 324 OpType::TK1, {tk1_angles[0], tk1_angles[1], tk1_angles[2]}, {0});
916
2/4
✓ Branch 2 taken 108 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 108 times.
✗ Branch 6 not taken.
 108 circ.add_phase(tk1_angles[3]);
917 108 return circ;
918 108 }
919
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 321 times.
2/2
✓ Decision 'true' taken 120 times.
✓ Decision 'false' taken 321 times.
 441 if (n == 1) {
920
1/2
✓ Branch 1 taken 120 times.
✗ Branch 2 not taken.
 120 add_cu_using_cu3(0, 1, circ, u);
921 120 return circ;
922 }
923
924 // Add pn(u) to qubits {1,...,n}
925
1/2
✓ Branch 1 taken 321 times.
✗ Branch 2 not taken.
 321 add_pn_unitary(circ, u, n, false);
926 // Add CU to {0, n}
927
1/2
✓ Branch 1 taken 321 times.
✗ Branch 2 not taken.
 321 Eigen::Matrix2cd m = nth_root(u, 1 << (n - 1));
928
1/2
✓ Branch 1 taken 321 times.
✗ Branch 2 not taken.
 321 add_cu_using_cu3(0, n, circ, m);
929 // Add incrementer (without toggling q0) to {0,...,n-1}
930
1/2
✓ Branch 1 taken 321 times.
✗ Branch 2 not taken.
 321 Circuit qn = incrementer_linear_depth(n, false);
931
1/2
✓ Branch 1 taken 321 times.
✗ Branch 2 not taken.
 321 Circuit qn_dag = qn.dagger();
932
1/2
✓ Branch 1 taken 321 times.
✗ Branch 2 not taken.
 321 circ.append(qn);
933
934 // Add pn(u).dagger to qubits {1,...,n}
935
1/2
✓ Branch 1 taken 321 times.
✗ Branch 2 not taken.
 321 add_pn_unitary(circ, u, n, true);
936
937 // Add incrementer inverse (without toggling q0) to {0,...,n-1}
938
1/2
✓ Branch 1 taken 321 times.
✗ Branch 2 not taken.
 321 circ.append(qn_dag);
939
940 321 return circ;
941 321 }
942
943 107 Circuit CnSU2_linear_decomp(
944 unsigned n, const Expr& alpha, const Expr& theta, const Expr& beta) {
945 // W == I iff one of the following two conditions is met
946 // 1. t/2 is even, and (a + b)/2 is even
947 // 2. t/2 is odd, and (a + b)/2 is odd
948 // check if SU(2) is identity
949
19/38
✓ Branch 1 taken 107 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 107 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 107 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 32 times.
✓ Branch 10 taken 75 times.
✓ Branch 12 taken 32 times.
✗ Branch 13 not taken.
✓ Branch 15 taken 32 times.
✗ Branch 16 not taken.
✓ Branch 18 taken 32 times.
✗ Branch 19 not taken.
✓ Branch 21 taken 32 times.
✗ Branch 22 not taken.
✓ Branch 23 taken 8 times.
✓ Branch 24 taken 24 times.
✓ Branch 26 taken 32 times.
✓ Branch 27 taken 75 times.
✓ Branch 29 taken 32 times.
✓ Branch 30 taken 75 times.
✓ Branch 32 taken 107 times.
✗ Branch 33 not taken.
✓ Branch 35 taken 107 times.
✗ Branch 36 not taken.
✓ Branch 38 taken 36 times.
✓ Branch 39 taken 71 times.
✗ Branch 40 not taken.
✗ Branch 41 not taken.
✗ Branch 43 not taken.
✗ Branch 44 not taken.
✗ Branch 46 not taken.
✗ Branch 47 not taken.
✗ Branch 49 not taken.
✗ Branch 50 not taken.
✗ Branch 52 not taken.
✗ Branch 53 not taken.
2/2
✓ Decision 'true' taken 36 times.
✓ Decision 'false' taken 261 times.
 297 if ((equiv_0(theta / 2., 2) && equiv_0((alpha + beta) / 2., 2)) ||
950
22/40
✓ Branch 1 taken 83 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 83 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 83 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 12 times.
✓ Branch 10 taken 71 times.
✓ Branch 12 taken 12 times.
✗ Branch 13 not taken.
✓ Branch 15 taken 12 times.
✗ Branch 16 not taken.
✓ Branch 18 taken 12 times.
✗ Branch 19 not taken.
✓ Branch 21 taken 12 times.
✗ Branch 22 not taken.
✓ Branch 23 taken 12 times.
✗ Branch 24 not taken.
✓ Branch 25 taken 12 times.
✓ Branch 26 taken 95 times.
✓ Branch 28 taken 12 times.
✓ Branch 29 taken 95 times.
✓ Branch 31 taken 12 times.
✓ Branch 32 taken 95 times.
✓ Branch 34 taken 83 times.
✓ Branch 35 taken 24 times.
✓ Branch 37 taken 83 times.
✓ Branch 38 taken 24 times.
✓ Branch 40 taken 32 times.
✓ Branch 41 taken 75 times.
✗ Branch 42 not taken.
✗ Branch 43 not taken.
✗ Branch 45 not taken.
✗ Branch 46 not taken.
✗ Branch 48 not taken.
✗ Branch 49 not taken.
✗ Branch 51 not taken.
✗ Branch 52 not taken.
✗ Branch 54 not taken.
✗ Branch 55 not taken.
 190 (equiv_val(theta / 2., 1., 2) && equiv_val((alpha + beta) / 2., 1., 2))) {
951
1/2
✓ Branch 2 taken 36 times.
✗ Branch 3 not taken.
 36 return Circuit(n + 1);
952 }
953
954
1/2
✓ Branch 1 taken 71 times.
✗ Branch 2 not taken.
 71 Circuit circ;
955
956
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 61 times.
2/2
✓ Decision 'true' taken 10 times.
✓ Decision 'false' taken 61 times.
 71 if (n == 0) {
957 // add tk1
958
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 circ.add_blank_wires(1);
959
10/20
✓ Branch 3 taken 10 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 10 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 10 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 10 times.
✗ Branch 13 not taken.
✓ Branch 15 taken 10 times.
✗ Branch 16 not taken.
✓ Branch 18 taken 10 times.
✗ Branch 19 not taken.
✓ Branch 22 taken 10 times.
✗ Branch 23 not taken.
✓ Branch 25 taken 10 times.
✗ Branch 26 not taken.
✓ Branch 29 taken 30 times.
✓ Branch 30 taken 10 times.
✗ Branch 39 not taken.
✗ Branch 40 not taken.
 40 circ.add_op<unsigned>(OpType::TK1, {alpha + 0.5, theta, beta - 0.5}, {0});
960
1/2
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
 10 return circ;
961 }
962
963 // SU(2) matrix W expressed as Rz(a)Ry(t)Rz(b)
964
1/2
✓ Branch 1 taken 61 times.
✗ Branch 2 not taken.
 61 Expr a = alpha;
965
1/2
✓ Branch 1 taken 61 times.
✗ Branch 2 not taken.
 61 Expr b = beta;
966
1/2
✓ Branch 1 taken 61 times.
✗ Branch 2 not taken.
 61 Expr t = theta;
967
968 // Lemma 4.3: W = A*X*B*X*C
969 // By lemma 5.4, C is identity iff W can be expressed as Rz(a')Ry(t')Rz(a')
970 // We handle the following two cases
971 // if (a-b)/2 is even, a' = (a + b)/2, t' = t
972 // if (a-b)/2 is odd, a' = (a + b)/2, t' = - t
973
6/10
✓ Branch 1 taken 61 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 61 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 61 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 61 times.
✗ Branch 11 not taken.
✓ Branch 15 taken 25 times.
✓ Branch 16 taken 36 times.
2/2
✓ Decision 'true' taken 25 times.
✓ Decision 'false' taken 36 times.
 61 if (equiv_0((a - b) / 2., 2)) {
974
3/6
✓ Branch 1 taken 25 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 25 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 25 times.
✗ Branch 8 not taken.
 25 a = (a + b) / 2.;
975
1/2
✓ Branch 1 taken 25 times.
✗ Branch 2 not taken.
 25 b = a;
976
6/10
✓ Branch 1 taken 36 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 36 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 36 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 36 times.
✗ Branch 11 not taken.
✓ Branch 15 taken 15 times.
✓ Branch 16 taken 21 times.
2/2
✓ Decision 'true' taken 15 times.
✓ Decision 'false' taken 21 times.
 36 } else if (equiv_val((a - b) / 2., 1., 2)) {
977
3/6
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 15 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 15 times.
✗ Branch 8 not taken.
 15 a = (a + b) / 2.;
978
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 b = a;
979
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 t = -t;
980 }
981
982 // We test whether W can be expressed as a single Ry(t'')
983
6/10
✓ Branch 1 taken 61 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 61 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 61 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 61 times.
✗ Branch 11 not taken.
✓ Branch 15 taken 40 times.
✓ Branch 16 taken 21 times.
2/2
✓ Decision 'true' taken 40 times.
✓ Decision 'false' taken 21 times.
 61 if (equiv_0((a - b) / 2., 2)) {
984
6/10
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 40 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 40 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 40 times.
✗ Branch 11 not taken.
✓ Branch 15 taken 11 times.
✓ Branch 16 taken 29 times.
2/2
✓ Decision 'true' taken 11 times.
✓ Decision 'false' taken 29 times.
 40 if (equiv_val((a + b) / 2., 1., 2)) {
985 // if (a-b)/2 is even, and (a+b)/2 is odd, t'' = 2-t
986
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 a = 0.;
987
1/2
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
 11 b = 0.;
988
2/4
✓ Branch 1 taken 11 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 11 times.
✗ Branch 5 not taken.
 11 t = 2. - t;
989
6/10
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 29 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 29 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 29 times.
✗ Branch 11 not taken.
✓ Branch 15 taken 19 times.
✓ Branch 16 taken 10 times.
2/2
✓ Decision 'true' taken 19 times.
✓ Decision 'false' taken 10 times.
 29 } else if (equiv_0((a + b) / 2., 2)) {
990 // if (a-b)/2 is even, and (a+b)/2 is even, t'' = t
991
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 a = 0.;
992
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 b = 0.;
993 }
994
5/10
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 21 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 21 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 21 times.
✗ Branch 11 not taken.
✗ Branch 15 not taken.
✓ Branch 16 taken 21 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 21 times.
 21 } else if (equiv_val((a - b) / 2., 1., 2)) {
995
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (equiv_val((a + b) / 2., 1., 2)) {
996 // if (a-b)/2 is odd, and (a+b)/2 is odd, t'' = 2-t
997 ✗ a = 0.;
998 ✗ b = 0.;
999 ✗ t = 2. + t;
1000
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ } else if (equiv_0((a + b) / 2., 2)) {
1001 // if (a-b)/2 is odd, and (a+b)/2 is even, t'' = -t
1002 ✗ a = 0.;
1003 ✗ b = 0.;
1004 ✗ t = -t;
1005 }
1006 }
1007
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 42 times.
2/2
✓ Decision 'true' taken 19 times.
✓ Decision 'false' taken 42 times.
 61 if (n == 1) {
1008
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 circ.add_blank_wires(2);
1009
4/6
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 19 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 9 times.
✓ Branch 8 taken 10 times.
2/2
✓ Decision 'true' taken 9 times.
✓ Decision 'false' taken 10 times.
 19 if (!equiv_0(b - a, 8)) {
1010
5/10
✓ Branch 3 taken 9 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 9 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 9 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 9 times.
✗ Branch 13 not taken.
✓ Branch 15 taken 9 times.
✗ Branch 16 not taken.
 9 circ.add_op<unsigned>(OpType::Rz, {(b - a) / 2.}, {1});
1011 }
1012
2/4
✓ Branch 3 taken 19 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 19 times.
✗ Branch 7 not taken.
 19 circ.add_op<unsigned>(OpType::CX, {0, 1});
1013
4/6
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 19 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 10 times.
✓ Branch 8 taken 9 times.
2/2
✓ Decision 'true' taken 10 times.
✓ Decision 'false' taken 9 times.
 19 if (!equiv_0(a + b, 8)) {
1014
6/12
✓ Branch 3 taken 10 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 10 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 10 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 10 times.
✗ Branch 13 not taken.
✓ Branch 15 taken 10 times.
✗ Branch 16 not taken.
✓ Branch 18 taken 10 times.
✗ Branch 19 not taken.
 10 circ.add_op<unsigned>(OpType::Rz, {(-a - b) / 2.}, {1});
1015 }
1016
3/4
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 16 times.
✓ Branch 4 taken 3 times.
2/2
✓ Decision 'true' taken 16 times.
✓ Decision 'false' taken 3 times.
 19 if (!equiv_0(t, 8)) {
1017
5/10
✓ Branch 3 taken 16 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 16 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 16 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 16 times.
✗ Branch 13 not taken.
✓ Branch 15 taken 16 times.
✗ Branch 16 not taken.
 16 circ.add_op<unsigned>(OpType::Ry, {-t / 2.}, {1});
1018 }
1019
2/4
✓ Branch 3 taken 19 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 19 times.
✗ Branch 7 not taken.
 19 circ.add_op<unsigned>(OpType::CX, {0, 1});
1020
3/4
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 16 times.
✓ Branch 4 taken 3 times.
2/2
✓ Decision 'true' taken 16 times.
✓ Decision 'false' taken 3 times.
 19 if (!equiv_0(t, 8)) {
1021
4/8
✓ Branch 3 taken 16 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 16 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 16 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 16 times.
✗ Branch 13 not taken.
 16 circ.add_op<unsigned>(OpType::Ry, {t / 2.}, {1});
1022 }
1023
3/4
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 11 times.
✓ Branch 4 taken 8 times.
2/2
✓ Decision 'true' taken 11 times.
✓ Decision 'false' taken 8 times.
 19 if (!equiv_0(a, 4)) {
1024
2/4
✓ Branch 3 taken 11 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 11 times.
✗ Branch 7 not taken.
 11 circ.add_op<unsigned>(OpType::Rz, {a}, {1});
1025 }
1026
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 return circ;
1027 }
1028 // Using lemma 7.9 for n >= 2
1029 42 candidate_t ct;
1030
1/2
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
 42 lemma79(circ, n + 1, a, t, b, ct);
1031
2/2
✓ Branch 5 taken 84 times.
✓ Branch 6 taken 42 times.
2/2
✓ Decision 'true' taken 84 times.
✓ Decision 'false' taken 42 times.
 126 for (const std::pair<Edge, Vertex>& pairy : ct) {
1032 84 Vertex original_cnx = pairy.second;
1033
1/2
✓ Branch 1 taken 84 times.
✗ Branch 2 not taken.
 84 unsigned cnx_arity = circ.n_in_edges(original_cnx);
1034
3/3
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 20 times.
✓ Branch 2 taken 40 times.
 84 switch (cnx_arity) {
1035
1/1
✓ Decision 'true' taken 24 times.
 24 case 2: {
1036
3/6
✓ Branch 2 taken 24 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 24 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 24 times.
✗ Branch 10 not taken.
 24 circ.dag[original_cnx] = {get_op_ptr(OpType::CX)};
1037 24 break;
1038 }
1039
1/1
✓ Decision 'true' taken 20 times.
 20 case 3: {
1040
3/6
✓ Branch 2 taken 20 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 20 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 20 times.
✗ Branch 10 not taken.
 20 circ.dag[original_cnx] = {get_op_ptr(OpType::CCX)};
1041 20 break;
1042 }
1043
1/1
✓ Decision 'true' taken 40 times.
 40 default: {
1044
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 lemma73(circ, pairy);
1045 }
1046 }
1047 }
1048
1/2
✓ Branch 1 taken 42 times.
✗ Branch 2 not taken.
 42 return circ;
1049 71 }
1050
1051 } // namespace CircPool
1052
1053 } // namespace tket
1054