Index

Tree traversal strategies for configuration search.

CostFunction module-attribute

CostFunction = Callable[[ConfigurationNode], float]

Computes the accumulated cost of reaching a node. Lower is better.

GoalPredicate module-attribute

GoalPredicate = Callable[[ConfigurationNode], bool]

Returns True if the node satisfies the search goal.

HeuristicFunction module-attribute

HeuristicFunction = Callable[[ConfigurationNode], float]

Estimates the cost from a node to the goal. Lower is better.

AStarTraversal dataclass

AStarTraversal(
    heuristic: HeuristicFunction,
    cost: CostFunction | None = None,
)

Bases: TraversalStrategyABC

A* traversal policy.

search

search(
    *,
    tree: ConfigurationTree,
    generator: MoveGenerator,
    goal: GoalPredicate,
    max_expansions: int | None = None,
    max_depth: int | None = None
) -> SearchResult

Execute search over the tree using the supplied generator.

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

def search(
    self,
    *,
    tree: ConfigurationTree,
    generator: MoveGenerator,
    goal: GoalPredicate,
    max_expansions: int | None = None,
    max_depth: int | None = None,
) -> SearchResult:
    _ = max_depth
    cost_fn: CostFunction = (
        self.cost if self.cost is not None else lambda node: float(node.depth)
    )
    frontier: list[PriorityEntry] = []
    root_f = cost_fn(tree.root) + self.heuristic(tree.root)
    heapq.heappush(frontier, PriorityEntry(root_f, tree.root))
    return run_frontier_search(
        tree=tree,
        generator=generator,
        goal=goal,
        pop_next=lambda: heapq.heappop(frontier).node if frontier else None,
        push_child=lambda child: heapq.heappush(
            frontier, PriorityEntry(cost_fn(child) + self.heuristic(child), child)
        ),
        frontier_has_items=lambda: bool(frontier),
        max_expansions=max_expansions,
        max_depth=None,
        goal_on_pop=True,
    )

BFSTraversal

Bases: TraversalStrategyABC

Breadth-first traversal policy.

search

search(
    *,
    tree: ConfigurationTree,
    generator: MoveGenerator,
    goal: GoalPredicate,
    max_expansions: int | None = None,
    max_depth: int | None = None
) -> SearchResult

Execute search over the tree using the supplied generator.

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

def search(
    self,
    *,
    tree: ConfigurationTree,
    generator: MoveGenerator,
    goal: GoalPredicate,
    max_expansions: int | None = None,
    max_depth: int | None = None,
) -> SearchResult:
    frontier: deque[ConfigurationNode] = deque([tree.root])
    return run_frontier_search(
        tree=tree,
        generator=generator,
        goal=goal,
        pop_next=lambda: frontier.popleft() if frontier else None,
        push_child=frontier.append,
        frontier_has_items=lambda: bool(frontier),
        max_expansions=max_expansions,
        max_depth=max_depth,
        goal_on_pop=False,
    )

DescendStepInfo dataclass

DescendStepInfo(
    entropy: int,
    unresolved_count: int,
    candidate_movesets: tuple[
        frozenset[LaneAddress], ...
    ] = (),
    candidate_index: int | None = None,
    moveset: frozenset[LaneAddress] = frozenset(),
    moveset_score: float = 0.0,
    score_breakdown: dict = dict(),
)

Bases: StepInfo

Metadata emitted when the search descends to a new child node.

EntropyBumpStepInfo dataclass

EntropyBumpStepInfo(
    entropy: int,
    unresolved_count: int,
    candidate_movesets: tuple[
        frozenset[LaneAddress], ...
    ] = (),
    candidate_index: int | None = None,
    new_entropy: int = 0,
    reason: str = "",
    no_valid_moves_qubit: int | None = None,
    state_seen_node_id: int | None = None,
    attempted_moveset: frozenset[LaneAddress] = frozenset(),
)

Bases: StepInfo

Metadata emitted when a node's entropy is incremented.

EntropyGuidedSearch

EntropyGuidedSearch(
    tree: ConfigurationTree,
    target: dict[int, LocationAddress],
    goal: GoalPredicate,
    params: SearchParams = SearchParams(),
    max_depth: int | None = None,
    max_expansions: int | None = None,
    on_step: (
        Callable[[str, ConfigurationNode, StepInfo], None]
        | None
    ) = None,
)

Entropy-guided depth-first search with reversion and sequential fallback.

Encapsulates the internal state of the search so that helper methods can access shared context (tree, target, params, etc.) without requiring long parameter lists.

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

def __init__(
    self,
    tree: ConfigurationTree,
    target: dict[int, LocationAddress],
    goal: GoalPredicate,
    params: SearchParams = SearchParams(),
    max_depth: int | None = None,
    max_expansions: int | None = None,
    on_step: Callable[[str, ConfigurationNode, StepInfo], None] | None = None,
) -> None:
    self.tree = tree
    self.target = target
    self.goal = goal
    self.params = params
    self.max_depth = max_depth
    self.max_expansions = max_expansions

    self.scorer = CandidateScorer(params=params, target=target)
    self.search_nodes: dict[int, _SearchNode] = {}
    self.debug = _DebugEmitter(scorer=self.scorer, tree=tree, on_step=on_step)
    self.nodes_expanded = 0
    self.max_depth_reached = 0

run

run(generator: MoveGenerator) -> SearchResult

Execute the entropy-guided search and return the result.

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

def run(self, generator: MoveGenerator) -> SearchResult:
    """Execute the entropy-guided search and return the result."""
    found_goals: list[ConfigurationNode] = []
    if self.goal(self.tree.root):
        self.debug.goal(self.tree.root, entropy=0)
        return SearchResult(
            nodes_expanded=0,
            max_depth_reached=0,
            goal_nodes=(self.tree.root,),
        )

    current_node = self.tree.root

    while self.max_expansions is None or self.nodes_expanded < self.max_expansions:
        sn = self._get_or_create_search_node(current_node)
        if self.max_depth is not None and current_node.depth >= self.max_depth:
            sn.force_entropy(self.params.e_max)

        if sn.entropy >= self.params.e_max:
            ancestor = current_node
            for _ in range(self.params.reversion_steps):
                if ancestor.parent is None:
                    break
                ancestor = ancestor.parent

            ancestor_sn = self._get_or_create_search_node(ancestor)
            if ancestor.parent is None and ancestor_sn.entropy >= self.params.e_max:
                fallback_result = self._sequential_fallback(self.tree.root)
                combined_goals = found_goals + list(fallback_result.goal_nodes)
                return self._make_result(goal_nodes=tuple(combined_goals))

            ancestor_sn.bump_entropy(self.params.delta_e)
            self.debug.revert(ancestor, ancestor_sn, sn)
            current_node = ancestor
            continue

        candidate = self._get_next_candidate(sn, current_node, generator)

        if candidate is None:
            no_valid_qid = self._first_unresolved_qubit_without_valid_move(
                current_node
            )
            sn.bump_entropy(
                self.params.delta_e,
                "no-valid-moves",
                no_valid_moves_qubit=no_valid_qid,
            )
            self.debug.entropy_bump(current_node, sn)
            continue

        outcome = self.tree.try_move_set(current_node, candidate, strict=False)
        sn.candidates_tried += 1

        if outcome.status != ExpansionStatus.CREATED_CHILD:
            if outcome.status == ExpansionStatus.TRANSPOSITION_SEEN:
                reason = "state-seen"
                seen_node_id = (
                    id(outcome.existing_node)
                    if outcome.existing_node is not None
                    else None
                )
                no_valid_qid = None
            else:
                reason = "no-valid-moves"
                seen_node_id = None
                no_valid_qid = self._first_unresolved_qubit_without_valid_move(
                    current_node
                )

            sn.bump_entropy(
                self.params.delta_e,
                reason,
                no_valid_moves_qubit=no_valid_qid,
                state_seen_node_id=seen_node_id,
            )
            self.debug.entropy_bump(current_node, sn)
            continue
        assert outcome.child is not None
        child = outcome.child

        self.nodes_expanded += 1
        self.max_depth_reached = max(self.max_depth_reached, child.depth)
        self.debug.descend(child, sn, candidate, current_node)

        if self.goal(child):
            self.debug.goal(child, entropy=sn.entropy)
            found_goals.append(child)
            if len(found_goals) >= self.params.max_goal_candidates:
                return self._make_result(goal_nodes=tuple(found_goals))
            current_node = self._cutoff_ancestor(child)
            continue

        current_node = child

    return self._make_result(goal_nodes=tuple(found_goals))

EntropyGuidedTraversal dataclass

EntropyGuidedTraversal(
    target: dict[int, LocationAddress],
    params: SearchParams = SearchParams(),
    on_step: (
        Callable[[str, ConfigurationNode, StepInfo], None]
        | None
    ) = None,
)

Bases: TraversalStrategyABC

Traversal strategy adapter for entropy-guided search.

search

search(
    *,
    tree: ConfigurationTree,
    generator: MoveGenerator,
    goal: GoalPredicate,
    max_expansions: int | None = None,
    max_depth: int | None = None
) -> SearchResult

Execute search over the tree using the supplied generator.

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

def search(
    self,
    *,
    tree: ConfigurationTree,
    generator: MoveGenerator,
    goal: GoalPredicate,
    max_expansions: int | None = None,
    max_depth: int | None = None,
) -> SearchResult:
    search = EntropyGuidedSearch(
        tree=tree,
        target=self.target,
        goal=goal,
        params=self.params,
        max_depth=max_depth,
        max_expansions=max_expansions,
        on_step=self.on_step,
    )
    if isinstance(generator, HeuristicMoveGenerator):
        entropy_view: dict[int, EntropyNode] = search.search_nodes  # type: ignore[assignment]
        generator.search_nodes = entropy_view
    return search.run(generator=generator)

FallbackStartStepInfo dataclass

FallbackStartStepInfo(
    entropy: int,
    unresolved_count: int,
    candidate_movesets: tuple[
        frozenset[LaneAddress], ...
    ] = (),
    candidate_index: int | None = None,
    unresolved_qubits: list[int] = list(),
)

Bases: StepInfo

Metadata emitted when the sequential fallback begins.

FallbackStepInfo dataclass

FallbackStepInfo(
    entropy: int,
    unresolved_count: int,
    candidate_movesets: tuple[
        frozenset[LaneAddress], ...
    ] = (),
    candidate_index: int | None = None,
    qubit_id: int | None = None,
    moveset: frozenset[LaneAddress] = frozenset(),
)

Bases: StepInfo

Metadata emitted for each step of the sequential fallback.

GoalStepInfo dataclass

GoalStepInfo(
    entropy: int,
    unresolved_count: int,
    candidate_movesets: tuple[
        frozenset[LaneAddress], ...
    ] = (),
    candidate_index: int | None = None,
    total_depth: int = 0,
)

Bases: StepInfo

Metadata emitted when the goal configuration is reached.

GreedyBestFirstTraversal dataclass

GreedyBestFirstTraversal(heuristic: HeuristicFunction)

Bases: TraversalStrategyABC

Greedy best-first traversal policy.

search

search(
    *,
    tree: ConfigurationTree,
    generator: MoveGenerator,
    goal: GoalPredicate,
    max_expansions: int | None = None,
    max_depth: int | None = None
) -> SearchResult

Execute search over the tree using the supplied generator.

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

def search(
    self,
    *,
    tree: ConfigurationTree,
    generator: MoveGenerator,
    goal: GoalPredicate,
    max_expansions: int | None = None,
    max_depth: int | None = None,
) -> SearchResult:
    _ = max_depth
    frontier: list[PriorityEntry] = []
    heapq.heappush(frontier, PriorityEntry(self.heuristic(tree.root), tree.root))
    return run_frontier_search(
        tree=tree,
        generator=generator,
        goal=goal,
        pop_next=lambda: heapq.heappop(frontier).node if frontier else None,
        push_child=lambda child: heapq.heappush(
            frontier, PriorityEntry(self.heuristic(child), child)
        ),
        frontier_has_items=lambda: bool(frontier),
        max_expansions=max_expansions,
        max_depth=None,
        goal_on_pop=False,
    )

RevertStepInfo dataclass

RevertStepInfo(
    entropy: int,
    unresolved_count: int,
    candidate_movesets: tuple[
        frozenset[LaneAddress], ...
    ] = (),
    candidate_index: int | None = None,
    reversion_steps: int = 0,
    ancestor_depth: int = 0,
    reason: str = "",
    state_seen_node_id: int | None = None,
    no_valid_moves_qubit: int | None = None,
    trigger_node_id: int | None = None,
    trigger_entropy: int | None = None,
)

Bases: StepInfo

Metadata emitted when the search reverts to an ancestor node.

SearchResult dataclass

SearchResult(
    *,
    nodes_expanded: int,
    max_depth_reached: int,
    goal_nodes: tuple[ConfigurationNode, ...] = (),
    goal_node: ConfigurationNode | None = None
)

Result of a search strategy.

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

def __init__(
    self,
    *,
    nodes_expanded: int,
    max_depth_reached: int,
    goal_nodes: tuple[ConfigurationNode, ...] = (),
    goal_node: ConfigurationNode | None = None,
) -> None:
    # Canonicalize all results into goal_nodes so single/multi-solution
    # handling uses one representation everywhere.
    if goal_node is not None:
        if goal_nodes and goal_nodes[0] is not goal_node:
            raise ValueError(
                "goal_node must match first item in goal_nodes when both are set"
            )
        goal_nodes = (goal_node, *goal_nodes[1:]) if goal_nodes else (goal_node,)

    self.nodes_expanded = nodes_expanded
    self.max_depth_reached = max_depth_reached
    self.goal_nodes = goal_nodes

goal_node property

goal_node: ConfigurationNode | None

Best goal node, or None if no goal was found.

goal_nodes instance-attribute

goal_nodes: tuple[ConfigurationNode, ...] = goal_nodes

Goal nodes found during search, ordered best to worst.

max_depth_reached instance-attribute

max_depth_reached: int = max_depth_reached

Maximum depth reached during search.

nodes_expanded instance-attribute

nodes_expanded: int = nodes_expanded

Total number of nodes expanded during search.

StepInfo dataclass

StepInfo(
    entropy: int,
    unresolved_count: int,
    candidate_movesets: tuple[
        frozenset[LaneAddress], ...
    ] = (),
    candidate_index: int | None = None,
)

Base metadata passed to on_step callbacks.

TraversalStrategyABC

Bases: ABC

Strategy interface for traversing a configuration tree.

Traversal strategies choose which frontier node to examine next. Candidate move generation is delegated to the provided MoveGenerator.

search abstractmethod

search(
    *,
    tree: ConfigurationTree,
    generator: MoveGenerator,
    goal: GoalPredicate,
    max_expansions: int | None = None,
    max_depth: int | None = None
) -> SearchResult

Execute search over the tree using the supplied generator.

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

@abc.abstractmethod
def search(
    self,
    *,
    tree: ConfigurationTree,
    generator: MoveGenerator,
    goal: GoalPredicate,
    max_expansions: int | None = None,
    max_depth: int | None = None,
) -> SearchResult:
    """Execute search over the tree using the supplied generator."""
    ...

entropy_guided_search

entropy_guided_search(
    tree: ConfigurationTree,
    target: dict[int, LocationAddress],
    goal: GoalPredicate,
    params: SearchParams = SearchParams(),
    max_depth: int | None = None,
    max_expansions: int | None = None,
    on_step: (
        Callable[[str, ConfigurationNode, StepInfo], None]
        | None
    ) = None,
) -> SearchResult

Entropy-guided depth-first search with reversion and sequential fallback.

Thin wrapper around EntropyGuidedSearch for backward compatibility. Also takes target directly (in addition to goal) because scoring needs the raw target mapping.

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

def entropy_guided_search(
    tree: ConfigurationTree,
    target: dict[int, LocationAddress],
    goal: GoalPredicate,
    params: SearchParams = SearchParams(),
    max_depth: int | None = None,
    max_expansions: int | None = None,
    on_step: Callable[[str, ConfigurationNode, StepInfo], None] | None = None,
) -> SearchResult:
    """Entropy-guided depth-first search with reversion and sequential fallback.

    Thin wrapper around ``EntropyGuidedSearch`` for backward compatibility.
    Also takes *target* directly (in addition to *goal*) because scoring needs
    the raw target mapping.
    """
    scorer = CandidateScorer(params=params, target=target)
    search = EntropyGuidedSearch(
        tree=tree,
        target=target,
        goal=goal,
        params=params,
        max_depth=max_depth,
        max_expansions=max_expansions,
        on_step=on_step,
    )
    entropy_view: dict[int, EntropyNode] = search.search_nodes  # type: ignore[assignment]
    generator = HeuristicMoveGenerator(
        scorer=scorer,
        params=params,
        search_nodes=entropy_view,
    )
    return search.run(generator=generator)

greedy_best_first

greedy_best_first(
    tree: ConfigurationTree,
    generator: MoveGenerator,
    goal: GoalPredicate,
    heuristic: HeuristicFunction,
    max_expansions: int | None = None,
) -> SearchResult

Greedy best-first search using heuristic only.

Expands the node with the lowest heuristic value first. Does not consider accumulated path cost — purely greedy. Fast but not guaranteed to find the optimal (shortest) solution.

Parameters:

Name	Type	Description	Default
tree	ConfigurationTree	The configuration tree to search.	required
generator	MoveGenerator	Move generator for producing candidates.	required
goal	GoalPredicate	Predicate that returns True for goal configurations.	required
heuristic	HeuristicFunction	Estimates cost to goal. Lower is better.	required
max_expansions	int | None	Maximum number of nodes to expand before giving up. None means no limit.	None

Returns:

Type	Description
SearchResult	SearchResult with the goal node (or None if not found).

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

def greedy_best_first(
    tree: ConfigurationTree,
    generator: MoveGenerator,
    goal: GoalPredicate,
    heuristic: HeuristicFunction,
    max_expansions: int | None = None,
) -> SearchResult:
    """Greedy best-first search using heuristic only.

    Expands the node with the lowest heuristic value first. Does not
    consider accumulated path cost — purely greedy. Fast but not
    guaranteed to find the optimal (shortest) solution.

    Args:
        tree: The configuration tree to search.
        generator: Move generator for producing candidates.
        goal: Predicate that returns True for goal configurations.
        heuristic: Estimates cost to goal. Lower is better.
        max_expansions: Maximum number of nodes to expand before
            giving up. None means no limit.

    Returns:
        SearchResult with the goal node (or None if not found).
    """
    return GreedyBestFirstTraversal(heuristic=heuristic).search(
        tree=tree,
        generator=generator,
        goal=goal,
        max_expansions=max_expansions,
    )

partial_placement_goal

partial_placement_goal(
    target: dict[int, LocationAddress],
    min_placed: int | None = None,
) -> GoalPredicate

Goal: at least some qubits are at their target locations.

If min_placed is None, all qubits in target must be placed (same as placement_goal). Otherwise, at least min_placed qubits must be at their target.

Parameters:

Name	Type	Description	Default
target	dict[int, LocationAddress]	Mapping of qubit ID to desired location.	required
min_placed	int | None	Minimum number of qubits that must be at their target. None means all.	None

Returns:

Type	Description
GoalPredicate	A GoalPredicate.

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

def partial_placement_goal(
    target: dict[int, LocationAddress],
    min_placed: int | None = None,
) -> GoalPredicate:
    """Goal: at least some qubits are at their target locations.

    If `min_placed` is None, all qubits in `target` must be placed
    (same as `placement_goal`). Otherwise, at least `min_placed`
    qubits must be at their target.

    Args:
        target: Mapping of qubit ID to desired location.
        min_placed: Minimum number of qubits that must be at their
            target. None means all.

    Returns:
        A GoalPredicate.
    """
    required = min_placed if min_placed is not None else len(target)

    def goal(node: ConfigurationNode) -> bool:
        placed = sum(
            1 for qid, loc in target.items() if node.configuration.get(qid) == loc
        )
        return placed >= required

    return goal

placement_goal

placement_goal(
    target: dict[int, LocationAddress],
) -> GoalPredicate

Goal: all specified qubits are at their target locations.

Every qubit in target must be at the exact location. Qubits not in target are ignored.

Parameters:

Name	Type	Description	Default
target	dict[int, LocationAddress]	Mapping of qubit ID to desired location.	required

Returns:

Type	Description
GoalPredicate	A GoalPredicate that returns True when all targets are met.

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

def placement_goal(target: dict[int, LocationAddress]) -> GoalPredicate:
    """Goal: all specified qubits are at their target locations.

    Every qubit in `target` must be at the exact location. Qubits not
    in `target` are ignored.

    Args:
        target: Mapping of qubit ID to desired location.

    Returns:
        A GoalPredicate that returns True when all targets are met.
    """

    def goal(node: ConfigurationNode) -> bool:
        return all(node.configuration.get(qid) == loc for qid, loc in target.items())

    return goal

zone_goal

zone_goal(
    zone_id: int, arch_spec: ArchSpec
) -> GoalPredicate

Goal: all qubits are located in the specified zone.

A qubit is "in the zone" if its location's word_id is in the zone's word list.

Parameters:

Name	Type	Description	Default
zone_id	int	The zone to target.	required
arch_spec	ArchSpec	Architecture specification (for zone → word mapping).	required

Returns:

Type	Description
GoalPredicate	A GoalPredicate that returns True when all qubits are in the zone.

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

def zone_goal(zone_id: int, arch_spec: ArchSpec) -> GoalPredicate:
    """Goal: all qubits are located in the specified zone.

    A qubit is "in the zone" if its location's word_id is in the
    zone's word list.

    Args:
        zone_id: The zone to target.
        arch_spec: Architecture specification (for zone → word mapping).

    Returns:
        A GoalPredicate that returns True when all qubits are in the zone.
    """
    zone_words = set(arch_spec.zones[zone_id])

    def goal(node: ConfigurationNode) -> bool:
        return all(loc.word_id in zone_words for loc in node.configuration.values())

    return goal