mqt.ionshuttler.linear.cost

Cost estimates used to choose promising schedules, not admissible.

Module Contents

class HeuristicFn[source]

Bases: Protocol

Estimate the remaining schedule work for one search state.

A custom heuristic supplied through heuristic must accept these arguments. The search always passes them positionally, so an implementation may name its parameters freely. The built-in heuristic() additionally accepts optional caching arguments, which the search passes only to that default.

__call__(state: State, architecture: Architecture, gate_order: Sequence[int], gates: Mapping[int, GateAction], predecessors: Mapping[int, frozenset[int]] | None = None, /) → int[source]

Estimate the work still needed to finish the requested gates.

Parameters:

  • state – Search state to score.

  • architecture – Hardware layout the schedule targets.

  • gate_order – Gates to schedule, including completed and running ones; filter with state.completed_gates and state.in_progress_gates.

  • gates – Gate actions indexed by identifier.

  • predecessors – Optional map of which gates must precede others.

Returns:

A nonnegative estimate of the remaining schedule time.

cost(state: State) → int[source]

Return the cost, currently simply the elapsed schedule time.

zero_heuristic(state: State, architecture: Architecture, gate_order: Sequence[int], gates: Mapping[int, GateAction], predecessors: Mapping[int, frozenset[int]] | None = None, /) → int[source]

Estimate nothing about the work left to finish the requested gates.

This admissible estimate turns the search into a uniform-cost search, so the first complete schedule has the minimum makespan among the schedules the configured hardware and action model can express. It usually explores many more states than the default heuristic().

Parameters:

  • state – Search state to score.

  • architecture – Hardware layout the schedule targets.

  • gate_order – Gates to schedule, including completed and running ones.

  • gates – Gate actions indexed by identifier.

  • predecessors – Optional map of which gates must precede others.

Returns:

Always 0.

min_distance_to_valid_pair(pos_a: int, pos_b: int, valid_pairs: tuple[tuple[int, int], ...]) → int[source]

Return the fewest simultaneous site moves needed to reach a valid pair.

The result depends only on the two sites and the architecture’s fixed pair list, so repeated lookups during search reuse a cached value.

heuristic(state: State, architecture: Architecture, gate_order: Sequence[int], gates: Mapping[int, GateAction], predecessors: Mapping[int, frozenset[int]] | None = None, *, critical_path_cache: dict[tuple[int, ...], int] | None = None, gate_zone: Mapping[int, str] | None = None, zone_site_pairs: Mapping[str, tuple[tuple[int, int], ...]] | None = None) → int[source]

Estimate the work still needed to finish the requested gates.

Movement and gate execution can overlap, so this estimate may overstate the remaining schedule time and does not guarantee an optimal result.

Supplying critical_path_cache reuses gate-depth estimates across states that share the same outstanding gates. The caller owns the dictionary and must not reuse it across different circuits or dependency maps.

Returns:

A nonnegative estimate combining ion movement and remaining gate depth.