GCC Code Coverage Report

Directory: ./
File: Utils/include/Utils/PauliStrings.hpp
Date: 2022-10-15 05:10:18
Exec Total Coverage
Lines: 4 23 17.4%
Functions: 7 20 35.0%
Branches: 16 44 36.4%
Decisions: 0 0 -%
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 #pragma once
16
17 #include <map>
18 #include <set>
19 #include <string>
20 #include <utility>
21 #include <vector>
22
23 #include "Utils/Constants.hpp"
24 #include "Utils/EigenConfig.hpp"
25 #include "Utils/Json.hpp"
26 #include "Utils/UnitID.hpp"
27 namespace tket {
28
29 /** Pauli not supported */
30 class UnknownPauli : public std::logic_error {
31 public:
32 ✗ UnknownPauli()
33 ✗ : std::logic_error("Unknown Pauli. This code should be unreachable!") {}
34 };
35 /** OpType not supported */
36 class UnknownOpType : public std::logic_error {
37 public:
38 ✗ UnknownOpType()
39 ✗ : std::logic_error(
40 ✗ "Unknown OpType received when applying conjugations.") {}
41 };
42
43 class UnknownCXConfigType : public std::logic_error {
44 public:
45 ✗ UnknownCXConfigType()
46 ✗ : std::logic_error(
47 ✗ "Unknown CXConfigType received when decomposing gadget.") {}
48 };
49
50 class NonDefaultQubit : public std::logic_error {
51 public:
52 NonDefaultQubit()
53 : std::logic_error("Only default register Qubits are supported.") {}
54 };
55
56 typedef Eigen::SparseMatrix<Complex, Eigen::ColMajor> CmplxSpMat;
57
58 /** Symbols for the Pauli operators (and identity) */
59 enum Pauli { I, X, Y, Z };
60
61
8/18
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 65 times.
✓ 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 12 taken 2 times.
✗ Branch 13 not taken.
✓ Branch 15 taken 2 times.
✗ Branch 16 not taken.
✗ Branch 23 not taken.
✓ Branch 24 taken 67 times.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
 526 NLOHMANN_JSON_SERIALIZE_ENUM(
62 Pauli, {
63 {Pauli::I, "I"},
64 {Pauli::X, "X"},
65 {Pauli::Y, "Y"},
66 {Pauli::Z, "Z"},
67 });
68
69 /**
70 * Whenever a decomposition choice of Pauli gadgets is presented,
71 * users may use either Snake (a.k.a. cascade, ladder), Tree (i.e. CX
72 * balanced tree) or Star (i.e. CXs target a common qubit).
73 */
74 enum class CXConfigType { Snake, Tree, Star, MultiQGate };
75
76
8/18
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 5 times.
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 1 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 1 times.
✗ Branch 13 not taken.
✓ Branch 15 taken 1 times.
✗ Branch 16 not taken.
✗ Branch 23 not taken.
✓ Branch 24 taken 6 times.
✗ Branch 27 not taken.
✗ Branch 28 not taken.
✗ Branch 30 not taken.
✗ Branch 31 not taken.
 36 NLOHMANN_JSON_SERIALIZE_ENUM(
77 CXConfigType, {{CXConfigType::Snake, "Snake"},
78 {CXConfigType::Tree, "Tree"},
79 {CXConfigType::Star, "Star"},
80 {CXConfigType::MultiQGate, "MultiQGate"}});
81
82 typedef std::map<Qubit, Pauli> QubitPauliMap;
83
84 /**
85 * A string of Pauli letters from the alphabet {I, X, Y, Z},
86 * implemented as a sparse list, indexed by qubit
87 */
88 class QubitPauliString {
89 public:
90 QubitPauliMap map;
91
92 /**
93 * Construct an identity map
94 */
95 ✗ QubitPauliString() : map() {}
96
97 /**
98 * Construct a single Pauli term
99 */
100 QubitPauliString(const Qubit &qubit, Pauli p) : map({{qubit, p}}) {}
101
102 /**
103 * Construct a string of many Pauli terms. Shortcut to make a
104 * string for a default qubit register, without explicitly
105 * constructing the QubitPauliMap
106 *
107 * @param _paulis list of Pauli letters
108 */
109 explicit QubitPauliString(const std::list<Pauli> &_paulis);
110
111 /**
112 * Construct several terms from lists
113 * (useful for python hackery, and therefore not extended to QubitPauliTensor,
114 * which is not exposed to python)
115 *
116 * @param qubits list of Qubits with corresponding Paulis
117 * @param paulis Pauli letters
118 */
119 QubitPauliString(
120 const std::list<Qubit> &qubits, const std::list<Pauli> &paulis);
121
122 /**
123 * Construct a string of many Pauli terms
124 *
125 * @param _map sparse representation of the full tensor
126 */
127 ✗ explicit QubitPauliString(const QubitPauliMap &_map) : map(_map) {}
128
129 /**
130 * Determine whether two strings are equivalent (ignoring I terms)
131 *
132 * @param other second string
133 *
134 * @return true iff *this and other represent the same numerical tensor
135 */
136 bool operator==(const QubitPauliString &other) const;
137
138 /**
139 * Determine whether two strings are not equivalent (ignoring I terms)
140 *
141 * @param other second string
142 *
143 * @return true iff *this and other represent different numerical tensors
144 */
145 bool operator!=(const QubitPauliString &other) const;
146
147 /**
148 * Determine the lexicographic ordering of two strings.
149 * Ignores I terms.
150 * Orders individual terms by the ordering of Qubits.
151 *
152 * @param other other string
153 *
154 * @return true iff *this orders strictly before other
155 */
156 bool operator<(const QubitPauliString &other) const;
157
158 /**
159 * Compares the lexicographical ordering of two strings.
160 * Ignores I terms.
161 * Ordered individual terms by the ordering of Qubits.
162 *
163 * @param other other string
164 *
165 * @returns -1 if *this orders strictly before other
166 * @returns 0 if *this and other represent the same numerical tensor
167 * @returns 1 if *this orders strictly after other
168 */
169 int compare(const QubitPauliString &other) const;
170
171 /**
172 * Removes I terms to compress the sparse representation.
173 */
174 void compress();
175
176 /**
177 * Determines whether or not two strings commute.
178 *
179 * @param other String to compare this to
180 *
181 * @return true if \p other commutes with this
182 * @return false if \p other anti-commutes with this
183 */
184 bool commutes_with(const QubitPauliString &other) const;
185
186 /**
187 * Finds qubits with the same (non-trivial) Pauli term.
188 *
189 * @param other String to compare this to
190 *
191 * @return All qubits q where this->map[q] == other.map[q] != I
192 */
193 std::set<Qubit> common_qubits(const QubitPauliString &other) const;
194
195 /**
196 * Finds qubits that only occur in this string.
197 *
198 * @param other String to compare this to
199 *
200 * @return All qubits q where this->map[q] != I and other.map[q] == I
201 */
202 std::set<Qubit> own_qubits(const QubitPauliString &other) const;
203
204 /**
205 * Finds qubits with different (non-trivial) Pauli terms.
206 *
207 * @param other String to compare this to
208 *
209 * @return All qubits q where I != this->map[q] != other.map[q] != I
210 */
211 std::set<Qubit> conflicting_qubits(const QubitPauliString &other) const;
212
213 /**
214 * Readable string for sparse operator
215 */
216 std::string to_str() const;
217
218 /**
219 * Gets Pauli for a given Qubit
220 *
221 * @param q Qubit to lookup
222 *
223 * @return this->map[q] if defined, Pauli::I otherwise
224 */
225 Pauli get(const Qubit &q) const;
226
227 /**
228 * Updates this->map[q] to p
229 *
230 * @param q Qubit to update
231 * @param p Pauli to set this->map[q] = p
232 */
233 void set(const Qubit &q, Pauli p);
234
235 /**
236 * Hash method, required for top-level python. Does not
237 * distinguish between equivalent Strings, i.e. ignores I terms.
238 */
239 friend std::size_t hash_value(const QubitPauliString &qps);
240
241 /**
242 * Calculate a sparse matrix corresponding to this string.
243 *
244 * @param n_qubits Number of qubits the string covers
245 *
246 * @return A complex sparse matrix corresponding to the n_qubit operator
247 */
248
249 CmplxSpMat to_sparse_matrix() const;
250 CmplxSpMat to_sparse_matrix(const unsigned n_qubits) const;
251 CmplxSpMat to_sparse_matrix(const qubit_vector_t &qubits) const;
252
253 Eigen::VectorXcd dot_state(const Eigen::VectorXcd &state) const;
254 Eigen::VectorXcd dot_state(
255 const Eigen::VectorXcd &state, const qubit_vector_t &qubits) const;
256
257 Complex state_expectation(const Eigen::VectorXcd &state) const;
258 Complex state_expectation(
259 const Eigen::VectorXcd &state, const qubit_vector_t &qubits) const;
260 };
261
262 JSON_DECL(QubitPauliString);
263
264 // a sum of QubitPauliString with complex coefficients
265 typedef std::vector<std::pair<QubitPauliString, Complex>> OperatorSum;
266
267 /**
268 * A simple struct for Pauli strings with +/- phase,
269 * used to represent Pauli strings in a stabiliser subgroup
270 */
271 struct PauliStabiliser {
272 std::vector<Pauli> string;
273
274 /** true -> 1
275 * false -> -1
276 */
277 bool coeff;
278
279 ✗ PauliStabiliser() {}
280
281 PauliStabiliser(const std::vector<Pauli> string, const bool coeff);
282
283 /**
284 * Determine whether two PauliStabilisers are equivalent
285 *
286 * @param other second PauliStabiliser
287 *
288 * @return true iff *this and other represent PauliStabiliser
289 */
290 bool operator==(const PauliStabiliser &other) const;
291
292 /**
293 * Determine whether two PauliStabilisers are not equivalent
294 *
295 * @param other second PauliStabiliser
296 *
297 * @return true iff *this and other represent different PauliStabiliser
298 */
299 bool operator!=(const PauliStabiliser &other) const;
300 };
301
302 typedef std::vector<PauliStabiliser> PauliStabiliserList;
303
304 JSON_DECL(PauliStabiliser)
305
306 /**
307 * Calculate a sparse matrix corresponding to a sum of QubitPauliString.
308 *
309 * @param total_operator Operator specified by sum of pauli strings
310 * @param n_qubits Number of qubits the string covers
311 *
312 * @return A complex sparse matrix corresponding to the n_qubit operator
313 */
314 CmplxSpMat operator_tensor(
315 const OperatorSum &total_operator, unsigned n_qubits);
316 CmplxSpMat operator_tensor(
317 const OperatorSum &total_operator, const qubit_vector_t &qubits);
318 /**
319 * Calculate expectation value of QubitPauliString with respect to a state.
320 * <state|Operator|state>
321 *
322 * @param total_operator Operator specified by sum of pauli strings
323 * @param state state, encoded by a complex vector
324 *
325 * @return Complex expectation value
326 */
327 Complex operator_expectation(
328 const OperatorSum &total_operator, const Eigen::VectorXcd &state);
329 Complex operator_expectation(
330 const OperatorSum &total_operator, const Eigen::VectorXcd &state,
331 const qubit_vector_t &qubits);
332
333 /**
334 * A tensor of Pauli terms
335 * \f$ P = i^k \sigma_1 \otimes \sigma_2 \otimes \cdots \otimes \sigma_n \f$.
336 * This is a QubitPauliString but with an additional complex coefficient.
337 */
338 class QubitPauliTensor {
339 public:
340 typedef std::map<std::pair<Pauli, Pauli>, std::pair<Complex, Pauli>>
341 Mult_Matrix;
342 static const Mult_Matrix &get_mult_matrix();
343
344 QubitPauliString string;
345 Complex coeff;
346
347 /**
348 * Construct an identity operator
349 */
350 ✗ QubitPauliTensor() : string(), coeff(1.) {}
351
352 /**
353 * Construct a constant multiple of the identity
354 */
355 ✗ explicit QubitPauliTensor(Complex _coeff) : string(), coeff(_coeff) {}
356
357 /**
358 * Construct a single Pauli term
359 */
360 ✗ QubitPauliTensor(const Qubit &qubit, Pauli p)
361 ✗ : string({{qubit, p}}), coeff(1.) {}
362
363 /**
364 * Construct a tensor of many Pauli terms. Shortcut to make a
365 * tensor for a default qubit register, without explicitly
366 * constructing the QubitPauliMap
367 *
368 * @param _paulis list of Pauli letters
369 */
370 explicit QubitPauliTensor(const std::list<Pauli> &_paulis)
371 : string({_paulis}), coeff(1.) {}
372
373 /**
374 * Construct a constant multiple of a single Pauli term
375 */
376 QubitPauliTensor(const Qubit &qubit, Pauli p, Complex _coeff)
377 : string({{qubit, p}}), coeff(_coeff) {}
378
379 /**
380 * Construct a tensor product of many Pauli terms
381 *
382 * @param _string sparse representation of the full tensor
383 */
384 203 explicit QubitPauliTensor(const QubitPauliString &_string)
385 203 : string(_string), coeff(1.) {}
386
387 /**
388 * Construct a tensor product of many Pauli terms
389 *
390 * @param _map sparse representation of the full tensor
391 */
392 ✗ explicit QubitPauliTensor(const QubitPauliMap &_map)
393 ✗ : string(_map), coeff(1.) {}
394
395 /**
396 * Construct an arbitrary QubitPauliTensor
397 *
398 * @param _string sparse representation of the full tensor
399 * @param _coeff complex coefficient
400 */
401 ✗ QubitPauliTensor(const QubitPauliString &_string, Complex _coeff)
402 ✗ : string(_string), coeff(_coeff) {}
403
404 /**
405 * Construct an arbitrary QubitPauliTensor
406 *
407 * @param _map sparse representation of the full tensor
408 * @param _coeff complex coefficient
409 */
410 QubitPauliTensor(const QubitPauliMap &_map, Complex _coeff)
411 : string(_map), coeff(_coeff) {}
412
413 /**
414 * Calculate the product of two tensors
415 *
416 * @param other second tensor
417 *
418 * @return *this x other
419 */
420 QubitPauliTensor operator*(const QubitPauliTensor &other) const;
421
422 /**
423 * Determine whether two tensors are equivalent (ignoring I terms)
424 *
425 * @param other second tensor
426 *
427 * @return true iff *this and other represent the same numerical tensor
428 */
429 bool operator==(const QubitPauliTensor &other) const;
430
431 /**
432 * Determine whether two tensors are not equivalent (ignoring I terms)
433 *
434 * @param other second tensor
435 *
436 * @return true iff *this and other represent different numerical tensors
437 */
438 bool operator!=(const QubitPauliTensor &other) const;
439
440 /**
441 * Determine the lexicographic ordering of two tensors.
442 * Ignores I terms.
443 * Orders individual terms by the ordering of Qubits.
444 * If two terms have equivalent tensors, they are ordered by coefficient
445 * (lexicographically according to the pair <real, imag>).
446 *
447 * @param other second tensor
448 *
449 * @return true iff *this orders strictly before other
450 */
451 bool operator<(const QubitPauliTensor &other) const;
452
453 /**
454 * Removes I terms to compress the sparse representation.
455 * Wrapper method for `QubitPauliString` method.
456 */
457 void compress();
458
459 /**
460 * Determines whether or not two tensor commute.
461 * Wrapper method for `QubitPauliString` method.
462 *
463 * @param other Tensor to compare this to
464 *
465 * @return true if \p other commutes with this
466 * @return false if \p other anti-commutes with this
467 */
468 bool commutes_with(const QubitPauliTensor &other) const;
469
470 /**
471 * Finds qubits with the same (non-trivial) Pauli term.
472 * Wrapper method for `QubitPauliString` method.
473 *
474 * @param other Tensor to compare this to
475 *
476 * @return All qubits q where this->string.map[q] == other.string.map[q] != I
477 */
478 std::set<Qubit> common_qubits(const QubitPauliTensor &other) const;
479
480 /**
481 * Finds qubits that only occur in this tensor.
482 * Wrapper method for `QubitPauliString` method.
483 *
484 * @param other Tensor to compare this to
485 *
486 * @return All qubits q where this->string.map[q] != I and other.string.map[q]
487 * == I
488 */
489 std::set<Qubit> own_qubits(const QubitPauliTensor &other) const;
490
491 /**
492 * Finds qubits with different (non-trivial) Pauli terms.
493 * Wrapper method for `QubitPauliString` method.
494 *
495 * @param other Tensor to compare this to
496 *
497 * @return All qubits q where I != this->string.map[q] != other.string.map[q]
498 * != I
499 */
500 std::set<Qubit> conflicting_qubits(const QubitPauliTensor &other) const;
501
502 /**
503 * Readable string for sparse operator
504 */
505 std::string to_str() const;
506
507 /**
508 * Hash method, required for top-level python. Does not
509 * distinguish between equivalent Strings, i.e. ignores I terms.
510 */
511 friend std::size_t hash_value(const QubitPauliTensor &qpt);
512 };
513
514 /**
515 * Multiply coefficient by a scalar
516 *
517 * @param a scalar multiplier
518 * @param qpt tensor
519 *
520 * @return result of the scalar multiplication
521 */
522 QubitPauliTensor operator*(Complex a, const QubitPauliTensor &qpt);
523
524 } // namespace tket
525