GCC Code Coverage Report

Directory: ./
File: ZX/include/ZX/ZXDiagram.hpp
Date: 2022-10-15 05:10:18
Exec Total Coverage
Lines: 3 3 100.0%
Functions: 2 3 66.7%
Branches: 2 4 50.0%
Decisions: 0 0 -%
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 "ZX/ZXDiagramImpl.hpp"
18
19 namespace tket {
20
21 namespace zx {
22
23 // Forward declare Rewrite, ZXDiagramPybind, Flow for friend access
24 class Rewrite;
25 class ZXDiagramPybind;
26 class Flow;
27
28 class ZXDiagram {
29 private:
30 /**
31 * Underlying representation
32 */
33
34 // Underlying graph
35 std::unique_ptr<ZXGraph> graph;
36
37 /**
38 * Boundary vertices in addressable order.
39 * This may include both Quantum and Classical boundaries.
40 * Each boundary vertex can be an Input, Output, or Open (for generic
41 * undirected boundary points).
42 */
43 ZXVertVec boundary;
44
45 // Global scalar for tracking during rewrites
46 Expr scalar;
47
48 public:
49 /**
50 * Constructors & assignment operators for:
51 * - empty diagram,
52 * - empty diagram with specific input / output signatures
53 * - copy constructor
54 * - copy assignment
55 */
56 ZXDiagram();
57 ZXDiagram(
58 unsigned in, unsigned out, unsigned classical_in, unsigned classical_out);
59 ZXDiagram(const ZXDiagram& other);
60 ZXDiagram(ZXDiagram&& other);
61 ZXDiagram& operator=(const ZXDiagram& other);
62 ZXDiagram& operator=(ZXDiagram&& other);
63
64 /**
65 * Getters & Setters
66 */
67 // If `qtype` is given, then a copy of the boundary subset will be returned
68 ZXVertVec get_boundary(
69 std::optional<ZXType> type = std::nullopt,
70 std::optional<QuantumType> qtype = std::nullopt) const;
71
72 // TODO discuss whether to expose these two
73 std::unique_ptr<ZXGraph>& get_graph();
74 void add_boundary(ZXVert& vert);
75
76 // Getting the global scalar and modifying by multiplication
77 const Expr& get_scalar() const;
78 void multiply_scalar(const Expr& sc);
79
80 // Counting all vertices / wires in the diagram
81 unsigned n_vertices() const;
82 unsigned n_wires() const;
83
84 // Count number of vertices with certain types & properties
85 unsigned count_vertices(ZXType type) const;
86 unsigned count_vertices(ZXType zxtype, QuantumType qtype) const;
87 unsigned count_wires(ZXWireType type) const;
88
89 // Local properties on vertices and edges
90 unsigned degree(const ZXVert& v) const;
91 // Neighbours given in order of iteration through the underlying boost graph,
92 // which is deterministic from a given insertion order but need not be
93 // semantically relevant
94 ZXVertVec neighbours(const ZXVert& v) const;
95 // Incident wires given in order of iteration through the underlying boost
96 // graph, outedges (and self-loops) before inedges (ignoring self-loops)
97 WireVec adj_wires(const ZXVert& v) const;
98 // Wires given in the same order as `adj_wires(u)`
99 WireVec wires_between(const ZXVert& u, const ZXVert& v) const;
100
101 /**
102 * Searches for an arbitrary wire between `va` and `vb`.
103 * If none exists, then `std::nullopt` is returned.
104 * `directed` controls the search for semantically undirected edges within
105 * the underlying directed graph structure and should be called with
106 * `UNDIRECTED` unless there is good reason to not.
107 */
108 enum class WireSearchOption { UNDIRECTED, DIRECTED };
109 std::optional<Wire> wire_between(
110 const ZXVert& va, const ZXVert& vb,
111 WireSearchOption directed = WireSearchOption::UNDIRECTED) const;
112
113 Wire wire_at_port(const ZXVert& v, std::optional<unsigned> port) const;
114
115 // Getting/setting vertex properties
116 ZXGen_ptr get_vertex_ZXGen_ptr(const ZXVert& v) const;
117 template <
118 typename T, typename = typename std::enable_if<
119 std::is_base_of<ZXGen, T>::value, bool>::type>
120 const T& get_vertex_ZXGen(const ZXVert& v) const;
121 std::string get_name(const ZXVert& v) const;
122 ZXType get_zxtype(const ZXVert& v) const;
123 std::optional<QuantumType> get_qtype(const ZXVert& v) const;
124 void set_vertex_ZXGen_ptr(const ZXVert& v, const ZXGen_ptr& op);
125
126 // Getting/setting wire properies
127 WireProperties get_wire_info(const Wire& w) const;
128 QuantumType get_qtype(const Wire& w) const;
129 ZXWireType get_wire_type(const Wire& w) const;
130 ZXVert source(const Wire& w) const;
131 ZXVert target(const Wire& w) const;
132 std::optional<unsigned> source_port(const Wire& w) const;
133 std::optional<unsigned> target_port(const Wire& w) const;
134 // Returns the vertex on `w` at the other end from `u`
135 ZXVert other_end(const Wire& w, const ZXVert& u) const;
136 ZXVert vertex_at_end(const Wire& w, WireEnd we) const;
137 // Returns which end of `w` is connected to `u`
138 WireEnd end_of(const Wire& w, const ZXVert& u) const;
139 void set_wire_info(const Wire& w, const WireProperties& wp);
140 void set_wire_qtype(const Wire& w, QuantumType qtype);
141 void set_wire_type(const Wire& w, ZXWireType type);
142
143 /**
144 * Shortcut utilities to detect whether `v` is a spider with a Pauli /
145 * proper Clifford phase
146 */
147 bool is_pauli_spider(const ZXVert& v) const;
148 bool is_proper_clifford_spider(const ZXVert& v) const;
149
150 /**
151 * Check for well-formedness of the internal graph.
152 * Checks:
153 * - Inputs/Outputs have degree 1 and all exist within the boundary.
154 * - Undirected vertices have no ports on incident edges.
155 * - Directed vertices have exactly one incident edge for each port.
156 * - All incident edges to vertex have a QuantumType compatible with that
157 * port. Throws an exception if one of the checks fail. Time complexity: O(V +
158 * E), for a graph with bounded degrees.
159 */
160 void check_validity() const;
161
162 /**
163 * Symbolic manipulation
164 */
165 void symbol_substitution(const symbol_map_t& symbol_map);
166 void symbol_substitution(
167 const std::map<Sym, double, SymEngine::RCPBasicKeyLess>& symbol_map);
168 void symbol_substitution(const SymEngine::map_basic_basic& sub_map);
169
170 // Set of all free symbols occurring in operation parameters
171 SymSet free_symbols() const;
172
173 // Whether the diagram contains any symbolic parameters
174 bool is_symbolic() const;
175
176 // Whether the diagram is graphlike (ZSpiders and H edges, Basics to
177 // boundaries)
178 bool is_graphlike() const;
179
180 // Whether the diagram is MBQC (MBQC, Inputs, and Outputs, Basic to
181 // boundaries, H otherwise)
182 bool is_MBQC() const;
183
184 /**
185 * Produces graphviz string, applying `highlights` to some vertices.
186 * Inputs:
187 * highlights: set of vertices to highlight (with a red star) in the
188 * visualisation. These should be valid vertices on `graph`.
189 **/
190 std::string to_graphviz_str(const std::set<ZXVert>& highlights = {}) const;
191
192 /**
193 * Diagram manipulation
194 */
195 /**
196 * Adds a vertex with a given generator to the diagram.
197 * It is initially disconnected from any other vertex.
198 * Automatically adds boundary generators to the boundary.
199 */
200 ZXVert add_vertex(ZXGen_ptr op);
201 ZXVert add_vertex(ZXType type, QuantumType qtype = QuantumType::Quantum);
202 ZXVert add_vertex(
203 ZXType type, const Expr& param, QuantumType qtype = QuantumType::Quantum);
204
205 /**
206 * Adds a wire between `va` and `vb` by a `WireProperties` object.
207 * Uses `va` as the source and `vb` as the target in the underlying directed
208 * graph structure.
209 **/
210 Wire add_wire(const ZXVert& va, const ZXVert& vb, const WireProperties& prop);
211 /**
212 * Adds a wire of specific types between `va` -> `vb`.
213 * `va_port`, `vb_port` are used by `DirectedZXGenerator` objects
214 * to specify which port on `va`, `vb` (respectively) the wire plugs into.
215 *
216 * See `ZXGenerator.hpp` --> `DirectedZXGenerator` for more
217 * information, including the definition of the port numbers.
218 * Returns:
219 * The successfully added `Wire`.
220 **/
221 Wire add_wire(
222 const ZXVert& va, const ZXVert& vb, ZXWireType type = ZXWireType::Basic,
223 QuantumType qtype = QuantumType::Quantum,
224 std::optional<unsigned> va_port = std::nullopt,
225 std::optional<unsigned> vb_port = std::nullopt);
226
227 /**
228 * Removes the vertex `v`, along with all wires connected to it.
229 * Boundary updated if vertex is in the `boundary`.
230 **/
231 void remove_vertex(const ZXVert& v);
232 void remove_wire(const Wire& w);
233
234 /**
235 * Removes exactly 1 wire that has property `prop` from vertex `va` -> `vb`.
236 * If there exist multiple edges matching the property, they are
237 * indistinguishable, so we just remove one arbitrarily. In this case, the
238 * only difference is the edge descriptor. If the user cares about
239 * preserving particular edge descriptors, remove_wire(const Wire&) should
240 * be used.
241 * Inputs:
242 * va, vb: (ordered) vertices to remove possible wire from
243 * prop: properties to look for in the wires between the two vertices
244 * directed: whether to try also with `vb` -> `va` (i.e. when we are
245 * trying to remove edges of unknown direction)
246 * Return value indicates whether an edge was removed.
247 **/
248 bool remove_wire(
249 const ZXVert& va, const ZXVert& vb, const WireProperties& prop,
250 WireSearchOption directed = WireSearchOption::UNDIRECTED);
251
252 /**
253 * Diagram conversion
254 */
255
256 /**
257 * Expands quantum vertices into pairs of classical vertices according to
258 * the "doubling" construction for CPM.
259 * New boundary vertices are ordered lexicographically by (b, c):
260 * - b boundary index in original diagram
261 * - c conjugate identifier
262 * + quantum boundaries are mapped to a pair with original and conjugated
263 * phases
264 * + unconjugated first
265 * + classical boundaries only have the unconjugated version
266 */
267 ZXDiagram to_doubled_diagram() const;
268
269 /**
270 * Expands classical boundary vertices into quantum boundaries via input
271 * extension with a ZSpider.
272 * Effectively prepends Z basis measurements and appends Z basis
273 * initialisations for each classical bit.
274 * This is used to map the entire semantics into a single CPTP-map, which
275 * can be represented by its Choi matrix.
276 */
277 ZXDiagram to_quantum_embedding() const;
278
279 /**
280 * Subdiagram
281 *
282 * Represents a closed region of the diagram by taking a cut through a set
283 * of edges. If the subdiagram were treated as a new ZXDiagram object:
284 * - The boundary order is as given by `boundary`.
285 * - All boundary vertices are treated as Open.
286 * - Boundary vertices inherit their QuantumType from the original Wire.
287 * - Boundary edges are all Basic (i.e. the Hadamard from Hadamard
288 * wires in the `boundary` list are treated as outside of the
289 * Subdiagram).
290 * Each wire in the boundary is tagged with the WireEnd facing the interior of
291 * the subdiagram. If a wire appears with both ends, they are treated as two
292 * separate boundary wires split by an identity (Basic) or Hadamard.
293 */
294 struct Subdiagram {
295 // Ordered boundary edges of the subdiagram
296 std::vector<std::pair<Wire, WireEnd>> boundary_;
297 // All vertices within the subdiagram
298 ZXVertSeqSet verts_;
299
300 Subdiagram();
301 Subdiagram(
302 const std::vector<std::pair<Wire, WireEnd>>& cut,
303 const ZXVertSeqSet& verts);
304
305 /**
306 * Checks for well-formedness of a subdiagram.
307 * - For each wire in `boundary`, exactly one end of it is in `verts`.
308 * - For each vertex in `verts`, every incident edge is either in `boundary`
309 * or connects to another vertex in `verts`.
310 * - There are no boundary vertices in `verts`.
311 * Throws an exception if any of these fail.
312 */
313 void check_validity(const ZXDiagram& diag) const;
314
315 // Copy the Subdiagram into a new ZXDiagram object.
316 ZXDiagram to_diagram(const ZXDiagram& orig) const;
317 };
318
319 void substitute(const ZXDiagram& to_insert, const Subdiagram& to_replace);
320
321 friend Rewrite;
322 friend ZXDiagramPybind;
323 friend Flow;
324
325 private:
326 /**
327 * Copy the `other`'s graph over into this diagram (such that `other.graph`)
328 * is a subgraph of `this`'s graph.
329 * Inputs:
330 * @param other the diagram to copy into `this` one
331 * @param merge_boundaries whether to update the boundary information on
332 * `this` diagram, combining the two diagrams' boundaries together. The
333 * newly added boundary elements will preserve their original order in
334 * `other`, and appended to the end of `this`'s boundary vector.
335 * Returns the isomorphism from the `other`'s graph into its copy in
336 * `this`'s graph.
337 *
338 * Users include:
339 * - the copy assignment `operator=`,
340 * - the copy constructor
341 **/
342 std::pair<std::map<ZXVert, ZXVert>, std::map<Wire, Wire>> copy_graph(
343 const ZXDiagram& other, bool merge_boundaries = true);
344 };
345
346 template <typename T, typename>
347 340 const T& ZXDiagram::get_vertex_ZXGen(const ZXVert& v) const {
348
1/2
✓ Branch 1 taken 170 times.
✗ Branch 2 not taken.
 340 ZXGen_ptr pt = get_vertex_ZXGen_ptr(v);
349
1/2
✓ Branch 1 taken 170 times.
✗ Branch 2 not taken.
 680 return dynamic_cast<const T&>(*pt);
350 }
351
352 } // namespace zx
353
354 } // namespace tket
355