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 <iostream> |
18 |
|
|
|
#include <numeric> |
19 |
|
|
|
#include <set> |
20 |
|
|
|
#include <string> |
21 |
|
|
|
#include <tklog/TketLog.hpp> |
22 |
|
|
|
#include <utility> |
23 |
|
|
|
#include <vector> |
24 |
|
|
|
|
25 |
|
|
|
#include "Graphs/CompleteGraph.hpp" |
26 |
|
|
|
#include "Graphs/DirectedGraph.hpp" |
27 |
|
|
|
#include "Utils/BiMapHeaders.hpp" |
28 |
|
|
|
#include "Utils/EigenConfig.hpp" |
29 |
|
|
|
#include "Utils/Json.hpp" |
30 |
|
|
|
#include "Utils/MatrixAnalysis.hpp" |
31 |
|
|
|
#include "Utils/UnitID.hpp" |
32 |
|
|
|
|
33 |
|
|
|
namespace tket { |
34 |
|
|
|
|
35 |
|
|
|
extern template class graphs::DirectedGraphBase<Node>; |
36 |
|
|
|
extern template class graphs::DirectedGraph<Node>; |
37 |
|
|
|
|
38 |
|
|
|
using dist_vec = graphs::dist_vec; |
39 |
|
|
|
|
40 |
|
|
|
class ArchitectureInvalidity : public std::logic_error { |
41 |
|
|
|
public: |
42 |
|
|
✗ |
explicit ArchitectureInvalidity(const std::string &message) |
43 |
|
|
✗ |
: std::logic_error(message) {} |
44 |
|
|
|
}; |
45 |
|
|
|
|
46 |
|
|
|
static inline std::vector<std::pair<Node, Node>> as_nodepairs( |
47 |
|
|
|
const std::vector<std::pair<unsigned, unsigned>> &edges) { |
48 |
|
|
|
std::vector<std::pair<Node, Node>> nodepairs; |
49 |
|
|
|
nodepairs.reserve(edges.size()); |
50 |
|
|
|
for (auto &[m, n] : edges) { |
51 |
|
|
|
nodepairs.push_back({Node(m), Node(n)}); |
52 |
|
|
|
} |
53 |
|
|
|
return nodepairs; |
54 |
|
|
|
} |
55 |
|
|
|
|
56 |
|
|
|
/** |
57 |
|
|
|
* Generic architecture class |
58 |
|
|
|
* |
59 |
|
|
|
* Constraints: T must derive from AbstractGraph, and must have node type |
60 |
|
|
|
* @ref Node. |
61 |
|
|
|
* |
62 |
|
|
|
* @tparam T underlying graph type |
63 |
|
|
|
*/ |
64 |
|
|
|
template <typename T> |
65 |
|
|
|
class ArchitectureBase : public T { |
66 |
|
|
|
public: |
67 |
|
|
|
using T::edge_exists; |
68 |
|
|
|
using T::get_all_edges_vec; |
69 |
|
|
|
using T::get_all_nodes_vec; |
70 |
|
|
|
using T::n_nodes; |
71 |
|
|
|
using T::node_exists; |
72 |
|
|
|
using T::nodes; |
73 |
|
|
|
using T::T; |
74 |
|
|
|
}; |
75 |
|
|
|
|
76 |
|
|
|
class Architecture : public ArchitectureBase<graphs::DirectedGraph<Node>> { |
77 |
|
|
|
public: |
78 |
|
|
|
/** Construct an empty Architecture. */ |
79 |
|
|
✗ |
Architecture() : ArchitectureBase() {} |
80 |
|
|
|
|
81 |
|
|
|
/** Construct an Architecture with given nodes and no edges. */ |
82 |
|
|
✗ |
explicit Architecture(const std::vector<Node> &nodes) |
83 |
|
|
✗ |
: ArchitectureBase(nodes) {} |
84 |
|
|
|
|
85 |
|
|
|
/** Construct an Architecture with given edges. */ |
86 |
|
|
✗ |
explicit Architecture(const std::vector<std::pair<Node, Node>> &edges) |
87 |
|
|
✗ |
: ArchitectureBase(edges) {} |
88 |
|
|
|
|
89 |
|
|
|
/** |
90 |
|
|
|
* Construct from a vector of pairs of indices in the default register. |
91 |
|
|
|
*/ |
92 |
|
|
|
explicit Architecture(const std::vector<std::pair<unsigned, unsigned>> &edges) |
93 |
|
|
|
: Architecture(as_nodepairs(edges)) {} |
94 |
|
|
|
|
95 |
|
|
|
/** |
96 |
|
|
|
* Nodes that cannot be removed without breaking connectivity. |
97 |
|
|
|
*/ |
98 |
|
|
|
node_set_t get_articulation_points() const; |
99 |
|
|
|
|
100 |
|
|
|
/** |
101 |
|
|
|
* Nodes that cannot be removed without breaking connectivity of the subarc. |
102 |
|
|
|
*/ |
103 |
|
|
|
node_set_t get_articulation_points(const Architecture &subarc) const; |
104 |
|
|
|
|
105 |
|
|
|
/** |
106 |
|
|
|
* Returns true if the given operation acting on the given nodes |
107 |
|
|
|
* can be executed on the Architecture connectivity graph. |
108 |
|
|
|
*/ |
109 |
|
|
|
bool valid_operation(const std::vector<Node> &uids) const; |
110 |
|
|
|
|
111 |
|
|
|
/** |
112 |
|
|
|
* Sub-architecture generated by a subset of nodes. |
113 |
|
|
|
*/ |
114 |
|
|
|
Architecture create_subarch(const std::vector<Node> &nodes) const; |
115 |
|
|
|
|
116 |
|
|
|
/** |
117 |
|
|
|
* Vectors of nodes corresponding to lines of given lengths |
118 |
|
|
|
*/ |
119 |
|
|
|
std::vector<node_vector_t> get_lines( |
120 |
|
|
|
std::vector<unsigned> required_lengths) const; |
121 |
|
|
|
|
122 |
|
|
|
/** |
123 |
|
|
|
* Remove a number of nodes according to a heuristic measure of connectivity. |
124 |
|
|
|
*/ |
125 |
|
|
|
node_set_t remove_worst_nodes(unsigned num); |
126 |
|
|
|
|
127 |
|
|
|
/** |
128 |
|
|
|
* Adjacency matrix. |
129 |
|
|
|
*/ |
130 |
|
|
|
MatrixXb get_connectivity() const; |
131 |
|
|
|
|
132 |
|
|
|
protected: |
133 |
|
|
|
// Returns node with least connectivity given some distance matrix. |
134 |
|
|
|
std::optional<Node> find_worst_node(const Architecture &orig_g); |
135 |
|
|
|
}; |
136 |
|
|
|
|
137 |
|
|
|
JSON_DECL(Architecture::Connection) |
138 |
|
|
|
JSON_DECL(Architecture) |
139 |
|
|
|
|
140 |
|
|
|
class FullyConnected : public ArchitectureBase<graphs::CompleteGraph<Node>> { |
141 |
|
|
|
public: |
142 |
|
|
|
FullyConnected() : ArchitectureBase<graphs::CompleteGraph<Node>>() {} |
143 |
|
|
|
|
144 |
|
|
|
/** |
145 |
|
|
|
* Construct a fully-connected graph of a given size. |
146 |
|
|
|
* |
147 |
|
|
|
* The nodes are labelled "fcNode" (indexed from 0 to n-1). |
148 |
|
|
|
* |
149 |
|
|
|
* @param n number of nodes |
150 |
|
|
|
*/ |
151 |
|
|
|
explicit FullyConnected(unsigned n) { |
152 |
|
|
|
for (unsigned i = 0; i < n; i++) { |
153 |
|
|
|
nodes_.insert(Node("fcNode", i)); |
154 |
|
|
|
} |
155 |
|
|
|
} |
156 |
|
|
|
}; |
157 |
|
|
|
|
158 |
|
|
|
JSON_DECL(FullyConnected) |
159 |
|
|
|
|
160 |
|
|
|
// Subclass, constructor generates adjacency matrix corresponding to a ring |
161 |
|
|
|
// architecture |
162 |
|
|
|
class RingArch : public Architecture { |
163 |
|
|
|
public: |
164 |
|
|
|
explicit RingArch(unsigned numberOfNodes); |
165 |
|
|
|
// nodes() does not guarantee to return nodes in any order |
166 |
|
|
|
// this returns the canonical ordering of nodes |
167 |
|
|
|
|
168 |
|
|
|
private: |
169 |
|
|
|
static std::vector<Connection> get_edges(unsigned numberOfNodes); |
170 |
|
|
|
}; |
171 |
|
|
|
|
172 |
|
|
|
// Subclass, constructor generates adjacency matrix corresponding to a |
173 |
|
|
|
// SquareGrid architecture |
174 |
|
|
|
class SquareGrid : public Architecture { |
175 |
|
|
|
public: |
176 |
|
|
|
// Converts square indexing to qubit indexing |
177 |
|
|
|
Vertex squind_to_qind( |
178 |
|
|
|
const unsigned ver, const unsigned hor, const unsigned layer = 0) const { |
179 |
|
|
|
return (ver * dimension_c + hor) + single_layer_nodes() * layer; |
180 |
|
|
|
} |
181 |
|
|
|
// Returns number of nodes in a single 2d layer |
182 |
|
|
|
unsigned single_layer_nodes() const { return dimension_c * dimension_r; } |
183 |
|
|
|
// Gets number of columns of square grid architecture |
184 |
|
|
|
unsigned get_columns() const { return dimension_c; } |
185 |
|
|
|
// Gets number of rows of square grid architecture |
186 |
|
|
|
unsigned get_rows() const { return dimension_r; } |
187 |
|
|
|
// Gets number of layers of square grid architecture |
188 |
|
|
|
unsigned get_layers() const { return layers; } |
189 |
|
|
|
// Converts qubit indexing to square indexing |
190 |
|
|
|
std::pair<unsigned, unsigned> qind_to_squind(const Vertex &qn) const { |
191 |
|
|
|
unsigned col = qn % dimension_c; |
192 |
|
|
|
unsigned row = (qn - col) / dimension_c; |
193 |
|
|
|
return {row, col}; |
194 |
|
|
|
} |
195 |
|
|
|
// SquareGrid constructor |
196 |
|
|
|
// dim_c equiv 'x', dim_r equiv 'y' |
197 |
|
|
|
SquareGrid( |
198 |
|
|
|
const unsigned dim_r, const unsigned dim_c, const unsigned _layers = 1); |
199 |
|
|
|
|
200 |
|
|
|
private: |
201 |
|
|
|
static std::vector<Connection> get_edges( |
202 |
|
|
|
const unsigned dim_r, const unsigned dim_c, const unsigned layers = 1); |
203 |
|
|
|
|
204 |
|
|
|
unsigned dimension_r; |
205 |
|
|
|
unsigned dimension_c; |
206 |
|
|
|
unsigned layers; |
207 |
|
|
|
}; |
208 |
|
|
|
|
209 |
|
|
|
typedef std::shared_ptr<Architecture> ArchitecturePtr; |
210 |
|
|
|
|
211 |
|
|
|
int tri_lexicographical_comparison( |
212 |
|
|
|
const dist_vec &dist1, const dist_vec &dist2); |
213 |
|
|
|
|
214 |
|
|
|
} // namespace tket |
215 |
|
|
|
|