Skip to content

Heuristic

Entropy-weighted heuristic move generator.

HeuristicMoveGenerator dataclass 

HeuristicMoveGenerator(
    scorer: CandidateScorer,
    params: SearchParams,
    search_nodes: dict[int, EntropyNode],
)

Generates ranked candidate movesets using entropy-weighted scoring.

Implements the MoveGenerator protocol. The traversal sets search_nodes before the search loop begins so the generator can read per-node entropy.

search_nodes instance-attribute 

search_nodes: dict[int, EntropyNode]

Mapping of id(ConfigurationNode) -> entropy metadata node.

generate 

generate(
    node: ConfigurationNode, tree: ConfigurationTree
) -> Iterator[frozenset[LaneAddress]]

Yield candidate movesets ranked by moveset score (descending).

Steps: 1. Get entropy from traversal metadata node. 2. Score all (qubit, move_type, bus_id, direction) pairs. 3. Per-qubit: keep top C triples. 4. Group by (move_type, bus_id, direction), collect positive-score qubits. 5. Resolve conflicts within each group (greedy by score). 6. Build moveset per group, score with score_moveset, sort descending.

Source code in .venv/lib/python3.12/site-packages/bloqade/lanes/search/generators/heuristic.py 
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
def generate(
    self,
    node: ConfigurationNode,
    tree: ConfigurationTree,
) -> Iterator[frozenset[LaneAddress]]:
    """Yield candidate movesets ranked by moveset score (descending).

    Steps:
    1. Get entropy from traversal metadata node.
    2. Score all (qubit, move_type, bus_id, direction) pairs.
    3. Per-qubit: keep top C triples.
    4. Group by (move_type, bus_id, direction), collect positive-score qubits.
    5. Resolve conflicts within each group (greedy by score).
    6. Build moveset per group, score with score_moveset, sort descending.
    """
    search_node = self.search_nodes.get(id(node))
    entropy = search_node.entropy if search_node is not None else 1

    scores = self.scorer.score_all_qubit_bus_pairs(node, entropy, tree)
    if not scores:
        return

    # Per-qubit: keep top C (move_type, bus_id, direction) triples
    qubit_top: dict[int, list[tuple[MoveType, int, Direction, float]]] = {}
    for (qid, mt, bid, d), score in scores.items():
        qubit_top.setdefault(qid, []).append((mt, bid, d, score))

    for qid in qubit_top:
        qubit_top[qid].sort(key=lambda x: x[3], reverse=True)
        qubit_top[qid] = qubit_top[qid][: self.params.top_c]

    # Group by (move_type, bus_id, direction): collect positive-scoring qubits
    groups: dict[
        tuple[MoveType, int, Direction],
        list[tuple[int, float]],
    ] = {}
    for qid, top_triples in qubit_top.items():
        for mt, bid, d, score in top_triples:
            if score > 0:
                groups.setdefault((mt, bid, d), []).append((qid, score))

    # Fallback: if no group has positive-scoring qubits, use best single entry
    if not groups:
        best_key = max(scores, key=lambda key: scores[key])
        qid, mt, bid, d = best_key
        groups[(mt, bid, d)] = [(qid, scores[best_key])]

    # Build one moveset per group with conflict resolution
    occupied = node.occupied_locations | tree.blocked_locations
    candidates: list[tuple[float, frozenset[LaneAddress]]] = []

    for (mt, bid, d), qubit_scores in groups.items():
        # Sort qubits by score descending for greedy conflict resolution
        qubit_scores.sort(key=lambda x: x[1], reverse=True)

        lanes: list[LaneAddress] = []
        used_dsts: set[LocationAddress] = set()

        for qid, _ in qubit_scores:
            loc = node.configuration[qid]
            lane = tree.lane_for_source(mt, bid, d, loc)
            if lane is None:
                continue
            _, dst = tree.arch_spec.get_endpoints(lane)
            if dst in occupied:
                continue
            # Destination conflict: another qubit in this group targets same dst
            if dst in used_dsts:
                continue
            # Lane compatibility check with existing lanes in this group
            if lanes and not all(
                tree.arch_spec.compatible_lanes(lane, existing)
                for existing in lanes
            ):
                continue
            lanes.append(lane)
            used_dsts.add(dst)

        if not lanes:
            continue

        moveset = frozenset(lanes)
        ms_score = self.scorer.score_moveset(moveset, node, tree)
        candidates.append((ms_score, moveset))

    # Sort by moveset score descending
    candidates.sort(key=lambda x: x[0], reverse=True)

    for _, moveset in candidates:
        yield moveset