| 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 "Utils/BiMapHeaders.hpp" | |||
| 19 | #include "Utils/UnitID.hpp" | |||
| 20 | ||||
| 21 | namespace tket { | |||
| 22 | ||||
| 23 | typedef std::map<Node, Node> interacting_nodes_t; | |||
| 24 | typedef std::pair<Node, Node> swap_t; | |||
| 25 | typedef std::set<swap_t> swap_set_t; | |||
| 26 | typedef std::vector<size_t> lexicographical_distances_t; | |||
| 27 | ||||
| 28 | class LexicographicalComparisonError : public std::logic_error { | |||
| 29 | public: | |||
| 30 | 2 | explicit LexicographicalComparisonError(const std::string& message) | ||
| 31 | 2 | : std::logic_error(message) {} | ||
| 32 | }; | |||
| 33 | ||||
| 34 | /** | |||
| 35 | * A class for running lexicographical comparisons of SWAP gates for some | |||
| 36 | * architecture and set of interacting qubits. | |||
| 37 | * Used in the 'LexiRoute' method for routing subcircuits as part of the | |||
| 38 | * MappingManager framework. | |||
| 39 | * Used in solution presented in "On the qubit routing problem" -> | |||
| 40 | * arXiv:1902.08091 | |||
| 41 | */ | |||
| 42 | class LexicographicalComparison { | |||
| 43 | public: | |||
| 44 | /** | |||
| 45 | * Class constructor | |||
| 46 | * @param _architecture Architecture object for calcuating distances from | |||
| 47 | * @param _interacting_nodes Pairs of physical Node with interacting logical | |||
| 48 | * Qubit | |||
| 49 | */ | |||
| 50 | LexicographicalComparison( | |||
| 51 | const ArchitecturePtr& _architecture, | |||
| 52 | const interacting_nodes_t& _interacting_nodes); | |||
| 53 | ||||
| 54 | /** | |||
| 55 | * Modifies some distances object by reference. | |||
| 56 | * Updates the distance between pair Node in interaction by increment. | |||
| 57 | * Increment and Interaction determined by some SWAP. | |||
| 58 | * | |||
| 59 | * @param distances Distances object updated. | |||
| 60 | * @param interaction Node pair increment distance indexing found from | |||
| 61 | * @param increment Amount to modify distance index by | |||
| 62 | */ | |||
| 63 | void increment_distances( | |||
| 64 | lexicographical_distances_t& distances, | |||
| 65 | const std::pair<Node, Node>& interaction, int increment) const; | |||
| 66 | ||||
| 67 | /** | |||
| 68 | * Returns a held lexicograhically ordered vector of distances between nodes | |||
| 69 | * and architectuture class object is constructed from, with changes | |||
| 70 | * from increment distances. | |||
| 71 | * | |||
| 72 | * @return Lexicographically ordered distance vector | |||
| 73 | */ | |||
| 74 | lexicographical_distances_t get_lexicographical_distances() const; | |||
| 75 | ||||
| 76 | /** | |||
| 77 | * Takes a copy of Distance vector held in object and modifies it to reflect | |||
| 78 | * how distance between pairs of interacting nodes in attribute would change | |||
| 79 | * given the logical qubits asisgned to the physical node in "swap" swapped. | |||
| 80 | * | |||
| 81 | * @param swap Physical Node Logical Qubit swapped between to derive copy | |||
| 82 | * distance | |||
| 83 | */ | |||
| 84 | lexicographical_distances_t get_updated_distances(const swap_t& swap) const; | |||
| 85 | ||||
| 86 | /** | |||
| 87 | * For each swap in candidate_swaps, removes swap from set if the distance | |||
| 88 | * vector produced by modifying this->lexicographical_distances by said swap | |||
| 89 | * is lexicographically smaller to that produced for any other swap. In this | |||
| 90 | * way, only swaps with lexicographically identical swap for the given | |||
| 91 | * interacting nodes remain after the method is called. | |||
| 92 | * | |||
| 93 | * @param candidate_swaps Potential pairs of nodes for comparing and removing | |||
| 94 | */ | |||
| 95 | void remove_swaps_lexicographical(swap_set_t& candidate_swaps) const; | |||
| 96 | ||||
| 97 | private: | |||
| 98 | ArchitecturePtr architecture_; | |||
| 99 | lexicographical_distances_t lexicographical_distances; | |||
| 100 | interacting_nodes_t interacting_nodes_; | |||
| 101 | }; | |||
| 102 | ||||
| 103 | } // namespace tket | |||
| 104 |