-
Notifications
You must be signed in to change notification settings - Fork 33
/
Copy pathtransforms.py
321 lines (268 loc) · 12.1 KB
/
transforms.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
# This code is a Qiskit project.
# (C) Copyright IBM 2023.
# This code is licensed under the Apache License, Version 2.0. You may
# obtain a copy of this license in the LICENSE.txt file in the root directory
# of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.
# Any modifications or derivative works of this code must retain this
# copyright notice, and modified files need to carry a notice indicating
# that they have been altered from the originals.
"""
Functions for manipulating quantum circuits.
.. currentmodule:: circuit_knitting.utils.transforms
.. autosummary::
:toctree: ../stubs
separate_circuit
.. autosummary::
:toctree: ../stubs
:template: autosummary/class_no_inherited_members.rst
SeparatedCircuits
"""
from __future__ import annotations
from uuid import uuid4, UUID
from collections import defaultdict
from collections.abc import Sequence, Iterable, Hashable, MutableMapping
from typing import NamedTuple, Callable
from rustworkx import PyGraph, connected_components # type: ignore[attr-defined]
from qiskit.circuit import (
QuantumCircuit,
CircuitInstruction,
QuantumRegister,
ClassicalRegister,
Barrier,
Qubit,
)
from .iteration import unique_by_eq
class SeparatedCircuits(NamedTuple):
"""Named tuple for result of :func:`separate_circuit`.
``subcircuits`` is a dict of circuits, keyed by each partition label.
``qubit_map`` is a list with length equal to the number of qubits in the original circuit.
Each element of that list is a 2-tuple which includes the partition label
of that qubit, together with the index of that qubit in the corresponding
subcircuit. If the original qubit is unused and has been removed from the separated circuits,
then that tuple will be equal to ``(None, None)``.
"""
subcircuits: dict[Hashable, QuantumCircuit]
qubit_map: list[tuple[Hashable, int] | tuple[None, None]]
def separate_circuit(
circuit: QuantumCircuit,
partition_labels: Sequence[Hashable] | None = None,
) -> SeparatedCircuits:
"""Separate the circuit into its disconnected components.
If ``partition_labels`` is provided, then the circuit will be separated
according to those labels. A partition label of ``None`` is treated specially:
it must be applied to an unused (idle) qubit, and that qubit will be removed
when separating the circuit.
If ``partition_labels`` is ``None``, then the circuit will be
fully separated into its disconnected components, each of which will be
labeled with consecutive integers starting with 0. Each idle wire
will be eliminated in the resulting circuits.
>>> qc = QuantumCircuit(4)
>>> _ = qc.x(0)
>>> _ = qc.cx(1, 2)
>>> separate_circuit(qc, "ABBA").subcircuits.keys()
dict_keys(['A', 'B'])
>>> separate_circuit(qc, "ABBA").qubit_map
[('A', 0), ('B', 0), ('B', 1), ('A', 1)]
>>> separate_circuit(qc, ["A", "B", "B", None]).qubit_map
[('A', 0), ('B', 0), ('B', 1), (None, None)]
>>> separate_circuit(qc).subcircuits.keys()
dict_keys([0, 1])
>>> separate_circuit(qc).qubit_map
[(0, 0), (1, 0), (1, 1), (None, None)]
>>> separate_circuit(qc, "BAAC").subcircuits.keys()
dict_keys(['B', 'A', 'C'])
>>> separate_circuit(qc, "BAAC").qubit_map
[('B', 0), ('A', 0), ('A', 1), ('C', 0)]
Args:
circuit: The circuit to separate into disconnected subcircuits
partition_labels: A sequence of length ``num_qubits``. Qubits with the
same label will end up in the same subcircuit.
Returns:
A :class:`SeparatedCircuits` named tuple containing the ``subcircuits``
and ``qubit_map``.
Raises:
ValueError: The number of partition labels does not equal the number of
qubits in the input circuit.
ValueError: Operation spans more than one partition.
"""
# Split barriers into single-qubit barriers before separating
new_qc = circuit.copy()
_split_barriers(new_qc)
# Generate partition labels based on the connected components of the circuit by default
if partition_labels is None:
partition_labels = _partition_labels_from_circuit(new_qc)
if len(partition_labels) != new_qc.num_qubits:
raise ValueError(
f"The number of partition_labels ({len(partition_labels)}) must equal the number of "
f"qubits in the input circuit ({new_qc.num_qubits})."
)
qubit_map, qubits_by_subsystem = _qubit_map_from_partition_labels(partition_labels)
# Gather instructions corresponding to the same partition together
subcircuit_data_ids = _separate_instructions_by_partition(new_qc, qubit_map)
# Create the subcircuits from the instruction subsets
subcircuits = {}
for label, subcircuit_data in subcircuit_data_ids.items():
tmp_data = (new_qc.data[j] for j in subcircuit_data)
tmp_circ = _circuit_from_instructions(
tmp_data,
[new_qc.qubits[j] for j in qubits_by_subsystem[label]],
new_qc.cregs,
)
_combine_barriers(tmp_circ)
subcircuits[label] = tmp_circ
return SeparatedCircuits(subcircuits, qubit_map)
def _partition_labels_from_circuit(
circuit: QuantumCircuit,
ignore: Callable[[CircuitInstruction], bool] = lambda instr: False,
*,
keep_idle_wires: bool = False,
) -> list[int | None]:
"""Generate partition labels from the connectivity of a quantum circuit."""
# Determine connectivity structure of the circuit
graph: PyGraph = PyGraph()
graph.add_nodes_from(range(circuit.num_qubits))
for instruction in circuit.data:
if ignore(instruction):
continue
qubits = instruction.qubits
for i, q1 in enumerate(qubits):
q1_id = circuit.find_bit(q1).index
for q2 in qubits[i + 1 :]:
q2_id = circuit.find_bit(q2).index
graph.add_edge(q1_id, q2_id, None)
# Find the connected subsets of qubits. For consistency, the subsets
# should be sorted in ascending order according to the lowest qubit index
# in each.
qubit_subsets = connected_components(graph)
qubit_subsets.sort(key=min)
# By default, filter qubit_subsets to remove idle wires
if not keep_idle_wires:
# Determine which qubit wires are idle/unused
idle_wires = set(range(circuit.num_qubits))
for instruction in circuit.data:
for q1 in instruction.qubits:
q1_id = circuit.find_bit(q1).index
idle_wires.discard(q1_id)
# Replace qubit_subsets with filtered list, removing idle qubits
qubit_subsets = [
subset
for subset in qubit_subsets
if not (len(subset) == 1 and next(iter(subset)) in idle_wires)
]
# Create partition labels from the connected components
partition_labels: list[int | None] = [None] * circuit.num_qubits
for i, subset in enumerate(qubit_subsets):
for qubit in subset:
partition_labels[qubit] = i
return partition_labels
def _circuit_from_instructions(
instructions: Iterable[CircuitInstruction],
qubits: Sequence[Qubit],
cregs: Iterable[ClassicalRegister],
) -> QuantumCircuit:
"""
Create a circuit from instructions.
This pipeline is designed to pass all the classical register(s) from the
uncut circuit to each subcircuit, so we add them here.
"""
circuit = QuantumCircuit()
circuit.add_register(QuantumRegister(bits=qubits))
for register in cregs:
circuit.add_register(register)
for data in instructions:
circuit.append(data)
return circuit
def _qubit_map_from_partition_labels(
partition_labels: Sequence[Hashable],
) -> tuple[list[tuple[Hashable, int] | tuple[None, None]], dict[Hashable, list[int]]]:
"""Generate a qubit map given a qubit partitioning."""
qubit_map: list[tuple[Hashable, int] | tuple[None, None]] = []
qubits_by_subsystem: MutableMapping[Hashable, list[int]] = defaultdict(list)
for i, qubit_label in enumerate(partition_labels):
if qubit_label is None:
qubit_map.append((None, None))
else:
current_label_qubits = qubits_by_subsystem[qubit_label]
qubit_map.append((qubit_label, len(current_label_qubits)))
current_label_qubits.append(i)
return qubit_map, dict(qubits_by_subsystem)
def _separate_instructions_by_partition(
circuit: QuantumCircuit,
qubit_map: Sequence[tuple[Hashable, int] | tuple[None, None]],
) -> dict[Hashable, list[int]]:
"""Generate a list of instructions for each partition of the circuit."""
unique_labels = unique_by_eq(label for label, _ in qubit_map if label is not None)
subcircuit_data_ids: dict[Hashable, list[int]] = {
label: [] for label in unique_labels
}
for i, inst in enumerate(circuit.data):
# Collect the partition labels spanned by the instruction
partitions_spanned = set()
for qubit in inst.qubits:
j = circuit.find_bit(qubit).index
partition_id = qubit_map[j][0]
if partition_id is None:
raise ValueError(
f"Operation '{inst.operation.name}' at index {i} acts on the "
f"{j}-th qubit, which was provided a partition label of `None`. "
"If the partition label of a qubit is `None`, then that qubit "
"cannot be used in the circuit."
)
partitions_spanned.add(partition_id)
# Ensure that all qubits touched by the instruction belong to the same
# partition label
if len(partitions_spanned) != 1:
assert len(partitions_spanned) != 0
raise ValueError(
"The input circuit cannot be separated along specified partitions. "
f"Operation '{inst.operation.name}' at index {i} spans more than "
"one partition."
)
# Record which partition id the current instruction is destined for
partition_id = partitions_spanned.pop()
subcircuit_data_ids[partition_id].append(i)
return subcircuit_data_ids
def _split_barriers(circuit: QuantumCircuit):
"""Mutate an input circuit to split barriers into single qubit barriers."""
for i, inst in enumerate(circuit):
num_qubits = len(inst.qubits)
if num_qubits == 1 or inst.operation.name != "barrier":
continue
barrier_uuid = uuid4()
# Replace the N-qubit barrier with a single-qubit barrier
circuit.data[i] = CircuitInstruction(
Barrier(1, label=barrier_uuid), qubits=[inst.qubits[0]]
)
# Insert the remaining single-qubit barriers directly behind the first
for j in range(1, num_qubits):
circuit.data.insert(
i + j,
CircuitInstruction(
Barrier(1, label=barrier_uuid), qubits=[inst.qubits[j]]
),
)
def _combine_barriers(circuit: QuantumCircuit):
"""Mutate input circuit to combine barriers with common UUID labels into a single barrier."""
# Gather the indices to each group of barriers with common UUID labels
uuid_map = defaultdict(list)
for i, inst in enumerate(circuit):
if (
inst.operation.name != "barrier"
or len(inst.qubits) != 1
or not isinstance(inst.operation.label, UUID)
):
continue
barrier_uuid = inst.operation.label
uuid_map[barrier_uuid].append(i)
# Replace the first single-qubit barrier in each group with the full-sized barrier
cleanup_inst = []
for barrier_indices in uuid_map.values():
qubits = [circuit.data[barrier_id].qubits[0] for barrier_id in barrier_indices]
new_barrier = CircuitInstruction(Barrier(len(barrier_indices)), qubits=qubits)
circuit.data[barrier_indices[0]] = new_barrier
# Gather indices of single-qubit barriers we need to clean up
cleanup_inst.extend(barrier_indices[1:])
# Clean up old, single-qubit barriers with uuid labels
cleanup_inst = sorted(cleanup_inst)
for shift, inst in enumerate(cleanup_inst):
del circuit.data[inst - shift]