Tree

Configuration tree for exploring valid atom move programs.

ConfigurationTree dataclass

ConfigurationTree(
    arch_spec: ArchSpec,
    root: ConfigurationNode,
    blocked_locations: frozenset[
        LocationAddress
    ] = frozenset(),
)

Tree that explores the space of valid atom configurations.

Starting from an initial placement, the tree manages the transposition table and validates move sets. Move generation and node expansion are delegated to MoveGenerator implementations.

NOTE: If deadlock density is high, consider refactoring to a DAG (directed acyclic graph) where nodes can have multiple parents. This enables backward propagation of deadlock information — when a subtree is exhausted, all parents are notified and can prune early. Currently the transposition table prevents re-expanding seen configurations, but does not propagate deadlock status upstream.

apply_move_set

apply_move_set(
    node: ConfigurationNode,
    move_set: frozenset[LaneAddress],
    strict: bool = True,
) -> ConfigurationNode | None

Apply a move set to a node, returning a new child or None.

Resolves lane endpoints, checks for collisions, and creates a child node if valid.

The move set is first validated against the arch spec (AOD geometry, consistency, bus membership). This check runs as an assert and is independent of strict — it signals an internal bug, not a recoverable runtime condition. It can be disabled with python -O.

Parameters:

Name	Type	Description	Default
node	ConfigurationNode	The node to apply moves to.	required
move_set	frozenset[LaneAddress]	The set of lane addresses to apply.	required
strict	bool	If True (default), raises InvalidMoveError when a move set causes a collision. If False, silently returns None for invalid moves.	True

Returns:

Type	Description
ConfigurationNode | None	A new ConfigurationNode, or None if:
ConfigurationNode | None	The move is invalid and strict=False
ConfigurationNode | None	The configuration was already reached via a different branch at equal-or-lesser depth (transposition table)

Raises:

Type	Description
AssertionError	If the move set fails lane-group validation (regardless of strict; disabled with python -O).
InvalidMoveError	If strict=True and the move set causes a collision or contains an invalid lane address.

Source code in .venv/lib/python3.12/site-packages/bloqade/lanes/search/tree.py

def apply_move_set(
    self,
    node: ConfigurationNode,
    move_set: frozenset[LaneAddress],
    strict: bool = True,
) -> ConfigurationNode | None:
    """Apply a move set to a node, returning a new child or None.

    Resolves lane endpoints, checks for collisions, and creates
    a child node if valid.

    The move set is first validated against the arch spec (AOD
    geometry, consistency, bus membership).  This check runs as an
    ``assert`` and is independent of *strict* — it signals an
    internal bug, not a recoverable runtime condition.  It can be
    disabled with ``python -O``.

    Args:
        node: The node to apply moves to.
        move_set: The set of lane addresses to apply.
        strict: If True (default), raises InvalidMoveError when a
            move set causes a collision. If False, silently returns
            None for invalid moves.

    Returns:
        A new ConfigurationNode, or None if:
        - The move is invalid and strict=False
        - The configuration was already reached via a different
          branch at equal-or-lesser depth (transposition table)

    Raises:
        AssertionError: If the move set fails lane-group validation
            (regardless of *strict*; disabled with ``python -O``).
        InvalidMoveError: If strict=True and the move set causes a
            collision or contains an invalid lane address.
    """
    outcome = self.try_move_set(node, move_set, strict=strict)
    return (
        outcome.child if outcome.status == ExpansionStatus.CREATED_CHILD else None
    )

expand_node

expand_node(
    node: ConfigurationNode,
    generator: MoveGenerator,
    strict: bool = True,
) -> list[ConfigurationNode]

Expand a node using the given generator.

Generates candidate move sets, validates each (collision checks, transposition table), and creates child nodes. Nodes already seen at equal-or-lesser depth are skipped.

Parameters:

Name	Type	Description	Default
node	ConfigurationNode	The node to expand.	required
generator	MoveGenerator	Produces candidate move sets.	required
strict	bool	If True, raises on invalid moves. If False, skips them.	True

Returns:

Type	Description
list[ConfigurationNode]	List of newly created child nodes (may be empty).

Source code in .venv/lib/python3.12/site-packages/bloqade/lanes/search/tree.py

def expand_node(
    self,
    node: ConfigurationNode,
    generator: MoveGenerator,
    strict: bool = True,
) -> list[ConfigurationNode]:
    """Expand a node using the given generator.

    Generates candidate move sets, validates each (collision checks,
    transposition table), and creates child nodes. Nodes already
    seen at equal-or-lesser depth are skipped.

    Args:
        node: The node to expand.
        generator: Produces candidate move sets.
        strict: If True, raises on invalid moves. If False, skips them.

    Returns:
        List of newly created child nodes (may be empty).
    """
    children: list[ConfigurationNode] = []
    for outcome in self.expand_node_detailed(node, generator, strict=strict):
        if outcome.status == ExpansionStatus.CREATED_CHILD:
            assert outcome.child is not None
            children.append(outcome.child)
    return children

expand_node_detailed

expand_node_detailed(
    node: ConfigurationNode,
    generator: MoveGenerator,
    strict: bool = True,
) -> Iterator[ExpansionOutcome]

Expand a node and yield one outcome per generated candidate.

Source code in .venv/lib/python3.12/site-packages/bloqade/lanes/search/tree.py

def expand_node_detailed(
    self,
    node: ConfigurationNode,
    generator: MoveGenerator,
    strict: bool = True,
) -> Iterator[ExpansionOutcome]:
    """Expand a node and yield one outcome per generated candidate."""
    for move_set in generator.generate(node, self):
        yield self.try_move_set(node, move_set, strict=strict)

from_initial_placement classmethod

from_initial_placement(
    arch_spec: ArchSpec,
    placement: dict[int, LocationAddress],
    blocked_locations: frozenset[
        LocationAddress
    ] = frozenset(),
) -> ConfigurationTree

Create a tree from an initial qubit placement.

Parameters:

Name	Type	Description	Default
arch_spec	ArchSpec	Architecture specification for lane validation.	required
placement	dict[int, LocationAddress]	Mapping of qubit IDs to their initial locations.	required

Returns:

Type	Description
ConfigurationTree	A new ConfigurationTree rooted at the given placement.

Source code in .venv/lib/python3.12/site-packages/bloqade/lanes/search/tree.py

@classmethod
def from_initial_placement(
    cls,
    arch_spec: ArchSpec,
    placement: dict[int, LocationAddress],
    blocked_locations: frozenset[LocationAddress] = frozenset(),
) -> ConfigurationTree:
    """Create a tree from an initial qubit placement.

    Args:
        arch_spec: Architecture specification for lane validation.
        placement: Mapping of qubit IDs to their initial locations.

    Returns:
        A new ConfigurationTree rooted at the given placement.
    """
    root = ConfigurationNode(configuration=dict(placement))
    return cls(
        arch_spec=arch_spec,
        root=root,
        blocked_locations=frozenset(blocked_locations),
    )

lane_for_source

lane_for_source(
    move_type: MoveType,
    bus_id: int,
    direction: Direction,
    source: LocationAddress,
) -> LaneAddress | None

Resolve one lane by source for a specific triplet.

Source code in .venv/lib/python3.12/site-packages/bloqade/lanes/search/tree.py

def lane_for_source(
    self,
    move_type: MoveType,
    bus_id: int,
    direction: Direction,
    source: LocationAddress,
) -> LaneAddress | None:
    """Resolve one lane by source for a specific triplet."""
    return self._lane_by_src[(move_type, bus_id, direction)].get(source)

lanes_for

lanes_for(
    move_type: MoveType, bus_id: int, direction: Direction
) -> Iterator[LaneAddress]

Yield all lane addresses for a specific (move_type, bus_id, direction).

Parameters:

Name	Type	Description	Default
move_type	MoveType	The move type (SITE or WORD).	required
bus_id	int	The bus index.	required
direction	Direction	The direction (FORWARD or BACKWARD).	required

Yields:

Type	Description
LaneAddress	LaneAddress values.

Source code in .venv/lib/python3.12/site-packages/bloqade/lanes/search/tree.py

def lanes_for(
    self,
    move_type: MoveType,
    bus_id: int,
    direction: Direction,
) -> Iterator[LaneAddress]:
    """Yield all lane addresses for a specific (move_type, bus_id, direction).

    Args:
        move_type: The move type (SITE or WORD).
        bus_id: The bus index.
        direction: The direction (FORWARD or BACKWARD).

    Yields:
        LaneAddress values.
    """
    yield from self._lanes_by_triplet[(move_type, bus_id, direction)]

outgoing_lanes

outgoing_lanes(
    source: LocationAddress,
) -> tuple[LaneAddress, ...]

Return all precomputed outgoing lanes from source.

Source code in .venv/lib/python3.12/site-packages/bloqade/lanes/search/tree.py

def outgoing_lanes(self, source: LocationAddress) -> tuple[LaneAddress, ...]:
    """Return all precomputed outgoing lanes from source."""
    return self._outgoing_lanes_by_src.get(source, ())

try_move_set

try_move_set(
    node: ConfigurationNode,
    move_set: frozenset[LaneAddress],
    strict: bool = True,
) -> ExpansionOutcome

Attempt one move set and return a detailed outcome.

In strict mode, invalid lanes and collisions raise InvalidMoveError (matching apply_move_set behavior). In non-strict mode, they are returned as INVALID_LANE/COLLISION outcomes.

Source code in .venv/lib/python3.12/site-packages/bloqade/lanes/search/tree.py

def try_move_set(
    self,
    node: ConfigurationNode,
    move_set: frozenset[LaneAddress],
    strict: bool = True,
) -> ExpansionOutcome:
    """Attempt one move set and return a detailed outcome.

    In strict mode, invalid lanes and collisions raise InvalidMoveError
    (matching apply_move_set behavior). In non-strict mode, they are
    returned as INVALID_LANE/COLLISION outcomes.
    """
    lane_errors = self.arch_spec.check_lane_group(list(move_set))
    if lane_errors:
        msg = f"Move set failed lane-group validation: {'; '.join(str(e) for e in lane_errors)}"
        if strict:
            raise InvalidMoveError(msg)
        return ExpansionOutcome(
            move_set=move_set,
            status=ExpansionStatus.INVALID_LANE,
            error_message=msg,
        )

    existing_child = node.children.get(move_set)
    if existing_child is not None:
        return ExpansionOutcome(
            move_set=move_set,
            status=ExpansionStatus.ALREADY_CHILD,
            child=existing_child,
        )

    new_config = dict(node.configuration)
    occupied = node.occupied_locations
    blocked = self.blocked_locations

    for lane in move_set:
        try:
            src, dst = self.arch_spec.get_endpoints(lane)
        except Exception as e:
            msg = f"Invalid lane address {lane!r}: {e}"
            if strict:
                raise InvalidMoveError(msg) from e
            return ExpansionOutcome(
                move_set=move_set,
                status=ExpansionStatus.INVALID_LANE,
                error_message=msg,
            )

        qid = node.get_qubit_at(src)
        if qid is None:
            continue

        # Bus src and dst are disjoint sets, so within a single-bus
        # move set, two sources cannot map to the same destination.
        # We only need to check against stationary atoms.
        if dst in occupied or dst in blocked:
            blocker = node.get_qubit_at(dst)
            blocker_text = (
                f"qubit {blocker}" if blocker is not None else "a blocked location"
            )
            msg = (
                f"Collision: qubit {qid} moving to {dst!r} "
                f"which is occupied by {blocker_text}"
            )
            if strict:
                raise InvalidMoveError(msg)
            return ExpansionOutcome(
                move_set=move_set,
                status=ExpansionStatus.COLLISION,
                error_message=msg,
            )

        new_config[qid] = dst

    # Check transposition table
    new_node = ConfigurationNode(
        configuration=new_config,
        parent=node,
        parent_moves=move_set,
        depth=node.depth + 1,
    )
    key = new_node.config_key

    if key in self.seen:
        existing = self.seen[key]
        if existing.depth <= new_node.depth:
            return ExpansionOutcome(
                move_set=move_set,
                status=ExpansionStatus.TRANSPOSITION_SEEN,
                existing_node=existing,
            )

    # Register in transposition table and add as child
    self.seen[key] = new_node
    node.children[move_set] = new_node
    return ExpansionOutcome(
        move_set=move_set,
        status=ExpansionStatus.CREATED_CHILD,
        child=new_node,
    )

valid_lanes

valid_lanes(
    node: ConfigurationNode,
    move_type: MoveType | None = None,
    bus_id: int | None = None,
    direction: Direction | None = None,
) -> Iterator[LaneAddress]

Yield valid individual lane addresses from a configuration.

A lane is valid if its source is occupied and its destination is not occupied. Optionally filter by move_type, bus_id, and direction — None means include all.

Parameters:

Name	Type	Description	Default
node	ConfigurationNode	The configuration to query.	required
move_type	MoveType | None	Filter to this move type, or None for all.	None
bus_id	int | None	Filter to this bus ID, or None for all.	None
direction	Direction | None	Filter to this direction, or None for all.	None

Yields:

Type	Description
LaneAddress	Valid LaneAddress values.

Source code in .venv/lib/python3.12/site-packages/bloqade/lanes/search/tree.py

def valid_lanes(
    self,
    node: ConfigurationNode,
    move_type: MoveType | None = None,
    bus_id: int | None = None,
    direction: Direction | None = None,
) -> Iterator[LaneAddress]:
    """Yield valid individual lane addresses from a configuration.

    A lane is valid if its source is occupied and its destination
    is not occupied. Optionally filter by move_type, bus_id, and
    direction — None means include all.

    Args:
        node: The configuration to query.
        move_type: Filter to this move type, or None for all.
        bus_id: Filter to this bus ID, or None for all.
        direction: Filter to this direction, or None for all.

    Yields:
        Valid LaneAddress values.
    """
    occupied = node.occupied_locations
    blocked = self.blocked_locations

    move_types = (
        [move_type] if move_type is not None else [MoveType.SITE, MoveType.WORD]
    )
    directions = (
        [direction]
        if direction is not None
        else [Direction.FORWARD, Direction.BACKWARD]
    )

    for mt in move_types:
        buses = (
            self.arch_spec.site_buses
            if mt == MoveType.SITE
            else self.arch_spec.word_buses
        )
        bus_ids = [bus_id] if bus_id is not None else list(range(len(buses)))

        for bid in bus_ids:
            for d in directions:
                for lane in self.lanes_for(mt, bid, d):
                    src, dst = self.arch_spec.get_endpoints(lane)
                    if (
                        src in occupied
                        and dst not in occupied
                        and dst not in blocked
                    ):
                        yield lane

ExpansionOutcome dataclass

ExpansionOutcome(
    move_set: frozenset[LaneAddress],
    status: ExpansionStatus,
    child: ConfigurationNode | None = None,
    existing_node: ConfigurationNode | None = None,
    error_message: str | None = None,
)

Detailed result for one attempted move-set expansion.

ExpansionStatus

Bases: str, Enum

Outcome status for one move-set expansion attempt.

InvalidMoveError

Bases: Exception

Raised when a generator produces an invalid move set in strict mode.