5648658767

pending completion

Build # 5648658767

Build Type

push

github

Committed by

web-flow

Commit Message

Convert additional bit_indices to dag.find_bit in transpiler passes (#10463) (#10481)

* Use dag find_bit in additional places

* Fix dag viz

* Lint

* More lint and cleanup

(cherry picked from commit d02a25475)

Co-authored-by: Edwin Navarro <enavarro@comcast.net>

Run Details

41 of 41 new or added lines in 11 files covered. (100.0%)

72886 of 84826 relevant lines covered (85.92%)

60107.61 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

16.96

/qiskit/transpiler/passes/routing/algorithms/bip_model.py

# 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.
"""Integer programming model for quantum circuit compilation."""
import copy
import logging
from functools import lru_cache

import numpy as np

from qiskit.transpiler.exceptions import TranspilerError, CouplingError
from qiskit.transpiler.layout import Layout
from qiskit.circuit.library.standard_gates import SwapGate
from qiskit.providers.models import BackendProperties
from qiskit.quantum_info import two_qubit_cnot_decompose
from qiskit.quantum_info.synthesis.two_qubit_decompose import (
    TwoQubitWeylDecomposition,
    trace_to_fid,
)
from qiskit.utils import optionals as _optionals
from qiskit.utils.deprecation import deprecate_func

logger = logging.getLogger(__name__)


@_optionals.HAS_DOCPLEX.require_in_instance
class BIPMappingModel:
    """Internal model to create and solve a BIP problem for mapping.

    Attributes:
        problem (Model):
            A CPLEX problem model object, which is set by calling
            :method:`create_cpx_problem`. After calling :method:`solve_cpx_problem`,
            the solution will be stored in :attr:`solution`). None if it's not yet set.
    """

    @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, dag, coupling_map, qubit_subset, dummy_timesteps=None):
        """
        Args:
            dag (DAGCircuit): DAG circuit to be mapped
            coupling_map (CouplingMap): Coupling map of the device on which the `dag` is mapped.
            qubit_subset (list[int]): Sublist of physical qubits to be used in the mapping.
            dummy_timesteps (int):
                Number of dummy time steps, after each real layer of gates, to
                allow arbitrary swaps between neighbors.

        Raises:
            MissingOptionalLibraryError: If docplex is not installed
            TranspilerError: If size of virtual qubits and physical qubits differ, or
                if coupling_map is not symmetric (bidirectional).
        """

        self._dag = dag
        self._coupling = copy.deepcopy(coupling_map)  # reduced coupling map
        try:
            self._coupling = self._coupling.reduce(qubit_subset)
        except CouplingError as err:
            raise TranspilerError(
                "The 'coupling_map' reduced by 'qubit_subset' must be connected."
            ) from err
        self._coupling.make_symmetric()
        self.global_qubit = qubit_subset  # the map from reduced qubit index to global qubit index

        self.problem = None
        self.solution = None
        self.num_vqubits = len(self._dag.qubits)
        self.num_pqubits = self._coupling.size()
        self._arcs = self._coupling.get_edges()

        if self.num_vqubits != self.num_pqubits:
            raise TranspilerError(
                "BIPMappingModel assumes the same size of virtual and physical qubits."
            )

        self._index_to_virtual = dict(enumerate(dag.qubits))

        # Construct internal circuit model
        # Extract layers with 2-qubit gates
        self._to_su4layer = []
        self.su4layers = []
        for lay in dag.layers():
            laygates = []
            for node in lay["graph"].two_qubit_ops():
                i1 = self._dag.find_bit(node.qargs[0]).index
                i2 = self._dag.find_bit(node.qargs[1]).index
                laygates.append(((i1, i2), node))
            if laygates:
                self._to_su4layer.append(len(self.su4layers))
                self.su4layers.append(laygates)
            else:
                self._to_su4layer.append(-1)
        # Add dummy time steps inbetween su4layers. Dummy time steps can only contain SWAPs.
        self.gates = []  # layered 2q-gates with dummy steps
        for k, lay in enumerate(self.su4layers):
            self.gates.append(lay)
            if k == len(self.su4layers) - 1:  # do not add dummy steps after the last layer
                break
            self.gates.extend([[]] * dummy_timesteps)

        self.bprop = None  # Backend properties to compute cx fidelities (set later if necessary)
        self.default_cx_error_rate = (
            None  # Default cx error rate in case backend properties are not available
        )

        logger.info("Num virtual qubits: %d", self.num_vqubits)
        logger.info("Num physical qubits: %d", self.num_pqubits)
        logger.info("Model depth: %d", self.depth)
        logger.info("Dummy steps: %d", dummy_timesteps)

    @property
    def depth(self):
        """Number of time-steps (including dummy steps)."""
        return len(self.gates)

    def is_su4layer(self, depth: int) -> bool:
        """Check if the depth-th layer is su4layer (layer containing 2q-gates) or not.

        Args:
            depth: Depth of the ordinary layer

        Returns:
            True if the depth-th layer is su4layer, otherwise False
        """
        return self._to_su4layer[depth] >= 0

    def to_su4layer_depth(self, depth: int) -> int:
        """Return the depth as a su4layer. If the depth-th layer is not a su4layer, return -1.

        Args:
            depth: Depth of the ordinary layer

        Returns:
            su4layer depth if the depth-th layer is a su4layer, otherwise -1
        """
        return self._to_su4layer[depth]

    # pylint: disable=invalid-name
    def _is_dummy_step(self, t: int):
        """Check if the time-step t is a dummy step or not."""
        return len(self.gates[t]) == 0

    @_optionals.HAS_DOCPLEX.require_in_call
    def create_cpx_problem(
        self,
        objective: str,
        backend_prop: BackendProperties = None,
        line_symm: bool = False,
        depth_obj_weight: float = 0.1,
        default_cx_error_rate: float = 5e-3,
    ):
        """Create integer programming model to compile a circuit.

        Args:
            objective:
                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 CNOT gate fidelities in the circuit. It takes into account
                    only the CNOT gate errors reported in ``backend_prop``.
                * ``'depth'``: Depth (number of timesteps) of the circuit
                * ``'balanced'``: Weighted sum of gate_error and depth

            backend_prop:
                Backend properties storing 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.

            line_symm:
                Use symmetry breaking constrainst for line topology. Should
                only be True if the hardware graph is a chain/line/path.

            depth_obj_weight:
                Weight of depth objective in ``'balanced'`` objective function.

            default_cx_error_rate:
                Default CX error rate to be used if backend_prop is not available.

        Raises:
            TranspilerError: if unknown objective type is specified or invalid options are specified.
            MissingOptionalLibraryError: If docplex is not installed
        """
        self.bprop = backend_prop
        self.default_cx_error_rate = default_cx_error_rate
        if self.bprop is None and self.default_cx_error_rate is None:
            raise TranspilerError("BackendProperties or default_cx_error_rate must be specified")
        from docplex.mp.model import Model

        mdl = Model()

        # *** Define main variables ***
        # Add w variables
        w = {}
        for t in range(self.depth):
            for q in range(self.num_vqubits):
                for j in range(self.num_pqubits):
                    w[t, q, j] = mdl.binary_var(name=f"w_{t}_{q}_{j}")
        # Add y variables
        y = {}
        for t in range(self.depth):
            for ((p, q), _) in self.gates[t]:
                for (i, j) in self._arcs:
                    y[t, p, q, i, j] = mdl.binary_var(name=f"y_{t}_{p}_{q}_{i}_{j}")
        # Add x variables
        x = {}
        for t in range(self.depth - 1):
            for q in range(self.num_vqubits):
                for i in range(self.num_pqubits):
                    x[t, q, i, i] = mdl.binary_var(name=f"x_{t}_{q}_{i}_{i}")
                    for j in self._coupling.neighbors(i):
                        x[t, q, i, j] = mdl.binary_var(name=f"x_{t}_{q}_{i}_{j}")

        # *** Define main constraints ***
        # Assignment constraints for w variables
        for t in range(self.depth):
            for q in range(self.num_vqubits):
                mdl.add_constraint(
                    sum(w[t, q, j] for j in range(self.num_pqubits)) == 1,
                    ctname=f"assignment_vqubits_{q}_at_{t}",
                )
        for t in range(self.depth):
            for j in range(self.num_pqubits):
                mdl.add_constraint(
                    sum(w[t, q, j] for q in range(self.num_vqubits)) == 1,
                    ctname=f"assignment_pqubits_{j}_at_{t}",
                )
        # Each gate must be implemented
        for t in range(self.depth):
            for ((p, q), _) in self.gates[t]:
                mdl.add_constraint(
                    sum(y[t, p, q, i, j] for (i, j) in self._arcs) == 1,
                    ctname=f"implement_gate_{p}_{q}_at_{t}",
                )
        # Gate can be implemented iff both of its qubits are located at the associated nodes
        for t in range(self.depth - 1):
            for ((p, q), _) in self.gates[t]:
                for (i, j) in self._arcs:
                    # Apply McCormick to y[t, p, q, i, j] == w[t, p, i] * w[t, q, j]
                    mdl.add_constraint(
                        y[t, p, q, i, j] >= w[t, p, i] + w[t, q, j] - 1,
                        ctname=f"McCormickLB_{p}_{q}_{i}_{j}_at_{t}",
                    )
                    # Stronger version of McCormick: gate (p,q) is implemented at (i, j)
                    # if i moves to i or j, and j moves to i or j
                    mdl.add_constraint(
                        y[t, p, q, i, j] <= x[t, p, i, i] + x[t, p, i, j],
                        ctname=f"McCormickUB1_{p}_{q}_{i}_{j}_at_{t}",
                    )
                    mdl.add_constraint(
                        y[t, p, q, i, j] <= x[t, q, j, i] + x[t, q, j, j],
                        ctname=f"McCormickUB2_{p}_{q}_{i}_{j}_at_{t}",
                    )
        # For last time step, use regular McCormick
        for ((p, q), _) in self.gates[self.depth - 1]:
            for (i, j) in self._arcs:
                # Apply McCormick to y[self.depth - 1, p, q, i, j]
                # == w[self.depth - 1, p, i] * w[self.depth - 1, q, j]
                mdl.add_constraint(
                    y[self.depth - 1, p, q, i, j]
                    >= w[self.depth - 1, p, i] + w[self.depth - 1, q, j] - 1,
                    ctname=f"McCormickLB_{p}_{q}_{i}_{j}_at_last",
                )
                mdl.add_constraint(
                    y[self.depth - 1, p, q, i, j] <= w[self.depth - 1, p, i],
                    ctname=f"McCormickUB1_{p}_{q}_{i}_{j}_at_last",
                )
                mdl.add_constraint(
                    y[self.depth - 1, p, q, i, j] <= w[self.depth - 1, q, j],
                    ctname=f"McCormickUB2_{p}_{q}_{i}_{j}_at_last",
                )
        # Logical qubit flow-out constraints
        for t in range(self.depth - 1):  # Flow out; skip last time step
            for q in range(self.num_vqubits):
                for i in range(self.num_pqubits):
                    mdl.add_constraint(
                        w[t, q, i]
                        == x[t, q, i, i] + sum(x[t, q, i, j] for j in self._coupling.neighbors(i)),
                        ctname=f"flow_out_{q}_{i}_at_{t}",
                    )
        # Logical qubit flow-in constraints
        for t in range(1, self.depth):  # Flow in; skip first time step
            for q in range(self.num_vqubits):
                for i in range(self.num_pqubits):
                    mdl.add_constraint(
                        w[t, q, i]
                        == x[t - 1, q, i, i]
                        + sum(x[t - 1, q, j, i] for j in self._coupling.neighbors(i)),
                        ctname=f"flow_in_{q}_{i}_at_{t}",
                    )
        # If a gate is implemented, involved qubits cannot swap with other positions
        for t in range(self.depth - 1):
            for ((p, q), _) in self.gates[t]:
                for (i, j) in self._arcs:
                    mdl.add_constraint(
                        x[t, p, i, j] == x[t, q, j, i], ctname=f"swap_{p}_{q}_{i}_{j}_at_{t}"
                    )
        # Qubit not in gates can flip with their neighbors
        for t in range(self.depth - 1):
            q_no_gate = list(range(self.num_vqubits))
            for ((p, q), _) in self.gates[t]:
                q_no_gate.remove(p)
                q_no_gate.remove(q)
            for (i, j) in self._arcs:
                mdl.add_constraint(
                    sum(x[t, q, i, j] for q in q_no_gate) == sum(x[t, p, j, i] for p in q_no_gate),
                    ctname=f"swap_no_gate_{i}_{j}_at_{t}",
                )

        # *** Define supplemental variables ***
        # Add z variables to count dummy steps (supplemental variables for symmetry breaking)
        z = {}
        for t in range(self.depth):
            if self._is_dummy_step(t):
                z[t] = mdl.binary_var(name=f"z_{t}")

        # *** Define supplemental constraints ***
        # See if a dummy time step is needed
        for t in range(self.depth):
            if self._is_dummy_step(t):
                for q in range(self.num_vqubits):
                    mdl.add_constraint(
                        sum(x[t, q, i, j] for (i, j) in self._arcs) <= z[t],
                        ctname=f"dummy_ts_needed_for_vqubit_{q}_at_{t}",
                    )
        # Symmetry breaking between dummy time steps
        for t in range(self.depth - 1):
            # This is a dummy time step and the next one is dummy too
            if self._is_dummy_step(t) and self._is_dummy_step(t + 1):
                # We cannot use the next time step unless this one is used too
                mdl.add_constraint(z[t] >= z[t + 1], ctname=f"dummy_precedence_{t}")
        # Symmetry breaking on the line -- only works on line topology!
        if line_symm:
            for h in range(1, self.num_vqubits):
                mdl.add_constraint(
                    sum(w[0, p, 0] for p in range(h))
                    + sum(w[0, q, self.num_pqubits - 1] for q in range(h, self.num_vqubits))
                    >= 1,
                    ctname=f"sym_break_line_{h}",
                )

        # *** Define objevtive function ***
        if objective == "depth":
            objexr = sum(z[t] for t in range(self.depth) if self._is_dummy_step(t))
            for t in range(self.depth - 1):
                for q in range(self.num_vqubits):
                    for (i, j) in self._arcs:
                        objexr += 0.01 * x[t, q, i, j]
            mdl.minimize(objexr)
        elif objective in ("gate_error", "balanced"):
            # We add the depth objective with coefficient depth_obj_weight if balanced was selected.
            objexr = 0
            for t in range(self.depth - 1):
                for (p, q), node in self.gates[t]:
                    for (i, j) in self._arcs:
                        # We pay the cost for gate implementation.
                        pbest_fid = -np.log(self._max_expected_fidelity(node, i, j))
                        objexr += y[t, p, q, i, j] * pbest_fid
                        # If a gate is mirrored (followed by a swap on the same qubit pair),
                        # its cost should be replaced with the cost of the combined (mirrored) gate.
                        pbest_fidm = -np.log(self._max_expected_mirrored_fidelity(node, i, j))
                        objexr += x[t, q, i, j] * (pbest_fidm - pbest_fid) / 2
                # Cost of swaps on unused qubits
                for q in range(self.num_vqubits):
                    used_qubits = {q for (pair, _) in self.gates[t] for q in pair}
                    if q not in used_qubits:
                        for i in range(self.num_pqubits):
                            for j in self._coupling.neighbors(i):
                                objexr += x[t, q, i, j] * -3 / 2 * np.log(self._cx_fidelity(i, j))
            # Cost for the last layer (x variables are not defined for depth-1)
            for (p, q), node in self.gates[self.depth - 1]:
                for (i, j) in self._arcs:
                    pbest_fid = -np.log(self._max_expected_fidelity(node, i, j))
                    objexr += y[self.depth - 1, p, q, i, j] * pbest_fid
            if objective == "balanced":
                objexr += depth_obj_weight * sum(
                    z[t] for t in range(self.depth) if self._is_dummy_step(t)
                )
            mdl.minimize(objexr)
        else:
            raise TranspilerError(f"Unknown objective type: {objective}")

        self.problem = mdl
        logger.info("BIP problem stats: %s", self.problem.statistics)

    def _max_expected_fidelity(self, node, i, j):
        return max(
            gfid * self._cx_fidelity(i, j) ** k
            for k, gfid in enumerate(self._gate_fidelities(node))
        )

    def _max_expected_mirrored_fidelity(self, node, i, j):
        return max(
            gfid * self._cx_fidelity(i, j) ** k
            for k, gfid in enumerate(self._mirrored_gate_fidelities(node))
        )

    def _cx_fidelity(self, i, j) -> float:
        # fidelity of cx on global physical qubits
        if self.bprop is not None:
            return 1.0 - self.bprop.gate_error("cx", [self.global_qubit[i], self.global_qubit[j]])
        else:
            return 1.0 - self.default_cx_error_rate

    @staticmethod
    @lru_cache()
    def _gate_fidelities(node):
        matrix = node.op.to_matrix()
        target = TwoQubitWeylDecomposition(matrix)
        traces = two_qubit_cnot_decompose.traces(target)
        return [trace_to_fid(traces[i]) for i in range(4)]

    @staticmethod
    @lru_cache()
    def _mirrored_gate_fidelities(node):
        matrix = node.op.to_matrix()
        swap = SwapGate().to_matrix()
        targetm = TwoQubitWeylDecomposition(matrix @ swap)
        tracesm = two_qubit_cnot_decompose.traces(targetm)
        return [trace_to_fid(tracesm[i]) for i in range(4)]

    @_optionals.HAS_CPLEX.require_in_call
    def solve_cpx_problem(self, time_limit: float = 60, threads: int = None) -> str:
        """Solve the BIP problem using CPLEX.

        Args:
            time_limit:
                Time limit (seconds) given to CPLEX.

            threads:
                Number of threads to be allowed for CPLEX to use.

        Returns:
            Status string that CPLEX returned after solving the BIP problem.

        Raises:
            MissingOptionalLibraryError: If CPLEX is not installed
        """
        self.problem.set_time_limit(time_limit)
        if threads is not None:
            self.problem.context.cplex_parameters.threads = threads
        self.problem.context.cplex_parameters.randomseed = 777

        self.solution = self.problem.solve()

        status = self.problem.solve_details.status
        logger.info("BIP solution status: %s", status)
        return status

    def get_layout(self, t: int) -> Layout:
        """Get layout at time-step t.

        Args:
            t: Time-step

        Returns:
            Layout
        """
        dic = {}
        for q in range(self.num_vqubits):
            for i in range(self.num_pqubits):
                if self.solution.get_value(f"w_{t}_{q}_{i}") > 0.5:
                    dic[self._index_to_virtual[q]] = self.global_qubit[i]
        layout = Layout(dic)
        for reg in self._dag.qregs.values():
            layout.add_register(reg)
        return layout

    def get_swaps(self, t: int) -> list:
        """Get swaps (pairs of physical qubits) inserted at time-step ``t``.

        Args:
            t: Time-step (<= depth - 1)

        Returns:
            List of swaps (pairs of physical qubits (integers))
        """
        swaps = []
        for (i, j) in self._arcs:
            if i >= j:
                continue
            for q in range(self.num_vqubits):
                if self.solution.get_value(f"x_{t}_{q}_{i}_{j}") > 0.5:
                    swaps.append((self.global_qubit[i], self.global_qubit[j]))
        return swaps

1	# This code is part of Qiskit.
2	#
3	# (C) Copyright IBM 2021.
4	#
5	# This code is licensed under the Apache License, Version 2.0. You may
6	# obtain a copy of this license in the LICENSE.txt file in the root directory
7	# of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.
8	#
9	# Any modifications or derivative works of this code must retain this
10	# copyright notice, and modified files need to carry a notice indicating
11	# that they have been altered from the originals.
12	"""Integer programming model for quantum circuit compilation."""	1✔
13	import copy	1✔
14	import logging	1✔
15	from functools import lru_cache	1✔
16
17	import numpy as np	1✔
18
19	from qiskit.transpiler.exceptions import TranspilerError, CouplingError	1✔
20	from qiskit.transpiler.layout import Layout	1✔
21	from qiskit.circuit.library.standard_gates import SwapGate	1✔
22	from qiskit.providers.models import BackendProperties	1✔
23	from qiskit.quantum_info import two_qubit_cnot_decompose	1✔
24	from qiskit.quantum_info.synthesis.two_qubit_decompose import (	1✔
25	TwoQubitWeylDecomposition,
26	trace_to_fid,
27	)
28	from qiskit.utils import optionals as _optionals	1✔
29	from qiskit.utils.deprecation import deprecate_func	1✔
30
31	logger = logging.getLogger(__name__)	1✔
32
33
34	@_optionals.HAS_DOCPLEX.require_in_instance	1✔
35	class BIPMappingModel:	1✔
36	"""Internal model to create and solve a BIP problem for mapping.	1✔
37
38	Attributes:
39	problem (Model):
40	A CPLEX problem model object, which is set by calling
41	:method:`create_cpx_problem`. After calling :method:`solve_cpx_problem`,
42	the solution will be stored in :attr:`solution`). None if it's not yet set.
43	"""
44
45	@deprecate_func(	1✔
46	since="0.24.0",
47	additional_msg="This has been replaced by a new transpiler plugin package: "
48	"qiskit-bip-mapper. More details can be found here: "
49	"https://github.com/qiskit-community/qiskit-bip-mapper",
50	) # pylint: disable=bad-docstring-quotes
51	def __init__(self, dag, coupling_map, qubit_subset, dummy_timesteps=None):	1✔
52	"""
53	Args:
54	dag (DAGCircuit): DAG circuit to be mapped
55	coupling_map (CouplingMap): Coupling map of the device on which the `dag` is mapped.
56	qubit_subset (list[int]): Sublist of physical qubits to be used in the mapping.
57	dummy_timesteps (int):
58	Number of dummy time steps, after each real layer of gates, to
59	allow arbitrary swaps between neighbors.
60
61	Raises:
62	MissingOptionalLibraryError: If docplex is not installed
63	TranspilerError: If size of virtual qubits and physical qubits differ, or
64	if coupling_map is not symmetric (bidirectional).
65	"""
66
67	self._dag = dag	×
68	self._coupling = copy.deepcopy(coupling_map) # reduced coupling map	×
69	try:	×
70	self._coupling = self._coupling.reduce(qubit_subset)	×
71	except CouplingError as err:	×
72	raise TranspilerError(	×
73	"The 'coupling_map' reduced by 'qubit_subset' must be connected."
74	) from err
75	self._coupling.make_symmetric()	×
76	self.global_qubit = qubit_subset # the map from reduced qubit index to global qubit index	×
77
78	self.problem = None	×
79	self.solution = None	×
80	self.num_vqubits = len(self._dag.qubits)	×
81	self.num_pqubits = self._coupling.size()	×
82	self._arcs = self._coupling.get_edges()	×
83
84	if self.num_vqubits != self.num_pqubits:	×
85	raise TranspilerError(	×
86	"BIPMappingModel assumes the same size of virtual and physical qubits."
87	)
88
89	self._index_to_virtual = dict(enumerate(dag.qubits))	×
90
91	# Construct internal circuit model
92	# Extract layers with 2-qubit gates
93	self._to_su4layer = []	×
94	self.su4layers = []	×
95	for lay in dag.layers():	×
96	laygates = []	×
97	for node in lay["graph"].two_qubit_ops():	×
98	i1 = self._dag.find_bit(node.qargs[0]).index	×
99	i2 = self._dag.find_bit(node.qargs[1]).index	×
100	laygates.append(((i1, i2), node))	×
101	if laygates:	×
102	self._to_su4layer.append(len(self.su4layers))	×
103	self.su4layers.append(laygates)	×
104	else:
105	self._to_su4layer.append(-1)	×
106	# Add dummy time steps inbetween su4layers. Dummy time steps can only contain SWAPs.
107	self.gates = [] # layered 2q-gates with dummy steps	×
108	for k, lay in enumerate(self.su4layers):	×
109	self.gates.append(lay)	×
110	if k == len(self.su4layers) - 1: # do not add dummy steps after the last layer	×
111	break	×
112	self.gates.extend([[]] * dummy_timesteps)	×
113
114	self.bprop = None # Backend properties to compute cx fidelities (set later if necessary)	×
115	self.default_cx_error_rate = (	×
116	None # Default cx error rate in case backend properties are not available
117	)
118
119	logger.info("Num virtual qubits: %d", self.num_vqubits)	×
120	logger.info("Num physical qubits: %d", self.num_pqubits)	×
121	logger.info("Model depth: %d", self.depth)	×
122	logger.info("Dummy steps: %d", dummy_timesteps)	×
123
124	@property	1✔
125	def depth(self):	1✔
126	"""Number of time-steps (including dummy steps)."""
127	return len(self.gates)	×
128
129	def is_su4layer(self, depth: int) -> bool:	1✔
130	"""Check if the depth-th layer is su4layer (layer containing 2q-gates) or not.
131
132	Args:
133	depth: Depth of the ordinary layer
134
135	Returns:
136	True if the depth-th layer is su4layer, otherwise False
137	"""
138	return self._to_su4layer[depth] >= 0	×
139
140	def to_su4layer_depth(self, depth: int) -> int:	1✔
141	"""Return the depth as a su4layer. If the depth-th layer is not a su4layer, return -1.
142
143	Args:
144	depth: Depth of the ordinary layer
145
146	Returns:
147	su4layer depth if the depth-th layer is a su4layer, otherwise -1
148	"""
149	return self._to_su4layer[depth]	×
150
151	# pylint: disable=invalid-name
152	def _is_dummy_step(self, t: int):	1✔
153	"""Check if the time-step t is a dummy step or not."""
154	return len(self.gates[t]) == 0	×
155
156	@_optionals.HAS_DOCPLEX.require_in_call	1✔
157	def create_cpx_problem(	1✔
158	self,
159	objective: str,
160	backend_prop: BackendProperties = None,
161	line_symm: bool = False,
162	depth_obj_weight: float = 0.1,
163	default_cx_error_rate: float = 5e-3,
164	):
165	"""Create integer programming model to compile a circuit.
166
167	Args:
168	objective:
169	Type of objective function to be minimized:
170
171	* ``'gate_error'``: Approximate gate error of the circuit, which is given as the sum of
172	negative logarithm of CNOT gate fidelities in the circuit. It takes into account
173	only the CNOT gate errors reported in ``backend_prop``.
174	* ``'depth'``: Depth (number of timesteps) of the circuit
175	* ``'balanced'``: Weighted sum of gate_error and depth
176
177	backend_prop:
178	Backend properties storing gate errors, which are required in computing certain
179	types of objective function such as ``'gate_error'`` or ``'balanced'``.
180	If this is not available, default_cx_error_rate is used instead.
181
182	line_symm:
183	Use symmetry breaking constrainst for line topology. Should
184	only be True if the hardware graph is a chain/line/path.
185
186	depth_obj_weight:
187	Weight of depth objective in ``'balanced'`` objective function.
188
189	default_cx_error_rate:
190	Default CX error rate to be used if backend_prop is not available.
191
192	Raises:
193	TranspilerError: if unknown objective type is specified or invalid options are specified.
194	MissingOptionalLibraryError: If docplex is not installed
195	"""
196	self.bprop = backend_prop	×
197	self.default_cx_error_rate = default_cx_error_rate	×
198	if self.bprop is None and self.default_cx_error_rate is None:	×
199	raise TranspilerError("BackendProperties or default_cx_error_rate must be specified")	×
200	from docplex.mp.model import Model	×
201
202	mdl = Model()	×
203
204	# * Define main variables *
205	# Add w variables
206	w = {}	×
207	for t in range(self.depth):	×
208	for q in range(self.num_vqubits):	×
209	for j in range(self.num_pqubits):	×
210	w[t, q, j] = mdl.binary_var(name=f"w_{t}_{q}_{j}")	×
211	# Add y variables
212	y = {}	×
213	for t in range(self.depth):	×
214	for ((p, q), _) in self.gates[t]:	×
215	for (i, j) in self._arcs:	×
216	y[t, p, q, i, j] = mdl.binary_var(name=f"y_{t}_{p}_{q}_{i}_{j}")	×
217	# Add x variables
218	x = {}	×
219	for t in range(self.depth - 1):	×
220	for q in range(self.num_vqubits):	×
221	for i in range(self.num_pqubits):	×
222	x[t, q, i, i] = mdl.binary_var(name=f"x_{t}_{q}_{i}_{i}")	×
223	for j in self._coupling.neighbors(i):	×
224	x[t, q, i, j] = mdl.binary_var(name=f"x_{t}_{q}_{i}_{j}")	×
225
226	# * Define main constraints *
227	# Assignment constraints for w variables
228	for t in range(self.depth):	×
229	for q in range(self.num_vqubits):	×
230	mdl.add_constraint(	×
231	sum(w[t, q, j] for j in range(self.num_pqubits)) == 1,
232	ctname=f"assignment_vqubits_{q}_at_{t}",
233	)
234	for t in range(self.depth):	×
235	for j in range(self.num_pqubits):	×
236	mdl.add_constraint(	×
237	sum(w[t, q, j] for q in range(self.num_vqubits)) == 1,
238	ctname=f"assignment_pqubits_{j}_at_{t}",
239	)
240	# Each gate must be implemented
241	for t in range(self.depth):	×
242	for ((p, q), _) in self.gates[t]:	×
243	mdl.add_constraint(	×
244	sum(y[t, p, q, i, j] for (i, j) in self._arcs) == 1,
245	ctname=f"implement_gate_{p}_{q}_at_{t}",
246	)
247	# Gate can be implemented iff both of its qubits are located at the associated nodes
248	for t in range(self.depth - 1):	×
249	for ((p, q), _) in self.gates[t]:	×
250	for (i, j) in self._arcs:	×
251	# Apply McCormick to y[t, p, q, i, j] == w[t, p, i] * w[t, q, j]
252	mdl.add_constraint(	×
253	y[t, p, q, i, j] >= w[t, p, i] + w[t, q, j] - 1,
254	ctname=f"McCormickLB_{p}_{q}_{i}_{j}_at_{t}",
255	)
256	# Stronger version of McCormick: gate (p,q) is implemented at (i, j)
257	# if i moves to i or j, and j moves to i or j
258	mdl.add_constraint(	×
259	y[t, p, q, i, j] <= x[t, p, i, i] + x[t, p, i, j],
260	ctname=f"McCormickUB1_{p}_{q}_{i}_{j}_at_{t}",
261	)
262	mdl.add_constraint(	×
263	y[t, p, q, i, j] <= x[t, q, j, i] + x[t, q, j, j],
264	ctname=f"McCormickUB2_{p}_{q}_{i}_{j}_at_{t}",
265	)
266	# For last time step, use regular McCormick
267	for ((p, q), _) in self.gates[self.depth - 1]:	×
268	for (i, j) in self._arcs:	×
269	# Apply McCormick to y[self.depth - 1, p, q, i, j]
270	# == w[self.depth - 1, p, i] * w[self.depth - 1, q, j]
271	mdl.add_constraint(	×
272	y[self.depth - 1, p, q, i, j]
273	>= w[self.depth - 1, p, i] + w[self.depth - 1, q, j] - 1,
274	ctname=f"McCormickLB_{p}_{q}_{i}_{j}_at_last",
275	)
276	mdl.add_constraint(	×
277	y[self.depth - 1, p, q, i, j] <= w[self.depth - 1, p, i],
278	ctname=f"McCormickUB1_{p}_{q}_{i}_{j}_at_last",
279	)
280	mdl.add_constraint(	×
281	y[self.depth - 1, p, q, i, j] <= w[self.depth - 1, q, j],
282	ctname=f"McCormickUB2_{p}_{q}_{i}_{j}_at_last",
283	)
284	# Logical qubit flow-out constraints
285	for t in range(self.depth - 1): # Flow out; skip last time step	×
286	for q in range(self.num_vqubits):	×
287	for i in range(self.num_pqubits):	×
288	mdl.add_constraint(	×
289	w[t, q, i]
290	== x[t, q, i, i] + sum(x[t, q, i, j] for j in self._coupling.neighbors(i)),
291	ctname=f"flow_out_{q}_{i}_at_{t}",
292	)
293	# Logical qubit flow-in constraints
294	for t in range(1, self.depth): # Flow in; skip first time step	×
295	for q in range(self.num_vqubits):	×
296	for i in range(self.num_pqubits):	×
297	mdl.add_constraint(	×
298	w[t, q, i]
299	== x[t - 1, q, i, i]
300	+ sum(x[t - 1, q, j, i] for j in self._coupling.neighbors(i)),
301	ctname=f"flow_in_{q}_{i}_at_{t}",
302	)
303	# If a gate is implemented, involved qubits cannot swap with other positions
304	for t in range(self.depth - 1):	×
305	for ((p, q), _) in self.gates[t]:	×
306	for (i, j) in self._arcs:	×
307	mdl.add_constraint(	×
308	x[t, p, i, j] == x[t, q, j, i], ctname=f"swap_{p}_{q}_{i}_{j}_at_{t}"
309	)
310	# Qubit not in gates can flip with their neighbors
311	for t in range(self.depth - 1):	×
312	q_no_gate = list(range(self.num_vqubits))	×
313	for ((p, q), _) in self.gates[t]:	×
314	q_no_gate.remove(p)	×
315	q_no_gate.remove(q)	×
316	for (i, j) in self._arcs:	×
317	mdl.add_constraint(	×
318	sum(x[t, q, i, j] for q in q_no_gate) == sum(x[t, p, j, i] for p in q_no_gate),
319	ctname=f"swap_no_gate_{i}_{j}_at_{t}",
320	)
321
322	# * Define supplemental variables *
323	# Add z variables to count dummy steps (supplemental variables for symmetry breaking)
324	z = {}	×
325	for t in range(self.depth):	×
326	if self._is_dummy_step(t):	×
327	z[t] = mdl.binary_var(name=f"z_{t}")	×
328
329	# * Define supplemental constraints *
330	# See if a dummy time step is needed
331	for t in range(self.depth):	×
332	if self._is_dummy_step(t):	×
333	for q in range(self.num_vqubits):	×
334	mdl.add_constraint(	×
335	sum(x[t, q, i, j] for (i, j) in self._arcs) <= z[t],
336	ctname=f"dummy_ts_needed_for_vqubit_{q}_at_{t}",
337	)
338	# Symmetry breaking between dummy time steps
339	for t in range(self.depth - 1):	×
340	# This is a dummy time step and the next one is dummy too
341	if self._is_dummy_step(t) and self._is_dummy_step(t + 1):	×
342	# We cannot use the next time step unless this one is used too
343	mdl.add_constraint(z[t] >= z[t + 1], ctname=f"dummy_precedence_{t}")	×
344	# Symmetry breaking on the line -- only works on line topology!
345	if line_symm:	×
346	for h in range(1, self.num_vqubits):	×
347	mdl.add_constraint(	×
348	sum(w[0, p, 0] for p in range(h))
349	+ sum(w[0, q, self.num_pqubits - 1] for q in range(h, self.num_vqubits))
350	>= 1,
351	ctname=f"sym_break_line_{h}",
352	)
353
354	# * Define objevtive function *
355	if objective == "depth":	×
356	objexr = sum(z[t] for t in range(self.depth) if self._is_dummy_step(t))	×
357	for t in range(self.depth - 1):	×
358	for q in range(self.num_vqubits):	×
359	for (i, j) in self._arcs:	×
360	objexr += 0.01 * x[t, q, i, j]	×
361	mdl.minimize(objexr)	×
362	elif objective in ("gate_error", "balanced"):	×
363	# We add the depth objective with coefficient depth_obj_weight if balanced was selected.
364	objexr = 0	×
365	for t in range(self.depth - 1):	×
366	for (p, q), node in self.gates[t]:	×
367	for (i, j) in self._arcs:	×
368	# We pay the cost for gate implementation.
369	pbest_fid = -np.log(self._max_expected_fidelity(node, i, j))	×
370	objexr += y[t, p, q, i, j] * pbest_fid	×
371	# If a gate is mirrored (followed by a swap on the same qubit pair),
372	# its cost should be replaced with the cost of the combined (mirrored) gate.
373	pbest_fidm = -np.log(self._max_expected_mirrored_fidelity(node, i, j))	×
374	objexr += x[t, q, i, j] * (pbest_fidm - pbest_fid) / 2	×
375	# Cost of swaps on unused qubits
376	for q in range(self.num_vqubits):	×
377	used_qubits = {q for (pair, _) in self.gates[t] for q in pair}	×
378	if q not in used_qubits:	×
379	for i in range(self.num_pqubits):	×
380	for j in self._coupling.neighbors(i):	×
381	objexr += x[t, q, i, j] * -3 / 2 * np.log(self._cx_fidelity(i, j))	×
382	# Cost for the last layer (x variables are not defined for depth-1)
383	for (p, q), node in self.gates[self.depth - 1]:	×
384	for (i, j) in self._arcs:	×
385	pbest_fid = -np.log(self._max_expected_fidelity(node, i, j))	×
386	objexr += y[self.depth - 1, p, q, i, j] * pbest_fid	×
387	if objective == "balanced":	×
388	objexr += depth_obj_weight * sum(	×
389	z[t] for t in range(self.depth) if self._is_dummy_step(t)
390	)
391	mdl.minimize(objexr)	×
392	else:
393	raise TranspilerError(f"Unknown objective type: {objective}")	×
394
395	self.problem = mdl	×
396	logger.info("BIP problem stats: %s", self.problem.statistics)	×
397
398	def _max_expected_fidelity(self, node, i, j):	1✔
399	return max(	×
400	gfid * self._cx_fidelity(i, j) ** k
401	for k, gfid in enumerate(self._gate_fidelities(node))
402	)
403
404	def _max_expected_mirrored_fidelity(self, node, i, j):	1✔
405	return max(	×
406	gfid * self._cx_fidelity(i, j) ** k
407	for k, gfid in enumerate(self._mirrored_gate_fidelities(node))
408	)
409
410	def _cx_fidelity(self, i, j) -> float:	1✔
411	# fidelity of cx on global physical qubits
412	if self.bprop is not None:	×
413	return 1.0 - self.bprop.gate_error("cx", [self.global_qubit[i], self.global_qubit[j]])	×
414	else:
415	return 1.0 - self.default_cx_error_rate	×
416
417	@staticmethod	1✔
418	@lru_cache()	1✔
419	def _gate_fidelities(node):	1✔
420	matrix = node.op.to_matrix()	×
421	target = TwoQubitWeylDecomposition(matrix)	×
422	traces = two_qubit_cnot_decompose.traces(target)	×
423	return [trace_to_fid(traces[i]) for i in range(4)]	×
424
425	@staticmethod	1✔
426	@lru_cache()	1✔
427	def _mirrored_gate_fidelities(node):	1✔
428	matrix = node.op.to_matrix()	×
429	swap = SwapGate().to_matrix()	×
430	targetm = TwoQubitWeylDecomposition(matrix @ swap)	×
431	tracesm = two_qubit_cnot_decompose.traces(targetm)	×
432	return [trace_to_fid(tracesm[i]) for i in range(4)]	×
433
434	@_optionals.HAS_CPLEX.require_in_call	1✔
435	def solve_cpx_problem(self, time_limit: float = 60, threads: int = None) -> str:	1✔
436	"""Solve the BIP problem using CPLEX.
437
438	Args:
439	time_limit:
440	Time limit (seconds) given to CPLEX.
441
442	threads:
443	Number of threads to be allowed for CPLEX to use.
444
445	Returns:
446	Status string that CPLEX returned after solving the BIP problem.
447
448	Raises:
449	MissingOptionalLibraryError: If CPLEX is not installed
450	"""
451	self.problem.set_time_limit(time_limit)	×
452	if threads is not None:	×
453	self.problem.context.cplex_parameters.threads = threads	×
454	self.problem.context.cplex_parameters.randomseed = 777	×
455
456	self.solution = self.problem.solve()	×
457
458	status = self.problem.solve_details.status	×
459	logger.info("BIP solution status: %s", status)	×
460	return status	×
461
462	def get_layout(self, t: int) -> Layout:	1✔
463	"""Get layout at time-step t.
464
465	Args:
466	t: Time-step
467
468	Returns:
469	Layout
470	"""
471	dic = {}	×
472	for q in range(self.num_vqubits):	×
473	for i in range(self.num_pqubits):	×
474	if self.solution.get_value(f"w_{t}_{q}_{i}") > 0.5:	×
475	dic[self._index_to_virtual[q]] = self.global_qubit[i]	×
476	layout = Layout(dic)	×
477	for reg in self._dag.qregs.values():	×
478	layout.add_register(reg)	×
479	return layout	×
480
481	def get_swaps(self, t: int) -> list:	1✔
482	"""Get swaps (pairs of physical qubits) inserted at time-step ``t``.
483
484	Args:
485	t: Time-step (<= depth - 1)
486
487	Returns:
488	List of swaps (pairs of physical qubits (integers))
489	"""
490	swaps = []	×
491	for (i, j) in self._arcs:	×
492	if i >= j:	×
493	continue	×
494	for q in range(self.num_vqubits):	×
495	if self.solution.get_value(f"x_{t}_{q}_{i}_{j}") > 0.5:	×
496	swaps.append((self.global_qubit[i], self.global_qubit[j]))	×
497	return swaps	×

Qiskit / qiskit-terra / 5648658767

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous