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):
    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 ) : 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.
Search for SWAPs which allow for application of largest number of gates .