-
Notifications
You must be signed in to change notification settings - Fork 975
/
boolean_hamiltonian.py
353 lines (287 loc) · 14.2 KB
/
boolean_hamiltonian.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
# Copyright 2021 The Cirq Developers
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# https://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
"""Represents Boolean functions as a series of CNOT and rotation gates. The Boolean functions are
passed as Sympy expressions and then turned into an optimized set of gates.
References:
[1] On the representation of Boolean and real functions as Hamiltonians for quantum computing
by Stuart Hadfield, https://arxiv.org/pdf/1804.09130.pdf
[2] https://www.youtube.com/watch?v=AOKM9BkweVU is a useful intro
[3] https://github.com/rsln-s/IEEE_QW_2020/blob/master/Slides.pdf
[4] Efficient Quantum Circuits for Diagonal Unitaries Without Ancillas by Jonathan Welch, Daniel
Greenbaum, Sarah Mostame, and Alán Aspuru-Guzik, https://arxiv.org/abs/1306.3991
"""
import itertools
import functools
from typing import Any, Dict, Generator, List, Sequence, Tuple
import sympy.parsing.sympy_parser as sympy_parser
import cirq
from cirq import value
from cirq.ops import raw_types
from cirq.ops.linear_combinations import PauliSum, PauliString
@value.value_equality
class BooleanHamiltonian(raw_types.Operation):
"""An operation that represents a Hamiltonian from a set of Boolean functions."""
def __init__(
self,
qubit_map: Dict[str, 'cirq.Qid'],
boolean_strs: Sequence[str],
theta: float,
):
"""Builds a BooleanHamiltonian.
For each element of a sequence of Boolean expressions, the code first transforms it into a
polynomial of Pauli Zs that represent that particular expression. Then, we sum all the
polynomials, thus making a function that goes from a series to Boolean inputs to an integer
that is the number of Boolean expressions that are true.
For example, if we were using this gate for the unweighted max-cut problem that is typically
used to demonstrate the QAOA algorithm, there would be one Boolean expression per edge. Each
Boolean expression would be true iff the vertices on that are in different cuts (i.e. it's)
an XOR.
Then, we compute exp(-j * theta * polynomial), which is unitary because the polynomial is
Hermitian.
Args:
boolean_strs: The list of Sympy-parsable Boolean expressions.
qubit_map: map of string (boolean variable name) to qubit.
theta: The evolution time (angle) for the Hamiltonian
"""
self._qubit_map: Dict[str, 'cirq.Qid'] = qubit_map
self._boolean_strs: Sequence[str] = boolean_strs
self._theta: float = theta
def with_qubits(self, *new_qubits: 'cirq.Qid') -> 'BooleanHamiltonian':
if len(self._qubit_map) != len(new_qubits):
raise ValueError('Length of replacement qubits must be the same')
new_qubit_map = {
variable_name: new_qubit
for variable_name, new_qubit in zip(self._qubit_map, new_qubits)
}
return BooleanHamiltonian(
new_qubit_map,
self._boolean_strs,
self._theta,
)
@property
def qubits(self) -> Tuple[raw_types.Qid, ...]:
return tuple(self._qubit_map.values())
def num_qubits(self) -> int:
return len(self._qubit_map)
def _value_equality_values_(self):
return self._qubit_map, self._boolean_strs, self._theta
def _json_dict_(self) -> Dict[str, Any]:
return {
'cirq_type': self.__class__.__name__,
'qubit_map': self._qubit_map,
'boolean_strs': self._boolean_strs,
'theta': self._theta,
}
@classmethod
def _from_json_dict_(cls, qubit_map, boolean_strs, theta, **kwargs):
return cls(qubit_map, boolean_strs, theta)
def _decompose_(self):
boolean_exprs = [sympy_parser.parse_expr(boolean_str) for boolean_str in self._boolean_strs]
hamiltonian_polynomial_list = [
PauliSum.from_boolean_expression(boolean_expr, self._qubit_map)
for boolean_expr in boolean_exprs
]
return _get_gates_from_hamiltonians(
hamiltonian_polynomial_list, self._qubit_map, self._theta
)
def _gray_code_comparator(k1: Tuple[int, ...], k2: Tuple[int, ...], flip: bool = False) -> int:
"""Compares two Gray-encoded binary numbers.
Args:
k1: A tuple of ints, representing the bits that are one. For example, 6 would be (1, 2).
k2: The second number, represented similarly as k1.
flip: Whether to flip the comparison.
Returns:
-1 if k1 < k2 (or +1 if flip is true)
0 if k1 == k2
+1 if k1 > k2 (or -1 if flip is true)
"""
max_1 = k1[-1] if k1 else -1
max_2 = k2[-1] if k2 else -1
if max_1 != max_2:
return -1 if (max_1 < max_2) ^ flip else 1
if max_1 == -1:
return 0
return _gray_code_comparator(k1[0:-1], k2[0:-1], not flip)
def _simplify_commuting_cnots(
cnots: List[Tuple[int, int]], flip_control_and_target: bool
) -> Tuple[bool, List[Tuple[int, int]]]:
"""Attempts to commute CNOTs and remove cancelling pairs.
Commutation relations are based on 9 (flip_control_and_target=False) or 10
(flip_control_target=True) of [4]:
When flip_control_target=True:
CNOT(j, i) @ CNOT(j, k) = CNOT(j, k) @ CNOT(j, i)
───X─────── ───────X───
│ │
───@───@─── = ───@───@───
│ │
───────X─── ───X───────
When flip_control_target=False:
CNOT(i, j) @ CNOT(k, j) = CNOT(k, j) @ CNOT(i, j)
───@─────── ───────@───
│ │
───X───X─── = ───X───X───
│ │
───────@─── ───@───────
Args:
cnots: A list of CNOTS, encoded as integer tuples (control, target). The code does not make
any assumption as to the order of the CNOTs, but it is likely to work better if its
inputs are from Gray-sorted Hamiltonians. Regardless of the order of the CNOTs, the
code is conservative and should be robust to mis-ordered inputs with the only side
effect being a lack of simplification.
flip_control_and_target: Whether to flip control and target.
Returns:
A tuple containing a Boolean that tells whether a simplification has been performed and the
CNOT list, potentially simplified, encoded as integer tuples (control, target).
"""
target, control = (0, 1) if flip_control_and_target else (1, 0)
i = 0
qubit_to_index: Dict[int, int] = {cnots[i][control]: i} if cnots else {}
for j in range(1, len(cnots)):
if cnots[i][target] != cnots[j][target]:
# The targets (resp. control) don't match, so we reset the search.
i = j
qubit_to_index = {cnots[j][control]: j}
continue
if cnots[j][control] in qubit_to_index:
k = qubit_to_index[cnots[j][control]]
# The controls (resp. targets) are the same, so we can simplify away.
cnots = [cnots[n] for n in range(len(cnots)) if n != j and n != k]
# TODO(#4532): Speed up code by not returning early.
return True, cnots
qubit_to_index[cnots[j][control]] = j
return False, cnots
def _simplify_cnots_triplets(
cnots: List[Tuple[int, int]], flip_control_and_target: bool
) -> Tuple[bool, List[Tuple[int, int]]]:
"""Simplifies CNOT pairs according to equation 11 of [4].
CNOT(i, j) @ CNOT(j, k) == CNOT(j, k) @ CNOT(i, k) @ CNOT(i, j)
───@─────── ───────@───@───
│ │ │
───X───@─── = ───@───┼───X───
│ │ │
───────X─── ───X───X───────
Args:
cnots: A list of CNOTS, encoded as integer tuples (control, target).
flip_control_and_target: Whether to flip control and target.
Returns:
A tuple containing a Boolean that tells whether a simplification has been performed and the
CNOT list, potentially simplified, encoded as integer tuples (control, target).
"""
target, control = (0, 1) if flip_control_and_target else (1, 0)
# We investigate potential pivots sequentially.
for j in range(1, len(cnots) - 1):
# First, we look back for as long as the controls (resp. targets) are the same.
# They all commute, so all are potential candidates for being simplified.
# prev_match_index is qubit to index in `cnots` array.
prev_match_index: Dict[int, int] = {}
for i in range(j - 1, -1, -1):
# These CNOTs have the same target (resp. control) and though they are not candidates
# for simplification, since they commute, we can keep looking for candidates.
if cnots[i][target] == cnots[j][target]:
continue
if cnots[i][control] != cnots[j][control]:
break
# We take a note of the control (resp. target).
prev_match_index[cnots[i][target]] = i
# Next, we look forward for as long as the targets (resp. controls) are the
# same. They all commute, so all are potential candidates for being simplified.
# post_match_index is qubit to index in `cnots` array.
post_match_index: Dict[int, int] = {}
for k in range(j + 1, len(cnots)):
# These CNOTs have the same control (resp. target) and though they are not candidates
# for simplification, since they commute, we can keep looking for candidates.
if cnots[j][control] == cnots[k][control]:
continue
if cnots[j][target] != cnots[k][target]:
break
# We take a note of the target (resp. control).
post_match_index[cnots[k][control]] = k
# Among all the candidates, find if they have a match.
keys = prev_match_index.keys() & post_match_index.keys()
for key in keys:
# We perform the swap which removes the pivot.
new_idx: List[int] = (
# Anything strictly before the pivot that is not the CNOT to swap.
[idx for idx in range(0, j) if idx != prev_match_index[key]]
# The two swapped CNOTs.
+ [post_match_index[key], prev_match_index[key]]
# Anything after the pivot that is not the CNOT to swap.
+ [idx for idx in range(j + 1, len(cnots)) if idx != post_match_index[key]]
)
# Since we removed the pivot, the length should be one fewer.
cnots = [cnots[idx] for idx in new_idx]
# TODO(#4532): Speed up code by not returning early.
return True, cnots
return False, cnots
def _simplify_cnots(cnots: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
"""Takes a series of CNOTs and tries to applies rule to cancel out gates.
Algorithm based on "Efficient quantum circuits for diagonal unitaries without ancillas" by
Jonathan Welch, Daniel Greenbaum, Sarah Mostame, Alán Aspuru-Guzik
https://arxiv.org/abs/1306.3991
Args:
cnots: A list of CNOTs represented as tuples of integer (control, target).
Returns:
The simplified list of CNOTs, encoded as integer tuples (control, target).
"""
found_simplification = True
while found_simplification:
for simplify_fn, flip_control_and_target in itertools.product(
[_simplify_commuting_cnots, _simplify_cnots_triplets], [False, True]
):
found_simplification, cnots = simplify_fn(cnots, flip_control_and_target)
if found_simplification:
break
return cnots
def _get_gates_from_hamiltonians(
hamiltonian_polynomial_list: List['cirq.PauliSum'],
qubit_map: Dict[str, 'cirq.Qid'],
theta: float,
) -> Generator['cirq.Operation', None, None]:
"""Builds a circuit according to [1].
Args:
hamiltonian_polynomial_list: the list of Hamiltonians, typically built by calling
PauliSum.from_boolean_expression().
qubit_map: map of string (boolean variable name) to qubit.
theta: A single float scaling the rotations.
Yields:
Gates that are the decomposition of the Hamiltonian.
"""
combined = sum(hamiltonian_polynomial_list, PauliSum.from_pauli_strings(PauliString({})))
qubit_names = sorted(qubit_map.keys())
qubits = [qubit_map[name] for name in qubit_names]
qubit_indices = {qubit: i for i, qubit in enumerate(qubits)}
hamiltonians = {}
for pauli_string in combined:
w = pauli_string.coefficient.real
qubit_idx = tuple(sorted(qubit_indices[qubit] for qubit in pauli_string.qubits))
hamiltonians[qubit_idx] = w
def _apply_cnots(prevh: Tuple[int, ...], currh: Tuple[int, ...]):
cnots: List[Tuple[int, int]] = []
cnots.extend((prevh[i], prevh[-1]) for i in range(len(prevh) - 1))
cnots.extend((currh[i], currh[-1]) for i in range(len(currh) - 1))
cnots = _simplify_cnots(cnots)
for gate in (cirq.CNOT(qubits[c], qubits[t]) for c, t in cnots):
yield gate
sorted_hamiltonian_keys = sorted(
hamiltonians.keys(), key=functools.cmp_to_key(_gray_code_comparator)
)
previous_h: Tuple[int, ...] = ()
for h in sorted_hamiltonian_keys:
w = hamiltonians[h]
yield _apply_cnots(previous_h, h)
if len(h) >= 1:
yield cirq.Rz(rads=(theta * w)).on(qubits[h[-1]])
previous_h = h
# Flush the last CNOTs.
yield _apply_cnots(previous_h, ())