| 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 "Architecture/Architecture.hpp" | |||
| 18 | #include "Circuit/Circuit.hpp" | |||
| 19 | #include "Utils/BiMapHeaders.hpp" | |||
| 20 | #include "Utils/UnitID.hpp" | |||
| 21 | ||||
| 22 | namespace tket { | |||
| 23 | ||||
| 24 | typedef sequenced_bimap_t<UnitID, VertPort> unit_vertport_frontier_t; | |||
| 25 | ||||
| 26 | // list of error types to throw out | |||
| 27 | class MappingFrontierError : public std::logic_error { | |||
| 28 | public: | |||
| 29 | 4 | explicit MappingFrontierError(const std::string& message) | ||
| 30 | 4 | : std::logic_error(message) {} | ||
| 31 | }; | |||
| 32 | ||||
| 33 | /** | |||
| 34 | * linear_boundary stored as vertport so that correct edge can be recovered | |||
| 35 | * after subcircuit substitution method uses Vertex and port_t and | |||
| 36 | * Circuit::get_nth_out_edge to generate unit_frontier_t object | |||
| 37 | */ | |||
| 38 | std::shared_ptr<unit_frontier_t> frontier_convert_vertport_to_edge( | |||
| 39 | const Circuit& circuit, | |||
| 40 | const std::shared_ptr<unit_vertport_frontier_t>& u_frontier); | |||
| 41 | ||||
| 42 | /** | |||
| 43 | * convert_u_frontier_to_edges | |||
| 44 | * Subcircuit requires EdgeVec, not unit_frontier_t as boundary information | |||
| 45 | * Helper Functions to convert types | |||
| 46 | */ | |||
| 47 | EdgeVec convert_u_frontier_to_edges(const unit_frontier_t& u_frontier); | |||
| 48 | struct MappingFrontier { | |||
| 49 | /** | |||
| 50 | * VertPort instead of Edge as Edge changes in substitution, but Vertex and | |||
| 51 | * Port key information | |||
| 52 | */ | |||
| 53 | std::shared_ptr<unit_vertport_frontier_t> linear_boundary; | |||
| 54 | ||||
| 55 | std::shared_ptr<b_frontier_t> boolean_boundary; | |||
| 56 | ||||
| 57 | /** | |||
| 58 | * Circuit held by reference and directly modified with SWAP (or other | |||
| 59 | * relevant) gates. | |||
| 60 | */ | |||
| 61 | Circuit& circuit_; | |||
| 62 | ||||
| 63 | std::set<Node> ancilla_nodes_; | |||
| 64 | ||||
| 65 | std::shared_ptr<unit_bimaps_t> bimaps_; | |||
| 66 | ||||
| 67 | MappingFrontier(Circuit& _circuit); | |||
| 68 | ||||
| 69 | MappingFrontier(Circuit& _circuit, std::shared_ptr<unit_bimaps_t> _bimaps); | |||
| 70 | ||||
| 71 | // copy constructor | |||
| 72 | MappingFrontier(const MappingFrontier& mapping_frontier); | |||
| 73 | ||||
| 74 | /** | |||
| 75 | * Given some Circuit Cut (or routed/unrouted boundary), advances the cut to | |||
| 76 | * the next cut of just two-qubit vertices, not including the current | |||
| 77 | * boundary. | |||
| 78 | * @param max_advance maximum number of cuts checked before terminating | |||
| 79 | */ | |||
| 80 | void advance_next_2qb_slice(unsigned max_advance); | |||
| 81 | ||||
| 82 | /** | |||
| 83 | * mapping_frontier data members updated to reflect | |||
| 84 | * the routed/non-routed boundary of mapping_frontier->circ | |||
| 85 | * architecture.valid_gate confirms whether circuit vertices are physically | |||
| 86 | * valid | |||
| 87 | * | |||
| 88 | * @param architecture Architecture governing physically allowed operations | |||
| 89 | */ | |||
| 90 | void advance_frontier_boundary(const ArchitecturePtr& architecture); | |||
| 91 | ||||
| 92 | /** | |||
| 93 | * Subcircuit produced from gates after held boundary. | |||
| 94 | * @param _max_subcircuit_depth | |||
| 95 | * @param _max_subcircuit_size | |||
| 96 | * | |||
| 97 | */ | |||
| 98 | Subcircuit get_frontier_subcircuit( | |||
| 99 | unsigned _max_subcircuit_depth, unsigned _max_subcircuit_size) const; | |||
| 100 | ||||
| 101 | /** | |||
| 102 | * update_linear_boundary_uids | |||
| 103 | * route_circuit has no constraint that passed circuits must have qubits | |||
| 104 | * relabelled to architecture nodes route_subcircuit is allowed to either | |||
| 105 | * permute labelled physical qubits, or label logical qubits if logical qubits | |||
| 106 | * are labelled physical, update_linear_boundary updates UnitID in | |||
| 107 | * this->linear_boundary to reflect this change Also updates this->circuit_ | |||
| 108 | * to reflect this relabelling | |||
| 109 | * | |||
| 110 | * @param relabel_map map between current UnitID's in linear_boundary and new | |||
| 111 | * UnitID's. | |||
| 112 | */ | |||
| 113 | void update_linear_boundary_uids(const unit_map_t& relabel_map); | |||
| 114 | ||||
| 115 | /** | |||
| 116 | * permute_subcircuit_q_out_hole | |||
| 117 | * | |||
| 118 | * Given initial permutation of UnitIDs, finds final permutation via SWAPs in | |||
| 119 | * circuit and updates mapping_frontier subcircuit q_out_hole to reflect this | |||
| 120 | * | |||
| 121 | * @param final_permutation map between initial and final physical qubits for | |||
| 122 | * each logical qubit, used to permute subcircuit.q_out_hole | |||
| 123 | * @param subcircuit Subcircuit for rearranging boundary | |||
| 124 | */ | |||
| 125 | void permute_subcircuit_q_out_hole( | |||
| 126 | const unit_map_t& final_permutation, Subcircuit& subcircuit); | |||
| 127 | ||||
| 128 | /** | |||
| 129 | * get_default_to_linear_boundary_unit_map | |||
| 130 | * subcircuit circuits created with default q register | |||
| 131 | * method returns map between default q register and physical qubit | |||
| 132 | * permutation at frontier used for circuit.rename_units | |||
| 133 | */ | |||
| 134 | unit_map_t get_default_to_linear_boundary_unit_map() const; | |||
| 135 | ||||
| 136 | /** | |||
| 137 | * add_swap | |||
| 138 | * Inserts an OpType::SWAP gate into the uid_0 and uid_1 edges held in | |||
| 139 | * linear_boundary. This directly modifies circuit_. | |||
| 140 | * Updates linear_boundary to reflect new edges. | |||
| 141 | * | |||
| 142 | * @param uid_0 First Node in SWAP | |||
| 143 | * @param uid_1 Second Node in SWAP | |||
| 144 | * @return true if SWAP added | |||
| 145 | */ | |||
| 146 | bool add_swap(const UnitID& uid_0, const UnitID& uid_1); | |||
| 147 | ||||
| 148 | /** | |||
| 149 | * add_bridge | |||
| 150 | * Inserts an OpType::BRIDGE gate into edges relevant to passed UnitID. | |||
| 151 | * | |||
| 152 | * @param control First Node in BRIDGE | |||
| 153 | * @param central Second Node in BRIDGE | |||
| 154 | * @param target Third Node in BRIDGE | |||
| 155 | */ | |||
| 156 | void add_bridge( | |||
| 157 | const UnitID& control, const UnitID& central, const UnitID& target); | |||
| 158 | ||||
| 159 | /** | |||
| 160 | * add_ancilla | |||
| 161 | * Adds an Ancillary UnitID to Circuit and tracked information | |||
| 162 | * | |||
| 163 | * @param ancilla UnitID of added ancilla | |||
| 164 | */ | |||
| 165 | void add_ancilla(const UnitID& ancilla); | |||
| 166 | ||||
| 167 | /** | |||
| 168 | * merge_ancilla | |||
| 169 | * Rewires this->circuit_.dag such that in wire to ancilla Output vertex | |||
| 170 | * is now mapped to out wire of merge Input vertex. | |||
| 171 | * | |||
| 172 | * @param merge UnitID to which ancilla path is prepended | |||
| 173 | * @param ancilla UnitID of ancilla opeartions | |||
| 174 | */ | |||
| 175 | void merge_ancilla(const UnitID& merge, const UnitID& ancilla); | |||
| 176 | ||||
| 177 | /** | |||
| 178 | * Assigns the linear_boundary_ attribute to that passed to method. | |||
| 179 | * | |||
| 180 | * @param new_boundary Object to reassign with. | |||
| 181 | */ | |||
| 182 | void set_linear_boundary(const unit_vertport_frontier_t& new_boundary); | |||
| 183 | ||||
| 184 | /** | |||
| 185 | * Returns true if the given operation acting on the given nodes | |||
| 186 | * can be executed on the Architecture connectivity graph. | |||
| 187 | * @param architecture given architecture to check the operation on | |||
| 188 | * @param op operation to check | |||
| 189 | * @param uids vector of nodes which is included in the operation | |||
| 190 | */ | |||
| 191 | bool valid_boundary_operation( | |||
| 192 | const ArchitecturePtr& architecture, const Op_ptr& op, | |||
| 193 | const std::vector<Node>& uids) const; | |||
| 194 | ||||
| 195 | /** | |||
| 196 | * Update a qubit mapping in both the initial map and the final map | |||
| 197 | * @param qubit the qubit mapping to be updated | |||
| 198 | * @param node the new node to be mapped | |||
| 199 | */ | |||
| 200 | void update_bimaps(UnitID qubit, UnitID node); | |||
| 201 | ||||
| 202 | /** | |||
| 203 | * Get the qubit in the initial map given it's mapped uid. | |||
| 204 | * @param uid UnitID in the circuit | |||
| 205 | */ | |||
| 206 | UnitID get_qubit_from_circuit_uid(const UnitID& uid); | |||
| 207 | }; | |||
| 208 | ||||
| 209 | typedef std::shared_ptr<MappingFrontier> MappingFrontier_ptr; | |||
| 210 | ||||
| 211 | } // namespace tket | |||
| 212 |