GCC Code Coverage Report

Directory: ./
File: ZX/ZXRWAxioms.cpp
Date: 2022-10-15 05:10:18
Warnings: 3 unchecked decisions!
Exec Total Coverage
Lines: 122 125 97.6%
Functions: 8 8 100.0%
Branches: 161 244 66.0%
Decisions: 25 32 78.1%
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 #include "Utils/GraphHeaders.hpp"
16 #include "ZX/Rewrite.hpp"
17 #include "ZXDiagramImpl.hpp"
18
19 namespace tket {
20
21 namespace zx {
22
23 2 bool Rewrite::red_to_green_fun(ZXDiagram& diag) {
24 2 bool success = false;
25
7/8
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 47 times.
✓ Branch 7 taken 2 times.
✓ Branch 9 taken 47 times.
✓ Branch 10 taken 2 times.
✓ Branch 12 taken 2 times.
✓ Branch 13 taken 2 times.
 51 BGL_FORALL_VERTICES(v, *diag.graph, ZXGraph) {
26
3/4
✓ Branch 1 taken 47 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 38 times.
✓ Branch 4 taken 9 times.
2/2
✓ Decision 'true' taken 9 times.
✓ Decision 'false' taken 38 times.
 47 if (diag.get_zxtype(v) != ZXType::XSpider) continue;
27 // Found a match
28 9 success = true;
29 // Apply hadamards all around the spider
30
3/4
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
✓ Branch 7 taken 25 times.
✓ Branch 8 taken 9 times.
0/1
? Decision couldn't be analyzed.
 34 for (Wire& w : diag.adj_wires(v)) {
31
2/4
✓ Branch 2 taken 25 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 25 times.
✗ Branch 6 not taken.
 50 (*diag.graph)[w].type = ((*diag.graph)[w].type == ZXWireType::H)
32 25 ? ZXWireType::Basic
33 : ZXWireType::H;
34 9 }
35 // Replace X spider with Z spider
36
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 const PhasedGen& x = diag.get_vertex_ZXGen<PhasedGen>(v);
37 9 ZXGen_ptr z = std::make_shared<const PhasedGen>(
38
3/6
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 9 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 9 times.
✗ Branch 8 not taken.
 27 ZXType::ZSpider, x.get_param(), *x.get_qtype());
39
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 diag.set_vertex_ZXGen_ptr(v, z);
40 9 }
41 2 return success;
42 }
43
44
1/2
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
 2 Rewrite Rewrite::red_to_green() { return Rewrite(red_to_green_fun); }
45
46 17 bool Rewrite::spider_fusion_fun(ZXDiagram& diag) {
47 17 bool success = false;
48 17 std::set<ZXVert> bin;
49
7/8
✓ Branch 2 taken 17 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 106 times.
✓ Branch 7 taken 17 times.
✓ Branch 9 taken 106 times.
✓ Branch 10 taken 17 times.
✓ Branch 12 taken 17 times.
✓ Branch 13 taken 17 times.
 140 BGL_FORALL_VERTICES(v, *diag.graph, ZXGraph) {
50
3/4
✓ Branch 1 taken 106 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 20 times.
✓ Branch 4 taken 86 times.
2/2
✓ Decision 'true' taken 86 times.
✓ Decision 'false' taken 67 times.
 153 if (bin.contains(v)) continue;
51
1/2
✓ Branch 1 taken 86 times.
✗ Branch 2 not taken.
 86 ZXType vtype = diag.get_zxtype(v);
52
3/4
✓ Branch 1 taken 86 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 47 times.
✓ Branch 4 taken 39 times.
2/2
✓ Decision 'true' taken 39 times.
✓ Decision 'false' taken 47 times.
 86 if (!is_spider_type(vtype)) continue;
53 /**
54 * Go through neighbours and find candidates for merging.
55 * A merge candidate is either of the same colour and connected by
56 * a normal edge or of different colour and connected by a Hadamard
57 * edge
58 **/
59
1/2
✓ Branch 1 taken 39 times.
✗ Branch 2 not taken.
 39 WireVec adj_vec = diag.adj_wires(v);
60
1/2
✓ Branch 4 taken 39 times.
✗ Branch 5 not taken.
 39 std::list<Wire> adj_list{adj_vec.begin(), adj_vec.end()};
61
2/2
✓ Branch 1 taken 144 times.
✓ Branch 2 taken 39 times.
2/2
✓ Decision 'true' taken 144 times.
✓ Decision 'false' taken 39 times.
 183 while (!adj_list.empty()) {
62 144 Wire w = adj_list.front();
63 144 adj_list.pop_front();
64
1/2
✓ Branch 1 taken 144 times.
✗ Branch 2 not taken.
 144 ZXWireType wtype = diag.get_wire_type(w);
65
1/2
✓ Branch 1 taken 144 times.
✗ Branch 2 not taken.
 144 ZXVert u = diag.other_end(w, v);
66
3/4
✓ Branch 1 taken 144 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 21 times.
✓ Branch 4 taken 123 times.
2/2
✓ Decision 'true' taken 123 times.
✓ Decision 'false' taken 124 times.
 247 if (bin.contains(u)) continue;
67
1/2
✓ Branch 1 taken 123 times.
✗ Branch 2 not taken.
 123 ZXType utype = diag.get_zxtype(u);
68 123 bool same_colour = vtype == utype;
69
7/8
✓ Branch 1 taken 123 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 80 times.
✓ Branch 4 taken 43 times.
✓ Branch 5 taken 73 times.
✓ Branch 6 taken 7 times.
✓ Branch 7 taken 103 times.
✓ Branch 8 taken 20 times.
2/2
✓ Decision 'true' taken 103 times.
✓ Decision 'false' taken 93 times.
 196 if (!is_spider_type(utype) || u == v ||
70
2/2
✓ Branch 0 taken 53 times.
✓ Branch 1 taken 20 times.
 73 (wtype == ZXWireType::Basic) != same_colour)
71 103 continue;
72 // The spiders `u` and `v` can be fused together
73 // We merge into `v` and remove `u` so that we can efficiently continue to
74 // search the neighbours
75
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 const PhasedGen& vspid = diag.get_vertex_ZXGen<PhasedGen>(v);
76
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 const PhasedGen& uspid = diag.get_vertex_ZXGen<PhasedGen>(u);
77
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 40 ZXGen_ptr new_spid = std::make_shared<const PhasedGen>(
78
2/4
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 20 times.
✗ Branch 5 not taken.
 40 vtype, vspid.get_param() + uspid.get_param(),
79
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 19 times.
 40 (vspid.get_qtype() == QuantumType::Classical ||
80
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 40 uspid.get_qtype() == QuantumType::Classical)
81
3/6
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 20 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 20 times.
✗ Branch 8 not taken.
 60 ? QuantumType::Classical
82 20 : QuantumType::Quantum);
83
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 diag.set_vertex_ZXGen_ptr(v, new_spid);
84
3/4
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 61 times.
✓ Branch 9 taken 20 times.
0/1
? Decision couldn't be analyzed.
 81 for (const Wire& uw : diag.adj_wires(u)) {
85
1/2
✓ Branch 1 taken 61 times.
✗ Branch 2 not taken.
 61 WireEnd u_end = diag.end_of(uw, u);
86
1/2
✓ Branch 1 taken 61 times.
✗ Branch 2 not taken.
 61 ZXVert other = diag.other_end(uw, u);
87
1/2
✓ Branch 1 taken 61 times.
✗ Branch 2 not taken.
 61 WireProperties uwp = diag.get_wire_info(uw);
88 // Wires may need flipping type to match colours
89
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 49 times.
2/2
✓ Decision 'true' taken 12 times.
✓ Decision 'false' taken 49 times.
 61 if (!same_colour)
90
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 4 times.
 12 uwp.type = (uwp.type == ZXWireType::Basic) ? ZXWireType::H
91 : ZXWireType::Basic;
92 /**
93 * Basic edges between `(u, v)` will be ignored (these will be
94 * contracted); H edges will become self loops on `v`
95 **/
96
4/4
✓ Branch 0 taken 27 times.
✓ Branch 1 taken 34 times.
✓ Branch 2 taken 20 times.
✓ Branch 3 taken 7 times.
2/2
✓ Decision 'true' taken 41 times.
✓ Decision 'false' taken 20 times.
 61 if (other == v && uwp.type == ZXWireType::Basic) continue;
97 // Self loops on `u` needs to become self loops on `v`
98
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 41 times.
1/2
✓ Decision 'true' taken 41 times.
✗ Decision 'false' not taken.
 41 if (other == u) other = v;
99 // Connect edge to `v` instead with the same properties.
100
1/2
✓ Branch 1 taken 41 times.
✗ Branch 2 not taken.
 41 Wire new_w;
101
2/2
✓ Branch 0 taken 26 times.
✓ Branch 1 taken 15 times.
2/2
✓ Decision 'true' taken 26 times.
✓ Decision 'false' taken 15 times.
 41 if (u_end == WireEnd::Source)
102
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 new_w = diag.add_wire(v, other, uwp);
103 else
104
1/2
✓ Branch 1 taken 15 times.
✗ Branch 2 not taken.
 15 new_w = diag.add_wire(other, v, uwp);
105 // Iteratively fuse along new wire if possible
106
1/2
✓ Branch 1 taken 41 times.
✗ Branch 2 not taken.
 41 adj_list.push_back(new_w);
107 20 }
108 // Remove `u`
109
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 bin.insert(u);
110 20 success = true;
111 20 }
112 39 }
113
2/2
✓ Branch 5 taken 20 times.
✓ Branch 6 taken 17 times.
2/2
✓ Decision 'true' taken 20 times.
✓ Decision 'false' taken 17 times.
 37 for (ZXVert u : bin) {
114
1/2
✓ Branch 1 taken 20 times.
✗ Branch 2 not taken.
 20 diag.remove_vertex(u);
115 }
116 17 return success;
117 17 }
118
119
1/2
✓ Branch 2 taken 9 times.
✗ Branch 3 not taken.
 9 Rewrite Rewrite::spider_fusion() { return Rewrite(spider_fusion_fun); }
120
121 18 bool Rewrite::self_loop_removal_fun(ZXDiagram& diag) {
122 18 bool success = false;
123
7/8
✓ Branch 2 taken 18 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 67 times.
✓ Branch 7 taken 18 times.
✓ Branch 9 taken 67 times.
✓ Branch 10 taken 18 times.
✓ Branch 12 taken 18 times.
✓ Branch 13 taken 18 times.
 103 BGL_FORALL_VERTICES(v, *diag.graph, ZXGraph) {
124
1/2
✓ Branch 1 taken 67 times.
✗ Branch 2 not taken.
 67 ZXType vtype = diag.get_zxtype(v);
125
3/4
✓ Branch 1 taken 67 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 34 times.
✓ Branch 4 taken 33 times.
2/2
✓ Decision 'true' taken 33 times.
✓ Decision 'false' taken 34 times.
 67 if (!is_spider_type(vtype)) continue;
126 33 unsigned n_pis = 0;
127
1/2
✓ Branch 1 taken 33 times.
✗ Branch 2 not taken.
 33 QuantumType vqtype = *diag.get_qtype(v);
128
3/4
✓ Branch 1 taken 33 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 103 times.
✓ Branch 9 taken 33 times.
0/1
? Decision couldn't be analyzed.
 136 for (const Wire& w : diag.adj_wires(v)) {
129
3/4
✓ Branch 1 taken 103 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 86 times.
✓ Branch 4 taken 17 times.
2/2
✓ Decision 'true' taken 17 times.
✓ Decision 'false' taken 86 times.
 103 if (diag.other_end(w, v) != v) continue;
130 // Found a self-loop
131
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 ZXWireType wtype = diag.get_wire_type(w);
132
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 QuantumType wqtype = diag.get_qtype(w);
133 /**
134 * Consider each case of quantumness:
135 * - vqtype is Quantum
136 * + wqtype must be Quantum so Hadamards add phase
137 * - vqtype is Classical
138 * + wqtype is Classical so each loop is 1 Hadamard
139 * + wqtype is Quantum so each loop is 2 Hadamards, cancelling out
140 **/
141
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 17 if ((vqtype == QuantumType::Quantum ||
142
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 5 times.
 17 wqtype == QuantumType::Classical) &&
143 wtype == ZXWireType::H)
144 12 ++n_pis;
145
1/2
✓ Branch 1 taken 17 times.
✗ Branch 2 not taken.
 17 diag.remove_wire(w);
146 17 success = true;
147 33 }
148
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 21 times.
 33 if ((n_pis % 2) == 1) {
149
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 const PhasedGen& spid = diag.get_vertex_ZXGen<PhasedGen>(v);
150
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 24 ZXGen_ptr new_spid = std::make_shared<const PhasedGen>(
151
3/6
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 12 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 12 times.
✗ Branch 8 not taken.
 36 vtype, spid.get_param() + 1., vqtype);
152
1/2
✓ Branch 1 taken 12 times.
✗ Branch 2 not taken.
 12 diag.set_vertex_ZXGen_ptr(v, new_spid);
153 12 }
154 }
155 18 return success;
156 }
157
158
1/2
✓ Branch 2 taken 8 times.
✗ Branch 3 not taken.
 8 Rewrite Rewrite::self_loop_removal() { return Rewrite(self_loop_removal_fun); }
159
160 6 bool Rewrite::parallel_h_removal_fun(ZXDiagram& diag) {
161 6 bool success = false;
162
7/8
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 69 times.
✓ Branch 7 taken 6 times.
✓ Branch 9 taken 69 times.
✓ Branch 10 taken 6 times.
✓ Branch 12 taken 6 times.
✓ Branch 13 taken 6 times.
 81 BGL_FORALL_VERTICES(v, *diag.graph, ZXGraph) {
163
1/2
✓ Branch 1 taken 69 times.
✗ Branch 2 not taken.
 69 ZXType vtype = diag.get_zxtype(v);
164
3/4
✓ Branch 1 taken 69 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 31 times.
✓ Branch 4 taken 38 times.
 69 if (!is_spider_type(vtype)) continue;
165
1/2
✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
 38 QuantumType vqtype = *diag.get_qtype(v);
166 38 std::map<ZXVert, Wire> h_wires;
167
3/4
✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 105 times.
✓ Branch 9 taken 38 times.
 143 for (const Wire& w : diag.adj_wires(v)) {
168
1/2
✓ Branch 1 taken 105 times.
✗ Branch 2 not taken.
 105 ZXWireType wtype = diag.get_wire_type(w);
169
1/2
✓ Branch 1 taken 105 times.
✗ Branch 2 not taken.
 105 ZXVert u = diag.other_end(w, v);
170
1/2
✓ Branch 1 taken 105 times.
✗ Branch 2 not taken.
 105 ZXType utype = diag.get_zxtype(u);
171
3/4
✓ Branch 1 taken 105 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 27 times.
✓ Branch 4 taken 78 times.
 107 if (!is_spider_type(utype)) continue;
172
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 76 times.
 78 if ((wtype == ZXWireType::H) != (utype == vtype)) continue;
173 // This is (effectively) a Hadamard edge
174
1/2
✓ Branch 1 taken 76 times.
✗ Branch 2 not taken.
 76 QuantumType uqtype = *diag.get_qtype(u);
175
1/2
✓ Branch 1 taken 76 times.
✗ Branch 2 not taken.
 76 QuantumType wqtype = diag.get_qtype(w);
176
3/4
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 74 times.
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
 76 if (vqtype == QuantumType::Classical &&
177
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
 2 uqtype == QuantumType::Classical && wqtype == QuantumType::Quantum) {
178 // Doubled wire forms a pair
179 ✗ diag.remove_wire(w);
180 ✗ success = true;
181 ✗ continue;
182 }
183 // Look for another wire to pair it with
184
1/2
✓ Branch 2 taken 76 times.
✗ Branch 3 not taken.
 76 auto added = h_wires.insert({u, w});
185
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 73 times.
 76 if (!added.second) {
186 // Already found the other of the pair, so remove both
187 3 Wire other_w = added.first->second;
188
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 h_wires.erase(added.first);
189
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 diag.remove_wire(w);
190
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 diag.remove_wire(other_w);
191 3 success = true;
192 }
193 38 }
194 38 }
195 6 return success;
196 }
197
198 6 Rewrite Rewrite::parallel_h_removal() {
199
1/2
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
 6 return Rewrite(parallel_h_removal_fun);
200 }
201
202 } // namespace zx
203
204 } // namespace tket
205