GCC Code Coverage Report

Directory: ./
File: Diagonalisation/PauliPartition.cpp
Date: 2022-10-15 05:10:18
Warnings: 3 unchecked decisions!
Exec Total Coverage
Lines: 116 127 91.3%
Functions: 12 12 100.0%
Branches: 128 213 60.1%
Decisions: 30 45 66.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 "PauliPartition.hpp"
16
17 #include <numeric>
18 #include <tkassert/Assert.hpp>
19
20 #include "Graphs/AdjacencyData.hpp"
21 #include "Graphs/GraphColouring.hpp"
22 #include "Utils/GraphHeaders.hpp"
23
24 namespace tket {
25
26 12 PauliPartitionerGraph::PauliPartitionerGraph(
27
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 const std::list<QubitPauliString>& strings, PauliPartitionStrat strat) {
28
2/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 12 times.
✗ Branch 5 not taken.
 12 pac_graph = {};
29
2/2
✓ Branch 5 taken 24 times.
✓ Branch 6 taken 12 times.
2/2
✓ Decision 'true' taken 24 times.
✓ Decision 'false' taken 12 times.
 36 for (const QubitPauliString& tensor : strings) {
30
1/2
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
 24 PauliACVertex new_vert = boost::add_vertex(tensor, pac_graph);
31
11/16
✓ Branch 1 taken 24 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 52 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 76 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 52 times.
✓ Branch 10 taken 24 times.
✓ Branch 12 taken 52 times.
✗ Branch 13 not taken.
✓ Branch 14 taken 52 times.
✓ Branch 15 taken 24 times.
✓ Branch 17 taken 48 times.
✗ Branch 18 not taken.
✓ Branch 19 taken 24 times.
✓ Branch 20 taken 24 times.
 100 BGL_FORALL_VERTICES(v, pac_graph, PauliACGraph) {
32
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 24 times.
2/2
✓ Decision 'true' taken 28 times.
✓ Decision 'false' taken 24 times.
 52 if (v != new_vert) {
33
2/3
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
 28 switch (strat) {
34
1/1
✓ Decision 'true' taken 14 times.
 14 case (PauliPartitionStrat::NonConflictingSets): {
35
2/4
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 14 times.
✗ Branch 5 not taken.
 14 bool conflict = !tensor.conflicting_qubits(pac_graph[v]).empty();
36
3/4
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 6 times.
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
1/2
✓ Decision 'true' taken 14 times.
✗ Decision 'false' not taken.
 14 if (conflict) boost::add_edge(new_vert, v, pac_graph);
37 14 break;
38 }
39
1/1
✓ Decision 'true' taken 14 times.
 14 case (PauliPartitionStrat::CommutingSets): {
40
4/6
✓ Branch 1 taken 14 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 14 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 8 times.
✓ Branch 7 taken 6 times.
2/2
✓ Decision 'true' taken 8 times.
✓ Decision 'false' taken 6 times.
 14 if (!tensor.commutes_with(pac_graph[v])) {
41
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 boost::add_edge(new_vert, v, pac_graph);
42 }
43 14 break;
44 }
45
0/1
✗ Decision 'true' not taken.
 ✗ default: {
46 ✗ throw UnknownPauliPartitionStrat();
47 }
48 }
49 }
50 }
51 }
52 12 }
53
54 // Consider templatising this and putting it into the graph routines.
55 // The purpose is to take a boost graph and convert it
56 // into our format, ready for graph colouring.
57 // Surely an insignificant overhead unless the graph is tiny.
58 // MAYBE consider changing our graph colouring routines,
59 // by templatising/converting to boost-style.
60 class AbstractGraphData {
61 public:
62 // All the conversion work is done inside the constructor.
63 explicit AbstractGraphData(const PauliACGraph& pac_graph);
64
65 // Return the ID of the string (and also assign a new ID if the string
66 // was not seen before); the eventual IDs will form an interval {0,1,2,...,n}.
67 std::size_t get_vertex_id(const QubitPauliString& pauli_string);
68
69 typedef
70 // KEY: the Pauli string present in a vertex
71 // VALUE: an integer label for that vertex.
72 // The labels will be a contiguous interval {0,1,2,...,m}.
73 std::map<QubitPauliString, std::size_t>
74 VertexMap;
75
76 const graphs::AdjacencyData& get_adjacency_data() const;
77
78 const VertexMap& get_vertex_map() const;
79
80 private:
81 graphs::AdjacencyData m_adjacency_data;
82 VertexMap m_vertex_map;
83 };
84
85 28 std::size_t AbstractGraphData::get_vertex_id(
86 const QubitPauliString& pauli_string) {
87
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 const auto citer = m_vertex_map.find(pauli_string);
88
2/2
✓ Branch 3 taken 16 times.
✓ Branch 4 taken 12 times.
2/2
✓ Decision 'true' taken 16 times.
✓ Decision 'false' taken 12 times.
 28 if (citer != m_vertex_map.cend()) {
89 16 return citer->second;
90 }
91 // Haven't seen this vertex before!
92 12 const auto new_id = m_vertex_map.size();
93
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 m_vertex_map[pauli_string] = new_id;
94 12 return new_id;
95 }
96
97 12 const AbstractGraphData::VertexMap& AbstractGraphData::get_vertex_map() const {
98 12 return m_vertex_map;
99 }
100
101 6 const graphs::AdjacencyData& AbstractGraphData::get_adjacency_data() const {
102 6 return m_adjacency_data;
103 }
104
105 6 AbstractGraphData::AbstractGraphData(const PauliACGraph& pac_graph)
106 6 : m_adjacency_data(boost::num_vertices(pac_graph)) {
107
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 const auto vertex_iterators = boost::vertices(pac_graph);
108
3/4
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 12 times.
✓ Branch 4 taken 6 times.
0/1
? Decision couldn't be analyzed.
 18 for (auto v_iter = vertex_iterators.first; v_iter != vertex_iterators.second;
109
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 ++v_iter) {
110 // NOTE: on Windows, *v_iter appears to be of type uint64,
111 // but presumably this is an internal Boost implementation detail
112 // and we cannot rely on this.
113 // (It might even be that the Boost vertex IDs are contiguous,
114 // just like ours, in which case this conversion
115 // is unnecessary - but again, we cannot rely on this).
116
3/6
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 12 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 12 times.
✗ Branch 8 not taken.
 12 const auto this_vertex_id = get_vertex_id(pac_graph[*v_iter]);
117 const auto neighbour_iterators =
118
2/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 12 times.
✗ Branch 5 not taken.
 12 boost::adjacent_vertices(*v_iter, pac_graph);
119
120 12 for (auto n_iter = neighbour_iterators.first;
121
4/6
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 28 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 16 times.
✓ Branch 7 taken 12 times.
 28 n_iter != neighbour_iterators.second; ++n_iter) {
122
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
 16 m_adjacency_data.add_edge(
123
3/6
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 16 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 16 times.
✗ Branch 8 not taken.
 16 this_vertex_id, get_vertex_id(pac_graph[*n_iter]));
124 }
125 }
126 6 }
127
128 static std::map<unsigned, std::list<QubitPauliString>>
129 6 get_partitioned_paulis_for_exhaustive_method(const PauliACGraph& pac_graph) {
130
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 const AbstractGraphData data(pac_graph);
131 const graphs::GraphColouringResult colouring =
132
2/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 6 times.
✗ Branch 5 not taken.
 6 graphs::GraphColouringRoutines ::get_colouring(data.get_adjacency_data());
133
134 TKET_ASSERT(data.get_vertex_map().size() == colouring.colours.size());
135
136 6 std::map<unsigned, std::list<QubitPauliString>> colour_map;
137
138
3/4
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✓ Branch 7 taken 12 times.
✓ Branch 8 taken 6 times.
0/1
? Decision couldn't be analyzed.
 18 for (const auto& entry : data.get_vertex_map()) {
139 12 const QubitPauliString& vertex = entry.first;
140 12 const size_t id = entry.second;
141 TKET_ASSERT(id < colouring.colours.size());
142
143 // "id" is the index of this vertex.
144 12 const size_t colour = colouring.colours[id];
145 TKET_ASSERT(colour < colouring.number_of_colours);
146
147
2/4
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 12 times.
✗ Branch 5 not taken.
 12 colour_map[colour].push_back(vertex);
148 }
149
2/2
✓ Branch 1 taken 4 times.
✓ Branch 2 taken 2 times.
0/1
? Decision couldn't be analyzed.
 6 if (!colour_map.empty()) {
150 TKET_ASSERT(colour_map.size() == 1 + colour_map.crbegin()->first);
151 TKET_ASSERT(colour_map.cbegin()->first == 0);
152 }
153 12 return colour_map;
154 6 }
155
156 static std::map<unsigned, std::list<QubitPauliString>>
157 6 get_partitioned_paulis_for_largest_first_method(const PauliACGraph& pac_graph) {
158
2/4
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 6 times.
✗ Branch 6 not taken.
 6 std::vector<unsigned> order_vec(boost::num_vertices(pac_graph));
159 6 std::iota(order_vec.begin(), order_vec.end(), 0);
160
161
1/2
✓ Branch 3 taken 6 times.
✗ Branch 4 not taken.
 6 std::sort(order_vec.begin(), order_vec.end(), [&](unsigned i, unsigned j) {
162 18 return (boost::out_degree(i, pac_graph) > boost::out_degree(j, pac_graph));
163 });
164
165 /* Some boost machinery */
166
2/4
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 6 times.
✗ Branch 6 not taken.
 6 std::vector<unsigned> colour_vec(boost::num_vertices(pac_graph));
167 boost::iterator_property_map<
168 unsigned*,
169 boost::property_map<PauliACGraph, boost::vertex_index_t>::const_type>
170 colour_prop_map(
171
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 &colour_vec.front(), boost::get(boost::vertex_index, pac_graph));
172
2/4
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 6 times.
✗ Branch 6 not taken.
 6 boost::sequential_vertex_coloring(
173 pac_graph,
174 boost::make_iterator_property_map(
175 order_vec.begin(), boost::identity_property_map()),
176 colour_prop_map);
177
178 6 std::map<unsigned, std::list<QubitPauliString>> colour_map;
179
11/16
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 12 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 16 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 12 times.
✓ Branch 10 taken 4 times.
✓ Branch 12 taken 12 times.
✗ Branch 13 not taken.
✓ Branch 14 taken 12 times.
✓ Branch 15 taken 4 times.
✓ Branch 17 taken 10 times.
✗ Branch 18 not taken.
✓ Branch 19 taken 4 times.
✓ Branch 20 taken 6 times.
 22 BGL_FORALL_VERTICES(v, pac_graph, PauliACGraph) {
180
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 unsigned v_colour = colour_prop_map[v];
181
3/6
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 12 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 12 times.
✗ Branch 8 not taken.
 12 colour_map[v_colour].push_back(pac_graph[v]);
182 }
183 12 return colour_map;
184 6 }
185
186 std::map<unsigned, std::list<QubitPauliString>>
187 12 PauliPartitionerGraph::partition_paulis(GraphColourMethod method) const {
188
2/4
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 12 switch (method) {
189
1/1
✓ Decision 'true' taken 6 times.
 6 case GraphColourMethod::LargestFirst:
190 6 return get_partitioned_paulis_for_largest_first_method(pac_graph);
191
192
1/1
✓ Decision 'true' taken 6 times.
 6 case GraphColourMethod::Exhaustive:
193 6 return get_partitioned_paulis_for_exhaustive_method(pac_graph);
194
195
0/1
✗ Decision 'true' not taken.
 ✗ case GraphColourMethod::Lazy:
196 ✗ throw std::logic_error(
197 ✗ "Lazy graph colouring should never reach this point");
198
199
0/1
✗ Decision 'true' not taken.
 ✗ default: {
200 ✗ throw std::logic_error("Unknown graph colouring method");
201 }
202 }
203 }
204
205 static std::list<std::list<QubitPauliString>>
206 12 get_term_sequence_for_lazy_colouring_method(
207 const std::list<QubitPauliString>& strings, PauliPartitionStrat strat) {
208 12 std::list<std::list<QubitPauliString>> terms;
209
2/2
✓ Branch 5 taken 52 times.
✓ Branch 6 taken 12 times.
2/2
✓ Decision 'true' taken 52 times.
✓ Decision 'false' taken 12 times.
 64 for (const QubitPauliString& qpt : strings) {
210
2/2
✓ Branch 1 taken 10 times.
✓ Branch 2 taken 42 times.
2/2
✓ Decision 'true' taken 20 times.
✓ Decision 'false' taken 32 times.
 52 if (terms.empty()) {
211
5/10
✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 10 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 10 times.
✗ Branch 9 not taken.
✓ Branch 12 taken 10 times.
✓ Branch 13 taken 10 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
 20 terms.push_back({qpt});
212 10 continue;
213 }
214
215 42 bool found_bin = false;
216 42 for (std::list<std::list<QubitPauliString>>::iterator term_iter =
217 42 terms.begin();
218
2/2
✓ Branch 3 taken 69 times.
✓ Branch 4 taken 20 times.
 89 term_iter != terms.end(); ++term_iter) {
219 69 const std::list<QubitPauliString>& qpt_list = *term_iter;
220 69 bool viable_bin = true;
221
2/2
✓ Branch 5 taken 117 times.
✓ Branch 6 taken 22 times.
2/2
✓ Decision 'true' taken 117 times.
✓ Decision 'false' taken 22 times.
 139 for (const QubitPauliString& qpt2 : qpt_list) {
222
2/3
✓ Branch 0 taken 55 times.
✓ Branch 1 taken 62 times.
✗ Branch 2 not taken.
 117 switch (strat) {
223
1/1
✓ Decision 'true' taken 55 times.
 55 case (PauliPartitionStrat::NonConflictingSets): {
224
1/2
✓ Branch 1 taken 55 times.
✗ Branch 2 not taken.
 55 bool conflict = !qpt.conflicting_qubits(qpt2).empty();
225
2/2
✓ Branch 0 taken 38 times.
✓ Branch 1 taken 17 times.
1/2
✓ Decision 'true' taken 55 times.
✗ Decision 'false' not taken.
 55 if (conflict) viable_bin = false;
226 55 break;
227 }
228
1/1
✓ Decision 'true' taken 62 times.
 62 case (PauliPartitionStrat::CommutingSets): {
229
3/4
✓ Branch 1 taken 62 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 9 times.
✓ Branch 4 taken 53 times.
1/2
✓ Decision 'true' taken 62 times.
✗ Decision 'false' not taken.
 62 if (!qpt.commutes_with(qpt2)) viable_bin = false;
230 62 break;
231 }
232
0/1
✗ Decision 'true' not taken.
 ✗ default: {
233 ✗ throw UnknownPauliPartitionStrat();
234 }
235 }
236
237
2/2
✓ Branch 0 taken 47 times.
✓ Branch 1 taken 70 times.
2/2
✓ Decision 'true' taken 69 times.
✓ Decision 'false' taken 48 times.
 117 if (viable_bin == false) break;
238 }
239
2/2
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 47 times.
2/2
✓ Decision 'true' taken 22 times.
✓ Decision 'false' taken 47 times.
 69 if (viable_bin) {
240
1/2
✓ Branch 2 taken 22 times.
✗ Branch 3 not taken.
 22 term_iter->push_back(qpt);
241 22 found_bin = true;
242 22 break;
243 }
244 }
245
246
2/2
✓ Branch 0 taken 20 times.
✓ Branch 1 taken 22 times.
2/2
✓ Decision 'true' taken 40 times.
✓ Decision 'false' taken 2 times.
 42 if (found_bin == false) {
247
5/10
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 20 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 20 times.
✗ Branch 9 not taken.
✓ Branch 12 taken 20 times.
✓ Branch 13 taken 20 times.
✗ Branch 17 not taken.
✗ Branch 18 not taken.
 40 terms.push_back({qpt});
248 }
249 }
250 12 return terms;
251 }
252
253 static std::list<std::list<QubitPauliString>>
254 12 get_term_sequence_with_constructed_dependency_graph(
255 const std::list<QubitPauliString>& strings, PauliPartitionStrat strat,
256 GraphColourMethod method) {
257 12 std::list<std::list<QubitPauliString>> terms;
258
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 PauliPartitionerGraph pp(strings, strat);
259 std::map<unsigned, std::list<QubitPauliString>> colour_map =
260
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 pp.partition_paulis(method);
261
262 12 for (const std::pair<const unsigned, std::list<QubitPauliString>>&
263
2/2
✓ Branch 5 taken 20 times.
✓ Branch 6 taken 12 times.
 44 colour_pair : colour_map) {
264
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 terms.push_back(colour_pair.second);
265 }
266 24 return terms;
267 12 }
268
269 24 std::list<std::list<QubitPauliString>> term_sequence(
270 const std::list<QubitPauliString>& strings, PauliPartitionStrat strat,
271 GraphColourMethod method) {
272
2/3
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 24 switch (method) {
273
1/1
✓ Decision 'true' taken 12 times.
 12 case GraphColourMethod::Lazy:
274 12 return get_term_sequence_for_lazy_colouring_method(strings, strat);
275
276
0/1
✗ Decision 'true' not taken.
 12 case GraphColourMethod::LargestFirst:
277 // Deliberate fall through
278 case GraphColourMethod::Exhaustive:
279 return get_term_sequence_with_constructed_dependency_graph(
280 12 strings, strat, method);
281
0/1
✗ Decision 'true' not taken.
 ✗ default:
282 ✗ throw std::logic_error("term_sequence : unknown graph colouring method");
283 }
284 }
285
286 } // namespace tket
287