# This code is part of Qiskit.
#
# (C) Copyright IBM 2021.
#
# 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.
"""Map a DAGCircuit onto a given ``coupling_map``, allocating qubits and adding swap gates."""
import copy
import logging
import math
from qiskit.circuit import QuantumRegister
from qiskit.circuit.library.standard_gates import SwapGate
from qiskit.dagcircuit import DAGCircuit, DAGOpNode
from qiskit.utils import optionals as _optionals
from qiskit.transpiler import TransformationPass
from qiskit.transpiler.exceptions import TranspilerError
from qiskit.transpiler.passes.routing.algorithms.bip_model import BIPMappingModel
from qiskit.transpiler.target import target_to_backend_properties, Target
from qiskit.utils.deprecation import deprecate_func
from qiskit.transpiler.passes.layout import disjoint_utils
logger = logging.getLogger(__name__)
[문서]@_optionals.HAS_CPLEX.require_in_instance("BIP-based mapping pass")
@_optionals.HAS_DOCPLEX.require_in_instance("BIP-based mapping pass")
class BIPMapping(TransformationPass):
r"""Map a DAGCircuit onto a given ``coupling_map``, allocating qubits and adding swap gates.
The BIP mapper tries to find the best layout and routing at once by
solving a BIP (binary integer programming) problem as described in [1].
The BIP problem represents the layer-by-layer mapping of 2-qubit gates, assuming all the gates
in a layer can be run on the ``coupling_map``. In the problem, the variables :math:`w` represent
the layout of qubits for each layer and the variables :math:`x` represent which pair of qubits
should be swapped in between layers. Based on the values in the solution of the BIP problem,
the mapped circuit will be constructed.
The BIP mapper depends on ``docplex`` to represent the BIP problem and CPLEX (``cplex``)
to solve it. Those packages can be installed with ``pip install qiskit-terra[bip-mapper]``.
Since the free version of CPLEX can solve only small BIP problems, i.e. mapping of circuits
with less than about 5 qubits, the paid version of CPLEX may be needed to map larger circuits.
If you want to fix physical qubits to be used in the mapping (e.g. running Quantum Volume
circuits), you need to supply ``qubit_subset``, i.e. list of physical qubits to be used
within the ``coupling_map``.
Please do not use ``initial_layout`` for that purpose because the BIP mapper gracefully
ignores ``initial_layout`` (and tries to determines its best layout).
.. warning::
The BIP mapper does not scale very well with respect to the number of qubits or gates.
For example, it may not work with ``qubit_subset`` beyond 10 qubits because
the BIP solver (CPLEX) may not find any solution within the default time limit.
**References:**
[1] G. Nannicini et al. "Optimal qubit assignment and routing via integer programming."
`arXiv:2106.06446 <https://arxiv.org/abs/2106.06446>`_
"""
@deprecate_func(
since="0.24.0",
additional_msg="This has been replaced by a new transpiler plugin package: "
"qiskit-bip-mapper. More details can be found here: "
"https://github.com/qiskit-community/qiskit-bip-mapper",
) # pylint: disable=bad-docstring-quotes
def __init__(
self,
coupling_map,
qubit_subset=None,
objective="balanced",
backend_prop=None,
time_limit=30,
threads=None,
max_swaps_inbetween_layers=None,
depth_obj_weight=0.1,
default_cx_error_rate=5e-3,
):
"""BIPMapping initializer.
Args:
coupling_map (Union[CouplingMap, Target]): Directed graph represented a coupling map.
qubit_subset (list[int]): Sublist of physical qubits to be used in the mapping.
If None, all qubits in the coupling_map will be considered.
objective (str): Type of objective function to be minimized:
* ``'gate_error'``: Approximate gate error of the circuit, which is given as the sum of
negative logarithm of 2q-gate fidelities in the circuit. It takes into account only
the 2q-gate (CNOT) errors reported in ``backend_prop`` and ignores the other errors
in such as 1q-gates, SPAMs and idle times.
* ``'depth'``: Depth (number of 2q-gate layers) of the circuit.
* ``'balanced'``: [Default] Weighted sum of ``'gate_error'`` and ``'depth'``
backend_prop (BackendProperties): Backend properties object containing 2q-gate gate errors,
which are required in computing certain types of objective function
such as ``'gate_error'`` or ``'balanced'``. If this is not available,
default_cx_error_rate is used instead.
time_limit (float): Time limit for solving BIP in seconds
threads (int): Number of threads to be allowed for CPLEX to solve BIP
max_swaps_inbetween_layers (int):
Number of swaps allowed in between layers. If None, automatically set.
Large value could decrease the probability to build infeasible BIP problem but also
could reduce the chance of finding a feasible solution within the ``time_limit``.
depth_obj_weight (float):
Weight of depth objective in ``'balanced'`` objective. The balanced objective is the
sum of error_rate + depth_obj_weight * depth.
default_cx_error_rate (float):
Default CX error rate to be used if backend_prop is not available.
Raises:
MissingOptionalLibraryError: if cplex or docplex are not installed.
TranspilerError: if invalid options are specified.
"""
super().__init__()
if isinstance(coupling_map, Target):
self.target = coupling_map
self.coupling_map = self.target.build_coupling_map()
self.backend_prop = target_to_backend_properties(self.target)
else:
self.target = None
self.coupling_map = coupling_map
self.backend_prop = None
self.qubit_subset = qubit_subset
self.objective = objective
if backend_prop is not None:
self.backend_prop = backend_prop
self.time_limit = time_limit
self.threads = threads
self.max_swaps_inbetween_layers = max_swaps_inbetween_layers
self.depth_obj_weight = depth_obj_weight
self.default_cx_error_rate = default_cx_error_rate
if self.coupling_map is not None and self.qubit_subset is None:
self.qubit_subset = list(range(self.coupling_map.size()))
[문서] def run(self, dag):
"""Run the BIPMapping pass on `dag`, assuming the number of virtual qubits (defined in
`dag`) and the number of physical qubits (defined in `coupling_map`) are the same.
Args:
dag (DAGCircuit): DAG to map.
Returns:
DAGCircuit: A mapped DAG. If there is no 2q-gate in DAG or it fails to map,
returns the original dag.
Raises:
TranspilerError: if the number of virtual and physical qubits are not the same.
AssertionError: if the final layout is not valid.
"""
if self.coupling_map is None:
return dag
if len(dag.qubits) > len(self.qubit_subset):
raise TranspilerError("More virtual qubits exist than physical qubits.")
if len(dag.qubits) != len(self.qubit_subset):
raise TranspilerError(
"BIPMapping requires the number of virtual and physical qubits to be the same. "
"Supply 'qubit_subset' to specify physical qubits to use."
)
disjoint_utils.require_layout_isolated_to_component(
dag, self.coupling_map if self.target is None else self.target
)
original_dag = dag
dummy_steps = math.ceil(math.sqrt(dag.num_qubits()))
if self.max_swaps_inbetween_layers is not None:
dummy_steps = max(0, self.max_swaps_inbetween_layers - 1)
model = BIPMappingModel(
dag=dag,
coupling_map=self.coupling_map,
qubit_subset=self.qubit_subset,
dummy_timesteps=dummy_steps,
)
if len(model.su4layers) == 0:
logger.info("BIPMapping is skipped due to no 2q-gates.")
return original_dag
model.create_cpx_problem(
objective=self.objective,
backend_prop=self.backend_prop,
depth_obj_weight=self.depth_obj_weight,
default_cx_error_rate=self.default_cx_error_rate,
)
status = model.solve_cpx_problem(time_limit=self.time_limit, threads=self.threads)
if model.solution is None:
logger.warning("Failed to solve a BIP problem. Status: %s", status)
return original_dag
# Get the optimized initial layout
optimized_layout = model.get_layout(0)
# Create a layout to track changes in layout for each layer
layout = copy.deepcopy(optimized_layout)
# Construct the mapped circuit
canonical_qreg = QuantumRegister(self.coupling_map.size(), "q")
mapped_dag = self._create_empty_dagcircuit(dag, canonical_qreg)
interval = dummy_steps + 1
for k, layer in enumerate(dag.layers()):
if model.is_su4layer(k):
su4dep = model.to_su4layer_depth(k)
# add swaps between (su4dep-1)-th and su4dep-th su4layer
from_steps = max(interval * (su4dep - 1), 0)
to_steps = min(interval * su4dep, model.depth - 1)
for t in range(from_steps, to_steps): # pylint: disable=invalid-name
for (i, j) in model.get_swaps(t):
mapped_dag.apply_operation_back(
op=SwapGate(),
qargs=[canonical_qreg[i], canonical_qreg[j]],
)
# update layout, swapping physical qubits (i, j)
layout.swap(i, j)
# map gates in k-th layer
for node in layer["graph"].nodes():
if isinstance(node, DAGOpNode):
mapped_dag.apply_operation_back(
op=copy.deepcopy(node.op),
qargs=[canonical_qreg[layout[q]] for q in node.qargs],
cargs=node.cargs,
)
# TODO: double check with y values?
# Check final layout
final_layout = model.get_layout(model.depth - 1)
if layout != final_layout:
raise AssertionError(
f"Bug: final layout {final_layout} != the layout computed from swaps {layout}"
)
self.property_set["layout"] = self._to_full_layout(optimized_layout)
self.property_set["final_layout"] = self._to_full_layout(final_layout)
return mapped_dag
@staticmethod
def _create_empty_dagcircuit(source_dag: DAGCircuit, canonical_qreg: QuantumRegister):
target_dag = DAGCircuit()
target_dag.name = source_dag.name
target_dag._global_phase = source_dag._global_phase
target_dag.metadata = source_dag.metadata
target_dag.add_qreg(canonical_qreg)
for creg in source_dag.cregs.values():
target_dag.add_creg(creg)
return target_dag
def _to_full_layout(self, layout):
# fill layout with ancilla qubits (required by drawers)
idle_physical_qubits = [
q for q in range(self.coupling_map.size()) if q not in layout.get_physical_bits()
]
if idle_physical_qubits:
qreg = QuantumRegister(len(idle_physical_qubits), name="ancilla")
for idx, idle_q in enumerate(idle_physical_qubits):
layout[idle_q] = qreg[idx]
layout.add_register(qreg)
return layout