qiskit/transpiler/passes/mapping/stochastic_swap.py
def _layer_permutation(layer_partition, initial_layout, layout, qubit_subset,
                       coupling, trials, qregs, rng):
    """Find a swap circuit that implements a permutation for this layer.

    Args:
        layer_partition (list): The layer_partition is a list of (qu)bit
            lists and each qubit is a tuple (qreg, index).
        initial_layout (Layout): The initial layout passed.
        layout (Layout): The layout is a Layout object mapping virtual
            qubits in the input circuit to physical qubits in the coupling
            graph. It reflects the current positions of the data.
        qubit_subset (list): The qubit_subset is the set of qubits in
            the coupling graph that we have chosen to map into, as tuples
            (Register, index).
        coupling (CouplingMap): Directed graph representing a coupling map.
            This coupling map should be one that was provided to the
            stochastic mapper.
        trials (int): Number of attempts the randomized algorithm makes.
        qregs (OrderedDict): Ordered dict of registers from input DAG.
        rng (RandomState): Random number generator.

    Returns:
        Tuple: success_flag, best_circuit, best_depth, best_layout, trivial_flag

    Raises:
        TranspilerError: if anything went wrong.
     """
    logger.debug("layer_permutation: layer_partition = %s",
                 pformat(layer_partition))
    logger.debug("layer_permutation: layout = %s",
                 pformat(layout.get_virtual_bits()))
    logger.debug("layer_permutation: qubit_subset = %s",
                 pformat(qubit_subset))
    logger.debug("layer_permutation: trials = %s", trials)

    gates = []  # list of lists of tuples [[(register, index), ...], ...]
    for gate_args in layer_partition:
        if len(gate_args) > 2:
            raise TranspilerError("Layer contains > 2-qubit gates")
        elif len(gate_args) == 2:
            gates.append(tuple(gate_args))
    logger.debug("layer_permutation: gates = %s", pformat(gates))

    # Can we already apply the gates? If so, there is no work to do.
    dist = sum([coupling.distance(layout[g[0]], layout[g[1]])
                for g in gates])
    logger.debug("layer_permutation: distance = %s", dist)
    if dist == len(gates):
        logger.debug("layer_permutation: nothing to do")
        circ = DAGCircuit()
        for register in layout.get_virtual_bits().keys():
            if register[0] not in circ.qregs.values():
                circ.add_qreg(register[0])
        return True, circ, 0, layout, (not bool(gates))

    # Begin loop over trials of randomized algorithm
    num_qubits = len(layout)
    best_depth = inf  # initialize best depth
    best_edges = None  # best edges found
    best_circuit = None  # initialize best swap circuit
    best_layout = None  # initialize best final layout

    cdist2 = coupling._dist_matrix**2
    # Scaling matrix
    scale = np.zeros((num_qubits, num_qubits))

    int_qubit_subset = regtuple_to_numeric(qubit_subset, qregs)
    int_gates = gates_to_idx(gates, qregs)
    int_layout = nlayout_from_layout(layout, qregs, coupling.size())

    trial_circuit = DAGCircuit()  # SWAP circuit for this trial
    for register in layout.get_virtual_bits().keys():
        if register[0] not in trial_circuit.qregs.values():
            trial_circuit.add_qreg(register[0])

    slice_circuit = DAGCircuit()  # circuit for this swap slice
    for register in layout.get_virtual_bits().keys():
        if register[0] not in slice_circuit.qregs.values():
            slice_circuit.add_qreg(register[0])
    edges = np.asarray(coupling.get_edges(), dtype=np.int32).ravel()
    cdist = coupling._dist_matrix
    for trial in range(trials):
        logger.debug("layer_permutation: trial %s", trial)
        # This is one Trial --------------------------------------
        dist, optim_edges, trial_layout, depth_step = swap_trial(num_qubits, int_layout,
                                                                 int_qubit_subset,
                                                                 int_gates, cdist2,
                                                                 cdist, edges, scale,
                                                                 rng)

        logger.debug("layer_permutation: final distance for this trial = %s", dist)
        if dist == len(gates) and depth_step < best_depth:
            logger.debug("layer_permutation: got circuit with improved depth %s",
                         depth_step)
            best_edges = optim_edges
            best_layout = trial_layout
            best_depth = min(best_depth, depth_step)

        # Break out of trial loop if we found a depth 1 circuit
        # since we can't improve it further
        if best_depth == 1:
            break

    # If we have no best circuit for this layer, all of the
    # trials have failed
    if best_layout is None:
        logger.debug("layer_permutation: failed!")
        return False, None, None, None, False

    edgs = best_edges.edges()
    for idx in range(best_edges.size//2):
        slice_circuit.apply_operation_back(
            SwapGate(), [initial_layout[edgs[2*idx]], initial_layout[edgs[2*idx+1]]], [])
    trial_circuit.extend_back(slice_circuit)
    best_circuit = trial_circuit

    # Otherwise, we return our result for this layer
    logger.debug("layer_permutation: success!")
    best_lay = best_layout.to_layout(qregs)
    return True, best_circuit, best_depth, best_lay, False
def _layer_permutation(layer_partition, initial_layout, layout, qubit_subset,
                       coupling, trials, qregs, rng):
    """Find a swap circuit that implements a permutation for this layer.

    Args:
        layer_partition (list): The layer_partition is a list of (qu)bit
            lists and each qubit is a tuple (qreg, index).
        initial_layout (Layout): The initial layout passed.
        layout (Layout): The layout is a Layout object mapping virtual
            qubits in the input circuit to physical qubits in the coupling
            graph. It reflects the current positions of the data.
        qubit_subset (list): The qubit_subset is the set of qubits in
            the coupling graph that we have chosen to map into, as tuples
            (Register, index).
        coupling (CouplingMap): Directed graph representing a coupling map.
            This coupling map should be one that was provided to the
            stochastic mapper.
        trials (int): Number of attempts the randomized algorithm makes.
        qregs (OrderedDict): Ordered dict of registers from input DAG.
        rng (RandomState): Random number generator.

    Returns:
        Tuple: success_flag, best_circuit, best_depth, best_layout, trivial_flag

    Raises:
        TranspilerError: if anything went wrong.
     """
    logger.debug("layer_permutation: layer_partition = %s",
                 pformat(layer_partition))
    logger.debug("layer_permutation: layout = %s",
                 pformat(layout.get_virtual_bits()))
    logger.debug("layer_permutation: qubit_subset = %s",
                 pformat(qubit_subset))
    logger.debug("layer_permutation: trials = %s", trials)

    gates = []  # list of lists of tuples [[(register, index), ...], ...]
    for gate_args in layer_partition:
        if len(gate_args) > 2:
            raise TranspilerError("Layer contains > 2-qubit gates")
        elif len(gate_args) == 2:
            gates.append(tuple(gate_args))
    logger.debug("layer_permutation: gates = %s", pformat(gates))

    # Can we already apply the gates? If so, there is no work to do.
    dist = sum([coupling.distance(layout[g[0]], layout[g[1]])
                for g in gates])
    logger.debug("layer_permutation: distance = %s", dist)
    if dist == len(gates):
        logger.debug("layer_permutation: nothing to do")
        circ = DAGCircuit()
        for register in layout.get_virtual_bits().keys():
            if register[0] not in circ.qregs.values():
                circ.add_qreg(register[0])
        return True, circ, 0, layout, (not bool(gates))

    # Begin loop over trials of randomized algorithm
    num_qubits = len(layout)
    best_depth = inf  # initialize best depth
    best_edges = None  # best edges found
    best_circuit = None  # initialize best swap circuit
    best_layout = None  # initialize best final layout

    cdist2 = coupling._dist_matrix**2
    # Scaling matrix
    scale = np.zeros((num_qubits, num_qubits))

    int_qubit_subset = regtuple_to_numeric(qubit_subset, qregs)
    int_gates = gates_to_idx(gates, qregs)
    int_layout = nlayout_from_layout(layout, qregs, coupling.size())

    trial_circuit = DAGCircuit()  # SWAP circuit for this trial
    for register in layout.get_virtual_bits().keys():
        if register[0] not in trial_circuit.qregs.values():
            trial_circuit.add_qreg(register[0])

    slice_circuit = DAGCircuit()  # circuit for this swap slice
    for register in layout.get_virtual_bits().keys():
        if register[0] not in slice_circuit.qregs.values():
            slice_circuit.add_qreg(register[0])
    edges = np.asarray(coupling.get_edges(), dtype=np.int32).ravel()
    cdist = coupling._dist_matrix
    for trial in range(trials):
        logger.debug("layer_permutation: trial %s", trial)
        # This is one Trial --------------------------------------
        dist, optim_edges, trial_layout, depth_step = swap_trial(num_qubits, int_layout,
                                                                 int_qubit_subset,
                                                                 int_gates, cdist2,
                                                                 cdist, edges, scale,
                                                                 rng)

        logger.debug("layer_permutation: final distance for this trial = %s", dist)
        if dist == len(gates) and depth_step < best_depth:
            logger.debug("layer_permutation: got circuit with improved depth %s",
                         depth_step)
            best_edges = optim_edges
            best_layout = trial_layout
            best_depth = min(best_depth, depth_step)

        # Break out of trial loop if we found a depth 1 circuit
        # since we can't improve it further
        if best_depth == 1:
            break

    # If we have no best circuit for this layer, all of the
    # trials have failed
    if best_layout is None:
        logger.debug("layer_permutation: failed!")
        return False, None, None, None, False

    edgs = best_edges.edges()
    for idx in range(best_edges.size//2):
        slice_circuit.apply_operation_back(
            SwapGate(), [initial_layout[edgs[2*idx]], initial_layout[edgs[2*idx+1]]], [])
    trial_circuit.extend_back(slice_circuit)
    best_circuit = trial_circuit

    # Otherwise, we return our result for this layer
    logger.debug("layer_permutation: success!")
    best_lay = best_layout.to_layout(qregs)
    return True, best_circuit, best_depth, best_lay, False
Find a swap circuit that implements a permutation for this layer.

    Args:
        layer_partition (list): The layer_partition is a list of (qu)bit
            lists and each qubit is a tuple (qreg, index).
        initial_layout (Layout): The initial layout passed.
        layout (Layout): The layout is a Layout object mapping virtual
            qubits in the input circuit to physical qubits in the coupling
            graph. It reflects the current positions of the data.
        qubit_subset (list): The qubit_subset is the set of qubits in
            the coupling graph that we have chosen to map into, as tuples
            (Register, index).
        coupling (CouplingMap): Directed graph representing a coupling map.
            This coupling map should be one that was provided to the
            stochastic mapper.
        trials (int): Number of attempts the randomized algorithm makes.
        qregs (OrderedDict): Ordered dict of registers from input DAG.
        rng (RandomState): Random number generator.

    Returns:
        Tuple: success_flag, best_circuit, best_depth, best_layout, trivial_flag

    Raises:
        TranspilerError: if anything went wrong.