qiskit/transpiler/passes/mapping/dense_layout.py
def _best_subset(self, n_qubits):
        """Computes the qubit mapping with the best connectivity.

        Args:
            n_qubits (int): Number of subset qubits to consider.

        Returns:
            ndarray: Array of qubits to use for best connectivity mapping.
        """
        if n_qubits == 1:
            return np.array([0])

        device_qubits = self.coupling_map.size()

        cmap = np.asarray(self.coupling_map.get_edges())
        data = np.ones_like(cmap[:, 0])
        sp_cmap = sp.coo_matrix((data, (cmap[:, 0], cmap[:, 1])),
                                shape=(device_qubits, device_qubits)).tocsr()
        best = 0
        best_map = None
        # do bfs with each node as starting point
        for k in range(sp_cmap.shape[0]):
            bfs = cs.breadth_first_order(sp_cmap, i_start=k, directed=False,
                                         return_predecessors=False)

            connection_count = 0
            sub_graph = []
            for i in range(n_qubits):
                node_idx = bfs[i]
                for j in range(sp_cmap.indptr[node_idx],
                               sp_cmap.indptr[node_idx + 1]):
                    node = sp_cmap.indices[j]
                    for counter in range(n_qubits):
                        if node == bfs[counter]:
                            connection_count += 1
                            sub_graph.append([node_idx, node])
                            break

            if connection_count > best:
                best = connection_count
                best_map = bfs[0:n_qubits]
                # Return a best mapping that has reduced bandwidth
                mapping = {}
                for edge in range(best_map.shape[0]):
                    mapping[best_map[edge]] = edge
                new_cmap = [[mapping[c[0]], mapping[c[1]]] for c in sub_graph]
                rows = [edge[0] for edge in new_cmap]
                cols = [edge[1] for edge in new_cmap]
                data = [1]*len(rows)
                sp_sub_graph = sp.coo_matrix((data, (rows, cols)),
                                             shape=(n_qubits, n_qubits)).tocsr()
                perm = cs.reverse_cuthill_mckee(sp_sub_graph)
                best_map = best_map[perm]
        return best_map
def _best_subset(self, n_qubits):
        if n_qubits == 1:
            return np.array([0])

        device_qubits = self.coupling_map.size()

        cmap = np.asarray(self.coupling_map.get_edges())
        data = np.ones_like(cmap[:, 0])
        sp_cmap = sp.coo_matrix((data, (cmap[:, 0], cmap[:, 1])),
                                shape=(device_qubits, device_qubits)).tocsr()
        best = 0
        best_map = None
        # do bfs with each node as starting point
        for k in range(sp_cmap.shape[0]):
            bfs = cs.breadth_first_order(sp_cmap, i_start=k, directed=False,
                                         return_predecessors=False)

            connection_count = 0
            sub_graph = []
            for i in range(n_qubits):
                node_idx = bfs[i]
                for j in range(sp_cmap.indptr[node_idx],
                               sp_cmap.indptr[node_idx + 1]):
                    node = sp_cmap.indices[j]
                    for counter in range(n_qubits):
                        if node == bfs[counter]:
                            connection_count += 1
                            sub_graph.append([node_idx, node])
                            break

            if connection_count > best:
                best = connection_count
                best_map = bfs[0:n_qubits]
                # Return a best mapping that has reduced bandwidth
                mapping = {}
                for edge in range(best_map.shape[0]):
                    mapping[best_map[edge]] = edge
                new_cmap = [[mapping[c[0]], mapping[c[1]]] for c in sub_graph]
                rows = [edge[0] for edge in new_cmap]
                cols = [edge[1] for edge in new_cmap]
                data = [1]*len(rows)
                sp_sub_graph = sp.coo_matrix((data, (rows, cols)),
                                             shape=(n_qubits, n_qubits)).tocsr()
                perm = cs.reverse_cuthill_mckee(sp_sub_graph)
                best_map = best_map[perm]
        return best_map
def _best_subset ( self , n_qubits ) : if n_qubits == 1 : return np . array ( [ 0 ] ) device_qubits = self . coupling_map . size ( ) cmap = np . asarray ( self . coupling_map . get_edges ( ) ) data = np . ones_like ( cmap [ : , 0 ] ) sp_cmap = sp . coo_matrix ( ( data , ( cmap [ : , 0 ] , cmap [ : , 1 ] ) ) , shape = ( device_qubits , device_qubits ) ) . tocsr ( ) best = 0 best_map = None # do bfs with each node as starting point for k in range ( sp_cmap . shape [ 0 ] ) : bfs = cs . breadth_first_order ( sp_cmap , i_start = k , directed = False , return_predecessors = False ) connection_count = 0 sub_graph = [ ] for i in range ( n_qubits ) : node_idx = bfs [ i ] for j in range ( sp_cmap . indptr [ node_idx ] , sp_cmap . indptr [ node_idx + 1 ] ) : node = sp_cmap . indices [ j ] for counter in range ( n_qubits ) : if node == bfs [ counter ] : connection_count += 1 sub_graph . append ( [ node_idx , node ] ) break if connection_count > best : best = connection_count best_map = bfs [ 0 : n_qubits ] # Return a best mapping that has reduced bandwidth mapping = { } for edge in range ( best_map . shape [ 0 ] ) : mapping [ best_map [ edge ] ] = edge new_cmap = [ [ mapping [ c [ 0 ] ] , mapping [ c [ 1 ] ] ] for c in sub_graph ] rows = [ edge [ 0 ] for edge in new_cmap ] cols = [ edge [ 1 ] for edge in new_cmap ] data = [ 1 ] * len ( rows ) sp_sub_graph = sp . coo_matrix ( ( data , ( rows , cols ) ) , shape = ( n_qubits , n_qubits ) ) . tocsr ( ) perm = cs . reverse_cuthill_mckee ( sp_sub_graph ) best_map = best_map [ perm ] return best_map
Computes the qubit mapping with the best connectivity.

        Args:
            n_qubits (int): Number of subset qubits to consider.

        Returns:
            ndarray: Array of qubits to use for best connectivity mapping.
Computes the qubit mapping with the best connectivity .