qiskit/transpiler/passes/mapping/lookahead_swap.py
def _search_forward_n_swaps(layout, gates, coupling_map,
                            depth=SEARCH_DEPTH, width=SEARCH_WIDTH):
    """Search for SWAPs which allow for application of largest number of gates.

    Arguments:
        layout (Layout): Map from virtual qubit index to physical qubit index.
        gates (list): Gates to be mapped.
        coupling_map (CouplingMap): CouplingMap of the target backend.
        depth (int): Number of SWAP layers to search before choosing a result.
        width (int): Number of SWAPs to consider at each layer.
    Returns:
        dict: Describes solution step found.
            layout (Layout): Virtual to physical qubit map after SWAPs.
            gates_remaining (list): Gates that could not be mapped.
            gates_mapped (list): Gates that were mapped, including added SWAPs.

    """

    gates_mapped, gates_remaining = _map_free_gates(layout, gates, coupling_map)

    base_step = {'layout': layout,
                 'swaps_added': 0,
                 'gates_mapped': gates_mapped,
                 'gates_remaining': gates_remaining}

    if not gates_remaining or depth == 0:
        return base_step

    possible_swaps = coupling_map.get_edges()

    def _score_swap(swap):
        """Calculate the relative score for a given SWAP."""
        trial_layout = layout.copy()
        trial_layout.swap(*swap)
        return _calc_layout_distance(gates, coupling_map, trial_layout)

    ranked_swaps = sorted(possible_swaps, key=_score_swap)

    best_swap, best_step = None, None
    for swap in ranked_swaps[:width]:
        trial_layout = layout.copy()
        trial_layout.swap(*swap)
        next_step = _search_forward_n_swaps(trial_layout, gates_remaining,
                                            coupling_map, depth - 1, width)

        # ranked_swaps already sorted by distance, so distance is the tie-breaker.
        if best_swap is None or _score_step(next_step) > _score_step(best_step):
            best_swap, best_step = swap, next_step

    best_swap_gate = _swap_ops_from_edge(best_swap, layout)
    return {
        'layout': best_step['layout'],
        'swaps_added': 1 + best_step['swaps_added'],
        'gates_remaining': best_step['gates_remaining'],
        'gates_mapped': gates_mapped + best_swap_gate + best_step['gates_mapped'],
    }
def _search_forward_n_swaps(layout, gates, coupling_map,
                            depth=SEARCH_DEPTH, width=SEARCH_WIDTH):
    """Search for SWAPs which allow for application of largest number of gates.

    Arguments:
        layout (Layout): Map from virtual qubit index to physical qubit index.
        gates (list): Gates to be mapped.
        coupling_map (CouplingMap): CouplingMap of the target backend.
        depth (int): Number of SWAP layers to search before choosing a result.
        width (int): Number of SWAPs to consider at each layer.
    Returns:
        dict: Describes solution step found.
            layout (Layout): Virtual to physical qubit map after SWAPs.
            gates_remaining (list): Gates that could not be mapped.
            gates_mapped (list): Gates that were mapped, including added SWAPs.

    """

    gates_mapped, gates_remaining = _map_free_gates(layout, gates, coupling_map)

    base_step = {'layout': layout,
                 'swaps_added': 0,
                 'gates_mapped': gates_mapped,
                 'gates_remaining': gates_remaining}

    if not gates_remaining or depth == 0:
        return base_step

    possible_swaps = coupling_map.get_edges()

    def _score_swap(swap):
        """Calculate the relative score for a given SWAP."""
        trial_layout = layout.copy()
        trial_layout.swap(*swap)
        return _calc_layout_distance(gates, coupling_map, trial_layout)

    ranked_swaps = sorted(possible_swaps, key=_score_swap)

    best_swap, best_step = None, None
    for swap in ranked_swaps[:width]:
        trial_layout = layout.copy()
        trial_layout.swap(*swap)
        next_step = _search_forward_n_swaps(trial_layout, gates_remaining,
                                            coupling_map, depth - 1, width)

        # ranked_swaps already sorted by distance, so distance is the tie-breaker.
        if best_swap is None or _score_step(next_step) > _score_step(best_step):
            best_swap, best_step = swap, next_step

    best_swap_gate = _swap_ops_from_edge(best_swap, layout)
    return {
        'layout': best_step['layout'],
        'swaps_added': 1 + best_step['swaps_added'],
        'gates_remaining': best_step['gates_remaining'],
        'gates_mapped': gates_mapped + best_swap_gate + best_step['gates_mapped'],
    }
Search for SWAPs which allow for application of largest number of gates.

    Arguments:
        layout (Layout): Map from virtual qubit index to physical qubit index.
        gates (list): Gates to be mapped.
        coupling_map (CouplingMap): CouplingMap of the target backend.
        depth (int): Number of SWAP layers to search before choosing a result.
        width (int): Number of SWAPs to consider at each layer.
    Returns:
        dict: Describes solution step found.
            layout (Layout): Virtual to physical qubit map after SWAPs.
            gates_remaining (list): Gates that could not be mapped.
            gates_mapped (list): Gates that were mapped, including added SWAPs.