GCC Code Coverage Report

Directory: ./
File: Circuit/include/Circuit/Circuit.hpp
Date: 2022-10-15 05:10:18
Warnings: 1 unchecked decisions!
Exec Total Coverage
Lines: 73 133 54.9%
Functions: 22 55 40.0%
Branches: 58 236 24.6%
Decisions: 22 38 57.9%
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 // NOTE: FOR ALL COMMENTS ON SCALING 'alpha' IS THE MAXIMUM ARITY OF VERTICES IN
18 // THE GRAPH CIRCUITS ARE TYPICALLY SPARSE UNLESS THEY CONTAIN LARGE PHASE
19 // GADGETS/BOXES CURRENTLY ie. `alpha` ~= 1-3 typically Other common variables:
20 // D - depth of circuit
21 // V - no. vertices in circuit
22 // E - no. edges in circuit
23 // q - no. qubits
24 // Other notes: the worstcase possibility of hashtable lookup (linear)
25 // is ignored, and the amortized constant time used for scaling instead
26
27 #include <algorithm>
28 #include <exception>
29 #include <functional>
30 #include <list>
31 #include <map>
32 #include <memory>
33 #include <optional>
34 #include <ostream>
35 #include <sstream>
36 #include <string>
37 #include <tkassert/Assert.hpp>
38 #include <tklog/TketLog.hpp>
39 #include <type_traits>
40 #include <unordered_map>
41 #include <utility>
42 #include <vector>
43
44 #include "Boxes.hpp"
45 #include "Command.hpp"
46 #include "Conditional.hpp"
47 #include "DAGDefs.hpp"
48 #include "Gate/OpPtrFunctions.hpp"
49 #include "Utils/Constants.hpp"
50 #include "Utils/GraphHeaders.hpp"
51 #include "Utils/Json.hpp"
52 #include "Utils/SequencedContainers.hpp"
53 #include "Utils/UnitID.hpp"
54
55 namespace tket {
56
57 typedef std::vector<EdgeVec> BundleVec;
58
59 typedef VertexVec Slice;
60 typedef std::vector<Slice> SliceVec;
61
62 typedef std::vector<VertPort> QPathDetailed;
63 typedef std::unordered_map<Vertex, Vertex> vertex_map_t;
64
65 /* these are used only for pattern matching */
66 typedef std::map<Edge, Edge> edge_map_t;
67
68 struct BoundaryElement {
69 UnitID id_;
70 Vertex in_;
71 Vertex out_;
72 ✗ UnitType type() const { return id_.type(); }
73 ✗ std::string reg_name() const { return id_.reg_name(); }
74 808337 register_info_t reg_info() const { return id_.reg_info(); }
75
76 bool operator==(const BoundaryElement &other) const {
77 return this->id_ == other.id_ && this->in_ == other.in_ &&
78 this->out_ == other.out_;
79 }
80 };
81
82 struct TagID {};
83 struct TagIn {};
84 struct TagOut {};
85 struct TagType {};
86 struct TagReg {};
87 typedef boost::multi_index::multi_index_container<
88 BoundaryElement,
89 boost::multi_index::indexed_by<
90 boost::multi_index::ordered_unique<
91 boost::multi_index::tag<TagID>,
92 boost::multi_index::member<
93 BoundaryElement, UnitID, &BoundaryElement::id_>>,
94 boost::multi_index::ordered_unique<
95 boost::multi_index::tag<TagIn>,
96 boost::multi_index::member<
97 BoundaryElement, Vertex, &BoundaryElement::in_>>,
98 boost::multi_index::ordered_unique<
99 boost::multi_index::tag<TagOut>,
100 boost::multi_index::member<
101 BoundaryElement, Vertex, &BoundaryElement::out_>>,
102 boost::multi_index::ordered_non_unique<
103 boost::multi_index::tag<TagType>,
104 boost::multi_index::const_mem_fun<
105 BoundaryElement, UnitType, &BoundaryElement::type>>,
106 boost::multi_index::ordered_non_unique<
107 boost::multi_index::tag<TagReg>,
108 boost::multi_index::const_mem_fun<
109 BoundaryElement, std::string, &BoundaryElement::reg_name>>>>
110 boundary_t;
111
112 typedef sequenced_map_t<UnitID, Edge> unit_frontier_t;
113 // typedef sequenced_map_t<Qubit, Edge> q_frontier_t;
114 typedef sequenced_map_t<Bit, EdgeVec> b_frontier_t;
115 // typedef sequenced_map_t<Bit, Edge> c_frontier_t;
116
117 typedef std::unordered_map<unsigned, unsigned> permutation_t;
118
119 /**
120 * Structure to describe a convex region of the interaction graph.
121 * Usually used to identify a region to replace by another circuit.
122 *
123 * The Subcircuit is valid if there exist two possible frontiers (complete cuts)
124 * through the circuit such that:
125 * - q_in_hole and c_in_hole are contained within the first frontier
126 * - q_out_hole and c_out_hole consist of exactly the edges in the later
127 * frontier corresponding to the same units as those in q_in_hole and
128 * c_in_hole
129 * - b_future corresponds exactly to the set of Boolean edges in the
130 * later frontier whose origins are in c_out_hole (these are needed when
131 * an edge is in both c_in_hole and c_out_hole to determine where the
132 * replacement circuit should be placed with respect to the vertices with
133 * Booleans from that unit)
134 */
135 struct Subcircuit {
136 /** Ordered incoming Quantum edges into the subcircuit */
137 EdgeVec q_in_hole;
138 /** Ordered outgoing Quantum edges from the subcircuit */
139 EdgeVec q_out_hole;
140 /** Ordered incoming Classical edges into the subcircuit */
141 EdgeVec c_in_hole;
142 /** Ordered outgoing Classical edges from the subcircuit */
143 EdgeVec c_out_hole;
144 /** Boolean edges in the future of the subcircuit, to be rewired to
145 * the replacement of the corresponding edge from c_out_hole
146 */
147 EdgeVec b_future;
148 VertexSet verts;
149
150 ✗ Subcircuit() {}
151 ✗ Subcircuit(
152 const EdgeVec &q_ins, const EdgeVec &q_outs, const VertexSet &vs = {})
153 ✗ : q_in_hole(q_ins),
154 ✗ q_out_hole(q_outs),
155 ✗ c_in_hole(),
156 ✗ c_out_hole(),
157 ✗ b_future(),
158 ✗ verts(vs) {}
159 ✗ Subcircuit(
160 const EdgeVec &q_ins, const EdgeVec &q_outs, const EdgeVec &c_ins,
161 const EdgeVec &c_outs, const EdgeVec &crs, const VertexSet &vs = {})
162 ✗ : q_in_hole(q_ins),
163 ✗ q_out_hole(q_outs),
164 ✗ c_in_hole(c_ins),
165 ✗ c_out_hole(c_outs),
166 ✗ b_future(crs),
167 ✗ verts(vs) {}
168 };
169
170 // Used for edge traversal in pattern-matching
171 struct TraversalPoint {
172 Vertex from;
173 Vertex to;
174 Edge edge;
175 };
176
177 struct CutFrontier {
178 std::shared_ptr<Slice> slice;
179 std::shared_ptr<unit_frontier_t> u_frontier;
180 std::shared_ptr<b_frontier_t> b_frontier;
181 23528 void init() {
182 23528 slice = std::make_shared<Slice>();
183 23528 u_frontier = std::make_shared<unit_frontier_t>();
184 23528 b_frontier = std::make_shared<b_frontier_t>();
185 23528 }
186 };
187
188 // list of error types to throw out
189 class CircuitInequality : public std::logic_error {
190 public:
191 7 explicit CircuitInequality(const std::string &message)
192 7 : std::logic_error(message) {}
193 };
194 class CircuitInvalidity : public std::logic_error {
195 public:
196 ✗ explicit CircuitInvalidity(const std::string &message)
197 ✗ : std::logic_error(message) {}
198 };
199
200 class Unsupported : public std::logic_error {
201 public:
202 4 explicit Unsupported(const std::string &message)
203 4 : std::logic_error(message) {}
204 };
205
206 class MissingVertex : public std::logic_error { // Necessary?
207 // Q: boost might pick this up and we can just catch it?
208 // A : it does not
209 public:
210 MissingVertex() : std::logic_error("unknown vertex missing") {}
211 ✗ explicit MissingVertex(const std::string &error_string)
212 ✗ : std::logic_error(error_string) {}
213 };
214
215 class MissingEdge : public std::logic_error {
216 public:
217 explicit MissingEdge(const tket::Edge &edge)
218 : std::logic_error("Edge missing") {
219 std::stringstream s;
220 s << edge;
221 tket_log()->info(s.str());
222 }
223 ✗ MissingEdge() : std::logic_error("unknown edge missing") {}
224 };
225
226 class SimpleOnly : public Unsupported {
227 public:
228 1 SimpleOnly()
229 1 : Unsupported(
230 "Function only allowed for simple circuits (single "
231
2/4
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
 1 "register)") {}
232 };
233
234 class CompilationUnit;
235
236 enum ReverseType {
237 dagger = 1,
238 transpose = 2,
239 };
240
241 /**
242 * A circuit.
243 *
244 * A circuit comprises some quantum and classical wires and a defined sequence
245 * of operations on them with a defined global phase.
246 */
247 class Circuit {
248 void _handle_boundaries(Circuit &circ, vertex_map_t &vmap) const;
249 void _handle_interior(
250 Circuit &circ, vertex_map_t &vmap, V_iterator &vi, V_iterator &vend,
251 ReverseType reverse_op) const;
252 void _handle_edges(
253 Circuit &circ, vertex_map_t &vmap, E_iterator &ei,
254 E_iterator &eend) const;
255
256 public:
257 /*SliceIterator class is used for lazy evaluation of slices */
258 class SliceIterator {
259 public: // these are currently public to allow skip_func slicing.
260 CutFrontier cut_;
261 std::shared_ptr<b_frontier_t> prev_b_frontier_;
262 const Circuit *circ_;
263
264 class Sliceholder {
265 private:
266 Slice current_slice_;
267
268 public:
269 12 explicit Sliceholder(Slice slice) : current_slice_(slice) {}
270 Slice operator*() const { return current_slice_; }
271 };
272
273 // take in an unsigned 'n' and a circuit and give the 'n'th slice
274 // note: n=0 gives an empty SliceIterator
275 // n=1 gives the first slice
276
277 SliceIterator(
278 const Circuit &circ, const std::function<bool(Op_ptr)> &skip_func);
279 explicit SliceIterator(const Circuit &circ);
280
1/2
✓ Branch 3 taken 2 times.
✗ Branch 4 not taken.
 2 SliceIterator() : cut_(), circ_() { cut_.init(); }
281 ✗ Slice operator*() const { return *cut_.slice; }
282 ✗ bool operator==(const SliceIterator &other) const {
283 ✗ return *cut_.slice == *other.cut_.slice;
284 }
285 ✗ bool operator!=(const SliceIterator &other) const {
286 ✗ return !(*this == other);
287 }
288 249905 std::shared_ptr<const unit_frontier_t> get_u_frontier() const {
289 249905 return cut_.u_frontier;
290 }
291 std::shared_ptr<const b_frontier_t> get_b_frontier() const {
292 return cut_.b_frontier;
293 }
294 249905 std::shared_ptr<const b_frontier_t> get_prev_b_frontier() const {
295 249905 return prev_b_frontier_;
296 }
297 // A postfix increment operator overload
298 Sliceholder operator++(int);
299 // A prefix increment operator overload
300 SliceIterator &operator++();
301 bool finished() const;
302 };
303
304 SliceIterator slice_begin() const;
305 static SliceIterator slice_end();
306 static const SliceIterator nullsit;
307
308 unit_vector_t args_from_frontier(
309 const Vertex &vert, std::shared_ptr<const unit_frontier_t> u_frontier,
310 std::shared_ptr<const b_frontier_t> b_frontier) const;
311 // find the full command for a vertex
312 Command command_from_vertex(
313 const Vertex &vert, std::shared_ptr<const unit_frontier_t> u_frontier,
314 std::shared_ptr<const b_frontier_t> prev_b_frontier) const;
315
316 class CommandIterator {
317 private:
318 Command current_command_;
319 SliceIterator current_slice_iterator_;
320 unsigned current_index_;
321 Vertex current_vertex_;
322 const Circuit *circ_;
323
324 class Commandholder {
325 private:
326 Command current_command_;
327
328 public:
329 3 explicit Commandholder(Command command) : current_command_(command) {}
330 Command operator*() const { return current_command_; }
331 };
332
333 public:
334 explicit CommandIterator(const Circuit &circ);
335 1 CommandIterator()
336
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 : current_vertex_(boost::graph_traits<DAG>::null_vertex()),
337
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 2 circ_(nullptr) {}
338
339 ✗ Command operator*() const { return current_command_; }
340 26118 const Command *operator->() const { return &current_command_; }
341 1525 Vertex get_vertex() const { return current_vertex_; }
342 ✗ bool operator==(const CommandIterator &other) const {
343 ✗ return current_vertex_ == other.current_vertex_;
344 }
345 ✗ bool operator!=(const CommandIterator &other) const {
346 ✗ return !(*this == other);
347 }
348 // A postfix increment operator overload
349 Commandholder operator++(int);
350
351 // A prefix increment operator overload
352 CommandIterator &operator++();
353 };
354
355 CommandIterator begin() const;
356 const CommandIterator end() const;
357 static const CommandIterator nullcit;
358
359 ///////////////////////
360 // Setters and Getters//
361 ///////////////////////
362
363 /* circuit constructor methods */
364
365 /**
366 * Construct an empty circuit.
367 */
368 ✗ Circuit() : phase(0) {}
369
370 /**
371 * Construct an empty named circuit.
372 *
373 * @param name name of circuit
374 */
375 explicit Circuit(const std::string &name);
376
377 // constructor for circuit with `n` qubits
378 // O(n)
379 explicit Circuit(
380 unsigned n, const std::optional<std::string> _name = std::nullopt);
381
382 // constructor for circuit with `n` qubits, plus initialise a classical
383 // register of size `m`
384 // ie `m` ClInput vertices connected to `m` ClOutputs
385 explicit Circuit(
386 unsigned n, unsigned m,
387 const std::optional<std::string> _name = std::nullopt);
388
389 // copy constructor
390 // not including op_table merge: O(E+V+q), `E` edges, `V` vertices, `q` qubits
391 Circuit(const Circuit &circ);
392
393 /**
394 * Constructor for an empty circuit with some given qubits/bits
395 */
396 222 Circuit(const qubit_vector_t &qubits, const bit_vector_t &bits) : Circuit() {
397
2/2
✓ Branch 5 taken 276 times.
✓ Branch 6 taken 222 times.
2/2
✓ Decision 'true' taken 276 times.
✓ Decision 'false' taken 222 times.
 498 for (const Qubit &q : qubits) {
398
1/2
✓ Branch 1 taken 276 times.
✗ Branch 2 not taken.
 276 add_qubit(q);
399 }
400
2/2
✓ Branch 5 taken 6 times.
✓ Branch 6 taken 222 times.
2/2
✓ Decision 'true' taken 6 times.
✓ Decision 'false' taken 222 times.
 228 for (const Bit &b : bits) {
401
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 add_bit(b);
402 }
403 222 }
404
405 // copy assignment. Moves boundary pointers.
406 Circuit &operator=(const Circuit &other);
407
408 /**
409 * Run a suite of checks for internal circuit validity.
410 *
411 * Abort if any fail. All circuit methods may assume these conditions and
412 * must ensure that they are preserved.
413 */
414 void assert_valid() const;
415
416 /* getters */
417 // returns the vector of input/output vertices to dag, ordered by register
418 VertexVec all_inputs() const;
419 VertexVec q_inputs() const;
420 VertexVec c_inputs() const;
421 VertexVec all_outputs() const;
422 VertexVec q_outputs() const;
423 VertexVec c_outputs() const;
424
425 qubit_vector_t all_qubits() const;
426 qubit_vector_t created_qubits() const;
427 qubit_vector_t discarded_qubits() const;
428 bit_vector_t all_bits() const;
429 unit_vector_t all_units() const;
430
431 /**
432 * Returns a map from bits to their (left-to-right) column index in
433 * ILO-BE readouts.
434 */
435 std::map<Bit, unsigned> bit_readout() const;
436
437 /**
438 * If a Measure op is the last operation on both its qubit and bit, this
439 * will map that qubit id to the same readout index as the bit. This is
440 * useful to extract from the circuit before compilation to correctly
441 * interpret the readouts, and after compilation to identify how to apply
442 * corrections for error mitigation.
443 */
444 std::map<Qubit, unsigned> qubit_readout() const;
445
446 /**
447 * If a Measure op is the last operation on both its qubit and bit, this
448 * will map that qubit id to bit id. This is
449 * useful after compilation to identify how to apply
450 * corrections for error mitigation.
451 */
452 std::map<Qubit, Bit> qubit_to_bit_map() const;
453
454 /**
455 * Returns whether or not a given qubit/bit exists in the circuit
456 */
457 bool contains_unit(const UnitID &id) const;
458
459 Vertex get_in(const UnitID &id) const;
460 Vertex get_out(const UnitID &id) const;
461
462 /** Looks up an input/output vertex in boundary to find the associated unit */
463 UnitID get_id_from_in(const Vertex &in) const;
464 UnitID get_id_from_out(const Vertex &out) const;
465
466 opt_reg_info_t get_reg_info(std::string reg_name) const;
467 register_t get_reg(std::string reg_name) const;
468
469 // returns the total number of vertices in dag
470 // O(1)
471 unsigned n_vertices() const;
472 // returns the total number of inputs/outputs to dag (via iterating through
473 // boundary map) O(1)
474 unsigned n_qubits() const;
475 unsigned n_bits() const;
476 unsigned n_units() const;
477
478 /**
479 * Does the given qubit begin with a \ref OpType::Create in the DAG?
480 */
481 bool is_created(const Qubit &id) const;
482
483 /**
484 * Does the given qubit end with a \ref OpType::Discard in the DAG?
485 */
486 bool is_discarded(const Qubit &id) const;
487
488 // returns the total number of non-boundary vertices in dag
489 // O(1)
490 unsigned n_gates() const;
491
492 // given a vertex, returns a vector of all its successor vertices (no
493 // duplicates) O(log(n!)), where `n` is number of outedges from `vert`
494 // (ignoring hashtable collisions)
495 VertexVec get_successors(const Vertex &vert) const;
496 VertexVec get_successors_of_type(const Vertex &vert, EdgeType type) const;
497 // O(log(n!)), where `n` is number of inedges of `vert` (ignoring hashtable
498 // collisions) given a vertex, returns a vector of all its predecessor
499 // vertices (no duplicates)
500 VertexVec get_predecessors(const Vertex &vert) const;
501 VertexVec get_predecessors_of_type(const Vertex &vert, EdgeType type) const;
502
503 // O(1)
504 unsigned n_edges() const;
505
506 unsigned n_edges_of_type(const EdgeType &et) const;
507
508 // return the ports corresponding to an edge
509 // O(1)
510 std::pair<port_t, port_t> get_ports(const Edge &edge) const;
511 port_t get_source_port(const Edge &edge) const;
512 port_t get_target_port(const Edge &edge) const;
513 EdgeType get_edgetype(const Edge &edge) const;
514
515 /**
516 * All inward edges, ordered by port number
517 * Every port has a single in-edge and they are numbered contiguously
518 * Types of edges will be mixed according to vert's signature
519 *
520 * @param vert vertex
521 */
522 EdgeVec get_in_edges(const Vertex &vert) const;
523
524 /**
525 * All inward edges of given type, ordered by port number
526 *
527 * @param vert vertex
528 * @param et edge type
529 */
530 EdgeVec get_in_edges_of_type(const Vertex &vert, EdgeType et) const;
531
532 /**
533 * Outward edges for linear (Quantum, Classical) types, ordered by port number
534 * Vector has one entry per port in vert's signature; Boolean ports have
535 * nullopt
536 *
537 * @param vert vertex
538 */
539 std::vector<std::optional<Edge>> get_linear_out_edges(
540 const Vertex &vert) const;
541
542 /**
543 * @brief Get the linear edge corresponding to `e`
544 *
545 * If `e` is linear, return itself, otherwise (if `e` is Boolean), return
546 * the corresponding Classical edge.
547 *
548 * EdgeType::Classical and EdgeType::Quantum are linear types (and thus left
549 * unchanged), whereas EdgeType::Boolean is not.
550 */
551 Edge get_linear_edge(const Edge &e) const;
552
553 /**
554 * Outward edges for all types, ordered by port number
555 * For classical ports, the Classical output is given, followed by any
556 * Boolean outputs
557 *
558 * @param vert vertex
559 */
560 EdgeVec get_all_out_edges(const Vertex &vert) const;
561
562 /**
563 * All outward edges of given type, ordered by port number
564 *
565 * @param vert vertex
566 * @param et edge type
567 */
568 EdgeVec get_out_edges_of_type(const Vertex &vert, EdgeType et) const;
569
570 /**
571 * All bundles of outward Boolean edges, ordered by port number
572 *
573 * Each member of the list is a list of edges sharing the same port
574 *
575 * @param vert vertex
576 */
577 std::vector<EdgeVec> get_b_out_bundles(
578 const Vertex &vert) const; // returned by port no.
579
580 /**
581 * All bundles of in Boolean edges, ordered by port number
582 *
583 * Each member of the list is a list of edges sharing the same port
584 *
585 * @param vert vertex
586 */
587 std::vector<EdgeVec> get_b_in_bundles(
588 const Vertex &vert) const; // returned by port no.
589
590 /**
591 * Total number of inward edges
592 *
593 * @param vert vertex
594 */
595 unsigned n_in_edges(const Vertex &vert) const;
596
597 /**
598 * Number of inward edges of a specific type
599 */
600 unsigned n_in_edges_of_type(const Vertex &vert, EdgeType et) const;
601
602 /**
603 * Total number of outward edges
604 *
605 * @param vert vertex
606 */
607 unsigned n_out_edges(const Vertex &vert) const;
608
609 /**
610 * Number of outward edges of a specific type
611 */
612 unsigned n_out_edges_of_type(const Vertex &vert, EdgeType et) const;
613
614 /**
615 * Number of ports expected on vertex based on Op signature
616 */
617 unsigned n_ports(const Vertex &vert) const;
618
619 // O(n) n is the number of ports
620 /**
621 * @brief Get the edge targeting the nth input port at vert_to
622 *
623 * @param vert_to a vertex
624 * @param n the input port number
625 * @return the corresponding edge
626 */
627 Edge get_nth_in_edge(const Vertex &vert_to, const port_t &n) const;
628
629 // O(n) n is the number of ports
630 /**
631 * @brief Get the edge originated from the nth output port at vert_from
632 *
633 * @param vert_from a vertex
634 * @param n the output port number
635 * @return the corresponding edge
636 */
637 Edge get_nth_out_edge(const Vertex &vert_from, const port_t &n) const;
638 EdgeVec get_nth_b_out_bundle(const Vertex &vert_from, const port_t &n) const;
639
640 /** True if no incident edges are @ref EdgeType::Classical */
641 bool is_quantum_node(const Vertex &vert) const;
642
643 /** True if no incident edges are @ref EdgeType::Quantum */
644 bool is_classical_node(const Vertex &vert) const;
645
646 // O(1)
647 ✗ Vertex target(const Edge &e) const { return boost::target(e, dag); }
648 // O(1)
649 ✗ Vertex source(const Edge &e) const { return boost::source(e, dag); }
650
651 // given a vertex, returns its associated op
652 // O(1)
653 const Op_ptr get_Op_ptr_from_Vertex(const Vertex &vert) const;
654 void set_vertex_Op_ptr(const Vertex &vert, const Op_ptr &op);
655
656 /**
657 * Get the op group name (if any) associated with a vertex.
658 */
659 const std::optional<std::string> &get_opgroup_from_Vertex(
660 const Vertex &vert) const;
661
662 /**
663 * Get the set of all opgroup names.
664 */
665 const std::unordered_set<std::string> get_opgroups() const;
666
667 // O(1) (lookup in hashtable)
668 OpDesc get_OpDesc_from_Vertex(const Vertex &vert) const;
669 OpType get_OpType_from_Vertex(const Vertex &vert) const;
670 op_signature_t get_Op_signature_from_Vertex(const Vertex &vert) const;
671
672 /**
673 * Given a Quantum or Classical in-edge to vert, returns the corresponding
674 * out-edge, tracing the resource unit through the dag.
675 * O(n), `n` is number of out edges of vert
676 */
677 Edge get_next_edge(const Vertex &vert, const Edge &in_edge)
678 const; // this doesnt need a vertex
679 // O(n), `n` is number of in edges of vert
680 Edge get_last_edge(const Vertex &vert, const Edge &out_edge) const;
681
682 // given a vertex and corresponding in edge, returns next operation as its
683 // vertex and edge O(n), `n` is number of out edges of vert
684 std::pair<Vertex, Edge> get_next_pair(
685 const Vertex &current_vertex, const Edge &inedge) const;
686 // given a vertex and corresponding out edge, returns last op as its vertex
687 // and edge
688 // O(n), `n` is number of in edges of vert
689 std::pair<Vertex, Edge> get_prev_pair(
690 const Vertex &current_vertex, const Edge &outedge) const;
691
692 /**
693 * Detect whether a vertex corresponds to an initial node in the DAG.
694 */
695 bool detect_initial_Op(const Vertex &vertex) const;
696
697 /**
698 * Detect whether a vertex corresponds to a final node in the DAG.
699 */
700 bool detect_final_Op(const Vertex &vertex) const;
701
702 /**
703 * Detect whether a vertex corresponds to a boundary node in the DAG.
704 */
705 bool detect_boundary_Op(const Vertex &vertex) const;
706
707 // returns true if given vertex is a single qubit, reversible gate
708 // O(1)
709 bool detect_singleq_unitary_op(const Vertex &vert) const;
710
711 /**
712 * Index of qubit for operation at a given vertex port
713 *
714 * @param vert vertex
715 * @param port_type type of specified port
716 * @param port port index
717 *
718 * @return qubit index
719 * @throw std::domain_error if port doesn't correspond to a quantum wire
720 */
721 unsigned qubit_index(
722 const Vertex &vert, PortType port_type, port_t port) const;
723
724 /**
725 * Which Pauli, if any, commutes with the operation at a given vertex and port
726 *
727 * @param vert vertex
728 * @param port_type type of specified port
729 * @param port port number at which Pauli should commute
730 * @return a Pauli that commutes with the given operation
731 * @retval std::nullopt no Pauli commutes (or operation is not a gate)
732 * @retval Pauli::I every Pauli commutes
733 */
734 std::optional<Pauli> commuting_basis(
735 const Vertex &vert, PortType port_type, port_t port) const;
736
737 /**
738 * Whether the operation at a vertex commutes with a Pauli at the given port
739 *
740 * @param vert vertex
741 * @param colour Pauli operation type
742 * @param port_type type of specified port
743 * @param port port number at which Pauli may commute
744 */
745 bool commutes_with_basis(
746 const Vertex &vert, const std::optional<Pauli> &colour,
747 PortType port_type, port_t port) const;
748
749 /**
750 * Convert all quantum and classical bits to use default registers.
751 *
752 * @return mapping from old to new unit IDs
753 */
754 unit_map_t flatten_registers();
755
756 //_________________________________________________
757
758 //////////////////////////////
759 // Basic Circuit Manipulation//
760 //////////////////////////////
761
762 // O(V), `V` the number of vertices
763 void remove_blank_wires();
764
765 /**
766 * Remove all gates in the circuits that are identities
767 */
768 void remove_noops();
769
770 /**
771 * Append an operation to the circuit.
772 *
773 * Appends vertex to the end of the given paths. Assumes the units already
774 * exist in the circuit and boundary.
775 *
776 * @param op operation to append
777 * @param args any Quantum, Boolean, or Classical inputs
778 * @param opgroup name of associated operation group, if any
779 *
780 * @return the newly-added vertex in the circuit's DAG
781 */
782 // O(n alpha), where `n` size of qubits vector
783 // the `alpha` comes from edge removal to rewire and is the number of edges in
784 // the highest arity vertex
785 template <class ID>
786 Vertex add_op(
787 const Op_ptr &op, const std::vector<ID> &args,
788 std::optional<std::string> opgroup = std::nullopt);
789
790 /**
791 * Append an operation of a given type (with no parameters) to the circuit
792 *
793 * @param type type of operation to append
794 * @param args any Quantum, Boolean, or Classical inputs
795 * @param opgroup name of associated operation group, if any
796 *
797 * @return the newly-added vertex in the circuit's DAG
798 */
799 template <class ID>
800 360 Vertex add_op(
801 OpType type, const std::vector<ID> &args,
802 std::optional<std::string> opgroup = std::nullopt) {
803
1/2
✓ Branch 3 taken 180 times.
✗ Branch 4 not taken.
 360 return add_op(type, std::vector<Expr>{}, args, opgroup);
804 }
805
806 /**
807 * Append an operation of a given type (with a parameter) to the circuit
808 *
809 * @param type type of operation to append
810 * @param param operation parameter
811 * @param args any Quantum, Boolean, or Classical inputs
812 * @param opgroup name of associated operation group, if any
813 *
814 * @return the newly-added vertex in the circuit's DAG
815 */
816 template <class ID>
817 65 Vertex add_op(
818 OpType type, const Expr &param, const std::vector<ID> &args,
819 std::optional<std::string> opgroup = std::nullopt) {
820
5/10
✓ Branch 2 taken 65 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 65 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 65 times.
✗ Branch 10 not taken.
✓ Branch 13 taken 65 times.
✓ Branch 14 taken 65 times.
✗ Branch 19 not taken.
✗ Branch 20 not taken.
 130 return add_op(type, std::vector<Expr>{param}, args, opgroup);
821 }
822
823 /**
824 * Append an operation of a given type (with parameters) to the circuit
825 *
826 * @param type type of operation to append
827 * @param params operation parameters
828 * @param args any Quantum, Boolean, or Classical inputs
829 * @param opgroup name of associated operation group, if any
830 *
831 * @return the newly-added vertex in the circuit's DAG
832 */
833 template <class ID>
834 472 Vertex add_op(
835 OpType type, const std::vector<Expr> &params, const std::vector<ID> &args,
836 std::optional<std::string> opgroup = std::nullopt) {
837
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 236 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 472 times.
 472 if (is_metaop_type(type)) {
838 ✗ throw CircuitInvalidity(
839 "Cannot add metaop. Please use `add_barrier` to add a "
840 "barrier.");
841 }
842
2/4
✓ Branch 3 taken 236 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 236 times.
✗ Branch 7 not taken.
 472 return add_op(get_op_ptr(type, params, args.size()), args, opgroup);
843 }
844
845 /**
846 * Add a measure operation from a qubit to a bit
847 *
848 * @param qubit qubit to measure
849 * @param bit target of measurement
850 *
851 * @return vertex representing the measure operation
852 */
853 ✗ Vertex add_measure(const Qubit &qubit, const Bit &bit) {
854 ✗ return add_op<UnitID>(OpType::Measure, {qubit, bit});
855 }
856
857 /**
858 * Add a measure operation from a qubit to a bit on the default registers
859 *
860 * @param qubit qubit to measure
861 * @param bit target of measurement
862 *
863 * @return vertex representing the measure operation
864 */
865 Vertex add_measure(unsigned qubit, unsigned bit) {
866 return add_measure(Qubit(qubit), Bit(bit));
867 }
868
869 /**
870 * Append a box to the circuit
871 *
872 * @param box box to append
873 * @param args any Quantum, Boolean, or Classical inputs
874 * @param opgroup name of associated operation group, if any
875 *
876 * @return the newly-added vertex in the circuit's DAG
877 */
878 template <class BoxT, class ID = unsigned>
879 ✗ Vertex add_box(
880 const BoxT &box, const std::vector<ID> &args,
881 std::optional<std::string> opgroup = std::nullopt) {
882 ✗ return add_op(std::make_shared<BoxT>(box), args, opgroup);
883 }
884
885 /**
886 * Append a conditional operation to the circuit
887 *
888 * @param type type of operation to append
889 * @param params parameters of operation
890 * @param args any Quantum, Boolean, or Classical inputs
891 * @param bits any Classical outputs
892 * @param value value on which to condition operation (little-endian)
893 * @param opgroup name of associated operation group, if any
894 *
895 * @return the newly-added vertex in the circuit's DAG
896 */
897 template <class ID>
898 Vertex add_conditional_gate(
899 OpType type, const std::vector<Expr> &params, const std::vector<ID> &args,
900 const std::vector<ID> &bits, unsigned value,
901 std::optional<std::string> opgroup = std::nullopt) {
902 if (is_metaop_type(type)) {
903 throw CircuitInvalidity("Cannot add a conditional metaop.");
904 }
905 Op_ptr cond = std::make_shared<Conditional>(
906 get_op_ptr(type, params, (unsigned)args.size()), (unsigned)bits.size(),
907 value);
908 std::vector<ID> new_args = bits;
909 new_args.insert(new_args.end(), args.begin(), args.end());
910 return add_op(cond, new_args, opgroup);
911 }
912
913 Vertex add_barrier(
914 const std::vector<unsigned> &qubits,
915 const std::vector<unsigned> &bits = {}, const std::string &_data = "");
916
917 Vertex add_barrier(const unit_vector_t &args, const std::string &_data = "");
918
919 /**
920 * Add a postfix to a classical register name if the register exists
921 * Example: tket_c results in tket_c_2 if tket_c and tket_c_1 both exist
922 *
923 * @param reg_name the base register name
924 *
925 * @return the incremented register name
926 */
927 std::string get_next_c_reg_name(const std::string &reg_name);
928
929 Vertex add_assertion(
930 const ProjectorAssertionBox &assertion_box,
931 const std::vector<Qubit> &qubits,
932 const std::optional<Qubit> &ancilla = std::nullopt,
933 const std::optional<std::string> &name = std::nullopt);
934
935 Vertex add_assertion(
936 const StabiliserAssertionBox &assertion_box,
937 const std::vector<Qubit> &qubits, const Qubit &ancilla,
938 const std::optional<std::string> &name = std::nullopt);
939
940 /**
941 * Add a vertex to the DAG.
942 *
943 * O(1)
944 *
945 * @param op_ptr operation associated with vertex
946 * @param opgroup name of associated operation group, if any
947 *
948 * @return the new vertex
949 */
950 Vertex add_vertex(
951 const Op_ptr op_ptr, std::optional<std::string> opgroup = std::nullopt);
952
953 /**
954 * Add a vertex of given type (no parameters) to the DAG.
955 *
956 * O(1)
957 *
958 * @param type type of operation associated with vertex
959 * @param opgroup name of associated operation group, if any
960 *
961 * @return the new vertex
962 */
963 Vertex add_vertex(
964 const OpType &type, std::optional<std::string> opgroup = std::nullopt);
965
966 // given vertices and desired in port for i2 and out port
967 // for i1, adds edge bewteen them
968 // O(1)
969 Edge add_edge(
970 const VertPort &source, const VertPort &target, const EdgeType &type);
971
972 // adds blank wire, originally intended to use all of architecture available
973 // in routing a 'blank wire' is an input -> output path
974 // O(n)
975 void add_blank_wires(unsigned n);
976
977 void add_qubit(const Qubit &id, bool reject_dups = true);
978 void add_bit(const Bit &id, bool reject_dups = true);
979 register_t add_q_register(std::string reg_name, unsigned size);
980 register_t add_c_register(std::string reg_name, unsigned size);
981
982 /**
983 * Create the given qubit in the zero state at the beginning of the circuit.
984 *
985 * The qubit must exist in the circuit already. This changes its initial
986 * node in the DAG to @ref OpType::Create instead of @ref OpType::Input.
987 * This is semantically equivalent to adding a @ref OpType::Reset operation
988 * immediately after the input node.
989 *
990 * If the node is already @ref OpType::Create, the method does nothing.
991 *
992 * @param id qubit
993 * @throws CircuitInvalidity if qubit not in circuit
994 */
995 void qubit_create(const Qubit &id);
996
997 /** Call \ref qubit_create on all qubits. */
998 void qubit_create_all();
999
1000 /**
1001 * Discard the given qubit at the end of the circuit.
1002 *
1003 * The qubit must exist in the circuit already. This changes its final node
1004 * in the DAG to @ref OpType::Discard instead of @ref OpType::Output. This
1005 * means that the qubit wire cannot be precomposed with a qubit wire in
1006 * another circuit that begins with an @ref OpType::Input.
1007 *
1008 * If the node is already @ref OpType::Discard, the method does nothing.
1009 *
1010 * @param id qubit
1011 * @throws CircuitInvalidity if qubit not in circuit
1012 */
1013 void qubit_discard(const Qubit &id);
1014
1015 /** Call \ref qubit_discard on all qubits. */
1016 void qubit_discard_all();
1017
1018 /**
1019 * Rename all the units according to the given mapping
1020 *
1021 * @return true iff circuit was modified
1022 */
1023 template <typename UnitA, typename UnitB>
1024 bool rename_units(const std::map<UnitA, UnitB> &qm);
1025
1026 /** Automatically rewire holes when removing vertices from the circuit? */
1027 enum class GraphRewiring { Yes, No };
1028
1029 /** Delete vertices from the DAG when removing them from the circuit? */
1030 enum class VertexDeletion { Yes, No };
1031
1032 /** How to treat op groups when substituting in larger circuit */
1033 enum class OpGroupTransfer {
1034 Preserve, /**< keep them, error only for collisions */
1035 Remove, /**< remove them */
1036 Disallow, /**< disallow them */
1037 Merge /**< merge them, error for mismatched signature */
1038 };
1039
1040 /** Merge boundaries when copying another circuit's DAG into a circuit? */
1041 enum class BoundaryMerge { Yes, No };
1042
1043 // this could be templated or VertexSet version removed entirely?
1044 // if graph_rewiring is on, this is O(N n alpha), where N the size of surplus,
1045 // `n` the number of edges on the maximum arity vertex to be removed
1046 // Else, O(N)
1047 // if any of the vertices are boundaries, introduces additional factor of
1048 // times `q`, where `q` size of boundary/number of qubits
1049 void remove_vertices(
1050 const VertexSet &surplus, GraphRewiring graph_rewiring,
1051 VertexDeletion vertex_deletion);
1052 void remove_vertices(
1053 const VertexList &surplus, GraphRewiring graph_rewiring,
1054 VertexDeletion vertex_deletion);
1055
1056 // given vertex, eradicates it from dag
1057 // if graph_rewiring is on, O(n alpha), where `n` is arity of vertex
1058 // else O(1)
1059 // if any of the vertices are boundaries, factor of `q` again
1060 void remove_vertex(
1061 const Vertex &deadvert, GraphRewiring graph_rewiring,
1062 VertexDeletion vertex_deletion);
1063 // sometimes want to remove a vertex from a circuit without destroying it
1064 // (eg to keep a container of vertices valid)
1065
1066 /**
1067 * Removes a single edge from the dag
1068 */
1069 void remove_edge(const Edge &edge);
1070
1071 /**
1072 * Rewires linear resources (Quantum or Classical) in place of pred
1073 * Adds new edges for Boolean
1074 * O(n alpha), where `n` is the number of edges in the cut
1075 */
1076 void rewire(
1077 const Vertex &new_vert, const EdgeVec &preds,
1078 const op_signature_t &types);
1079
1080 //_________________________________________________
1081
1082 ////////////////////
1083 // Macro Circuit Info//
1084 ////////////////////
1085
1086 bool is_simple() const;
1087 bool default_regs_ok() const;
1088
1089 /**
1090 * Count operations by type.
1091 *
1092 * Includes all types of operation, including initial and final nodes.
1093 *
1094 * @return map from op type to number of instances
1095 */
1096 std::map<OpType, unsigned> op_counts() const;
1097
1098 unsigned count_gates(const OpType &op_type) const;
1099 VertexSet get_gates_of_type(const OpType &op_type) const;
1100
1101 /**
1102 * @brief Get all commands of a given type.
1103 *
1104 * @param op_type operation type
1105 *
1106 * @return list of commands of given type, in causal order
1107 */
1108 std::list<Command> get_commands_of_type(OpType op_type) const;
1109
1110 // returns 'slices' of 'parallel' actions in dag as a vector encompassing
1111 // all vertices
1112 // O(D qlog^2(q!) alpha log(alpha!))
1113 // this is o(D q^3 log^2(q) alpha^2 log(alpha))
1114 SliceVec get_slices() const;
1115
1116 // returns slices of parallel actions from the end to the front
1117 SliceVec get_reverse_slices() const;
1118
1119 // starts at input edge and follows qubit path, returns first edge on path
1120 // with non single qubit target (or Output) O(D + alpha)
1121 Edge skip_irrelevant_edges(Edge current) const;
1122
1123 // given current slice and a set of slices, returns the next slice
1124 // O(q log^2(q!) alpha log(alpha!))
1125 CutFrontier next_cut(
1126 std::shared_ptr<const unit_frontier_t> u_frontier,
1127 std::shared_ptr<const b_frontier_t> b_frontier) const;
1128
1129 CutFrontier next_cut(
1130 std::shared_ptr<const unit_frontier_t> u_frontier,
1131 std::shared_ptr<const b_frontier_t> b_frontier,
1132 const std::function<bool(Op_ptr)> &skip_func) const;
1133
1134 // given current slice of quantum frontier, returns the next slice.
1135 // ignore classical and boolean edges
1136 CutFrontier next_q_cut(
1137 std::shared_ptr<const unit_frontier_t> u_frontier) const;
1138
1139 /**
1140 * Depth of circuit.
1141 *
1142 * This is the number of vertices in the longest path through the DAG,
1143 * excluding boundary vertices and vertices representing barriers.
1144 *
1145 * O(D qlog^2(q!) alpha log(alpha!))
1146 *
1147 * @return depth
1148 */
1149 unsigned depth() const;
1150
1151 /**
1152 * Depth of circuit restricting to one operation type.
1153 *
1154 * This is the number of vertices in the longest path through the sub-DAG
1155 * consisting of vertices representing operations of the given type.
1156 *
1157 * @return depth
1158 */
1159 unsigned depth_by_type(OpType _type) const;
1160
1161 /**
1162 * Depth of circuit restricting to a set of operation types.
1163 *
1164 * This is the number of vertices in the longest path through the sub-DAG
1165 * consisting of vertices representing operations of the given types.
1166 *
1167 * @return depth
1168 */
1169 unsigned depth_by_types(const OpTypeSet &_types) const;
1170
1171 std::map<Vertex, unit_set_t> vertex_unit_map() const;
1172 std::map<Vertex, unsigned> vertex_depth_map() const;
1173 std::map<Vertex, unsigned> vertex_rev_depth_map() const;
1174 std::map<Edge, UnitID> edge_unit_map() const;
1175
1176 Circuit subcircuit(const Subcircuit &sc) const;
1177
1178 // returns qubit path via vertices & inhabited port in vertices
1179 QPathDetailed unit_path(const UnitID &unit) const; // vector<vertex,port>
1180 // returns a vector of each qubits path via qubit_path
1181 std::vector<QPathDetailed> all_qubit_paths() const;
1182 std::map<UnitID, QPathDetailed> all_unit_paths() const;
1183 // returns a basic qubit path consisting of just vertices
1184 VertexVec qubit_path_vertices(const Qubit &qubit) const;
1185
1186 // returns a map from input qubit to output qubit on the same path
1187 qubit_map_t implicit_qubit_permutation() const;
1188
1189 /**
1190 * Whether the circuit contains implicit wireswaps
1191 */
1192 bool has_implicit_wireswaps() const;
1193
1194 /*
1195 Permute output boundary of circuit according to qubit map
1196 Assumes all circuit Qubits are mapped
1197 */
1198 void permute_boundary_output(const qubit_map_t &qm);
1199
1200 /**
1201 * Equality operator
1202 *
1203 * Two circuits compare equal if they comprise the same sequence of
1204 * operators, with the ordering guaranteed by @ref get_commands, and if name,
1205 * phase, Qubits, Bits and implicit permutation also match.
1206 * By using the circuit_equality method, attributes other than commands
1207 * can be ignored in the equality check by being passed to the optional
1208 * except parameter.
1209 */
1210 enum class Check { Units, ImplicitPermutation, Phase, Name };
1211 // fine grained equality check, can set attributes to be ignored
1212 // optionally throws errors when mismatch found
1213 bool circuit_equality(
1214 const Circuit &other, const std::set<Check> &except = {},
1215 bool throw_error = true) const;
1216 ✗ bool operator==(const Circuit &other) const {
1217 ✗ return this->circuit_equality(other, {}, false);
1218 }
1219
1220 /** @brief Checks causal ordering of vertices
1221 *
1222 * @param target the target vertex
1223 * @param from the source vertex
1224 * @param forward whether causality check is towards the future or reverse
1225 * @param v_to_depth depth map
1226 * @param v_to_units units map
1227 * @param strict whether causality check should be strict (i.e. from == target
1228 * returns false) or not. Defaults to true
1229 */
1230 bool in_causal_order(
1231 const Vertex &target, const Vertex &from, bool forward,
1232 const std::map<Vertex, unsigned> &v_to_depth,
1233 const std::map<Vertex, unit_set_t> &v_to_units, bool strict = true) const;
1234
1235 //___________________________________________________
1236
1237 ////////////////////////////
1238 // Large Scale Manipulation//
1239 ////////////////////////////
1240
1241 /**
1242 * Copy a circuit's DAG into the current circuit.
1243 *
1244 * Optionally updates the boundary of the composite circuit.
1245 *
1246 * Self-copy is not supported.
1247 *
1248 * @param c2 circuit to copy
1249 * @param boundary_merge whether to merge circuit boundaries
1250 * @param opgroup_transfer how to handle op group names
1251 *
1252 * @return map from vertices in inserted circuit to new inserted vertices
1253 */
1254 vertex_map_t copy_graph(
1255 const Circuit &c2, BoundaryMerge boundary_merge = BoundaryMerge::Yes,
1256 OpGroupTransfer opgroup_transfer = OpGroupTransfer::Merge);
1257
1258 // O(E+V+q) -- E,V,q of c2
1259 void append(const Circuit &c2);
1260 // TODO:: Register-specific appending, probably be defining a register
1261 // renaming method
1262 void append_with_map(const Circuit &c2, const unit_map_t &qm);
1263 void append_qubits(
1264 const Circuit &c2, const std::vector<unsigned> &qubits,
1265 const std::vector<unsigned> &bits = {});
1266
1267 // O(E+V+q) -- E,V,q of c2
1268 friend Circuit operator*(const Circuit &c1, const Circuit &c2);
1269 // given two circuits, adds second circuit to first sequentially by tying
1270 // qubits together
1271 // O(E1+V1+q1+E2+V2+q2) -- both circuits are copied here
1272 friend Circuit operator>>(const Circuit &c1, const Circuit &c2);
1273
1274 // O(E+V+q) -- E,V,q of incirc
1275 void cut_insert(
1276 const Circuit &incirc, const EdgeVec &q_preds,
1277 const EdgeVec &c_preds = {},
1278 const EdgeVec &b_future = {}); // naive insertion
1279
1280 // Insert v2: Takes a subcircuit with valid boundary and replaces whatever
1281 // is in a hole
1282 // O(E+V+q+(n alpha)), where `n` the number of vertices to delete (regardless
1283 // of vertex_deletion) E,V,q are of `to_insert` Will fail if any classical
1284 // inputs/outputs of to_insert are discarded/trivial
1285
1286 /**
1287 * Replace a subcircuit with a new circuit
1288 *
1289 * @param to_insert circuit to insert
1290 * @param to_replace subcircuit to replace
1291 * @param vertex_deletion whether to delete replaced vertices from the DAG
1292 * @param opgroup_transfer how to treat op groups in \p to_insert
1293 */
1294 void substitute(
1295 const Circuit &to_insert, const Subcircuit &to_replace,
1296 VertexDeletion vertex_deletion = VertexDeletion::Yes,
1297 OpGroupTransfer opgroup_transfer = OpGroupTransfer::Disallow);
1298
1299 /**
1300 * Replace a vertex with a new circuit
1301 *
1302 * @param to_insert replacement circuit
1303 * @param to_replace vertex to replace
1304 * @param vertex_deletion whether to remove \p to_replace from the DAG
1305 * @param opgroup_transfer how to treat op groups in \p to_insert
1306 *
1307 * @pre \p to_replace has no Boolean inputs
1308 */
1309 void substitute(
1310 const Circuit &to_insert, const Vertex &to_replace,
1311 VertexDeletion vertex_deletion = VertexDeletion::Yes,
1312 OpGroupTransfer opgroup_transfer = OpGroupTransfer::Disallow);
1313
1314 /**
1315 * Replace a conditional vertex with a new circuit.
1316 *
1317 * The new circuit replaces the op to be performed conditionally (i.e. the
1318 * conditions are not included in this circuit).
1319 *
1320 * @param to_insert replacement circuit
1321 * @param to_replace vertex with conditional op to replace
1322 * @param vertex_deletion whether to remove \p to_replace from the DAG
1323 * @param opgroup_transfer how to treat op groups in \p to_insert
1324 *
1325 * @pre \p to_insert should have no named op groups
1326 */
1327 void substitute_conditional(
1328 Circuit to_insert, const Vertex &to_replace,
1329 VertexDeletion vertex_deletion = VertexDeletion::Yes,
1330 OpGroupTransfer opgroup_transfer = OpGroupTransfer::Disallow);
1331
1332 /**
1333 * Replace all explicit swaps (i.e. SWAP gates) with implicit swaps.
1334 *
1335 * The boundaries are not updated. Implicit permutations introduced in this
1336 * way can be obtained using the \ref implicit_qubit_permutation method.
1337 *
1338 * O(V)
1339 */
1340 void replace_SWAPs();
1341
1342 /**
1343 * this function replaces an implicit wire swap between the two given qubits
1344 * with three CX operations
1345 *
1346 * @param first qubits to add the wireswap on
1347 * @param second qubits to add the wireswap on
1348 *
1349 * O(c)
1350 */
1351 void replace_implicit_wire_swap(const Qubit first, const Qubit second);
1352
1353 // O(E+V+q)
1354 Circuit dagger() const;
1355
1356 Circuit transpose() const;
1357
1358 /**
1359 * Substitute all vertices matching the given op with the given circuit
1360 *
1361 * @param to_insert circuit to insert
1362 * @param op operation to match
1363 *
1364 * @return whether any vertices were replaced
1365 *
1366 * @pre \p to_insert should have no named op groups
1367 */
1368 bool substitute_all(const Circuit &to_insert, const Op_ptr op);
1369
1370 /**
1371 * Substitute all operations matching the given name with the given circuit.
1372 *
1373 * Any named operations in the inserted circuit retain their names in the
1374 * new circuit.
1375 *
1376 * @param to_insert circuit to insert
1377 * @param opname name of operations to replace
1378 *
1379 * @return whether any replacements were made
1380 *
1381 * @pre Named operations in the inserted circuit must have the same
1382 * signature as any named operations in the main circuit with the same name.
1383 */
1384 bool substitute_named(const Circuit &to_insert, const std::string opname);
1385
1386 /**
1387 * Substitute all operations matching the given name with the given op.
1388 *
1389 * The inserted operations retain the name of the substituted ones.
1390 *
1391 * @param to_insert operation to insert
1392 * @param opname name of operations to replace
1393 *
1394 * @return whether any replacements were made
1395 */
1396 bool substitute_named(Op_ptr to_insert, const std::string opname);
1397
1398 /**
1399 * Substitute all operations matching the given name with the given box.
1400 *
1401 * The inserted boxes retain the name of the substituted ones.
1402 *
1403 * @param to_insert box to insert
1404 * @param opname name of operations to replace
1405 *
1406 * @return whether any replacements were made
1407 */
1408 template <class BoxT>
1409 bool substitute_named(const BoxT &to_insert, const std::string opname) {
1410 // Do nothing if opname not present
1411 if (opgroupsigs.find(opname) == opgroupsigs.end()) {
1412 return false;
1413 }
1414
1415 // Check signatures match
1416 op_signature_t sig = opgroupsigs[opname];
1417 if (to_insert.get_signature() != sig) {
1418 throw CircuitInvalidity("Signature mismatch");
1419 }
1420
1421 VertexVec to_replace;
1422 BGL_FORALL_VERTICES(v, dag, DAG) {
1423 std::optional<std::string> v_opgroup = get_opgroup_from_Vertex(v);
1424 if (v_opgroup && v_opgroup.value() == opname) {
1425 to_replace.push_back(v);
1426 }
1427 }
1428
1429 unsigned sig_n_q = std::count(sig.begin(), sig.end(), EdgeType::Quantum);
1430 unsigned sig_n_c = std::count(sig.begin(), sig.end(), EdgeType::Classical);
1431 Circuit c(sig_n_q, sig_n_c);
1432 unit_vector_t args(sig_n_q + sig_n_c);
1433 for (unsigned i = 0; i < sig_n_q; i++) args[i] = Qubit(i);
1434 for (unsigned i = 0; i < sig_n_c; i++) args[sig_n_q + i] = Bit(i);
1435 c.add_box(to_insert, args, opname);
1436 for (const Vertex &v : to_replace) {
1437 substitute(c, v, VertexDeletion::Yes, OpGroupTransfer::Merge);
1438 }
1439
1440 return !to_replace.empty();
1441 }
1442
1443 /**
1444 * Adds a condition to every op in the circuit.
1445 * Will throw a CircuitInvalidity error if the circuit contains implicit
1446 * wireswaps (as these cannot be applied conditionally) or writes to the
1447 * condition bits at any point.
1448 *
1449 * @param bits Set of bits to condition the execution
1450 * @param value Little-endian target value for the condition bits (e.g. value
1451 * 2 (10b) means bits[0] must be 0 and bits[1] must be 1)
1452 */
1453 Circuit conditional_circuit(const bit_vector_t &bits, unsigned value) const;
1454
1455 /**
1456 * Replaces one vertex by applying \ref Box::to_circuit
1457 *
1458 * @return whether the vertex holds a box or a conditional box
1459 */
1460 bool substitute_box_vertex(Vertex &vert, VertexDeletion vertex_deletion);
1461
1462 /**
1463 * Replaces each \ref Box operation by applying \ref Box::to_circuit
1464 *
1465 * @return whether any replacements were made
1466 */
1467 bool decompose_boxes();
1468
1469 /**
1470 * Recursively apply \ref decompose_boxes
1471 *
1472 * @post no \ref Box operations remain
1473 */
1474 void decompose_boxes_recursively();
1475
1476 /////////////////
1477 // Other Methods//
1478 /////////////////
1479
1480 void symbol_substitution(const symbol_map_t &symbol_map);
1481 void symbol_substitution(
1482 const std::map<Sym, double, SymEngine::RCPBasicKeyLess> &symbol_map);
1483 void symbol_substitution(const SymEngine::map_basic_basic sub_map);
1484
1485 /** Set of all free symbols occurring in operation parameters. */
1486 const SymSet free_symbols() const;
1487
1488 /** Whether the circuit contains any symbolic parameters */
1489 bool is_symbolic() const;
1490
1491 // from Circuit to various output formats
1492 void to_graphviz_file(const std::string &filename) const;
1493 void to_graphviz(std::ostream &out) const;
1494 std::string to_graphviz_str() const;
1495 // output stream overload
1496 friend std::ostream &operator<<(std::ostream &out, const Circuit &circ);
1497
1498 std::string to_latex_str() const;
1499 void to_latex_file(const std::string &filename) const;
1500
1501 void extract_slice_segment(unsigned slice_one, unsigned slice_two);
1502
1503 /* 'backends' for tket */
1504
1505 /**
1506 * Get the sequence of commands comprising the circuit
1507 *
1508 * The order is determined first by the temporal order in the circuit and
1509 * secondly by the register names and indices.
1510 *
1511 * Running time is \f$ O(D q^2 \log^2(q!)) \f$ where \f$ q \f$ is the number
1512 * of qubits and \f$ D \f$ is the circuit depth.
1513 */
1514 std::vector<Command> get_commands() const;
1515
1516 /**
1517 * Set the vertex indices in the DAG.
1518 *
1519 * Has no effect on circuit semantics, so "morally" const.
1520 */
1521 void index_vertices() /*const*/;
1522
1523 /**
1524 * All vertices of the DAG, topologically sorted.
1525 *
1526 * This method is "morally" const, but it sets the vertex indices in the DAG.
1527 *
1528 * @return vector of vertices in a topological (causal) order
1529 */
1530 std::vector<Vertex> vertices_in_order() /*const*/;
1531
1532 /**
1533 * Index the vertices according to their ordering in the DAG.
1534 *
1535 * Does not set the indices in the DAG: use @ref index_vertices for that.
1536 *
1537 * @return index map from Vertex to int
1538 */
1539 IndexMap index_map() const;
1540
1541 /**
1542 * Get the global phase offset as a multiple of pi (in the range [0,2)).
1543 *
1544 * This is not meaningful for circuits with classical interaction.
1545 *
1546 * @return global phase
1547 */
1548 Expr get_phase() const;
1549
1550 /**
1551 * Adds a global phase to the circuit
1552 *
1553 * @param a phase to add, as a multiple of pi
1554 */
1555 void add_phase(Expr a);
1556
1557 /**
1558 * Get the name of the circuit.
1559 *
1560 * @return name
1561 */
1562 ✗ std::optional<std::string> get_name() const { return name; };
1563
1564 /**
1565 * Set the name of the circuit
1566 *
1567 * @param _name name string
1568 */
1569 ✗ void set_name(const std::string _name) { name = _name; };
1570
1571 const Op_ptr command2op(Command &com);
1572
1573 /**
1574 * Evaluate a classical circuit on given inputs.
1575 *
1576 * The circuit must have only ClassicalTransform and SetBits operations. The
1577 * keys of the input map must correspond to the bits of the circuit.
1578 *
1579 * @param values input values
1580 * @return output values
1581 */
1582 std::map<Bit, bool> classical_eval(const std::map<Bit, bool> &values) const;
1583
1584 /* class members */
1585 // currently public (no bueno)
1586 DAG dag; /** Representation as directed graph */
1587 boundary_t boundary;
1588
1589 private:
1590 std::optional<std::string>
1591 name; /** optional string name descriptor for human identification*/
1592 Expr phase; /**< Global phase applied to circuit */
1593
1594 /** Signature associated with each named operation group */
1595 std::map<std::string, op_signature_t> opgroupsigs;
1596 };
1597
1598 JSON_DECL(Circuit)
1599
1600 /** Templated method definitions */
1601
1602 template <typename UnitA, typename UnitB>
1603 760 bool Circuit::rename_units(const std::map<UnitA, UnitB> &qm) {
1604 // Can only work for Unit classes
1605 static_assert(std::is_base_of<UnitID, UnitA>::value);
1606 static_assert(std::is_base_of<UnitID, UnitB>::value);
1607 // Unit types must be related, so cannot rename e.g. Bits to Qubits
1608 static_assert(
1609 std::is_base_of<UnitA, UnitB>::value ||
1610 std::is_base_of<UnitB, UnitA>::value);
1611 760 std::map<UnitID, BoundaryElement> new_elems;
1612 760 bool modified = false;
1613
2/2
✓ Branch 5 taken 1547 times.
✓ Branch 6 taken 380 times.
2/2
✓ Decision 'true' taken 1547 times.
✓ Decision 'false' taken 380 times.
 3854 for (const std::pair<const UnitA, UnitB> &pair : qm) {
1614
1/2
✓ Branch 2 taken 1547 times.
✗ Branch 3 not taken.
 3094 boundary_t::iterator found = boundary.get<TagID>().find(pair.first);
1615
2/4
✓ Branch 3 taken 1547 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 1547 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 3094 times.
 3094 if (found == boundary.get<TagID>().end()) {
1616 ✗ std::stringstream ss;
1617 ✗ ss << "unit " << pair.first.repr() << " not found in circuit";
1618 ✗ tket_log()->warn(ss.str());
1619 ✗ continue;
1620 }
1621
1622
2/4
✓ Branch 1 taken 1547 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1547 times.
✗ Branch 5 not taken.
 3094 opt_reg_info_t target_reg_info = get_reg_info(pair.second.reg_name());
1623
2/2
✓ Branch 1 taken 108 times.
✓ Branch 2 taken 1439 times.
2/2
✓ Decision 'true' taken 216 times.
✓ Decision 'false' taken 2878 times.
 3094 if (target_reg_info) {
1624
3/6
✓ Branch 1 taken 108 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 108 times.
✗ Branch 5 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 108 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 216 times.
 216 if (target_reg_info.value().first != found->type())
1625 ✗ throw CircuitInvalidity(
1626 "Incompatible registers: " + pair.first.reg_name() + " and " +
1627 pair.second.reg_name());
1628
2/4
✓ Branch 1 taken 108 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 108 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 216 times.
 216 if (target_reg_info.value().second != pair.second.reg_dim())
1629 ✗ throw CircuitInvalidity(
1630 "Existing register " + pair.second.reg_name() +
1631 " cannot support id: " + pair.second.repr());
1632 }
1633 std::pair<std::map<UnitID, BoundaryElement>::iterator, bool> inserted =
1634
3/6
✓ Branch 2 taken 1547 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1547 times.
✗ Branch 6 not taken.
✓ Branch 9 taken 1547 times.
✗ Branch 10 not taken.
 3094 new_elems.insert({pair.second, {pair.second, found->in_, found->out_}});
1635
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1547 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 3094 times.
 3094 if (!inserted.second)
1636 ✗ throw CircuitInvalidity(
1637 "Mapping two units to the same id: " + pair.second.repr());
1638 3094 modified = true;
1639
1/2
✓ Branch 1 taken 1547 times.
✗ Branch 2 not taken.
 3094 boundary.erase(found);
1640 }
1641
2/2
✓ Branch 5 taken 1547 times.
✓ Branch 6 taken 380 times.
2/2
✓ Decision 'true' taken 1547 times.
✓ Decision 'false' taken 380 times.
 3854 for (const std::pair<const UnitID, BoundaryElement> &pair : new_elems) {
1642
1/2
✓ Branch 1 taken 1547 times.
✗ Branch 2 not taken.
 3094 std::pair<boundary_t::iterator, bool> added = boundary.insert(pair.second);
1643
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1547 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 3094 times.
 3094 if (!added.second)
1644 ✗ throw CircuitInvalidity(
1645 "Unit already exists in circuit: " + pair.first.repr());
1646 TKET_ASSERT(modified);
1647 }
1648 760 return modified;
1649 }
1650
1651 template <>
1652 Vertex Circuit::add_op<unsigned>(
1653 const Op_ptr &op, const std::vector<unsigned> &args,
1654 std::optional<std::string> opgroup);
1655 template <class ID>
1656 478 Vertex Circuit::add_op(
1657 const Op_ptr &op, const std::vector<ID> &args,
1658 std::optional<std::string> opgroup) {
1659 static_assert(std::is_base_of<UnitID, ID>::value);
1660
1/2
✓ Branch 2 taken 239 times.
✗ Branch 3 not taken.
 478 op_signature_t sig = op->get_signature();
1661
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 239 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 478 times.
 478 if (sig.size() != args.size()) {
1662 ✗ throw CircuitInvalidity(
1663 ✗ std::to_string(args.size()) + " args provided, but " + op->get_name() +
1664 " requires " + std::to_string(sig.size()));
1665 }
1666
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 239 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 478 times.
 478 if (opgroup) {
1667 ✗ auto opgroupsig = opgroupsigs.find(opgroup.value());
1668
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (opgroupsig != opgroupsigs.end()) {
1669
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (opgroupsig->second != sig) {
1670
0/1
? Decision couldn't be analyzed.
 ✗ throw CircuitInvalidity("Mismatched signature for operation group");
1671 }
1672 } else {
1673 ✗ opgroupsigs[opgroup.value()] = sig;
1674 }
1675 }
1676
1677
2/4
✓ Branch 1 taken 239 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 239 times.
✗ Branch 6 not taken.
 478 Vertex new_v = add_vertex(op, opgroup);
1678 478 unit_set_t write_arg_set;
1679 478 EdgeVec preds;
1680
2/2
✓ Branch 1 taken 315 times.
✓ Branch 2 taken 239 times.
2/2
✓ Decision 'true' taken 315 times.
✓ Decision 'false' taken 239 times.
 1108 for (unsigned i = 0; i < args.size(); ++i) {
1681 630 const UnitID &arg = args[i];
1682
1/2
✓ Branch 1 taken 315 times.
✗ Branch 2 not taken.
1/2
✓ Decision 'true' taken 630 times.
✗ Decision 'false' not taken.
 630 if (sig[i] != EdgeType::Boolean) {
1683
2/4
✓ Branch 2 taken 315 times.
✗ Branch 3 not taken.
✗ Branch 5 not taken.
✓ Branch 6 taken 315 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 630 times.
 630 if (write_arg_set.find(arg) != write_arg_set.end())
1684 ✗ throw CircuitInvalidity(
1685 "Multiple operation arguments reference " + arg.repr());
1686
1/2
✓ Branch 1 taken 315 times.
✗ Branch 2 not taken.
 630 write_arg_set.insert(arg);
1687 }
1688
1/2
✓ Branch 1 taken 315 times.
✗ Branch 2 not taken.
 630 Vertex out_vert = get_out(arg);
1689
1/2
✓ Branch 1 taken 315 times.
✗ Branch 2 not taken.
 630 Edge pred_out_e = get_nth_in_edge(out_vert, 0);
1690
1/2
✓ Branch 1 taken 315 times.
✗ Branch 2 not taken.
 630 preds.push_back(pred_out_e);
1691 }
1692
1/2
✓ Branch 1 taken 239 times.
✗ Branch 2 not taken.
 478 rewire(new_v, preds, sig);
1693 478 return new_v;
1694 }
1695
1696 } // namespace tket
1697