| 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 <fstream> | |||
| 18 | #include <stdexcept> | |||
| 19 | ||||
| 20 | #include "Clifford/CliffTableau.hpp" | |||
| 21 | #include "Utils/Expression.hpp" | |||
| 22 | #include "Utils/GraphHeaders.hpp" | |||
| 23 | #include "Utils/PauliStrings.hpp" | |||
| 24 | #include "Utils/SequencedContainers.hpp" | |||
| 25 | ||||
| 26 | namespace tket { | |||
| 27 | class Gate; | |||
| 28 | ||||
| 29 | struct PauliGadgetProperties { | |||
| 30 | QubitPauliTensor tensor_; | |||
| 31 | Expr angle_; | |||
| 32 | }; | |||
| 33 | ||||
| 34 | struct DependencyEdgeProperties {}; | |||
| 35 | ||||
| 36 | typedef boost::adjacency_list< | |||
| 37 | boost::listS, boost::listS, boost::bidirectionalS, PauliGadgetProperties, | |||
| 38 | DependencyEdgeProperties> | |||
| 39 | PauliDAG; | |||
| 40 | typedef boost::graph_traits<PauliDAG>::vertex_descriptor PauliVert; | |||
| 41 | typedef boost::graph_traits<PauliDAG>::edge_descriptor PauliEdge; | |||
| 42 | ||||
| 43 | typedef sequence_set_t<PauliVert> PauliVertSet; | |||
| 44 | typedef sequence_set_t<PauliEdge> PauliEdgeSet; | |||
| 45 | typedef std::list<std::pair<OpType, qubit_vector_t>> Conjugations; | |||
| 46 | ||||
| 47 | class Circuit; | |||
| 48 | ||||
| 49 | class MidCircuitMeasurementNotAllowed : public std::logic_error { | |||
| 50 | public: | |||
| 51 | 1 | explicit MidCircuitMeasurementNotAllowed(const std::string &message) | ||
| 52 | 1 | : std::logic_error(message) {} | ||
| 53 | }; | |||
| 54 | ||||
| 55 | /** | |||
| 56 | * Dependency graph of a circuit wrt Pauli Gadgets. | |||
| 57 | * Constructed by effectively commuting all non-Clifford gates to the front | |||
| 58 | * of the circuit and determining their dependencies based on commutation | |||
| 59 | * of the Pauli strings. | |||
| 60 | * The Clifford effect of a circuit is maintained as a tableau, thought of as | |||
| 61 | * being applied after all of the gadgets. | |||
| 62 | */ | |||
| 63 | class PauliGraph { | |||
| 64 | public: | |||
| 65 | /** Construct an empty dependency graph for the identity over n qubits. */ | |||
| 66 | explicit PauliGraph(unsigned n); | |||
| 67 | ||||
| 68 | /** Construct an empty dependency graph for the identity over given qubits. */ | |||
| 69 | explicit PauliGraph(const qubit_vector_t &qbs, const bit_vector_t &bits = {}); | |||
| 70 | ||||
| 71 | /** | |||
| 72 | * Applies the given gate to the end of the circuit. | |||
| 73 | * Clifford gates transform the tableau. | |||
| 74 | * Non-Clifford gates are transformed into gadgets by the tableau and added | |||
| 75 | * to the graph. | |||
| 76 | */ | |||
| 77 | void apply_gate_at_end(const Gate &gate, const unit_vector_t &args); | |||
| 78 | ||||
| 79 | /** Visualisation of the dependency graph */ | |||
| 80 | void to_graphviz_file(const std::string &filename) const; | |||
| 81 | void to_graphviz(std::ostream &out) const; | |||
| 82 | ||||
| 83 | const CliffTableau &get_clifford_ref() { return cliff_; } | |||
| 84 | unsigned n_vertices() const { return boost::num_vertices(this->graph_); } | |||
| 85 | ||||
| 86 | friend PauliGraph circuit_to_pauli_graph(const Circuit &circ); | |||
| 87 | friend Circuit pauli_graph_to_circuit_individually( | |||
| 88 | const PauliGraph &pg, CXConfigType cx_config); | |||
| 89 | friend Circuit pauli_graph_to_circuit_pairwise( | |||
| 90 | const PauliGraph &pg, CXConfigType cx_config); | |||
| 91 | friend Circuit pauli_graph_to_circuit_sets( | |||
| 92 | const PauliGraph &pg, CXConfigType cx_config); | |||
| 93 | ||||
| 94 | private: | |||
| 95 | /** The dependency graph of Pauli gadgets */ | |||
| 96 | PauliDAG graph_; | |||
| 97 | /** The tableau of the Clifford effect of the circuit */ | |||
| 98 | CliffTableau cliff_; | |||
| 99 | /** The record of measurements at the very end of the circuit */ | |||
| 100 | boost::bimap<Qubit, Bit> measures_; | |||
| 101 | bit_vector_t bits_; | |||
| 102 | /** | |||
| 103 | * Caches of the set of Pauli gadgets that can be commuted to the start | |||
| 104 | * or the end of the circuit. | |||
| 105 | */ | |||
| 106 | PauliVertSet start_line_; | |||
| 107 | PauliVertSet end_line_; | |||
| 108 | ||||
| 109 | PauliVertSet get_successors(const PauliVert &vert) const; | |||
| 110 | PauliVertSet get_predecessors(const PauliVert &vert) const; | |||
| 111 | PauliEdgeSet get_in_edges(const PauliVert &vert) const; | |||
| 112 | PauliEdgeSet get_out_edges(const PauliVert &vert) const; | |||
| 113 | PauliVert source(const PauliEdge &edge) const; | |||
| 114 | PauliVert target(const PauliEdge &edge) const; | |||
| 115 | ||||
| 116 | /** | |||
| 117 | * Appends a pauli gadget at the end of the dependency graph. | |||
| 118 | * Assumes this is the result AFTER pushing it through the Clifford | |||
| 119 | * tableau. | |||
| 120 | */ | |||
| 121 | void apply_pauli_gadget_at_end( | |||
| 122 | const QubitPauliTensor &pauli, const Expr &angle); | |||
| 123 | ||||
| 124 | /** | |||
| 125 | * Iterates through the vertices of a PauliGraph in a topological ordering. | |||
| 126 | * When there are multiple commuting vertices that could be emitted, this | |||
| 127 | * selects the one with the lowest lexicographic ordering on the Pauli string. | |||
| 128 | */ | |||
| 129 | class TopSortIterator { | |||
| 130 | public: | |||
| 131 | TopSortIterator(); | |||
| 132 | explicit TopSortIterator(const PauliGraph &pg); | |||
| 133 | ||||
| 134 | const PauliVert &operator*() const; | |||
| 135 | const PauliVert *operator->() const; | |||
| 136 | bool operator==(const TopSortIterator &other) const; | |||
| 137 | bool operator!=(const TopSortIterator &other) const; | |||
| 138 | ||||
| 139 | TopSortIterator operator++(int); | |||
| 140 | TopSortIterator &operator++(); | |||
| 141 | ||||
| 142 | private: | |||
| 143 | const PauliGraph *pg_; | |||
| 144 | PauliVert current_vert_; | |||
| 145 | std::set<std::pair<QubitPauliTensor, PauliVert>> | |||
| 146 | search_set_; // Use pair to force ordering by string | |||
| 147 | std::unordered_set<PauliVert> visited_; | |||
| 148 | }; | |||
| 149 | ||||
| 150 | TopSortIterator begin() const; | |||
| 151 | TopSortIterator end() const; | |||
| 152 | }; | |||
| 153 | ||||
| 154 | } // namespace tket | |||
| 155 |