/
csp_layout.py
132 lines (109 loc) · 5.29 KB
/
csp_layout.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
# This code is part of Qiskit.
#
# (C) Copyright IBM 2019.
#
# 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.
"""A pass for choosing a Layout of a circuit onto a Coupling graph, as a
Constraint Satisfaction Problem. It tries to find a solution that fully
satisfy the circuit, i.e. no further swap is needed. If no solution is
found, no ``property_set['layout']`` is set.
"""
import random
from qiskit.transpiler.layout import Layout
from qiskit.transpiler.basepasses import AnalysisPass
from qiskit.transpiler.exceptions import TranspilerError
from qiskit.utils import optionals as _optionals
from qiskit.transpiler.target import Target
@_optionals.HAS_CONSTRAINT.require_in_instance
class CSPLayout(AnalysisPass):
"""If possible, chooses a Layout as a CSP, using backtracking."""
def __init__(
self,
coupling_map,
strict_direction=False,
seed=None,
call_limit=1000,
time_limit=10,
):
"""If possible, chooses a Layout as a CSP, using backtracking.
If not possible, does not set the layout property. In all the cases,
the property `CSPLayout_stop_reason` will be added with one of the
following values:
* solution found: If a perfect layout was found.
* nonexistent solution: If no perfect layout was found and every combination was checked.
* call limit reached: If no perfect layout was found and the call limit was reached.
* time limit reached: If no perfect layout was found and the time limit was reached.
Args:
coupling_map (Union[CouplingMap, Target]): Directed graph representing a coupling map.
strict_direction (bool): If True, considers the direction of the coupling map.
Default is False.
seed (int): Sets the seed of the PRNG.
call_limit (int): Amount of times that
``constraint.RecursiveBacktrackingSolver.recursiveBacktracking`` will be called.
None means no call limit. Default: 1000.
time_limit (int): Amount of seconds that the pass will try to find a solution.
None means no time limit. Default: 10 seconds.
"""
super().__init__()
if isinstance(coupling_map, Target):
self.target = coupling_map
self.coupling_map = self.target.build_coupling_map()
else:
self.target = None
self.coupling_map = coupling_map
self.strict_direction = strict_direction
self.call_limit = call_limit
self.time_limit = time_limit
self.seed = seed
def run(self, dag):
"""run the layout method"""
if not self.coupling_map.is_connected():
raise TranspilerError(
"Coupling Map is disjoint, this pass can't be used with a disconnected coupling "
"map."
)
qubits = dag.qubits
cxs = set()
from constraint import Problem, AllDifferentConstraint, RecursiveBacktrackingSolver
from qiskit.transpiler.passes.layout._csp_custom_solver import CustomSolver
for gate in dag.two_qubit_ops():
cxs.add((qubits.index(gate.qargs[0]), qubits.index(gate.qargs[1])))
edges = set(self.coupling_map.get_edges())
if self.time_limit is None and self.call_limit is None:
solver = RecursiveBacktrackingSolver()
else:
solver = CustomSolver(call_limit=self.call_limit, time_limit=self.time_limit)
variables = list(range(len(qubits)))
variable_domains = list(self.coupling_map.physical_qubits)
random.Random(self.seed).shuffle(variable_domains)
problem = Problem(solver)
problem.addVariables(variables, variable_domains)
problem.addConstraint(AllDifferentConstraint()) # each wire is map to a single qubit
if self.strict_direction:
def constraint(control, target):
return (control, target) in edges
else:
def constraint(control, target):
return (control, target) in edges or (target, control) in edges
for pair in cxs:
problem.addConstraint(constraint, [pair[0], pair[1]])
solution = problem.getSolution()
if solution is None:
stop_reason = "nonexistent solution"
if isinstance(solver, CustomSolver):
if solver.time_current is not None and solver.time_current >= self.time_limit:
stop_reason = "time limit reached"
elif solver.call_current is not None and solver.call_current >= self.call_limit:
stop_reason = "call limit reached"
else:
stop_reason = "solution found"
self.property_set["layout"] = Layout({v: qubits[k] for k, v in solution.items()})
for reg in dag.qregs.values():
self.property_set["layout"].add_register(reg)
self.property_set["CSPLayout_stop_reason"] = stop_reason