Skip to content

Greedy

Greedy shortest-path move generator.

GreedyMoveGenerator dataclass 

GreedyMoveGenerator(target: dict[int, LocationAddress])

Greedy shortest-path move generator.

For each unresolved qubit, computes the shortest path to its target while routing around all other atoms (but not itself) and takes the first lane. Those first-step lanes are grouped by (move_type, bus_id, direction) and partitioned into AOD-compatible rectangular grids via BusContext.

target instance-attribute 

target: dict[int, LocationAddress]

Mapping of qubit ID to target location.

generate 

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

Yield candidate move sets.

Steps: 1. For each qubit, find shortest path to target routing around all other atoms (but not itself). 2. Take the first lane from each path. 3. Group by (move_type, bus_id, direction). 4. Build AOD-compatible rectangular grids per group.

Source code in .venv/lib/python3.12/site-packages/bloqade/lanes/search/generators/greedy.py 
35
36
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
def generate(
    self,
    node: ConfigurationNode,
    tree: ConfigurationTree,
) -> Iterator[frozenset[LaneAddress]]:
    """Yield candidate move sets.

    Steps:
    1. For each qubit, find shortest path to target routing around
       all other atoms (but not itself).
    2. Take the first lane from each path.
    3. Group by (move_type, bus_id, direction).
    4. Build AOD-compatible rectangular grids per group.
    """
    occupied = node.occupied_locations | tree.blocked_locations

    first_lanes: dict[int, LaneAddress] = {}
    for qid, current in node.configuration.items():
        target_loc = self.target.get(qid)
        if target_loc is None or current == target_loc:
            continue

        result = tree.path_finder.find_path(
            current, target_loc, occupied=occupied - {current}
        )
        if result is None:
            continue

        lanes, _ = result
        if lanes:
            first_lanes[qid] = lanes[0]

    if not first_lanes:
        return

    groups: dict[
        tuple[MoveType, int, Direction],
        dict[int, LaneAddress],
    ] = {}
    for qid, lane in first_lanes.items():
        key = (lane.move_type, lane.bus_id, lane.direction)
        groups.setdefault(key, {})[qid] = lane

    for (mt, bid, d), entries in groups.items():
        ctx = BusContext.from_tree(tree, occupied, mt, bid, d)
        yield from ctx.build_aod_grids(entries)