| 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 "Transform.hpp" | |||
| 18 | ||||
| 19 | namespace tket { | |||
| 20 | ||||
| 21 | /** | |||
| 22 | * Represents a position that one port of a 2qb Clifford gadget could be | |||
| 23 | * commuted to (towards the end of the circuit). | |||
| 24 | */ | |||
| 25 | struct InteractionPoint { | |||
| 26 | /** | |||
| 27 | * Edge to which one point of the interaction could potentially be moved. | |||
| 28 | * This is always in the causal future of the source vertex. | |||
| 29 | */ | |||
| 30 | Edge e; | |||
| 31 | ||||
| 32 | /** Vertex representing the current interaction */ | |||
| 33 | Vertex source; | |||
| 34 | ||||
| 35 | /** What the Pauli term would be transformed to if moved to new location */ | |||
| 36 | Pauli p; | |||
| 37 | ||||
| 38 | /** Phase of source (true for -pi/2, false for +pi/2) */ | |||
| 39 | bool phase; // For each source of an interaction, True for -pi/2, false for | |||
| 40 | // +pi/2 | |||
| 41 | ||||
| 42 | 81419 | std::pair<Edge, Vertex> key() const { return {e, source}; } | ||
| 43 | }; | |||
| 44 | ||||
| 45 | /** | |||
| 46 | * Represents a position that one port of a 2qb Clifford gadget could be | |||
| 47 | * commuted to (towards the start of the circuit). We don't need to store the | |||
| 48 | * source since we only consider commuting one gadget backwards at a time to | |||
| 49 | * search for matches. | |||
| 50 | */ | |||
| 51 | struct RevInteractionPoint { | |||
| 52 | /** | |||
| 53 | * Edge to which one point of the interaction could potentially be moved. | |||
| 54 | * This is always in the causal past of the source vertex. | |||
| 55 | */ | |||
| 56 | Edge e; | |||
| 57 | ||||
| 58 | /** What the Pauli term would be transformed to if moved to new location */ | |||
| 59 | Pauli p; | |||
| 60 | ||||
| 61 | /** Phase of source (true for -pi/2, false for +pi/2) */ | |||
| 62 | bool phase; | |||
| 63 | }; | |||
| 64 | ||||
| 65 | /** | |||
| 66 | * Represents a position to which two 2q Clifford gadgets could be commuted to | |||
| 67 | * Assumes: | |||
| 68 | * - point0.source == point1.source | |||
| 69 | * - point0.e == rev0.e | |||
| 70 | * - point1.e == rev1.e | |||
| 71 | */ | |||
| 72 | struct InteractionMatch { | |||
| 73 | InteractionPoint point0; | |||
| 74 | InteractionPoint point1; | |||
| 75 | RevInteractionPoint rev0; | |||
| 76 | RevInteractionPoint rev1; | |||
| 77 | }; | |||
| 78 | ||||
| 79 | struct TagEdge {}; | |||
| 80 | struct TagSource {}; | |||
| 81 | ||||
| 82 | /** | |||
| 83 | * Stores all current InteractionPoints encountered. | |||
| 84 | * Each gadget can only commute to a given edge in a unique way. | |||
| 85 | * Searching by edge is needed to search for possible matches. | |||
| 86 | * Searching by vertex is needed to remove InteractionPoints when a pair merge. | |||
| 87 | */ | |||
| 88 | typedef boost::multi_index::multi_index_container< | |||
| 89 | InteractionPoint, | |||
| 90 | boost::multi_index::indexed_by< | |||
| 91 | boost::multi_index::hashed_unique< | |||
| 92 | boost::multi_index::tag<TagKey>, | |||
| 93 | boost::multi_index::const_mem_fun< | |||
| 94 | InteractionPoint, std::pair<Edge, Vertex>, | |||
| 95 | &InteractionPoint::key>>, | |||
| 96 | boost::multi_index::hashed_non_unique< | |||
| 97 | boost::multi_index::tag<TagEdge>, | |||
| 98 | boost::multi_index::member< | |||
| 99 | InteractionPoint, Edge, &InteractionPoint::e>>, | |||
| 100 | boost::multi_index::hashed_non_unique< | |||
| 101 | boost::multi_index::tag<TagSource>, | |||
| 102 | boost::multi_index::member< | |||
| 103 | InteractionPoint, Vertex, &InteractionPoint::source>>>> | |||
| 104 | interaction_table_t; | |||
| 105 | ||||
| 106 | class CliffordReductionPass { | |||
| 107 | public: | |||
| 108 | /** Apply the transformation to a circuit */ | |||
| 109 | static bool reduce_circuit(Circuit &circ, bool allow_swaps = false); | |||
| 110 | ||||
| 111 | private: | |||
| 112 | /** The circuit under transformation */ | |||
| 113 | Circuit ˆ | |||
| 114 | ||||
| 115 | /** Table of potential transports of 2qb interactions through the circuit */ | |||
| 116 | interaction_table_t itable; | |||
| 117 | ||||
| 118 | /** Map from vertex to depth in circuit */ | |||
| 119 | std::map<Vertex, unsigned> v_to_depth; | |||
| 120 | ||||
| 121 | /** Map from vertex to sets of units that it acts on */ | |||
| 122 | std::map<Vertex, unit_set_t> v_to_units; | |||
| 123 | ||||
| 124 | /** Map from edge to corresponding unit */ | |||
| 125 | std::map<Edge, UnitID> e_to_unit; | |||
| 126 | ||||
| 127 | /** Whether any changes have been made to the circuit */ | |||
| 128 | bool success; | |||
| 129 | ||||
| 130 | /** Current depth in forward pass through circuit. */ | |||
| 131 | unsigned current_depth; | |||
| 132 | ||||
| 133 | /** Whether to allow SWAP gates in the final circuit */ | |||
| 134 | bool allow_swaps; | |||
| 135 | ||||
| 136 | /** | |||
| 137 | * Inserts a new interaction point into the table and tries to commute it as | |||
| 138 | * far forwards as possible, taking into account commutations and | |||
| 139 | * change-of-basis through 1q Cliffords. Does not change the circuit, but | |||
| 140 | * extends the table of interaction points as it goes. Stops propagating | |||
| 141 | * when it reaches an interaction point that is already in the table. | |||
| 142 | */ | |||
| 143 | void insert_interaction_point(InteractionPoint ip); | |||
| 144 | ||||
| 145 | /** | |||
| 146 | * Tries to commute an interaction backwards to search for a match, | |||
| 147 | * consulting the current table of interaction points to find canditates. | |||
| 148 | */ | |||
| 149 | std::optional<InteractionMatch> search_back_for_match( | |||
| 150 | const RevInteractionPoint &rip0, const RevInteractionPoint &rip1) const; | |||
| 151 | ||||
| 152 | /** | |||
| 153 | * Called when a new 2q Clifford gate is observed (either encountered by | |||
| 154 | * advancing through the circuit or by substitution mid-circuit). Handles | |||
| 155 | * scanning for pattern matches and substituting, and adding new | |||
| 156 | * InteractionPoints to look for matches further into the circuit. | |||
| 157 | */ | |||
| 158 | void process_new_interaction(const Vertex &v); | |||
| 159 | ||||
| 160 | /** | |||
| 161 | * Inserts a circuit at the given point, updating itable, v_to_depth, | |||
| 162 | * v_to_units, and e_to_unit appropriately. | |||
| 163 | * | |||
| 164 | * @pre Depth of `to_replace` is at most 1. | |||
| 165 | */ | |||
| 166 | Subcircuit substitute(const Circuit &to_insert, const Subcircuit &to_replace); | |||
| 167 | ||||
| 168 | /** | |||
| 169 | * Given a set of candidate edges, finds the earliest one that is in the | |||
| 170 | * strict causal future of source. Returns nullopt if none are in the future | |||
| 171 | * of source. Search threshold is set by only having v_to_depth defined for | |||
| 172 | * the vertices to search. | |||
| 173 | */ | |||
| 174 | std::optional<Edge> find_earliest_successor( | |||
| 175 | const Edge &source, const EdgeSet &candidates) const; | |||
| 176 | ||||
| 177 | /** | |||
| 178 | * Given two lists of edges, identifies a cut where a two-qubit operation | |||
| 179 | * could feasibly be introduced without breaking the causal structure (i.e. | |||
| 180 | * introducing loops in the DAG). Returns nullopt if there is no such cut, | |||
| 181 | * otherwise will yield the future-most valid point with respect to each of | |||
| 182 | * the sequences. | |||
| 183 | */ | |||
| 184 | std::optional<std::pair<InteractionPoint, InteractionPoint>> | |||
| 185 | valid_insertion_point( | |||
| 186 | const std::list<InteractionPoint> &seq0, | |||
| 187 | const std::list<InteractionPoint> &seq1) const; | |||
| 188 | ||||
| 189 | CliffordReductionPass(Circuit &c, bool swaps); | |||
| 190 | ||||
| 191 | friend class CliffordReductionPassTester; | |||
| 192 | }; | |||
| 193 | ||||
| 194 | /** a simple friend class of `CliffordReductionPass` used for testing | |||
| 195 | * private member functions */ | |||
| 196 | class CliffordReductionPassTester { | |||
| 197 | public: | |||
| 198 | explicit CliffordReductionPassTester(Circuit &circ); | |||
| 199 | ||||
| 200 | std::optional<std::pair<InteractionPoint, InteractionPoint>> | |||
| 201 | valid_insertion_point( | |||
| 202 | const std::list<InteractionPoint> &seq0, | |||
| 203 | const std::list<InteractionPoint> &seq1) const; | |||
| 204 | ||||
| 205 | private: | |||
| 206 | CliffordReductionPass context; | |||
| 207 | }; | |||
| 208 | ||||
| 209 | namespace Transforms { | |||
| 210 | ||||
| 211 | Transform clifford_reduction(bool allow_swaps = false); | |||
| 212 | ||||
| 213 | } | |||
| 214 | ||||
| 215 | } // namespace tket | |||
| 216 |