| 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 <memory> | |||
| 18 | #include <optional> | |||
| 19 | ||||
| 20 | #include "Circuit/Circuit.hpp" | |||
| 21 | #include "Gate/GatePtr.hpp" | |||
| 22 | ||||
| 23 | namespace tket { | |||
| 24 | ||||
| 25 | /** | |||
| 26 | * @brief Abstract Squasher interface | |||
| 27 | * | |||
| 28 | * Subclasses must implement these methods to be used as a squasher | |||
| 29 | * in SingleQubitSquash | |||
| 30 | * | |||
| 31 | * Squashers should always squash circuits into a "normal form", which is left | |||
| 32 | * invariant under further squashing. This is to avoid infinite loops where | |||
| 33 | * circuits would get squashed in a cycle, never reaching an equilibrium. | |||
| 34 | */ | |||
| 35 | class AbstractSquasher { | |||
| 36 | public: | |||
| 37 | /** | |||
| 38 | * @brief Whether the OpType can be added to current squash. | |||
| 39 | * | |||
| 40 | * @param gp Gate_ptr to be accepted. | |||
| 41 | * @retval true `ot` can be squashed. | |||
| 42 | * @retval false `ot` cannot be squashed. | |||
| 43 | */ | |||
| 44 | virtual bool accepts(Gate_ptr gp) const = 0; | |||
| 45 | ||||
| 46 | /** | |||
| 47 | * @brief Add gate to current squash. | |||
| 48 | * | |||
| 49 | * @pre `accepts(gp->get_type())` must return true | |||
| 50 | * @param gp Gate to add to squash. | |||
| 51 | */ | |||
| 52 | virtual void append(Gate_ptr gp) = 0; | |||
| 53 | ||||
| 54 | /** | |||
| 55 | * @brief obtain the current squash as circuit and gate to be commuted | |||
| 56 | * | |||
| 57 | * Optionally use the commutation colour of the next gate to return an | |||
| 58 | * additional Gate_ptr to be commuted through. | |||
| 59 | * If no gate should be commuted, return nullptr. | |||
| 60 | * If `commutation_colour==std::nullopt`, then the returned Gate_ptr | |||
| 61 | * is expected to be `nullptr` | |||
| 62 | * | |||
| 63 | * @param commutation_colour | |||
| 64 | * @return std::pair<Circuit, Gate_ptr> | |||
| 65 | */ | |||
| 66 | virtual std::pair<Circuit, Gate_ptr> flush( | |||
| 67 | std::optional<Pauli> commutation_colour) const = 0; | |||
| 68 | ||||
| 69 | /** | |||
| 70 | * @brief Reset the current squash. | |||
| 71 | */ | |||
| 72 | virtual void clear() = 0; | |||
| 73 | ||||
| 74 | /** | |||
| 75 | * @brief Virtual constructor | |||
| 76 | * | |||
| 77 | * @return std::unique_ptr<AbstractSquasher> A copy of *this. | |||
| 78 | */ | |||
| 79 | virtual std::unique_ptr<AbstractSquasher> clone() const = 0; | |||
| 80 | ||||
| 81 | 12910 | virtual ~AbstractSquasher() {} | ||
| 82 | }; | |||
| 83 | ||||
| 84 | /** | |||
| 85 | * @brief Squashes single qubit gates using given Squasher. | |||
| 86 | */ | |||
| 87 | class SingleQubitSquash { | |||
| 88 | private: | |||
| 89 | using Condition = std::optional<std::pair<std::list<VertPort>, unsigned>>; | |||
| 90 | ||||
| 91 | public: | |||
| 92 | /** | |||
| 93 | * @brief Construct a new Single Qubit Squash object. | |||
| 94 | * | |||
| 95 | * @param squasher The Squasher instance. | |||
| 96 | * @param circ The circuit to be squashed. | |||
| 97 | * @param reversed Whether squashing is made back to front or front to back | |||
| 98 | * (default: false, ie front to back). | |||
| 99 | */ | |||
| 100 | ✗ | SingleQubitSquash( | ||
| 101 | std::unique_ptr<AbstractSquasher> squasher, Circuit &circ, | |||
| 102 | bool reversed = false) | |||
| 103 | ✗ | : squasher_(std::move(squasher)), circ_(circ), reversed_(reversed) {} | ||
| 104 | ||||
| 105 | // rule of 5 | |||
| 106 | SingleQubitSquash(const SingleQubitSquash &other); | |||
| 107 | SingleQubitSquash &operator=(const SingleQubitSquash &other); | |||
| 108 | ✗ | ~SingleQubitSquash() = default; | ||
| 109 | SingleQubitSquash(SingleQubitSquash &&other); | |||
| 110 | SingleQubitSquash &operator=(SingleQubitSquash &&other); | |||
| 111 | ||||
| 112 | /** | |||
| 113 | * @brief Squash entire circuit, one qubit at a time. | |||
| 114 | * | |||
| 115 | * @retval true The squash succeeded. | |||
| 116 | * @retval false The circuit was not changed. | |||
| 117 | */ | |||
| 118 | bool squash(); | |||
| 119 | ||||
| 120 | /** | |||
| 121 | * @brief Squash everything between in-edge and out-edge | |||
| 122 | * | |||
| 123 | * If `reversed=true`, then the in-edge should come after the out-edge | |||
| 124 | * in the circuit. | |||
| 125 | * | |||
| 126 | * @param in Starting edge of the squash. | |||
| 127 | * @param out Last edge of the squash. | |||
| 128 | * | |||
| 129 | * @retval true The circuit was changed. | |||
| 130 | * @retval false The circuit was not changed. | |||
| 131 | */ | |||
| 132 | bool squash_between(const Edge &in, const Edge &out); | |||
| 133 | ||||
| 134 | private: | |||
| 135 | std::unique_ptr<AbstractSquasher> squasher_; | |||
| 136 | Circuit &circ_; | |||
| 137 | bool reversed_; | |||
| 138 | ||||
| 139 | // substitute chain by a sub circuit, handling conditions | |||
| 140 | // and backing up + restoring current edge | |||
| 141 | void substitute( | |||
| 142 | const Circuit &sub, const VertexVec &single_chain, Edge &e, | |||
| 143 | const Condition &condition); | |||
| 144 | ||||
| 145 | // insert a gate at the given edge, respecting condition | |||
| 146 | void insert_left_over_gate( | |||
| 147 | Op_ptr left_over, const Edge &e, const Condition &condition); | |||
| 148 | ||||
| 149 | // whether a vertex can be squashed with the previous vertices | |||
| 150 | bool is_squashable(Vertex v, OpType v_type) const; | |||
| 151 | ||||
| 152 | // whether the sub circuit is shorter than chain | |||
| 153 | bool sub_is_better( | |||
| 154 | const Circuit &sub, const std::vector<Gate_ptr> chain) const; | |||
| 155 | ||||
| 156 | // returns a description of the condition of current vertex | |||
| 157 | Condition get_condition(Vertex v) const; | |||
| 158 | ||||
| 159 | // simple utils respecting reversed boolean | |||
| 160 | Vertex next_vertex(const Edge &e) const; | |||
| 161 | ||||
| 162 | port_t next_port(const Edge &e) const; | |||
| 163 | ||||
| 164 | Edge prev_edge(const VertPort &pair) const; | |||
| 165 | ||||
| 166 | Edge next_edge(const Vertex &v, const Edge &e) const; | |||
| 167 | ||||
| 168 | bool is_last_optype(OpType type) const; | |||
| 169 | ||||
| 170 | static bool is_equal( | |||
| 171 | const Circuit &circ, const std::vector<Gate_ptr> &gates, | |||
| 172 | bool reversed = false); | |||
| 173 | }; | |||
| 174 | ||||
| 175 | } // namespace tket | |||
| 176 |