GCC Code Coverage Report

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 <algorithm>
18				#include <iostream>
19				#include <map>
20				#include <memory>
21				#include <stdexcept>
22				#include <string>
23				#include <utility>
24				#include <vector>
25
26				#include "Architecture/Architecture.hpp"
27				#include "Characterisation/DeviceCharacterisation.hpp"
28				#include "Circuit/Circuit.hpp"
29				#include "Graphs/Utils.hpp"
30				#include "Utils/BiMapHeaders.hpp"
31				#include "Utils/GraphHeaders.hpp"
32				#include "Utils/Json.hpp"
33
34				namespace tket {
35
36				extern template class graphs::DirectedGraphBase<Qubit>;
37				extern template class graphs::DirectedGraph<Qubit>;
38
39				struct QubitWeight;
40				struct InteractionWeight;
41				class Placement;
42
43				typedef std::map<Qubit, Node> qubit_mapping_t;
44				typedef boost::bimap<Qubit, Node> qubit_bimap_t;
45				typedef qubit_bimap_t::left_map::const_iterator l_const_iterator_t;
46				typedef qubit_bimap_t::right_map::const_iterator r_const_iterator_t;
47				// Adjacent elements in a QubitLine interact in some timesteps such that
48				// these qubits do not need to be moved to be executed
49				typedef qubit_vector_t QubitLine;
50				typedef std::vector<QubitLine>
51				QubitLineList; // Used in placement of qubits methods
52
53				typedef std::shared_ptr<Placement> PlacementPtr;
54
55				JSON_DECL(PlacementPtr)
56
57				class QubitGraphInvalidity : public std::logic_error {
58				public:
59				explicit QubitGraphInvalidity(const std::string& message)
60				: std::logic_error(message) {}
61				};
62
63				class PlacementError : public std::logic_error {
64				public:
65			✗	explicit PlacementError(const std::string& message)
66			✗	: std::logic_error(message) {}
67				};
68
69				/** Print a map to stdout. */
70				template <class MapType>
71				void print_map(const MapType& m) {
72				typedef typename MapType::const_iterator const_iterator;
73				for (const_iterator iter = m.begin(), iend = m.end(); iter != iend; ++iter) {
74				std::cout << iter->first << "-->" << iter->second << std::endl;
75				}
76				}
77
78				// structure of configuration parameters for placement
79				struct PlacementConfig {
80				// circuit look ahead limit
81				unsigned depth_limit;
82				// max edges in interaction graph
83				unsigned max_interaction_edges;
84				// max number of matches from monomorphism calculator.
85				unsigned monomorphism_max_matches = 1000;
86
87				/*
88				value of num_gates/num_qubits above which to contract architecture before
89				placement for high values of this ratio it is assumed swap count is more
90				critical than initial noise minimisation for which is architecture contraction
91				to most mst highly connected subgraph is critical
92				*/
93				unsigned arc_contraction_ratio = 10;
94				// Timeout, corresponds to milliseconds. Default 1 minute.
95				unsigned timeout = 60000;
96
97			✗	PlacementConfig(){};
98
99				PlacementConfig(
100				unsigned _depth_limit, unsigned _max_interaction_edges,
101				unsigned _monomorphism_max_matches = 1000,
102				unsigned _arc_contraction_ratio = 10, unsigned _timeout = 60000);
103
104				bool operator==(const PlacementConfig& other) const;
105				};
106
107				JSON_DECL(PlacementConfig)
108
109				// stores and tracks the points of the circuit up to which has been solved
110				struct PlacementFrontier {
111				// set of 2qb vertices which need to be solved for
112				std::shared_ptr<Slice> slice;
113				// Quantum Edges coming in to vertices in slice, indexed by qubit
114				std::shared_ptr<unit_frontier_t> quantum_in_edges;
115				// Quantum Edges leaving vertices in slice, indexed by qubit
116				std::shared_ptr<unit_frontier_t> quantum_out_edges;
117				// Boolean edges coming in to vertices in slice. Guarantees that all edges
118				// into every vertex in slice is represented in next_cut
119				std::shared_ptr<b_frontier_t> boolean_in_edges;
120
121				// reference to circuit that it acts on
122				const Circuit& circ;
123
124				// initialise at front of circuit
125				explicit PlacementFrontier(const Circuit& _circ);
126				// move to next slice
127				void next_slicefrontier();
128				};
129
130				// Class for storing interaction graph.
131				// Interacting qubits have an edge between them.
132				class QubitGraph : public graphs::DirectedGraph<Qubit> {
133				private:
134				using Base = graphs::DirectedGraph<Qubit>;
135
136				public:
137			✗	QubitGraph() : Base() {}
138			✗	explicit QubitGraph(const qubit_vector_t& _qubits) : Base(_qubits) {}
139				};
140
141				/* ACTUALLY PLACEMENT METHODS */
142
143				// generate interaction graph of circuit
144				QubitGraph generate_interaction_graph(
145				const Circuit& circ, unsigned depth_limit = 10);
146				// generate lines of interacting qubits
147				QubitLineList qubit_lines(const Circuit& circ);
148				// generate mapping of qubit lines to lines on architecture. n_qubits is total
149				// number of qubits in circuit
150				qubit_mapping_t lines_on_arc(
151				Architecture arc, QubitLineList qb_lines, unsigned n_qubits);
152
153				// build interaction graph of circ, max_edges in graph, depth_limit sets how far
154				// to look ahead
155				QubitGraph monomorph_interaction_graph(
156				const Circuit& circ, const unsigned max_edges, unsigned depth_limit);
157
158				/**
159				* Search for embeddings of the qubit graph in the architecture graph.
160				*
161				* @param arc architecture
162				* @param q_graph qubit graph
163				* @param max_matches maximum number of matches to find
164				* @param timeout timeout in milliseconds
165				* @return vector of matches found, sorted in canonical order
166				*/
167				std::vector<qubit_bimap_t> monomorphism_edge_break(
168				const Architecture& arc, const QubitGraph& q_graph, unsigned max_matches,
169				unsigned timeout);
170
171				/** Solves the pure unweighted subgraph monomorphism problem, trying
172				* to embed the pattern graph into the target graph.
173				* Note that graph edge weights are IGNORED by this function.
174				*/
175				std::vector<qubit_bimap_t> get_unweighted_subgraph_monomorphisms(
176				const QubitGraph::UndirectedConnGraph& pattern_graph,
177				const Architecture::UndirectedConnGraph& target_graph, unsigned max_matches,
178				unsigned timeout_ms);
179
180				node_set_t best_nodes(Architecture& arc, unsigned n_remove);
181
182				class PatternError : public std::logic_error {
183				public:
184				explicit PatternError(const std::string& message)
185				: std::logic_error(message) {}
186				};
187
188				// Note: the WSM subgraph monomorphism algorithm
189				// matches any vertex with any vertex
190				// and any edge with any edge, regardless of their bundled properties.
191				struct QubitWeight {
192				QubitWeight() : val(0.) {}
193				explicit QubitWeight(const boost::no_property) : val(0.) {}
194				explicit QubitWeight(double d) : val(d) {}
195				double val;
196				};
197
198				struct InteractionWeight {
199				InteractionWeight() : val(0.) {}
200				explicit InteractionWeight(const boost::no_property) : val(0.) {}
201				explicit InteractionWeight(double d) : val(d) {}
202				template <typename Property>
203				explicit InteractionWeight(Property p)
204				: val(static_cast<double>(p.m_value)) {}
205				double val;
206				};
207
208				// structure of qubit mapping with associated cost
209				struct MapCost {
210				qubit_mapping_t map;
211				double cost;
212			2543	bool operator<(const MapCost& other) const { return this->cost < other.cost; }
213			1138	bool operator>(const MapCost& other) const { return this->cost > other.cost; }
214				};
215
216				class Placement {
217				public:
218			✗	explicit Placement(const Architecture& _arc) : arc_(_arc) {}
219			✗	Placement(){};
220
221				/**
222				* Modify qubits in place.
223				*
224				* @return true iff circuit or maps are modified
225				*/
226				bool place(
227				Circuit& circ_, std::shared_ptr<unit_bimaps_t> maps = nullptr) const;
228
229				/**
230				* Relabel circuit qubits to device nodes according to given map.
231				*
232				* @return true iff circuit or maps were modified
233				*/
234				static bool place_with_map(
235				Circuit& circ, qubit_mapping_t& map_,
236				std::shared_ptr<unit_bimaps_t> maps = nullptr);
237
238				virtual qubit_mapping_t get_placement_map(const Circuit& circ_) const;
239
240				// methods that return maps, for base this returns one empty map
241				virtual std::vector<qubit_mapping_t> get_all_placement_maps(
242				const Circuit& circ_) const;
243
244				static const std::string& unplaced_reg();
245
246			119	const Architecture& get_architecture_ref() { return arc_; }
247			✗	virtual ~Placement(){};
248
249				protected:
250				Architecture arc_;
251				};
252
253				/**
254				* NaivePlacement class provides methods for relabelling any
255				* Qubit objects in some Circuit to Node objects in some Architecture
256				* given the constraint that only Qubit that are not already labelled
257				* as some Node can be relabelled, and only to Architecture Node
258				* that are not already in the Circuit.
259				*/
260				class NaivePlacement : public Placement {
261				public:
262				/**
263				* @param _arc Architecture object later relabellings are produced for
264				*/
265			✗	explicit NaivePlacement(const Architecture& _arc) { arc_ = _arc; }
266				/**
267				* Given some circuit, returns a map between Qubit which defines some
268				* relabelling of some Circuit qubits to Architecture qubits
269				*
270				* @param circ_ Circuit map relabelling is defined for
271				*
272				* @return Map defining relabelling for circuit Qubit objects
273				*/
274				qubit_mapping_t get_placement_map(const Circuit& circ_) const override;
275
276				/**
277				* Given some circuit, returns a single map for relabelling
278				* in a vector.
279				*
280				* @param circ_ Circuit map relabelling is defined for
281				*
282				* @return Vector of a single Map defining relabelling for Circuit
283				* Qubit objects.
284				*/
285				std::vector<qubit_mapping_t> get_all_placement_maps(
286				const Circuit& circ_) const override;
287				};
288
289				class LinePlacement : public Placement {
290				public:
291			✗	explicit LinePlacement(const Architecture& _arc) { arc_ = _arc; }
292
293				qubit_mapping_t get_placement_map(const Circuit& circ_) const override;
294
295				// methods that return maps, for base this returns one empty map
296				std::vector<qubit_mapping_t> get_all_placement_maps(
297				const Circuit& circ_) const override;
298				};
299
300				class GraphPlacement : public Placement {
301				public:
302			✗	explicit GraphPlacement(const Architecture& _arc) {
303			✗	arc_ = _arc;
304			✗	config_.depth_limit = 5;
305			✗	config_.max_interaction_edges = arc_.n_connections();
306			✗	config_.monomorphism_max_matches = 10000;
307			✗	config_.arc_contraction_ratio = 10;
308				}
309
310			✗	explicit GraphPlacement(
311				const Architecture& _arc, const PlacementConfig& _config)
312			✗	: Placement(_arc), config_(_config) {}
313
314				explicit GraphPlacement(const PlacementConfig& _config) : config_(_config) {}
315
316			41	PlacementConfig get_config() { return config_; }
317				void set_config(const PlacementConfig& new_config) { config_ = new_config; }
318
319				qubit_mapping_t get_placement_map(const Circuit& circ_) const override;
320				// methods that return maps, for base this returns one empty map
321				std::vector<qubit_mapping_t> get_all_placement_maps(
322				const Circuit& circ_) const override;
323
324				private:
325				PlacementConfig config_;
326				};
327
328				///////////////////////////////
329				// NOISE-AWARE PLACEMENT //
330				///////////////////////////////
331
332				// Class for performing noise-aware placement using graph monomorphism
333				class Monomorpher {
334				public:
335			✗	Monomorpher(
336				const Circuit& _circ, const Architecture& _arc,
337				const DeviceCharacterisation& _characterisation,
338				const PlacementConfig& _config)
339			✗	: circ(_circ),
340			✗	arc(_arc),
341			✗	characterisation(_characterisation),
342			✗	config(_config) {
343			✗	q_graph = monomorph_interaction_graph(
344			✗	circ, config.max_interaction_edges, config.depth_limit);
345				}
346
347				// return best maps, up to max_return in number, unsorted
348				std::vector<MapCost> place(unsigned max_return);
349				// calculate cost of map
350				double map_cost(const qubit_bimap_t& n_map);
351
352				private:
353				const Circuit& circ;
354				Architecture arc;
355				DeviceCharacterisation characterisation;
356				PlacementConfig config;
357				QubitGraph q_graph;
358				};
359
360				class NoiseAwarePlacement : public Placement {
361				public:
362				NoiseAwarePlacement(
363				const Architecture& _arc,
364				std::optional<avg_node_errors_t> _node_errors = std::nullopt,
365				std::optional<avg_link_errors_t> _link_errors = std::nullopt,
366				std::optional<avg_readout_errors_t> _readout_errors = std::nullopt) {
367				arc_ = _arc;
368				characterisation_ = {
369				_node_errors ? *_node_errors : avg_node_errors_t(),
370				_link_errors ? *_link_errors : avg_link_errors_t(),
371				_readout_errors ? *_readout_errors : avg_readout_errors_t()};
372				config_.depth_limit = 5;
373				config_.max_interaction_edges = arc_.n_connections();
374				config_.monomorphism_max_matches = 10000;
375				config_.arc_contraction_ratio = 10;
376				config_.timeout = 60000;
377				}
378			✗	explicit NoiseAwarePlacement(
379				const Architecture& _arc, const PlacementConfig& _config,
380				std::optional<avg_node_errors_t> _node_errors = std::nullopt,
381				std::optional<avg_link_errors_t> _link_errors = std::nullopt,
382				std::optional<avg_readout_errors_t> _readout_errors = std::nullopt)
383			✗	: Placement(_arc), config_(_config) {
384				characterisation_ = {
385			✗	_node_errors ? *_node_errors : avg_node_errors_t(),
386			✗	_link_errors ? *_link_errors : avg_link_errors_t(),
387			✗	_readout_errors ? *_readout_errors : avg_readout_errors_t()};
388				}
389				explicit NoiseAwarePlacement(const PlacementConfig& _config)
390				: config_(_config) {}
391			5	PlacementConfig get_config() { return config_; }
392				void set_config(const PlacementConfig& new_config) { config_ = new_config; }
393				qubit_mapping_t get_placement_map(const Circuit& circ_) const override;
394				// methods that return maps, for base this returns one empty map
395				std::vector<qubit_mapping_t> get_all_placement_maps(
396				const Circuit& circ_) const override;
397
398				private:
399				friend void to_json(nlohmann::json& j, const PlacementPtr& placement_ptr);
400				friend void from_json(const nlohmann::json& j, PlacementPtr& placement_ptr);
401
402				PlacementConfig config_;
403				DeviceCharacterisation characterisation_;
404				};
405
406				} // namespace tket
407