Entropy guided

Entropy-guided tree search traversal.

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)

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)