GCC Code Coverage Report

Directory: ./
File: PauliGraph/PauliGraph.cpp
Date: 2022-10-15 05:10:18
Warnings: 18 unchecked decisions!
Exec Total Coverage
Lines: 184 272 67.6%
Functions: 13 23 56.5%
Branches: 261 775 33.7%
Decisions: 48 103 46.6%
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 "PauliGraph.hpp"
16
17 #include "Gate/Gate.hpp"
18 #include "OpType/OpType.hpp"
19 #include "Utils/GraphHeaders.hpp"
20
21 namespace tket {
22
23 ✗ bool operator<(
24 const PauliGadgetProperties &pgp1, const PauliGadgetProperties &pgp2) {
25 ✗ return (pgp1.tensor_.string < pgp2.tensor_.string);
26 }
27
28 ✗ PauliGraph::PauliGraph(unsigned n) : cliff_(n) {}
29
30 52 PauliGraph::PauliGraph(const qubit_vector_t &qbs, const bit_vector_t &bits)
31
6/12
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 52 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 52 times.
✗ Branch 9 not taken.
✓ Branch 12 taken 52 times.
✗ Branch 13 not taken.
✓ Branch 15 taken 52 times.
✗ Branch 16 not taken.
✓ Branch 18 taken 52 times.
✗ Branch 19 not taken.
 52 : cliff_(qbs), bits_(bits) {}
32
33 2856 PauliVertSet PauliGraph::get_successors(const PauliVert &vert) const {
34 2856 PauliVertSet succs;
35
1/2
✓ Branch 1 taken 2856 times.
✗ Branch 2 not taken.
1/2
✓ Decision 'true' taken 2856 times.
✗ Decision 'false' not taken.
 7109 for (auto iter = boost::adjacent_vertices(vert, graph_);
36
3/4
✓ Branch 1 taken 7109 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 4253 times.
✓ Branch 4 taken 2856 times.
 7109 iter.first != iter.second; iter.first++) {
37
3/6
✓ Branch 1 taken 4253 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4253 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 4253 times.
✗ Branch 8 not taken.
 4253 succs.insert(*iter.first);
38 }
39 2856 return succs;
40 }
41
42 1939 PauliVertSet PauliGraph::get_predecessors(const PauliVert &vert) const {
43 1939 PauliVertSet preds;
44
1/2
✓ Branch 1 taken 1939 times.
✗ Branch 2 not taken.
1/2
✓ Decision 'true' taken 1939 times.
✗ Decision 'false' not taken.
 4659 for (auto iter = boost::inv_adjacent_vertices(vert, graph_);
45
3/4
✓ Branch 1 taken 4659 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 2720 times.
✓ Branch 4 taken 1939 times.
 4659 iter.first != iter.second; iter.first++) {
46
3/6
✓ Branch 1 taken 2720 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2720 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 2720 times.
✗ Branch 8 not taken.
 2720 preds.insert(*iter.first);
47 }
48 1939 return preds;
49 }
50
51 ✗ PauliEdgeSet PauliGraph::get_in_edges(const PauliVert &vert) const {
52 ✗ PauliEdgeSet ins;
53
0/1
? Decision couldn't be analyzed.
 ✗ for (auto iter = boost::in_edges(vert, graph_); iter.first != iter.second;
54 ✗ iter.first++) {
55 ✗ ins.insert(*iter.first);
56 }
57 ✗ return ins;
58 }
59
60 ✗ PauliEdgeSet PauliGraph::get_out_edges(const PauliVert &vert) const {
61 ✗ PauliEdgeSet outs;
62
0/1
? Decision couldn't be analyzed.
 ✗ for (auto iter = boost::out_edges(vert, graph_); iter.first != iter.second;
63 ✗ iter.first++) {
64 ✗ outs.insert(*iter.first);
65 }
66 ✗ return outs;
67 }
68
69 ✗ PauliVert PauliGraph::source(const PauliEdge &edge) const {
70 ✗ return boost::source(edge, graph_);
71 }
72
73 ✗ PauliVert PauliGraph::target(const PauliEdge &edge) const {
74 ✗ return boost::target(edge, graph_);
75 }
76
77 665 void PauliGraph::apply_gate_at_end(
78 const Gate &gate, const unit_vector_t &args) {
79
2/2
✓ Branch 5 taken 868 times.
✓ Branch 6 taken 664 times.
2/2
✓ Decision 'true' taken 868 times.
✓ Decision 'false' taken 664 times.
 1532 for (const UnitID &arg : args) {
80
2/2
✓ Branch 1 taken 856 times.
✓ Branch 2 taken 12 times.
2/2
✓ Decision 'true' taken 856 times.
✓ Decision 'false' taken 12 times.
 868 if (arg.type() == UnitType::Qubit) {
81
6/10
✓ Branch 1 taken 856 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 856 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 856 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 856 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 1 times.
✓ Branch 14 taken 855 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 855 times.
 856 if (measures_.left.find(Qubit(arg)) != measures_.left.end()) {
82
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 throw MidCircuitMeasurementNotAllowed(
83 "PauliGraph does not support mid-circuit measurements "
84
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 2 "- cannot add gate after measure on qubit " +
85
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 2 arg.repr());
86 }
87
5/10
✓ 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.
✓ Branch 10 taken 12 times.
✗ Branch 11 not taken.
✗ Branch 13 not taken.
✓ Branch 14 taken 12 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 12 times.
 12 } else if (measures_.right.find(Bit(arg)) != measures_.right.end()) {
88 ✗ throw MidCircuitMeasurementNotAllowed(
89 "PauliGraph does not support mid-circuit measurements - "
90 ✗ "cannot add gate after measure to bit " +
91 ✗ arg.repr());
92 }
93 }
94 664 OpType type = gate.get_type();
95
2/2
✓ Branch 0 taken 12 times.
✓ Branch 1 taken 652 times.
2/2
✓ Decision 'true' taken 12 times.
✓ Decision 'false' taken 652 times.
 664 if (type == OpType::Measure) {
96
6/12
✓ 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.
✓ Branch 10 taken 12 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 12 times.
✗ Branch 14 not taken.
✓ Branch 16 taken 12 times.
✗ Branch 17 not taken.
 12 measures_.insert({Qubit(args.at(0)), Bit(args.at(1))});
97 12 return;
98 }
99
1/2
✓ Branch 4 taken 652 times.
✗ Branch 5 not taken.
 652 qubit_vector_t qbs = {args.begin(), args.end()};
100
8/11
✓ Branch 0 taken 294 times.
✓ Branch 1 taken 131 times.
✓ Branch 2 taken 136 times.
✓ Branch 3 taken 28 times.
✓ Branch 4 taken 48 times.
✓ Branch 5 taken 9 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 5 times.
✓ Branch 8 taken 1 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 652 switch (type) {
101 294 case OpType::Z:
102 case OpType::X:
103 case OpType::Y:
104 case OpType::S:
105 case OpType::Sdg:
106 case OpType::V:
107 case OpType::Vdg:
108 case OpType::H:
109 case OpType::CX:
110 case OpType::CY:
111 case OpType::CZ:
112 case OpType::SWAP:
113 case OpType::noop:
114 case OpType::Phase: {
115
1/2
✓ Branch 1 taken 294 times.
✗ Branch 2 not taken.
 294 cliff_.apply_gate_at_end(type, qbs);
116 294 break;
117 }
118
1/1
✓ Decision 'true' taken 131 times.
 131 case OpType::Rz: {
119
2/4
✓ Branch 1 taken 131 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 131 times.
✗ Branch 5 not taken.
 131 QubitPauliTensor pauli = cliff_.get_zpauli(qbs.at(0));
120
3/6
✓ Branch 1 taken 131 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 131 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 131 times.
✗ Branch 8 not taken.
 131 Expr angle = gate.get_params().at(0);
121
1/2
✓ Branch 1 taken 131 times.
✗ Branch 2 not taken.
 131 std::optional<unsigned> cliff_angle = equiv_Clifford(angle);
122
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 131 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 131 times.
 131 if (cliff_angle) {
123
0/1
? Decision couldn't be analyzed.
 ✗ for (unsigned i = 0; i < cliff_angle.value(); i++) {
124 ✗ cliff_.apply_gate_at_end(OpType::S, qbs);
125 }
126 } else
127
1/2
✓ Branch 1 taken 131 times.
✗ Branch 2 not taken.
 131 apply_pauli_gadget_at_end(pauli, angle);
128 131 break;
129 131 }
130
1/1
✓ Decision 'true' taken 136 times.
 136 case OpType::Rx: {
131
2/4
✓ Branch 1 taken 136 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 136 times.
✗ Branch 5 not taken.
 136 QubitPauliTensor pauli = cliff_.get_xpauli(qbs.at(0));
132
3/6
✓ Branch 1 taken 136 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 136 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 136 times.
✗ Branch 8 not taken.
 136 Expr angle = gate.get_params().at(0);
133
1/2
✓ Branch 1 taken 136 times.
✗ Branch 2 not taken.
 136 std::optional<unsigned> cliff_angle = equiv_Clifford(angle);
134
2/2
✓ Branch 1 taken 96 times.
✓ Branch 2 taken 40 times.
0/1
? Decision couldn't be analyzed.
 136 if (cliff_angle) {
135
3/4
✓ Branch 1 taken 288 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 192 times.
✓ Branch 4 taken 96 times.
0/1
? Decision couldn't be analyzed.
 288 for (unsigned i = 0; i < cliff_angle.value(); i++) {
136
1/2
✓ Branch 1 taken 192 times.
✗ Branch 2 not taken.
 192 cliff_.apply_gate_at_end(OpType::V, qbs);
137 }
138 } else
139
1/2
✓ Branch 1 taken 40 times.
✗ Branch 2 not taken.
 40 apply_pauli_gadget_at_end(pauli, angle);
140 136 break;
141 136 }
142
1/1
✓ Decision 'true' taken 28 times.
 28 case OpType::Ry: {
143
3/6
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 28 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 28 times.
✗ Branch 8 not taken.
 28 Expr angle = gate.get_params().at(0);
144
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 std::optional<unsigned> cliff_angle = equiv_Clifford(angle);
145
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 28 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 28 times.
 28 if (cliff_angle) {
146
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (cliff_angle.value() != 0) {
147 ✗ cliff_.apply_gate_at_end(OpType::V, qbs);
148
0/1
? Decision couldn't be analyzed.
 ✗ for (unsigned i = 0; i < cliff_angle.value(); i++) {
149 ✗ cliff_.apply_gate_at_end(OpType::S, qbs);
150 }
151 ✗ cliff_.apply_gate_at_end(OpType::Vdg, qbs);
152 }
153 } else {
154
2/4
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 28 times.
✗ Branch 5 not taken.
 28 QubitPauliTensor zpauli = cliff_.get_zpauli(qbs.at(0));
155
2/4
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 28 times.
✗ Branch 5 not taken.
 28 QubitPauliTensor xpauli = cliff_.get_xpauli(qbs.at(0));
156
2/4
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 28 times.
✗ Branch 5 not taken.
 28 QubitPauliTensor ypauli = i_ * xpauli * zpauli;
157
1/2
✓ Branch 1 taken 28 times.
✗ Branch 2 not taken.
 28 apply_pauli_gadget_at_end(ypauli, angle);
158 28 }
159 28 break;
160 28 }
161
1/1
✓ Decision 'true' taken 48 times.
 48 case OpType::T: {
162
2/4
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 48 times.
✗ Branch 5 not taken.
 48 QubitPauliTensor pauli = cliff_.get_zpauli(qbs.at(0));
163
2/4
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 48 times.
✗ Branch 5 not taken.
 48 apply_pauli_gadget_at_end(pauli, 0.25);
164 48 break;
165 48 }
166
1/1
✓ Decision 'true' taken 9 times.
 9 case OpType::Tdg: {
167
2/4
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 9 times.
✗ Branch 5 not taken.
 9 QubitPauliTensor pauli = cliff_.get_zpauli(qbs.at(0));
168
2/4
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 9 times.
✗ Branch 5 not taken.
 9 apply_pauli_gadget_at_end(pauli, 0.25);
169 9 break;
170 9 }
171
0/1
✗ Decision 'true' not taken.
 ✗ case OpType::ZZMax: {
172 ✗ cliff_.apply_gate_at_end(OpType::H, {qbs.at(1)});
173 ✗ cliff_.apply_gate_at_end(OpType::CX, qbs);
174 ✗ cliff_.apply_gate_at_end(OpType::Sdg, {qbs.at(0)});
175 ✗ cliff_.apply_gate_at_end(OpType::S, {qbs.at(1)});
176 ✗ cliff_.apply_gate_at_end(OpType::V, {qbs.at(1)});
177 ✗ break;
178 }
179 5 case OpType::PhaseGadget:
180 case OpType::ZZPhase: {
181
3/6
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 5 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 5 times.
✗ Branch 8 not taken.
 5 Expr angle = gate.get_params().at(0);
182
1/2
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
 5 std::optional<unsigned> cliff_angle = equiv_Clifford(angle);
183
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 4 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 4 times.
 5 if (cliff_angle) {
184
2/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
0/1
? Decision couldn't be analyzed.
 1 if (cliff_angle.value() != 0) {
185
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 1 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 1 times.
 2 for (unsigned i = 1; i < qbs.size(); i++) {
186
6/12
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 1 times.
✗ Branch 14 not taken.
✓ Branch 17 taken 2 times.
✓ Branch 18 taken 1 times.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
 3 cliff_.apply_gate_at_end(OpType::CX, {qbs.at(i - 1), qbs.at(i)});
187 }
188
3/4
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1 times.
✓ Branch 4 taken 1 times.
0/1
? Decision couldn't be analyzed.
 2 for (unsigned i = 0; i < cliff_angle.value(); i++) {
189
4/8
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
✓ Branch 11 taken 1 times.
✓ Branch 12 taken 1 times.
✗ Branch 16 not taken.
✗ Branch 17 not taken.
 2 cliff_.apply_gate_at_end(OpType::S, {qbs.back()});
190 }
191
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 1 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 1 times.
 2 for (unsigned i = qbs.size() - 1; i > 0; i--) {
192
6/12
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 1 times.
✗ Branch 14 not taken.
✓ Branch 17 taken 2 times.
✓ Branch 18 taken 1 times.
✗ Branch 22 not taken.
✗ Branch 23 not taken.
 3 cliff_.apply_gate_at_end(OpType::CX, {qbs.at(i - 1), qbs.at(i)});
193 }
194 }
195 } else {
196 4 QubitPauliTensor pauli;
197
2/2
✓ Branch 4 taken 8 times.
✓ Branch 5 taken 4 times.
2/2
✓ Decision 'true' taken 8 times.
✓ Decision 'false' taken 4 times.
 12 for (const Qubit &qb : qbs) {
198
2/4
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
 8 pauli = pauli * cliff_.get_zpauli(qb);
199 }
200
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 apply_pauli_gadget_at_end(pauli, angle);
201 4 }
202 5 break;
203 5 }
204
1/1
✓ Decision 'true' taken 1 times.
 1 case OpType::XXPhase: {
205
3/6
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
 1 Expr angle = gate.get_params().at(0);
206
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 std::optional<unsigned> cliff_angle = equiv_Clifford(angle);
207
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 1 times.
 1 if (cliff_angle) {
208
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (cliff_angle.value() != 0) {
209 ✗ cliff_.apply_gate_at_end(OpType::CX, {qbs.at(1), qbs.at(0)});
210
0/1
? Decision couldn't be analyzed.
 ✗ for (unsigned i = 0; i < cliff_angle.value(); i++) {
211 ✗ cliff_.apply_gate_at_end(OpType::V, {qbs.back()});
212 }
213 ✗ cliff_.apply_gate_at_end(OpType::CX, {qbs.at(1), qbs.at(0)});
214 }
215 } else {
216 QubitPauliTensor pauli =
217
5/10
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 1 times.
✗ Branch 14 not taken.
 2 cliff_.get_xpauli(qbs.at(0)) * cliff_.get_xpauli(qbs.at(1));
218
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 apply_pauli_gadget_at_end(pauli, angle);
219 1 }
220 1 break;
221 1 }
222
0/1
✗ Decision 'true' not taken.
 ✗ case OpType::YYPhase: {
223 ✗ Expr angle = gate.get_params().at(0);
224 ✗ std::optional<unsigned> cliff_angle = equiv_Clifford(angle);
225
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (cliff_angle) {
226
0/2
✗ Decision 'true' not taken.
✗ Decision 'false' not taken.
 ✗ if (cliff_angle.value() != 0) {
227 ✗ const Qubit &arg0 = qbs.at(0);
228 ✗ const Qubit &arg1 = qbs.at(1);
229 ✗ cliff_.apply_gate_at_end(OpType::V, {arg0});
230 ✗ cliff_.apply_gate_at_end(OpType::V, {arg1});
231 ✗ cliff_.apply_gate_at_end(OpType::CX, {arg1, arg0});
232
0/1
? Decision couldn't be analyzed.
 ✗ for (unsigned i = 0; i < cliff_angle.value(); i++) {
233 ✗ cliff_.apply_gate_at_end(OpType::V, {arg1});
234 }
235 ✗ cliff_.apply_gate_at_end(OpType::CX, {arg1, arg0});
236 ✗ cliff_.apply_gate_at_end(OpType::Vdg, {arg0});
237 ✗ cliff_.apply_gate_at_end(OpType::Vdg, {arg1});
238 }
239 } else {
240 QubitPauliTensor pauli =
241 ✗ -1. * cliff_.get_xpauli(qbs.at(0)) * cliff_.get_zpauli(qbs.at(0)) *
242 ✗ cliff_.get_xpauli(qbs.at(1)) * cliff_.get_zpauli(qbs.at(1));
243 ✗ apply_pauli_gadget_at_end(pauli, angle);
244 }
245 ✗ break;
246 }
247
0/1
✗ Decision 'true' not taken.
 ✗ default: {
248 ✗ throw BadOpType("Cannot add gate to PauliGraph", type);
249 }
250 }
251 652 }
252
253 373 void PauliGraph::apply_pauli_gadget_at_end(
254 const QubitPauliTensor &pauli, const Expr &angle) {
255
1/2
✓ Branch 1 taken 373 times.
✗ Branch 2 not taken.
 373 PauliVertSet to_search = end_line_;
256
1/2
✓ Branch 1 taken 373 times.
✗ Branch 2 not taken.
 373 PauliVertSet commuted;
257
1/2
✓ Branch 1 taken 373 times.
✗ Branch 2 not taken.
 373 PauliVert new_vert = boost::add_vertex(graph_);
258
3/6
✓ Branch 1 taken 373 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 373 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 373 times.
✗ Branch 8 not taken.
 373 graph_[new_vert] = {pauli, angle};
259
2/2
✓ Branch 1 taken 2592 times.
✓ Branch 2 taken 346 times.
2/2
✓ Decision 'true' taken 2592 times.
✓ Decision 'false' taken 346 times.
 2938 while (!to_search.empty()) {
260 // Get next candidate parent
261
1/2
✓ Branch 2 taken 2592 times.
✗ Branch 3 not taken.
 2592 PauliVert to_compare = *to_search.begin();
262
1/2
✓ Branch 2 taken 2592 times.
✗ Branch 3 not taken.
 2592 to_search.erase(to_search.begin());
263
264 // Check that we have already commuted past all of its children
265 2592 bool ready = true;
266
6/10
✓ Branch 1 taken 2592 times.
✗ Branch 2 not taken.
✓ Branch 6 taken 2884 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 2024 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 4616 times.
✗ Branch 13 not taken.
✓ Branch 14 taken 2884 times.
✓ Branch 15 taken 1732 times.
0/1
? Decision couldn't be analyzed.
 4616 for (const PauliVert &child : get_successors(to_compare)) {
267
4/6
✓ Branch 4 taken 2884 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 2884 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 860 times.
✓ Branch 10 taken 2024 times.
2/2
✓ Decision 'true' taken 860 times.
✓ Decision 'false' taken 2024 times.
 2884 if (commuted.get<TagKey>().find(child) == commuted.get<TagKey>().end()) {
268 860 ready = false;
269 860 break;
270 }
271 2592 }
272
2/2
✓ Branch 0 taken 860 times.
✓ Branch 1 taken 1732 times.
2/2
✓ Decision 'true' taken 1732 times.
✓ Decision 'false' taken 860 times.
 2592 if (!ready) continue;
273
274 // Check if we can commute past it
275
2/4
✓ Branch 1 taken 1732 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1732 times.
✗ Branch 5 not taken.
 1732 QubitPauliTensor compare_pauli = graph_[to_compare].tensor_;
276
3/4
✓ Branch 1 taken 1732 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1294 times.
✓ Branch 4 taken 438 times.
2/2
✓ Decision 'true' taken 1294 times.
✓ Decision 'false' taken 438 times.
 1732 if (pauli.commutes_with(compare_pauli)) {
277
3/4
✓ Branch 1 taken 1294 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 27 times.
✓ Branch 4 taken 1267 times.
2/2
✓ Decision 'true' taken 27 times.
✓ Decision 'false' taken 1267 times.
 1294 if (pauli.string == compare_pauli.string) {
278 // Identical strings - we can merge vertices
279
1/2
✓ Branch 1 taken 27 times.
✗ Branch 2 not taken.
1/2
✓ Decision 'true' taken 27 times.
✗ Decision 'false' not taken.
 27 if (pauli.coeff == compare_pauli.coeff) {
280
2/4
✓ Branch 1 taken 27 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 27 times.
✗ Branch 5 not taken.
 27 graph_[to_compare].angle_ += angle;
281 } else {
282 ✗ graph_[to_compare].angle_ -= angle;
283 }
284
1/2
✓ Branch 1 taken 27 times.
✗ Branch 2 not taken.
 27 boost::clear_vertex(new_vert, graph_);
285
1/2
✓ Branch 1 taken 27 times.
✗ Branch 2 not taken.
 27 boost::remove_vertex(new_vert, graph_);
286
287 std::optional<unsigned> cl_ang =
288
2/4
✓ Branch 1 taken 27 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 27 times.
✗ Branch 5 not taken.
 27 equiv_Clifford(graph_[to_compare].angle_);
289
2/2
✓ Branch 1 taken 21 times.
✓ Branch 2 taken 6 times.
2/2
✓ Decision 'true' taken 21 times.
✓ Decision 'false' taken 6 times.
 27 if (cl_ang) {
290
2/4
✓ Branch 2 taken 21 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 21 times.
✗ Branch 6 not taken.
 21 cliff_.apply_pauli_at_front(graph_[to_compare].tensor_, *cl_ang);
291
1/2
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
 21 start_line_.erase(to_compare);
292
6/10
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
✓ Branch 6 taken 41 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 41 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 62 times.
✗ Branch 13 not taken.
✓ Branch 14 taken 41 times.
✓ Branch 15 taken 21 times.
0/1
? Decision couldn't be analyzed.
 62 for (const PauliVert &v : get_predecessors(to_compare)) {
293
3/4
✓ Branch 1 taken 41 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 4 times.
✓ Branch 4 taken 37 times.
2/2
✓ Decision 'true' taken 4 times.
✓ Decision 'false' taken 37 times.
 41 if (boost::out_degree(v, graph_) == 1) {
294
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 end_line_.insert(v);
295 }
296 21 }
297
1/2
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
 21 end_line_.erase(to_compare);
298
1/2
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
 21 boost::clear_vertex(to_compare, graph_);
299
1/2
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
 21 boost::remove_vertex(to_compare, graph_);
300 }
301 27 return;
302 } else {
303 // Commute and continue searching
304
1/2
✓ Branch 1 taken 1267 times.
✗ Branch 2 not taken.
 1267 PauliVertSet preds = get_predecessors(to_compare);
305
1/2
✓ Branch 3 taken 1267 times.
✗ Branch 4 not taken.
 1267 to_search.insert(preds.begin(), preds.end());
306
1/2
✓ Branch 1 taken 1267 times.
✗ Branch 2 not taken.
 1267 commuted.insert(to_compare);
307 1267 }
308 } else {
309 // Does not commute - add dependency edge
310
1/2
✓ Branch 1 taken 438 times.
✗ Branch 2 not taken.
 438 boost::add_edge(to_compare, new_vert, graph_);
311
1/2
✓ Branch 1 taken 438 times.
✗ Branch 2 not taken.
 438 end_line_.erase(to_compare);
312 }
313
2/2
✓ Branch 1 taken 1705 times.
✓ Branch 2 taken 27 times.
 1732 }
314
1/2
✓ Branch 1 taken 346 times.
✗ Branch 2 not taken.
 346 end_line_.insert(new_vert);
315
4/6
✓ Branch 1 taken 346 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 145 times.
✓ Branch 6 taken 201 times.
✓ Branch 8 taken 145 times.
✗ Branch 9 not taken.
0/1
? Decision couldn't be analyzed.
 346 if (get_predecessors(new_vert).empty()) start_line_.insert(new_vert);
316
4/4
✓ Branch 1 taken 346 times.
✓ Branch 2 taken 27 times.
✓ Branch 4 taken 346 times.
✓ Branch 5 taken 27 times.
 400 }
317
318 390 PauliGraph::TopSortIterator::TopSortIterator()
319 390 : pg_(nullptr),
320 390 current_vert_(boost::graph_traits<PauliDAG>::null_vertex()) {}
321
322 38 PauliGraph::TopSortIterator::TopSortIterator(const PauliGraph &pg) {
323
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 38 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 38 times.
 38 if (pg.start_line_.empty()) {
324 ✗ current_vert_ = boost::graph_traits<PauliDAG>::null_vertex();
325 ✗ return;
326 }
327 38 pg_ = &pg;
328
4/6
✓ Branch 3 taken 107 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 145 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 107 times.
✓ Branch 9 taken 38 times.
0/1
? Decision couldn't be analyzed.
 145 for (const PauliVert &vert : pg.start_line_) {
329
4/8
✓ Branch 1 taken 107 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 107 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 107 times.
✗ Branch 8 not taken.
✓ Branch 11 taken 107 times.
✗ Branch 12 not taken.
 107 search_set_.insert({pg.graph_[vert].tensor_, vert});
330 }
331 38 current_vert_ = search_set_.begin()->second;
332
1/2
✓ Branch 2 taken 38 times.
✗ Branch 3 not taken.
 38 search_set_.erase(search_set_.begin());
333
1/2
✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
 38 visited_ = {current_vert_};
334
5/8
✓ Branch 1 taken 38 times.
✗ Branch 2 not taken.
✓ Branch 6 taken 22 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 60 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 22 times.
✓ Branch 12 taken 38 times.
0/1
? Decision couldn't be analyzed.
 60 for (const PauliVert &child : pg_->get_successors(current_vert_)) {
335
4/8
✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 22 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 22 times.
✗ Branch 8 not taken.
✓ Branch 11 taken 22 times.
✗ Branch 12 not taken.
 22 search_set_.insert({pg.graph_[child].tensor_, child});
336 38 }
337 }
338
339 290 const PauliVert &PauliGraph::TopSortIterator::operator*() const {
340 290 return current_vert_;
341 }
342
343 ✗ const PauliVert *PauliGraph::TopSortIterator::operator->() const {
344 ✗ return &current_vert_;
345 }
346
347 352 bool PauliGraph::TopSortIterator::operator==(
348 const TopSortIterator &other) const {
349 352 return this->current_vert_ == other.current_vert_;
350 }
351
352 318 bool PauliGraph::TopSortIterator::operator!=(
353 const TopSortIterator &other) const {
354 318 return !(*this == other);
355 }
356
357 ✗ PauliGraph::TopSortIterator PauliGraph::TopSortIterator::operator++(int) {
358 ✗ PauliGraph::TopSortIterator it = *this;
359 ✗ ++*this;
360 ✗ return it;
361 }
362
363 264 PauliGraph::TopSortIterator &PauliGraph::TopSortIterator::operator++() {
364 264 bool found_next = false;
365
6/6
✓ Branch 0 taken 343 times.
✓ Branch 1 taken 226 times.
✓ Branch 3 taken 305 times.
✓ Branch 4 taken 38 times.
✓ Branch 5 taken 305 times.
✓ Branch 6 taken 264 times.
0/1
? Decision couldn't be analyzed.
 569 while (!found_next && !search_set_.empty()) {
366 305 current_vert_ = search_set_.begin()->second;
367 305 search_set_.erase(search_set_.begin());
368
369 // Check that we have visited all parents
370 305 found_next = true;
371
6/10
✓ Branch 1 taken 305 times.
✗ Branch 2 not taken.
✓ Branch 6 taken 476 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 397 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 702 times.
✗ Branch 13 not taken.
✓ Branch 14 taken 476 times.
✓ Branch 15 taken 226 times.
0/1
? Decision couldn't be analyzed.
 702 for (const PauliVert &parent : pg_->get_predecessors(current_vert_)) {
372
3/4
✓ Branch 2 taken 476 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 79 times.
✓ Branch 6 taken 397 times.
2/2
✓ Decision 'true' taken 79 times.
✓ Decision 'false' taken 397 times.
 476 if (visited_.find(parent) == visited_.end()) {
373 79 found_next = false;
374 79 break;
375 }
376 305 }
377 }
378
2/2
✓ Branch 0 taken 226 times.
✓ Branch 1 taken 38 times.
2/2
✓ Decision 'true' taken 226 times.
✓ Decision 'false' taken 38 times.
 264 if (found_next) {
379 226 visited_.insert(current_vert_);
380
5/8
✓ Branch 1 taken 226 times.
✗ Branch 2 not taken.
✓ Branch 6 taken 309 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 535 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 309 times.
✓ Branch 12 taken 226 times.
0/1
? Decision couldn't be analyzed.
 535 for (const PauliVert &child : pg_->get_successors(current_vert_)) {
381
4/8
✓ Branch 1 taken 309 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 309 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 309 times.
✗ Branch 8 not taken.
✓ Branch 11 taken 309 times.
✗ Branch 12 not taken.
 309 search_set_.insert({pg_->graph_[child].tensor_, child});
382 226 }
383 } else {
384 38 *this = TopSortIterator();
385 }
386 264 return *this;
387 }
388
389 38 PauliGraph::TopSortIterator PauliGraph::begin() const {
390 38 return TopSortIterator(*this);
391 }
392
393 352 PauliGraph::TopSortIterator PauliGraph::end() const {
394 352 return TopSortIterator();
395 }
396
397 ✗ void PauliGraph::to_graphviz_file(const std::string &filename) const {
398 ✗ std::ofstream dot_file(filename);
399 ✗ to_graphviz(dot_file);
400 }
401
402 ✗ void PauliGraph::to_graphviz(std::ostream &out) const {
403 ✗ out << "digraph G {\n";
404
405 ✗ std::map<PauliVert, unsigned> index_map;
406 ✗ unsigned i = 0;
407 ✗ BGL_FORALL_VERTICES(v, graph_, PauliDAG) {
408 ✗ index_map.insert({v, i});
409 ✗ out << i << " [label = \"" << graph_[v].tensor_.to_str() << ", "
410 ✗ << graph_[v].angle_ << "\"];\n";
411 ✗ ++i;
412 }
413
414 ✗ BGL_FORALL_EDGES(e, graph_, PauliDAG) {
415 ✗ PauliVert v_so = source(e);
416 ✗ PauliVert v_ta = target(e);
417 ✗ out << index_map.at(v_so) << " -> " << index_map.at(v_ta) << ";\n";
418 }
419
420 ✗ out << "}";
421 }
422
423 } // namespace tket
424