| 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 "Mapping/LexicographicalComparison.hpp" | |||
| 18 | #include "Mapping/MappingFrontier.hpp" | |||
| 19 | #include "Mapping/RoutingMethod.hpp" | |||
| 20 | #include "Mapping/RoutingMethodJson.hpp" | |||
| 21 | ||||
| 22 | namespace tket { | |||
| 23 | ||||
| 24 | class LexiRouteError : public std::logic_error { | |||
| 25 | public: | |||
| 26 | 3 | explicit LexiRouteError(const std::string& message) | ||
| 27 | 3 | : std::logic_error(message) {} | ||
| 28 | }; | |||
| 29 | ||||
| 30 | /** | |||
| 31 | * A class for modifiying a Circuit held in a MappingFrontier object | |||
| 32 | * with either an Architecture permitted single SWAP gate or BRIDGE gate. | |||
| 33 | * Used in the LexiRouteRoutingMethod class which provides a subcircuit | |||
| 34 | * modification method for MappingManager. Used in solution presented in "On the | |||
| 35 | * qubit routing problem" -> arXiv:1902.08091 | |||
| 36 | */ | |||
| 37 | class LexiRoute { | |||
| 38 | public: | |||
| 39 | /** | |||
| 40 | * Class Constructor | |||
| 41 | * @param _architecture Architecture object added operations must respect | |||
| 42 | * @param _mapping_frontier Contains Circuit object to be modified | |||
| 43 | */ | |||
| 44 | LexiRoute( | |||
| 45 | const ArchitecturePtr& _architecture, | |||
| 46 | MappingFrontier_ptr& _mapping_frontier); | |||
| 47 | ||||
| 48 | /** | |||
| 49 | * When called, LexiRoute::solve will modify the Circuit held in | |||
| 50 | * MappingFrontier object passed at class construction. Either a SWAP gate | |||
| 51 | * will be inserted at the input boundary of the held Circuit or a CX gate | |||
| 52 | * will be transformed into a BRIDGE gate. The added SWAP or BRIDGE gate will | |||
| 53 | * be valid for the Architecture passed at class construction. | |||
| 54 | * The decision making is based on the heuristic outlined in arXiv:1902.08091. | |||
| 55 | * | |||
| 56 | * @param lookahead Number of slices to lookahead at when determining best | |||
| 57 | * SWAP or BRIDGE | |||
| 58 | * | |||
| 59 | * @return True if solve has modified circuit for mapping purposes | |||
| 60 | */ | |||
| 61 | bool solve(unsigned lookahead); | |||
| 62 | ||||
| 63 | /** | |||
| 64 | * When called an "unlabelled" Qubit in the Circuit may be relabelled to a | |||
| 65 | * Node in the Architecture, or an "unlabelled" Qubit may have its path merged | |||
| 66 | * with an ancilla qubit. The decision making is based on the heuristic | |||
| 67 | * outlined in arXiv:1902.08091. | |||
| 68 | * | |||
| 69 | * @return True if solve_labelling has modified circuit for mapping purposes | |||
| 70 | */ | |||
| 71 | bool solve_labelling(); | |||
| 72 | ||||
| 73 | private: | |||
| 74 | /** Only considers two-qubit vertices if both qubits are labelled to | |||
| 75 | * Architecture */ | |||
| 76 | enum class AssignedOnly { Yes, No }; | |||
| 77 | /** Returns a bool confirming if vertices are valid for LexiRoute::solve */ | |||
| 78 | enum class CheckRoutingValidity { Yes, No }; | |||
| 79 | /** Returns a bool confirming if vertices are valid for | |||
| 80 | * LexiRoute::solve_labelling */ | |||
| 81 | enum class CheckLabellingValidity { Yes, No }; | |||
| 82 | ||||
| 83 | /** | |||
| 84 | * this->interacting_uids_ attribute is a map where key is one UnitID | |||
| 85 | * and value is the UnitID it needs to be adjacent to. | |||
| 86 | * This map is implicitly updated whenever a logical SWAP is inserted. | |||
| 87 | * set_interacting_uids determines this map for the first parallel set of | |||
| 88 | * interacting UnitID in the Circuit held in this->mapping_frontier_ | |||
| 89 | * @param assigned_only If Yes, only include interactions where both UnitID | |||
| 90 | * are in this->architecture_. | |||
| 91 | * @param route_check If Yes, return false if solve not possible | |||
| 92 | * @param label_check If Yes, return false if solve_labelling not possible | |||
| 93 | * | |||
| 94 | * @return bool depending on ENUM conditions | |||
| 95 | */ | |||
| 96 | bool set_interacting_uids( | |||
| 97 | AssignedOnly assigned_only, CheckRoutingValidity route_check, | |||
| 98 | CheckLabellingValidity label_check); | |||
| 99 | ||||
| 100 | /** | |||
| 101 | * If there is some "free" Node in Architecture at distance "distances" on | |||
| 102 | * the connectivity graph, assign (relable) UnitID assignee to it. "free" | |||
| 103 | * => not in Circuit. If no unassigned node at distances from root, return | |||
| 104 | * false. | |||
| 105 | * @param assignee UnitID not in Architecture to relabel | |||
| 106 | * @param root Node in Architecture | |||
| 107 | * @param distances Distance at which to find free Node from root at | |||
| 108 | * @return True if assigned, else False | |||
| 109 | */ | |||
| 110 | bool assign_at_distance( | |||
| 111 | const UnitID& assignee, const Node& root, unsigned distances); | |||
| 112 | ||||
| 113 | /** | |||
| 114 | * If this->set_interacting_uids assigned_only bool is false then the | |||
| 115 | * this->interacting_uids attribute may have key and value UnitID not in | |||
| 116 | * this->architecture_. | |||
| 117 | * update_labelling assigns these non-architecture UnitID to some Architecture | |||
| 118 | * UnitID, updating the this->labelling_ attribute. | |||
| 119 | * @return True if anything relabelled, else false | |||
| 120 | */ | |||
| 121 | bool update_labelling(); | |||
| 122 | ||||
| 123 | /** | |||
| 124 | * Returns a set of pair of UnitID, each denoting a SWAP. | |||
| 125 | * Returned SWAP have at least one UnitID in interacting_uids_. | |||
| 126 | * This is such that enacting any of these SWAP will alter the distance | |||
| 127 | * between some interacting UnitID. | |||
| 128 | * @return std::pair<UnitID, UnitID> suitable for addition to Circuit | |||
| 129 | */ | |||
| 130 | swap_set_t get_candidate_swaps(); | |||
| 131 | ||||
| 132 | /** | |||
| 133 | * Proposed swap will have two Node | |||
| 134 | * Each of these Node may be in some interaction in the first layer of circuit | |||
| 135 | * held in mapping_frontier. If either of these Node are in an interaction, | |||
| 136 | * check whether said interaction is a CX interaction, and if the pair of Node | |||
| 137 | * in the interaction are at distance 2. If true, compare lexicographical | |||
| 138 | * distances between no swap and given swap assuming distance 2 interactions | |||
| 139 | * are complete. If no swap is better, update return object to reflect this. | |||
| 140 | * @param swap Pair of Node comprising SWAP for checking | |||
| 141 | * @param lookahead Number of steps of lookahead emplyed for comparison | |||
| 142 | * @return Pair of bool, where true implies BRIDGE to be added | |||
| 143 | */ | |||
| 144 | std::pair<bool, bool> check_bridge( | |||
| 145 | const std::pair<Node, Node>& swap, unsigned lookahead); | |||
| 146 | ||||
| 147 | /** | |||
| 148 | * Returns a pair of distances, where the distances are between n1 & p1, and | |||
| 149 | * n2 & p2. Pair object is ordered such that the greatest distance is first. | |||
| 150 | * | |||
| 151 | * @param p0_first First Node in first interaction to find distance between | |||
| 152 | * @param p0_second Second Node in first interaction to find distance between | |||
| 153 | * @param p1_first First Node in second interaction to find distance between | |||
| 154 | * @param p1_second Second Node in second interaction to find distance between | |||
| 155 | * @return Pair of size_t, being distances on architecture graph | |||
| 156 | */ | |||
| 157 | const std::pair<size_t, size_t> pair_distances( | |||
| 158 | const Node& p0_first, const Node& p0_second, const Node& p1_first, | |||
| 159 | const Node& p1_second) const; | |||
| 160 | ||||
| 161 | /** | |||
| 162 | * It is always expected that at least one Node in a SWAP will be in some | |||
| 163 | * interaction. This method checks that the given swap will strictly decrease | |||
| 164 | * the distance for this interaction, and removes it from the swaps set if | |||
| 165 | * not. | |||
| 166 | * | |||
| 167 | * @param swaps Potential swaps to remove from | |||
| 168 | */ | |||
| 169 | void remove_swaps_decreasing(swap_set_t& swaps); | |||
| 170 | ||||
| 171 | // Architecture all new physical operations must respect | |||
| 172 | ArchitecturePtr architecture_; | |||
| 173 | // Contains circuit for finding SWAP from and non-routed/routed boundary | |||
| 174 | MappingFrontier_ptr& mapping_frontier_; | |||
| 175 | // Map between UnitID and UnitID they interact with at boundary | |||
| 176 | unit_map_t interacting_uids_; | |||
| 177 | // Map between original circuit UnitID and new UnitID due to dynamic | |||
| 178 | // placement | |||
| 179 | unit_map_t labelling_; | |||
| 180 | // Set tracking which Architecture Node are present in Circuit | |||
| 181 | std::set<Node> assigned_nodes_; | |||
| 182 | }; | |||
| 183 | ||||
| 184 | } // namespace tket | |||
| 185 |