GCC Code Coverage Report

Directory: ./
File: Diagonalisation/Diagonalisation.cpp
Date: 2022-10-15 05:10:18
Warnings: 1 unchecked decisions!
Exec Total Coverage
Lines: 228 246 92.7%
Functions: 5 5 100.0%
Branches: 304 532 57.1%
Decisions: 98 108 90.7%
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 "Diagonalisation.hpp"
16
17 #include <tkassert/Assert.hpp>
18
19 #include "Ops/Op.hpp"
20 #include "PauliGraph/ConjugatePauliFunctions.hpp"
21 #include "Utils/UnitID.hpp"
22
23 namespace tket {
24
25 67 void check_easy_diagonalise(
26 std::list<std::pair<QubitPauliTensor, Expr>> &gadgets,
27 std::set<Qubit> &qubits, Circuit &circ) {
28 67 Conjugations conjugations;
29 67 std::set<Qubit>::iterator qb_iter = qubits.begin();
30
2/2
✓ Branch 2 taken 194 times.
✓ Branch 3 taken 67 times.
2/2
✓ Decision 'true' taken 194 times.
✓ Decision 'false' taken 67 times.
 261 for (std::set<Qubit>::iterator next = qb_iter; qb_iter != qubits.end();
31 194 qb_iter = next) {
32 194 ++next;
33 194 Pauli p1 = Pauli::I;
34 194 bool remove_qb = true;
35
2/2
✓ Branch 5 taken 625 times.
✓ Branch 6 taken 111 times.
2/2
✓ Decision 'true' taken 625 times.
✓ Decision 'false' taken 111 times.
 736 for (const std::pair<QubitPauliTensor, Expr> &pgp : gadgets) {
36 std::map<tket::Qubit, tket::Pauli>::const_iterator map_iter =
37
1/2
✓ Branch 2 taken 625 times.
✗ Branch 3 not taken.
 625 pgp.first.string.map.find(*qb_iter);
38
2/2
✓ Branch 2 taken 120 times.
✓ Branch 3 taken 505 times.
2/2
✓ Decision 'true' taken 505 times.
✓ Decision 'false' taken 237 times.
 742 if (map_iter == pgp.first.string.map.end()) continue;
39 505 Pauli p2 = map_iter->second;
40
2/2
✓ Branch 0 taken 117 times.
✓ Branch 1 taken 388 times.
2/2
✓ Decision 'true' taken 388 times.
✓ Decision 'false' taken 117 times.
 505 if (p2 == Pauli::I) continue;
41
2/2
✓ Branch 0 taken 182 times.
✓ Branch 1 taken 206 times.
2/2
✓ Decision 'true' taken 182 times.
✓ Decision 'false' taken 206 times.
 388 if (p1 == Pauli::I) {
42 182 p1 = p2;
43
2/2
✓ Branch 0 taken 83 times.
✓ Branch 1 taken 123 times.
2/2
✓ Decision 'true' taken 83 times.
✓ Decision 'false' taken 123 times.
 206 } else if (p1 != p2) {
44 83 remove_qb = false;
45 83 break;
46 }
47 }
48
2/2
✓ Branch 0 taken 111 times.
✓ Branch 1 taken 83 times.
2/2
✓ Decision 'true' taken 111 times.
✓ Decision 'false' taken 83 times.
 194 if (remove_qb) {
49
4/5
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 50 times.
✓ Branch 2 taken 32 times.
✓ Branch 3 taken 17 times.
✗ Branch 4 not taken.
 111 switch (p1) {
50
1/1
✓ Decision 'true' taken 12 times.
 12 case Pauli::I:
51 12 break;
52
1/1
✓ Decision 'true' taken 100 times.
 50 case Pauli::X:
53
5/10
✓ Branch 4 taken 50 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 50 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 50 times.
✗ Branch 11 not taken.
✓ Branch 15 taken 50 times.
✓ Branch 16 taken 50 times.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
 100 conjugations.push_back({OpType::H, {*qb_iter}});
54
4/8
✓ Branch 5 taken 50 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 50 times.
✗ Branch 9 not taken.
✓ Branch 12 taken 50 times.
✓ Branch 13 taken 50 times.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
 100 circ.add_op<Qubit>(OpType::H, {*qb_iter});
55 50 break;
56
1/1
✓ Decision 'true' taken 64 times.
 32 case Pauli::Y:
57
5/10
✓ Branch 4 taken 32 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 32 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 32 times.
✗ Branch 11 not taken.
✓ Branch 15 taken 32 times.
✓ Branch 16 taken 32 times.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
 64 conjugations.push_back({OpType::Vdg, {*qb_iter}});
58
4/8
✓ Branch 5 taken 32 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 32 times.
✗ Branch 9 not taken.
✓ Branch 12 taken 32 times.
✓ Branch 13 taken 32 times.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
 64 circ.add_op<Qubit>(OpType::V, {*qb_iter});
59 32 break;
60
1/1
✓ Decision 'true' taken 17 times.
 17 case Pauli::Z:
61 17 break;
62
0/1
✗ Decision 'true' not taken.
 ✗ default:
63 ✗ throw UnknownPauli();
64 }
65
1/2
✓ Branch 1 taken 111 times.
✗ Branch 2 not taken.
 111 qubits.erase(qb_iter);
66 }
67 }
68 67 for (std::list<std::pair<QubitPauliTensor, Expr>>::iterator iter =
69 67 gadgets.begin();
70
2/2
✓ Branch 3 taken 296 times.
✓ Branch 4 taken 67 times.
 363 iter != gadgets.end(); ++iter) {
71
1/2
✓ Branch 2 taken 296 times.
✗ Branch 3 not taken.
 296 apply_conjugations(iter->first, conjugations);
72 }
73 67 }
74
75 61 std::optional<std::pair<Pauli, Pauli>> check_pair_compatibility(
76 const Qubit &qb1, const Qubit &qb2,
77 const std::list<std::pair<QubitPauliTensor, Expr>> &gadgets) {
78
3/4
✓ Branch 1 taken 61 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 23 times.
✓ Branch 4 taken 38 times.
2/2
✓ Decision 'true' taken 38 times.
✓ Decision 'false' taken 23 times.
 61 if (qb1 == qb2) return std::nullopt;
79
80 /* Do exhaustive search for a Pauli A and Pauli B that
81 satisfy Theorem */
82
1/2
✓ Branch 2 taken 38 times.
✗ Branch 3 not taken.
 38 std::list<Pauli> paulis{Pauli::Z, Pauli::X, Pauli::Y};
83
2/2
✓ Branch 5 taken 82 times.
✓ Branch 6 taken 20 times.
2/2
✓ Decision 'true' taken 82 times.
✓ Decision 'false' taken 20 times.
 102 for (Pauli pauli1 : paulis) {
84
2/2
✓ Branch 5 taken 225 times.
✓ Branch 6 taken 64 times.
2/2
✓ Decision 'true' taken 225 times.
✓ Decision 'false' taken 64 times.
 289 for (Pauli pauli2 : paulis) {
85 225 bool found_pair = true;
86
2/2
✓ Branch 5 taken 512 times.
✓ Branch 6 taken 18 times.
2/2
✓ Decision 'true' taken 512 times.
✓ Decision 'false' taken 18 times.
 530 for (const std::pair<QubitPauliTensor, Expr> &pgp : gadgets) {
87 Pauli inner_p_1;
88
1/2
✓ Branch 1 taken 512 times.
✗ Branch 2 not taken.
 512 QubitPauliMap::const_iterator iter1 = pgp.first.string.map.find(qb1);
89
2/2
✓ Branch 2 taken 151 times.
✓ Branch 3 taken 361 times.
2/2
✓ Decision 'true' taken 151 times.
✓ Decision 'false' taken 361 times.
 512 if (iter1 == pgp.first.string.map.end())
90 151 inner_p_1 = Pauli::I;
91 else
92 361 inner_p_1 = iter1->second;
93
94 Pauli inner_p_2;
95
1/2
✓ Branch 1 taken 512 times.
✗ Branch 2 not taken.
 512 QubitPauliMap::const_iterator iter2 = pgp.first.string.map.find(qb2);
96
2/2
✓ Branch 2 taken 146 times.
✓ Branch 3 taken 366 times.
2/2
✓ Decision 'true' taken 146 times.
✓ Decision 'false' taken 366 times.
 512 if (iter2 == pgp.first.string.map.end())
97 146 inner_p_2 = Pauli::I;
98 else
99 366 inner_p_2 = iter2->second;
100
101
4/4
✓ Branch 0 taken 340 times.
✓ Branch 1 taken 172 times.
✓ Branch 2 taken 83 times.
✓ Branch 3 taken 257 times.
2/2
✓ Decision 'true' taken 255 times.
✓ Decision 'false' taken 257 times.
 512 if (inner_p_1 == Pauli::I || inner_p_1 == pauli1) {
102
4/4
✓ Branch 0 taken 161 times.
✓ Branch 1 taken 94 times.
✓ Branch 2 taken 101 times.
✓ Branch 3 taken 60 times.
2/2
✓ Decision 'true' taken 101 times.
✓ Decision 'false' taken 154 times.
 255 if (!(inner_p_2 == Pauli::I || inner_p_2 == pauli2)) {
103 101 found_pair = false;
104 207 break;
105 }
106 }
107
4/4
✓ Branch 0 taken 247 times.
✓ Branch 1 taken 164 times.
✓ Branch 2 taken 96 times.
✓ Branch 3 taken 151 times.
2/2
✓ Decision 'true' taken 260 times.
✓ Decision 'false' taken 151 times.
 411 if (inner_p_2 == Pauli::I || inner_p_2 == pauli2) {
108
4/4
✓ Branch 0 taken 164 times.
✓ Branch 1 taken 96 times.
✓ Branch 2 taken 106 times.
✓ Branch 3 taken 58 times.
2/2
✓ Decision 'true' taken 106 times.
✓ Decision 'false' taken 154 times.
 260 if (!(inner_p_1 == Pauli::I || inner_p_1 == pauli1)) {
109 106 found_pair = false;
110 106 break;
111 }
112 }
113 }
114
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 207 times.
2/2
✓ Decision 'true' taken 18 times.
✓ Decision 'false' taken 207 times.
 225 if (found_pair) {
115
1/2
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
 18 return std::make_pair(pauli1, pauli2);
116 }
117 }
118 }
119 20 return std::nullopt;
120 38 }
121
122 19 void greedy_diagonalise(
123 const std::list<std::pair<QubitPauliTensor, Expr>> &gadgets,
124 std::set<Qubit> &qubits, Conjugations &conjugations, Circuit &circ,
125 CXConfigType cx_config) {
126 19 unsigned total_counter = UINT_MAX;
127 19 QubitPauliMap to_diag;
128 19 for (std::list<std::pair<QubitPauliTensor, Expr>>::const_iterator pgp_iter =
129 19 gadgets.begin();
130
2/2
✓ Branch 3 taken 97 times.
✓ Branch 4 taken 19 times.
 116 pgp_iter != gadgets.end(); ++pgp_iter) {
131 97 unsigned support_counter = 0;
132 97 QubitPauliMap to_diag_candidates;
133
2/2
✓ Branch 5 taken 430 times.
✓ Branch 6 taken 97 times.
2/2
✓ Decision 'true' taken 430 times.
✓ Decision 'false' taken 97 times.
 527 for (const Qubit &qb : qubits) {
134 QubitPauliMap::const_iterator pauli_iter =
135
1/2
✓ Branch 2 taken 430 times.
✗ Branch 3 not taken.
 430 pgp_iter->first.string.map.find(qb);
136
2/2
✓ Branch 3 taken 11 times.
✓ Branch 4 taken 419 times.
2/2
✓ Decision 'true' taken 419 times.
✓ Decision 'false' taken 11 times.
 430 if (pauli_iter == pgp_iter->first.string.map.end()) continue;
137
2/2
✓ Branch 1 taken 358 times.
✓ Branch 2 taken 61 times.
2/2
✓ Decision 'true' taken 358 times.
✓ Decision 'false' taken 61 times.
 419 if (pauli_iter->second != Pauli::I) {
138 358 ++support_counter;
139
1/2
✓ Branch 2 taken 358 times.
✗ Branch 3 not taken.
 358 to_diag_candidates.insert(*pauli_iter);
140 }
141 }
142
4/4
✓ Branch 0 taken 41 times.
✓ Branch 1 taken 56 times.
✓ Branch 2 taken 22 times.
✓ Branch 3 taken 19 times.
2/2
✓ Decision 'true' taken 22 times.
✓ Decision 'false' taken 75 times.
 97 if (support_counter < total_counter && support_counter > 1) {
143 22 total_counter = support_counter;
144
1/2
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
 22 to_diag = to_diag_candidates;
145 }
146 97 }
147
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 19 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 19 times.
 19 if (to_diag.empty()) {
148 ✗ throw std::logic_error("Brute Force Diagonalise can't find a candidate!");
149 }
150 19 for (QubitPauliMap::iterator qb_p_iter = to_diag.begin();
151
2/2
✓ Branch 3 taken 76 times.
✓ Branch 4 taken 19 times.
 95 qb_p_iter != to_diag.end(); ++qb_p_iter) {
152 76 const Qubit &qb = qb_p_iter->first;
153 76 Pauli p = qb_p_iter->second;
154
3/4
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 40 times.
✗ Branch 3 not taken.
 76 switch (p) {
155
1/1
✓ Decision 'true' taken 56 times.
 28 case Pauli::X: {
156
5/10
✓ Branch 3 taken 28 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 28 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 28 times.
✗ Branch 10 not taken.
✓ Branch 14 taken 28 times.
✓ Branch 15 taken 28 times.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
 56 conjugations.push_back({OpType::H, {qb}});
157
4/8
✓ Branch 4 taken 28 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 28 times.
✗ Branch 8 not taken.
✓ Branch 11 taken 28 times.
✓ Branch 12 taken 28 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
 56 circ.add_op<Qubit>(OpType::H, {qb});
158 28 break;
159 }
160
1/1
✓ Decision 'true' taken 16 times.
 8 case Pauli::Y: {
161
5/10
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 8 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 8 times.
✗ Branch 10 not taken.
✓ Branch 14 taken 8 times.
✓ Branch 15 taken 8 times.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
 16 conjugations.push_back({OpType::Vdg, {qb}});
162
4/8
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 8 times.
✗ Branch 8 not taken.
✓ Branch 11 taken 8 times.
✓ Branch 12 taken 8 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
 16 circ.add_op<Qubit>(OpType::V, {qb});
163 8 break;
164 }
165
1/1
✓ Decision 'true' taken 40 times.
 40 case Pauli::Z: {
166 40 break;
167 }
168 ✗ case Pauli::I:
169 default:
170 ✗ throw UnknownPauli();
171 }
172 }
173 38 qubit_vector_t diag_qubits;
174
3/4
✓ Branch 6 taken 76 times.
✗ Branch 7 not taken.
✓ Branch 10 taken 76 times.
✓ Branch 11 taken 19 times.
0/1
? Decision couldn't be analyzed.
 95 for (const auto &[k, v] : to_diag) diag_qubits.push_back(k);
175 19 unsigned n_qubits = diag_qubits.size();
176 38 Qubit first_qb = diag_qubits[0];
177
178
4/5
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 5 times.
✗ Branch 4 not taken.
 19 switch (cx_config) {
179
1/1
✓ Decision 'true' taken 21 times.
 6 case CXConfigType::Snake: {
180
2/2
✓ Branch 0 taken 15 times.
✓ Branch 1 taken 6 times.
2/2
✓ Decision 'true' taken 15 times.
✓ Decision 'false' taken 6 times.
 21 for (unsigned i = n_qubits - 1; i > 0; --i) {
181 15 Qubit qb = diag_qubits[i], before = diag_qubits[i - 1];
182
5/10
✓ Branch 4 taken 15 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 15 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 15 times.
✗ Branch 11 not taken.
✓ Branch 15 taken 30 times.
✓ Branch 16 taken 15 times.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
 45 conjugations.push_back({OpType::CX, {qb, before}});
183
4/8
✓ Branch 5 taken 15 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 15 times.
✗ Branch 9 not taken.
✓ Branch 12 taken 30 times.
✓ Branch 13 taken 15 times.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
 45 circ.add_op<Qubit>(OpType::CX, {qb, before});
184 15 }
185 6 break;
186 }
187
1/1
✓ Decision 'true' taken 18 times.
 4 case CXConfigType::Star: {
188
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 for (unsigned i = 1; i < n_qubits; ++i) {
189 14 Qubit qb = diag_qubits[i];
190
5/10
✓ Branch 4 taken 14 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 14 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 14 times.
✗ Branch 11 not taken.
✓ Branch 15 taken 28 times.
✓ Branch 16 taken 14 times.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
 42 conjugations.push_back({OpType::CX, {qb, first_qb}});
191
4/8
✓ Branch 5 taken 14 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 14 times.
✗ Branch 9 not taken.
✓ Branch 12 taken 28 times.
✓ Branch 13 taken 14 times.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
 42 circ.add_op<Qubit>(OpType::CX, {qb, first_qb});
192 14 }
193 4 break;
194 }
195
1/1
✓ Decision 'true' taken 4 times.
 4 case CXConfigType::Tree: {
196 4 unsigned complete_layers = floor(log2(n_qubits));
197 4 unsigned dense_end = pow(2, complete_layers);
198
2/2
✓ Branch 0 taken 4 times.
✓ Branch 1 taken 4 times.
2/2
✓ Decision 'true' taken 4 times.
✓ Decision 'false' taken 4 times.
 8 for (unsigned j = 0; j < n_qubits - dense_end; j++) {
199
4/8
✓ Branch 5 taken 4 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 4 times.
✗ Branch 9 not taken.
✓ Branch 12 taken 8 times.
✓ Branch 13 taken 4 times.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
 20 circ.add_op<Qubit>(
200 OpType::CX,
201 8 {diag_qubits[dense_end + j], diag_qubits[dense_end - 1 - j]});
202
5/10
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 4 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 4 times.
✗ Branch 11 not taken.
✓ Branch 15 taken 8 times.
✓ Branch 16 taken 4 times.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
 16 conjugations.push_back(
203 4 {OpType::CX,
204 8 {diag_qubits[dense_end + j], diag_qubits[dense_end - 1 - j]}});
205 }
206
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 4 times.
2/2
✓ Decision 'true' taken 6 times.
✓ Decision 'false' taken 4 times.
 10 for (unsigned step_size = 1; step_size < dense_end; step_size *= 2) {
207
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 6 times.
2/2
✓ Decision 'true' taken 8 times.
✓ Decision 'false' taken 6 times.
 14 for (unsigned j = 0; j < dense_end; j += 2 * step_size) {
208
4/8
✓ Branch 5 taken 8 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 8 times.
✗ Branch 9 not taken.
✓ Branch 12 taken 16 times.
✓ Branch 13 taken 8 times.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
 40 circ.add_op<Qubit>(
209 16 OpType::CX, {diag_qubits[j + step_size], diag_qubits[j]});
210
5/10
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 8 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 8 times.
✗ Branch 11 not taken.
✓ Branch 15 taken 16 times.
✓ Branch 16 taken 8 times.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
 32 conjugations.push_back(
211 24 {OpType::CX, {diag_qubits[j + step_size], diag_qubits[j]}});
212 }
213 }
214 4 break;
215 }
216
1/1
✓ Decision 'true' taken 5 times.
 5 case CXConfigType::MultiQGate: {
217 5 int sign_correction = 1;
218
2/2
✓ Branch 0 taken 10 times.
✓ Branch 1 taken 5 times.
2/2
✓ Decision 'true' taken 10 times.
✓ Decision 'false' taken 5 times.
 15 for (int q = n_qubits - 1; q > 0; q -= 2) {
219 10 Qubit qb = diag_qubits[q];
220
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 4 times.
2/2
✓ Decision 'true' taken 6 times.
✓ Decision 'false' taken 4 times.
 10 if (q - 1 > 0) {
221 6 Qubit before = diag_qubits[q - 1];
222
4/8
✓ 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 taken 6 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
 12 circ.add_op<Qubit>(OpType::H, {qb});
223
4/8
✓ 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 taken 6 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
 12 circ.add_op<Qubit>(OpType::H, {before});
224
5/10
✓ Branch 6 taken 6 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 6 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 6 times.
✗ Branch 13 not taken.
✓ Branch 17 taken 18 times.
✓ Branch 18 taken 6 times.
✗ Branch 24 not taken.
✗ Branch 25 not taken.
 24 circ.add_op<Qubit>(OpType::XXPhase3, 0.5, {qb, before, first_qb});
225
5/10
✓ Branch 3 taken 6 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 6 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 6 times.
✗ Branch 10 not taken.
✓ Branch 14 taken 6 times.
✓ Branch 15 taken 6 times.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
 12 conjugations.push_back({OpType::H, {qb}});
226
5/10
✓ Branch 3 taken 6 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 6 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 6 times.
✗ Branch 10 not taken.
✓ Branch 14 taken 6 times.
✓ Branch 15 taken 6 times.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
 12 conjugations.push_back({OpType::H, {before}});
227
5/10
✓ Branch 5 taken 6 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 6 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 6 times.
✗ Branch 12 not taken.
✓ Branch 16 taken 18 times.
✓ Branch 17 taken 6 times.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
 24 conjugations.push_back({OpType::XXPhase3, {qb, before, first_qb}});
228 6 sign_correction *= -1;
229 6 } else {
230
4/8
✓ Branch 5 taken 4 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 4 times.
✗ Branch 9 not taken.
✓ Branch 12 taken 8 times.
✓ Branch 13 taken 4 times.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
 12 circ.add_op<Qubit>(OpType::CX, {qb, first_qb});
231
5/10
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 4 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 4 times.
✗ Branch 11 not taken.
✓ Branch 15 taken 8 times.
✓ Branch 16 taken 4 times.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
 12 conjugations.push_back({OpType::CX, {qb, first_qb}});
232 }
233 10 }
234
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 3 times.
2/2
✓ Decision 'true' taken 4 times.
✓ Decision 'false' taken 1 times.
 5 if (sign_correction < 0) {
235
4/8
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 2 times.
✗ Branch 8 not taken.
✓ Branch 11 taken 2 times.
✓ Branch 12 taken 2 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
 4 circ.add_op<Qubit>(OpType::X, {first_qb});
236
5/10
✓ 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.
✓ Branch 14 taken 2 times.
✓ Branch 15 taken 2 times.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
 4 conjugations.push_back({OpType::X, {first_qb}});
237 }
238 5 break;
239 }
240
0/1
✗ Decision 'true' not taken.
 ✗ default:
241 ✗ throw UnknownCXConfigType();
242 }
243
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 qubits.erase(first_qb);
244 19 }
245
246 /* Diagonalise a set of Pauli Gadgets simultaneously using Cliffords*/
247 34 Circuit mutual_diagonalise(
248 std::list<std::pair<QubitPauliTensor, Expr>> &gadgets,
249 std::set<Qubit> qubits, CXConfigType cx_config) {
250 34 Circuit cliff_circ;
251
2/2
✓ Branch 5 taken 120 times.
✓ Branch 6 taken 34 times.
2/2
✓ Decision 'true' taken 120 times.
✓ Decision 'false' taken 34 times.
 154 for (const Qubit &qb : qubits) {
252
1/2
✓ Branch 1 taken 120 times.
✗ Branch 2 not taken.
 120 cliff_circ.add_qubit(qb);
253 }
254
1/2
✓ Branch 1 taken 34 times.
✗ Branch 2 not taken.
 34 check_easy_diagonalise(gadgets, qubits, cliff_circ);
255
2/2
✓ Branch 1 taken 19 times.
✓ Branch 2 taken 34 times.
2/2
✓ Decision 'true' taken 19 times.
✓ Decision 'false' taken 34 times.
 53 while (!qubits.empty()) {
256 19 Conjugations conjugations;
257
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 Qubit qb_a;
258
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 Qubit qb_b;
259 19 std::pair<Pauli, Pauli> pauli_pair;
260 19 bool found_match = false;
261 /* First, try to find some qubits we can reduce using only 1 CX */
262
2/2
✓ Branch 5 taken 23 times.
✓ Branch 6 taken 1 times.
2/2
✓ Decision 'true' taken 23 times.
✓ Decision 'false' taken 1 times.
 24 for (const Qubit &qb1 : qubits) {
263
2/2
✓ Branch 5 taken 61 times.
✓ Branch 6 taken 5 times.
2/2
✓ Decision 'true' taken 61 times.
✓ Decision 'false' taken 5 times.
 66 for (const Qubit &qb2 : qubits) {
264 std::optional<std::pair<Pauli, Pauli>> compatible =
265
1/2
✓ Branch 1 taken 61 times.
✗ Branch 2 not taken.
 61 check_pair_compatibility(qb1, qb2, gadgets);
266
2/2
✓ Branch 1 taken 18 times.
✓ Branch 2 taken 43 times.
2/2
✓ Decision 'true' taken 18 times.
✓ Decision 'false' taken 43 times.
 61 if (compatible.has_value()) {
267 18 pauli_pair = *compatible;
268 18 qb_a = qb1;
269 18 qb_b = qb2;
270 18 found_match = true;
271 18 break;
272 }
273 }
274
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 5 times.
2/2
✓ Decision 'true' taken 19 times.
✓ Decision 'false' taken 4 times.
 23 if (found_match) break;
275 }
276
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 1 times.
2/2
✓ Decision 'true' taken 18 times.
✓ Decision 'false' taken 1 times.
 19 if (found_match) {
277 18 Pauli p1 = pauli_pair.first;
278 18 Pauli p2 = pauli_pair.second;
279
2/4
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 16 times.
✗ Branch 3 not taken.
 18 switch (p1) {
280
0/1
✗ Decision 'true' not taken.
 ✗ case Pauli::X: {
281 ✗ conjugations.push_back({OpType::H, {qb_a}});
282 ✗ cliff_circ.add_op<Qubit>(OpType::H, {qb_a});
283 ✗ break;
284 }
285
1/1
✓ Decision 'true' taken 4 times.
 2 case Pauli::Y: {
286
5/10
✓ 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.
✓ Branch 14 taken 2 times.
✓ Branch 15 taken 2 times.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
 4 conjugations.push_back({OpType::Vdg, {qb_a}});
287
4/8
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 2 times.
✗ Branch 8 not taken.
✓ Branch 11 taken 2 times.
✓ Branch 12 taken 2 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
 4 cliff_circ.add_op<Qubit>(OpType::V, {qb_a});
288 2 break;
289 }
290
1/1
✓ Decision 'true' taken 16 times.
 16 case Pauli::Z: {
291 16 break;
292 }
293 ✗ case Pauli::I:
294 default:
295 ✗ throw UnknownPauli();
296 }
297
3/4
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 6 times.
✓ Branch 2 taken 9 times.
✗ Branch 3 not taken.
 18 switch (p2) {
298
1/1
✓ Decision 'true' taken 6 times.
 3 case Pauli::X: {
299
5/10
✓ Branch 3 taken 3 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 3 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 3 times.
✗ Branch 10 not taken.
✓ Branch 14 taken 3 times.
✓ Branch 15 taken 3 times.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
 6 conjugations.push_back({OpType::H, {qb_b}});
300
4/8
✓ 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 taken 3 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
 6 cliff_circ.add_op<Qubit>(OpType::H, {qb_b});
301 3 break;
302 }
303
1/1
✓ Decision 'true' taken 12 times.
 6 case Pauli::Y: {
304
5/10
✓ Branch 3 taken 6 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 6 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 6 times.
✗ Branch 10 not taken.
✓ Branch 14 taken 6 times.
✓ Branch 15 taken 6 times.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
 12 conjugations.push_back({OpType::Vdg, {qb_b}});
305
4/8
✓ 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 taken 6 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
 12 cliff_circ.add_op<Qubit>(OpType::V, {qb_b});
306 6 break;
307 }
308
1/1
✓ Decision 'true' taken 9 times.
 9 case Pauli::Z: {
309 9 break;
310 }
311 ✗ case Pauli::I:
312 default:
313 ✗ throw UnknownPauli();
314 }
315
5/10
✓ Branch 4 taken 18 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 18 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 18 times.
✗ Branch 11 not taken.
✓ Branch 15 taken 36 times.
✓ Branch 16 taken 18 times.
✗ Branch 21 not taken.
✗ Branch 22 not taken.
 54 conjugations.push_back({OpType::CX, {qb_a, qb_b}});
316
4/8
✓ Branch 5 taken 18 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 18 times.
✗ Branch 9 not taken.
✓ Branch 12 taken 36 times.
✓ Branch 13 taken 18 times.
✗ Branch 18 not taken.
✗ Branch 19 not taken.
 54 cliff_circ.add_op<Qubit>(OpType::CX, {qb_a, qb_b});
317
1/2
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
 18 qubits.erase(qb_b);
318 }
319 /* If we can't, do it with `n-1` CXs, where `n` := no. of undiagonalised
320 * qubits */
321
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 18 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 18 times.
 19 if (!found_match) {
322
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 greedy_diagonalise(gadgets, qubits, conjugations, cliff_circ, cx_config);
323 }
324 19 for (std::list<std::pair<QubitPauliTensor, Expr>>::iterator iter =
325 19 gadgets.begin();
326
2/2
✓ Branch 3 taken 117 times.
✓ Branch 4 taken 19 times.
 136 iter != gadgets.end(); ++iter) {
327
1/2
✓ Branch 2 taken 117 times.
✗ Branch 3 not taken.
 117 apply_conjugations(iter->first, conjugations);
328 }
329 // we may have made some easy-to-remove qubits
330
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 check_easy_diagonalise(gadgets, qubits, cliff_circ);
331 19 }
332 34 return cliff_circ;
333 }
334
335 483 void apply_conjugations(
336 QubitPauliTensor &qps, const Conjugations &conjugations) {
337
2/2
✓ Branch 5 taken 759 times.
✓ Branch 6 taken 483 times.
2/2
✓ Decision 'true' taken 759 times.
✓ Decision 'false' taken 483 times.
 1242 for (const auto &optype_qubit_pair : conjugations) {
338 759 OpType ot = optype_qubit_pair.first;
339 759 const qubit_vector_t &qbs = optype_qubit_pair.second;
340
5/10
✓ Branch 1 taken 759 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 759 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 759 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✓ Branch 10 taken 759 times.
✗ Branch 11 not taken.
✓ Branch 12 taken 759 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 1518 times.
 1518 if (!optypeinfo().at(ot).signature ||
341
2/4
✓ Branch 1 taken 759 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 759 times.
✗ Branch 5 not taken.
 759 optypeinfo().at(ot).signature->size() != qbs.size())
342
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ throw std::logic_error("Incompatible qubit count for conjugations");
343
3/4
✓ Branch 0 taken 480 times.
✓ Branch 1 taken 259 times.
✓ Branch 2 taken 20 times.
✗ Branch 3 not taken.
 759 switch (ot) {
344 480 case OpType::H:
345 case OpType::S:
346 case OpType::Sdg:
347 case OpType::V:
348 case OpType::Vdg:
349 case OpType::X:
350 case OpType::Z:
351
1/2
✓ Branch 2 taken 480 times.
✗ Branch 3 not taken.
 480 conjugate_PauliTensor(qps, ot, qbs[0]);
352 480 break;
353
1/1
✓ Decision 'true' taken 259 times.
 259 case OpType::CX:
354
1/2
✓ Branch 3 taken 259 times.
✗ Branch 4 not taken.
 259 conjugate_PauliTensor(qps, ot, qbs[0], qbs[1]);
355 259 break;
356
1/1
✓ Decision 'true' taken 20 times.
 20 case OpType::XXPhase3:
357
1/2
✓ Branch 4 taken 20 times.
✗ Branch 5 not taken.
 20 conjugate_PauliTensor(qps, ot, qbs[0], qbs[1], qbs[2]);
358 20 break;
359
0/1
✗ Decision 'true' not taken.
 ✗ default:
360 ✗ throw UnknownOpType();
361 }
362 }
363 483 }
364
365 } // namespace tket
366