qiskit/transpiler/passes/mapping/legacy_swap.py
def layer_permutation(self, layer_partition, layout, qubit_subset):
        """Find a swap circuit that implements a permutation for this layer.

        The goal is to swap qubits such that qubits in the same two-qubit gates
        are adjacent.

        Based on Sergey Bravyi's algorithm.

        The layer_partition is a list of (qu)bit lists and each qubit is a
        tuple (qreg, index).
        The layout is a dict mapping qubits in the circuit to qubits in the
        coupling graph and represents the current positions of the data.
        The qubit_subset is the subset of qubits in the coupling graph that
        we have chosen to map into.
        The coupling is a CouplingGraph.
        TRIALS is the number of attempts the randomized algorithm makes.

        Returns: success_flag, best_circ, best_d, best_layout, trivial_flag

        If success_flag is True, then best_circ contains a DAGCircuit with
        the swap circuit, best_d contains the depth of the swap circuit, and
        best_layout contains the new positions of the data qubits after the
        swap circuit has been applied. The trivial_flag is set if the layer
        has no multi-qubit gates.
        """
        if self.seed is None:
            self.seed = np.random.randint(0, np.iinfo(np.int32).max)
        rng = np.random.RandomState(self.seed)
        rev_layout = {b: a for a, b in layout.items()}
        gates = []
        for layer in layer_partition:
            if len(layer) > 2:
                raise TranspilerError("Layer contains >2 qubit gates")
            elif len(layer) == 2:
                gates.append(tuple(layer))

        # Can we already apply the gates?
        dist = sum([self.coupling_map.distance(layout[g[0]][1], layout[g[1]][1]) for g in gates])
        if dist == len(gates):
            circ = DAGCircuit()
            circ.add_qreg(QuantumRegister(self.coupling_map.size(), "q"))
            return True, circ, 0, layout, bool(gates)

        # Begin loop over trials of randomized algorithm
        n = self.coupling_map.size()
        best_d = sys.maxsize  # initialize best depth
        best_circ = None  # initialize best swap circuit
        best_layout = None  # initialize best final layout
        QR = QuantumRegister(self.coupling_map.size(), "q")
        for _ in range(self.trials):

            trial_layout = layout.copy()
            rev_trial_layout = rev_layout.copy()
            # SWAP circuit constructed this trial
            trial_circ = DAGCircuit()
            trial_circ.add_qreg(QR)

            # Compute Sergey's randomized distance
            xi = {}
            for i in self.coupling_map.physical_qubits:
                xi[(QR, i)] = {}
            for i in self.coupling_map.physical_qubits:
                i = (QR, i)
                for j in self.coupling_map.physical_qubits:
                    j = (QR, j)
                    scale = 1 + rng.normal(0, 1 / n)
                    xi[i][j] = scale * self.coupling_map.distance(i[1], j[1]) ** 2
                    xi[j][i] = xi[i][j]

            # Loop over depths d up to a max depth of 2n+1
            d = 1
            # Circuit for this swap slice
            circ = DAGCircuit()
            circ.add_qreg(QR)

            # Identity wire-map for composing the circuits
            identity_wire_map = {(QR, j): (QR, j) for j in range(n)}

            while d < 2 * n + 1:
                # Set of available qubits
                qubit_set = set(qubit_subset)
                # While there are still qubits available
                while qubit_set:
                    # Compute the objective function
                    min_cost = sum([xi[trial_layout[g[0]]][trial_layout[g[1]]]
                                    for g in gates])
                    # Try to decrease objective function
                    progress_made = False
                    # Loop over edges of coupling graph
                    for e in self.coupling_map.get_edges():
                        e = [(QR, edge) for edge in e]
                        # Are the qubits available?
                        if e[0] in qubit_set and e[1] in qubit_set:
                            # Try this edge to reduce the cost
                            new_layout = trial_layout.copy()
                            new_layout[rev_trial_layout[e[0]]] = e[1]
                            new_layout[rev_trial_layout[e[1]]] = e[0]
                            rev_new_layout = rev_trial_layout.copy()
                            rev_new_layout[e[0]] = rev_trial_layout[e[1]]
                            rev_new_layout[e[1]] = rev_trial_layout[e[0]]
                            # Compute the objective function
                            new_cost = sum([xi[new_layout[g[0]]][new_layout[g[1]]]
                                            for g in gates])
                            # Record progress if we succceed
                            if new_cost < min_cost:
                                progress_made = True
                                min_cost = new_cost
                                opt_layout = new_layout
                                rev_opt_layout = rev_new_layout
                                opt_edge = e

                    # Were there any good choices?
                    if progress_made:
                        qubit_set.remove(opt_edge[0])
                        qubit_set.remove(opt_edge[1])
                        trial_layout = opt_layout
                        rev_trial_layout = rev_opt_layout
                        circ.apply_operation_back(
                            SwapGate(),
                            [(opt_edge[0][0], opt_edge[0][1]), (opt_edge[1][0], opt_edge[1][1])],
                            [])
                    else:
                        break

                # We have either run out of qubits or failed to improve
                # Compute the coupling graph distance_qubits
                dist = sum([self.coupling_map.distance(trial_layout[g[0]][1],
                                                       trial_layout[g[1]][1]) for g in gates])
                # If all gates can be applied now, we are finished
                # Otherwise we need to consider a deeper swap circuit
                if dist == len(gates):
                    trial_circ.compose_back(circ, identity_wire_map)
                    break

                # Increment the depth
                d += 1

            # Either we have succeeded at some depth d < dmax or failed
            dist = sum([self.coupling_map.distance(trial_layout[g[0]][1],
                                                   trial_layout[g[1]][1]) for g in gates])
            if dist == len(gates):
                if d < best_d:
                    best_circ = trial_circ
                    best_layout = trial_layout
                best_d = min(best_d, d)

        if best_circ is None:
            return False, None, None, None, False

        return True, best_circ, best_d, best_layout, False
def layer_permutation(self, layer_partition, layout, qubit_subset):
        """Find a swap circuit that implements a permutation for this layer.

        The goal is to swap qubits such that qubits in the same two-qubit gates
        are adjacent.

        Based on Sergey Bravyi's algorithm.

        The layer_partition is a list of (qu)bit lists and each qubit is a
        tuple (qreg, index).
        The layout is a dict mapping qubits in the circuit to qubits in the
        coupling graph and represents the current positions of the data.
        The qubit_subset is the subset of qubits in the coupling graph that
        we have chosen to map into.
        The coupling is a CouplingGraph.
        TRIALS is the number of attempts the randomized algorithm makes.

        Returns: success_flag, best_circ, best_d, best_layout, trivial_flag

        If success_flag is True, then best_circ contains a DAGCircuit with
        the swap circuit, best_d contains the depth of the swap circuit, and
        best_layout contains the new positions of the data qubits after the
        swap circuit has been applied. The trivial_flag is set if the layer
        has no multi-qubit gates.
        """
        if self.seed is None:
            self.seed = np.random.randint(0, np.iinfo(np.int32).max)
        rng = np.random.RandomState(self.seed)
        rev_layout = {b: a for a, b in layout.items()}
        gates = []
        for layer in layer_partition:
            if len(layer) > 2:
                raise TranspilerError("Layer contains >2 qubit gates")
            elif len(layer) == 2:
                gates.append(tuple(layer))

        # Can we already apply the gates?
        dist = sum([self.coupling_map.distance(layout[g[0]][1], layout[g[1]][1]) for g in gates])
        if dist == len(gates):
            circ = DAGCircuit()
            circ.add_qreg(QuantumRegister(self.coupling_map.size(), "q"))
            return True, circ, 0, layout, bool(gates)

        # Begin loop over trials of randomized algorithm
        n = self.coupling_map.size()
        best_d = sys.maxsize  # initialize best depth
        best_circ = None  # initialize best swap circuit
        best_layout = None  # initialize best final layout
        QR = QuantumRegister(self.coupling_map.size(), "q")
        for _ in range(self.trials):

            trial_layout = layout.copy()
            rev_trial_layout = rev_layout.copy()
            # SWAP circuit constructed this trial
            trial_circ = DAGCircuit()
            trial_circ.add_qreg(QR)

            # Compute Sergey's randomized distance
            xi = {}
            for i in self.coupling_map.physical_qubits:
                xi[(QR, i)] = {}
            for i in self.coupling_map.physical_qubits:
                i = (QR, i)
                for j in self.coupling_map.physical_qubits:
                    j = (QR, j)
                    scale = 1 + rng.normal(0, 1 / n)
                    xi[i][j] = scale * self.coupling_map.distance(i[1], j[1]) ** 2
                    xi[j][i] = xi[i][j]

            # Loop over depths d up to a max depth of 2n+1
            d = 1
            # Circuit for this swap slice
            circ = DAGCircuit()
            circ.add_qreg(QR)

            # Identity wire-map for composing the circuits
            identity_wire_map = {(QR, j): (QR, j) for j in range(n)}

            while d < 2 * n + 1:
                # Set of available qubits
                qubit_set = set(qubit_subset)
                # While there are still qubits available
                while qubit_set:
                    # Compute the objective function
                    min_cost = sum([xi[trial_layout[g[0]]][trial_layout[g[1]]]
                                    for g in gates])
                    # Try to decrease objective function
                    progress_made = False
                    # Loop over edges of coupling graph
                    for e in self.coupling_map.get_edges():
                        e = [(QR, edge) for edge in e]
                        # Are the qubits available?
                        if e[0] in qubit_set and e[1] in qubit_set:
                            # Try this edge to reduce the cost
                            new_layout = trial_layout.copy()
                            new_layout[rev_trial_layout[e[0]]] = e[1]
                            new_layout[rev_trial_layout[e[1]]] = e[0]
                            rev_new_layout = rev_trial_layout.copy()
                            rev_new_layout[e[0]] = rev_trial_layout[e[1]]
                            rev_new_layout[e[1]] = rev_trial_layout[e[0]]
                            # Compute the objective function
                            new_cost = sum([xi[new_layout[g[0]]][new_layout[g[1]]]
                                            for g in gates])
                            # Record progress if we succceed
                            if new_cost < min_cost:
                                progress_made = True
                                min_cost = new_cost
                                opt_layout = new_layout
                                rev_opt_layout = rev_new_layout
                                opt_edge = e

                    # Were there any good choices?
                    if progress_made:
                        qubit_set.remove(opt_edge[0])
                        qubit_set.remove(opt_edge[1])
                        trial_layout = opt_layout
                        rev_trial_layout = rev_opt_layout
                        circ.apply_operation_back(
                            SwapGate(),
                            [(opt_edge[0][0], opt_edge[0][1]), (opt_edge[1][0], opt_edge[1][1])],
                            [])
                    else:
                        break

                # We have either run out of qubits or failed to improve
                # Compute the coupling graph distance_qubits
                dist = sum([self.coupling_map.distance(trial_layout[g[0]][1],
                                                       trial_layout[g[1]][1]) for g in gates])
                # If all gates can be applied now, we are finished
                # Otherwise we need to consider a deeper swap circuit
                if dist == len(gates):
                    trial_circ.compose_back(circ, identity_wire_map)
                    break

                # Increment the depth
                d += 1

            # Either we have succeeded at some depth d < dmax or failed
            dist = sum([self.coupling_map.distance(trial_layout[g[0]][1],
                                                   trial_layout[g[1]][1]) for g in gates])
            if dist == len(gates):
                if d < best_d:
                    best_circ = trial_circ
                    best_layout = trial_layout
                best_d = min(best_d, d)

        if best_circ is None:
            return False, None, None, None, False

        return True, best_circ, best_d, best_layout, False
Find a swap circuit that implements a permutation for this layer.

        The goal is to swap qubits such that qubits in the same two-qubit gates
        are adjacent.

        Based on Sergey Bravyi's algorithm.

        The layer_partition is a list of (qu)bit lists and each qubit is a
        tuple (qreg, index).
        The layout is a dict mapping qubits in the circuit to qubits in the
        coupling graph and represents the current positions of the data.
        The qubit_subset is the subset of qubits in the coupling graph that
        we have chosen to map into.
        The coupling is a CouplingGraph.
        TRIALS is the number of attempts the randomized algorithm makes.

        Returns: success_flag, best_circ, best_d, best_layout, trivial_flag

        If success_flag is True, then best_circ contains a DAGCircuit with
        the swap circuit, best_d contains the depth of the swap circuit, and
        best_layout contains the new positions of the data qubits after the
        swap circuit has been applied. The trivial_flag is set if the layer
        has no multi-qubit gates.