| 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 "DiagUtils.hpp" | |||
| 18 | ||||
| 19 | namespace tket { | |||
| 20 | ||||
| 21 | class UnknownPauliPartitionStrat : public std::logic_error { | |||
| 22 | public: | |||
| 23 | ✗ | UnknownPauliPartitionStrat() | ||
| 24 | ✗ | : std::logic_error( | ||
| 25 | "Unknown PauliPartitionStrat received when partitioning " | |||
| 26 | ✗ | "Pauli tensors.") {} | ||
| 27 | }; | |||
| 28 | ||||
| 29 | /** | |||
| 30 | * A PauliACGraph is a graph where each vertex is a Pauli tensor, and | |||
| 31 | * an edge corresponds to anticommuting tensors | |||
| 32 | */ | |||
| 33 | ||||
| 34 | typedef boost::adjacency_list< | |||
| 35 | boost::vecS, boost::vecS, boost::undirectedS, QubitPauliString> | |||
| 36 | PauliACGraph; | |||
| 37 | ||||
| 38 | typedef boost::graph_traits<PauliACGraph>::vertex_descriptor PauliACVertex; | |||
| 39 | ||||
| 40 | /** | |||
| 41 | * A choice of strategies to partition Pauli tensors into sets | |||
| 42 | */ | |||
| 43 | enum class PauliPartitionStrat { | |||
| 44 | /** | |||
| 45 | * Sets of tensors with no conflicting Paulis; requires no CXs for | |||
| 46 | * diagonalisation | |||
| 47 | */ | |||
| 48 | NonConflictingSets, | |||
| 49 | /** | |||
| 50 | * Sets of mutually commuting tensors; requires O(n^2) CXs for | |||
| 51 | * diagonalisation | |||
| 52 | */ | |||
| 53 | CommutingSets | |||
| 54 | }; | |||
| 55 | ||||
| 56 | /** | |||
| 57 | * A choice of methods to perform graph colouring for Pauli partitioning | |||
| 58 | */ | |||
| 59 | enum class GraphColourMethod { | |||
| 60 | /** | |||
| 61 | * Lazy: does not build the graph before performing the colouring; | |||
| 62 | * partitions while iterating through the Pauli tensors in the | |||
| 63 | * input order. | |||
| 64 | */ | |||
| 65 | Lazy, | |||
| 66 | /** | |||
| 67 | * Builds the graph and then greedily colours by iterating through | |||
| 68 | * the vertices, with the highest degree first. | |||
| 69 | */ | |||
| 70 | LargestFirst, | |||
| 71 | /** | |||
| 72 | * Builds the graph, then colours it using the minimum possible | |||
| 73 | * number of colours. Exponential time in the worst case, | |||
| 74 | * but usually returns a result in reasonable time. | |||
| 75 | */ | |||
| 76 | Exhaustive | |||
| 77 | }; | |||
| 78 | ||||
| 79 | /** | |||
| 80 | * A helper class for converting QubitOperator into PauliACGraphs and | |||
| 81 | * then colouring the PauliACGraph using some method. | |||
| 82 | */ | |||
| 83 | class PauliPartitionerGraph { | |||
| 84 | public: | |||
| 85 | explicit PauliPartitionerGraph( | |||
| 86 | const std::list<QubitPauliString>& strings, PauliPartitionStrat strat); | |||
| 87 | ||||
| 88 | // KEY: the colour VALUE: all the Pauli strings assigned that colour. | |||
| 89 | std::map<unsigned, std::list<QubitPauliString>> partition_paulis( | |||
| 90 | GraphColourMethod method) const; | |||
| 91 | ||||
| 92 | private: | |||
| 93 | PauliACGraph pac_graph; | |||
| 94 | }; | |||
| 95 | ||||
| 96 | /** | |||
| 97 | * Partitions a QubitOperator into lists of mutually commuting gadgets. | |||
| 98 | * Assumes that each `QubitPauliString` is unique and does not attempt | |||
| 99 | * to combine them. If it is given non-unique tensors it will produce | |||
| 100 | * inefficient results. | |||
| 101 | */ | |||
| 102 | std::list<std::list<QubitPauliString>> term_sequence( | |||
| 103 | const std::list<QubitPauliString>& strings, PauliPartitionStrat strat, | |||
| 104 | GraphColourMethod method = GraphColourMethod::Lazy); | |||
| 105 | ||||
| 106 | } // namespace tket | |||
| 107 |