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 <memory> |
18 |
|
|
|
#include <optional> |
19 |
|
|
|
|
20 |
|
|
|
#include "Circuit/Circuit.hpp" |
21 |
|
|
|
#include "Gate/GatePtr.hpp" |
22 |
|
|
|
|
23 |
|
|
|
namespace tket { |
24 |
|
|
|
|
25 |
|
|
|
/** |
26 |
|
|
|
* @brief Abstract Squasher interface |
27 |
|
|
|
* |
28 |
|
|
|
* Subclasses must implement these methods to be used as a squasher |
29 |
|
|
|
* in SingleQubitSquash |
30 |
|
|
|
* |
31 |
|
|
|
* Squashers should always squash circuits into a "normal form", which is left |
32 |
|
|
|
* invariant under further squashing. This is to avoid infinite loops where |
33 |
|
|
|
* circuits would get squashed in a cycle, never reaching an equilibrium. |
34 |
|
|
|
*/ |
35 |
|
|
|
class AbstractSquasher { |
36 |
|
|
|
public: |
37 |
|
|
|
/** |
38 |
|
|
|
* @brief Whether the OpType can be added to current squash. |
39 |
|
|
|
* |
40 |
|
|
|
* @param gp Gate_ptr to be accepted. |
41 |
|
|
|
* @retval true `ot` can be squashed. |
42 |
|
|
|
* @retval false `ot` cannot be squashed. |
43 |
|
|
|
*/ |
44 |
|
|
|
virtual bool accepts(Gate_ptr gp) const = 0; |
45 |
|
|
|
|
46 |
|
|
|
/** |
47 |
|
|
|
* @brief Add gate to current squash. |
48 |
|
|
|
* |
49 |
|
|
|
* @pre `accepts(gp->get_type())` must return true |
50 |
|
|
|
* @param gp Gate to add to squash. |
51 |
|
|
|
*/ |
52 |
|
|
|
virtual void append(Gate_ptr gp) = 0; |
53 |
|
|
|
|
54 |
|
|
|
/** |
55 |
|
|
|
* @brief obtain the current squash as circuit and gate to be commuted |
56 |
|
|
|
* |
57 |
|
|
|
* Optionally use the commutation colour of the next gate to return an |
58 |
|
|
|
* additional Gate_ptr to be commuted through. |
59 |
|
|
|
* If no gate should be commuted, return nullptr. |
60 |
|
|
|
* If `commutation_colour==std::nullopt`, then the returned Gate_ptr |
61 |
|
|
|
* is expected to be `nullptr` |
62 |
|
|
|
* |
63 |
|
|
|
* @param commutation_colour |
64 |
|
|
|
* @return std::pair<Circuit, Gate_ptr> |
65 |
|
|
|
*/ |
66 |
|
|
|
virtual std::pair<Circuit, Gate_ptr> flush( |
67 |
|
|
|
std::optional<Pauli> commutation_colour) const = 0; |
68 |
|
|
|
|
69 |
|
|
|
/** |
70 |
|
|
|
* @brief Reset the current squash. |
71 |
|
|
|
*/ |
72 |
|
|
|
virtual void clear() = 0; |
73 |
|
|
|
|
74 |
|
|
|
/** |
75 |
|
|
|
* @brief Virtual constructor |
76 |
|
|
|
* |
77 |
|
|
|
* @return std::unique_ptr<AbstractSquasher> A copy of *this. |
78 |
|
|
|
*/ |
79 |
|
|
|
virtual std::unique_ptr<AbstractSquasher> clone() const = 0; |
80 |
|
|
|
|
81 |
|
|
12910 |
virtual ~AbstractSquasher() {} |
82 |
|
|
|
}; |
83 |
|
|
|
|
84 |
|
|
|
/** |
85 |
|
|
|
* @brief Squashes single qubit gates using given Squasher. |
86 |
|
|
|
*/ |
87 |
|
|
|
class SingleQubitSquash { |
88 |
|
|
|
private: |
89 |
|
|
|
using Condition = std::optional<std::pair<std::list<VertPort>, unsigned>>; |
90 |
|
|
|
|
91 |
|
|
|
public: |
92 |
|
|
|
/** |
93 |
|
|
|
* @brief Construct a new Single Qubit Squash object. |
94 |
|
|
|
* |
95 |
|
|
|
* @param squasher The Squasher instance. |
96 |
|
|
|
* @param circ The circuit to be squashed. |
97 |
|
|
|
* @param reversed Whether squashing is made back to front or front to back |
98 |
|
|
|
* (default: false, ie front to back). |
99 |
|
|
|
*/ |
100 |
|
|
✗ |
SingleQubitSquash( |
101 |
|
|
|
std::unique_ptr<AbstractSquasher> squasher, Circuit &circ, |
102 |
|
|
|
bool reversed = false) |
103 |
|
|
✗ |
: squasher_(std::move(squasher)), circ_(circ), reversed_(reversed) {} |
104 |
|
|
|
|
105 |
|
|
|
// rule of 5 |
106 |
|
|
|
SingleQubitSquash(const SingleQubitSquash &other); |
107 |
|
|
|
SingleQubitSquash &operator=(const SingleQubitSquash &other); |
108 |
|
|
✗ |
~SingleQubitSquash() = default; |
109 |
|
|
|
SingleQubitSquash(SingleQubitSquash &&other); |
110 |
|
|
|
SingleQubitSquash &operator=(SingleQubitSquash &&other); |
111 |
|
|
|
|
112 |
|
|
|
/** |
113 |
|
|
|
* @brief Squash entire circuit, one qubit at a time. |
114 |
|
|
|
* |
115 |
|
|
|
* @retval true The squash succeeded. |
116 |
|
|
|
* @retval false The circuit was not changed. |
117 |
|
|
|
*/ |
118 |
|
|
|
bool squash(); |
119 |
|
|
|
|
120 |
|
|
|
/** |
121 |
|
|
|
* @brief Squash everything between in-edge and out-edge |
122 |
|
|
|
* |
123 |
|
|
|
* If `reversed=true`, then the in-edge should come after the out-edge |
124 |
|
|
|
* in the circuit. |
125 |
|
|
|
* |
126 |
|
|
|
* @param in Starting edge of the squash. |
127 |
|
|
|
* @param out Last edge of the squash. |
128 |
|
|
|
* |
129 |
|
|
|
* @retval true The circuit was changed. |
130 |
|
|
|
* @retval false The circuit was not changed. |
131 |
|
|
|
*/ |
132 |
|
|
|
bool squash_between(const Edge &in, const Edge &out); |
133 |
|
|
|
|
134 |
|
|
|
private: |
135 |
|
|
|
std::unique_ptr<AbstractSquasher> squasher_; |
136 |
|
|
|
Circuit &circ_; |
137 |
|
|
|
bool reversed_; |
138 |
|
|
|
|
139 |
|
|
|
// substitute chain by a sub circuit, handling conditions |
140 |
|
|
|
// and backing up + restoring current edge |
141 |
|
|
|
void substitute( |
142 |
|
|
|
const Circuit &sub, const VertexVec &single_chain, Edge &e, |
143 |
|
|
|
const Condition &condition); |
144 |
|
|
|
|
145 |
|
|
|
// insert a gate at the given edge, respecting condition |
146 |
|
|
|
void insert_left_over_gate( |
147 |
|
|
|
Op_ptr left_over, const Edge &e, const Condition &condition); |
148 |
|
|
|
|
149 |
|
|
|
// whether a vertex can be squashed with the previous vertices |
150 |
|
|
|
bool is_squashable(Vertex v, OpType v_type) const; |
151 |
|
|
|
|
152 |
|
|
|
// whether the sub circuit is shorter than chain |
153 |
|
|
|
bool sub_is_better( |
154 |
|
|
|
const Circuit &sub, const std::vector<Gate_ptr> chain) const; |
155 |
|
|
|
|
156 |
|
|
|
// returns a description of the condition of current vertex |
157 |
|
|
|
Condition get_condition(Vertex v) const; |
158 |
|
|
|
|
159 |
|
|
|
// simple utils respecting reversed boolean |
160 |
|
|
|
Vertex next_vertex(const Edge &e) const; |
161 |
|
|
|
|
162 |
|
|
|
port_t next_port(const Edge &e) const; |
163 |
|
|
|
|
164 |
|
|
|
Edge prev_edge(const VertPort &pair) const; |
165 |
|
|
|
|
166 |
|
|
|
Edge next_edge(const Vertex &v, const Edge &e) const; |
167 |
|
|
|
|
168 |
|
|
|
bool is_last_optype(OpType type) const; |
169 |
|
|
|
|
170 |
|
|
|
static bool is_equal( |
171 |
|
|
|
const Circuit &circ, const std::vector<Gate_ptr> &gates, |
172 |
|
|
|
bool reversed = false); |
173 |
|
|
|
}; |
174 |
|
|
|
|
175 |
|
|
|
} // namespace tket |
176 |
|
|
|
|