HierarchicalStrategy

class HierarchicalStrategy(group_size=4, k_per_partition=20, max_per_group=200, merge_width=None)

Bases: AggregationStrategy

Divide-and-conquer beam that delays cross-group commitment.

Partitions are split into groups of group_size. Each group is solved independently with a beam of width max_per_group (so within a group this is not an exhaustive product — it is a pruned beam). The resulting group pools are then combined in a pairwise merge tree, re-scoring and pruning at each level. A merge rebuilds each combined solution by replaying both groups’ candidate selections through extend_fn, so combination semantics stay entirely with the problem (any extend_fn encoding works; nothing here assumes a particular “unset” value or that partitions own disjoint indices).

Compared to a single left-to-right beam, deferring cross-group commitment lets each group retain prefixes that a global beam would prune early.

Cost: a merge scores every pair of participating pool entries, so its work grows with the square of the per-merge fan-in. max_per_group is held fixed across all stages and is not inflated by top_n — top_n only widens the final slice, which adds no extra scoring. Use merge_width to cap the per-merge fan-in below max_per_group.

Limitations:

• Groups are formed in decomposition order (consecutive program IDs); no coupling-aware grouping is performed. The benefit over a wide beam only materializes when strongly-coupled partitions happen to land in the same group.

• Cross-group interactions in evaluate_fn (e.g. penalties spanning partitions in different groups) are invisible during per-group pruning and only surface at merge time.

The output format matches BeamSearchStrategy: (score, solution) pairs sorted ascending (lower is better).

Parameters:

• group_size (int) – Maximum partitions per group.

• k_per_partition (int) – Candidates to fetch from each partition.

• max_per_group (int) – Maximum solutions retained per group and per merge level; the main quality/cost dial. Drives the per-merge cost; not inflated by top_n.

• merge_width (int | None) – Maximum entries from each pool that participate in a merge’s Cartesian product, bounding per-merge cost to merge_width squared. None (default) uses all max_per_group entries. Setting it below top_n can limit how many distinct solutions are returnable.

Attributes Summary

group_size
k_per_partition
max_per_group
merge_width

Methods Summary

aggregate(programs, initial_solution, ...[, ...])

Aggregate per-partition candidates into the top-N global solutions.

Attributes Documentation

group_size: int = 4

k_per_partition: int = 20

max_per_group: int = 200

merge_width: int | None = None

Methods Documentation

aggregate(programs, initial_solution, extend_fn, evaluate_fn, top_n=1)

Aggregate per-partition candidates into the top-N global solutions.

Parameters:

• programs (dict[Any, SolutionSamplingMixin]) – Mapping of program IDs to executed VariationalQuantumAlgorithm instances.

• initial_solution (Sequence[int]) – Starting global solution vector (typically all zeros).

• extend_fn (Callable[[list[int], Any, SolutionEntry], list[int]]) – (current_solution, prog_id, candidate) -> extended_solution; splices a partition’s candidate into the global vector.

• evaluate_fn (Callable[[list[int]], float]) – (solution) -> float. Lower is better.

• top_n (int) – Number of top solutions to return.

Return type:

list[tuple[float, list[int]]]

Returns:

List of (score, solution) tuples sorted ascending by score (best first), with at most top_n entries.