graphix.space_minimization module

Space minimization procedures for patterns.

pattern_max_space(pattern: Pattern) → int[source]

Compute the maximum number of nodes that must be present in the graph (graph space) during the execution of the pattern.

For statevector simulation, this is equivalent to the maximum memory needed for classical simulation.

Parameters:

pattern (Pattern) – The pattern.

Returns:

max_active – Maximum number of nodes present in the graph during pattern execution.

Return type:

int

standardized_pattern_max_space(pattern: StandardizedPattern) → int[source]

Compute the maximum number of nodes that must be present in the graph (graph space) during the execution of the space-optimal pattern for the given measurement order.

This is equivalent to pattern.to_space_optimal_pattern().max_space().

Parameters:

pattern (StandardizedPattern) – The pattern.

Returns:

max_active – Maximum number of nodes present in the graph during space-optimal pattern execution.

Return type:

int

standardized_to_space_optimal_pattern(pattern: StandardizedPattern) → Pattern[source]

Return a pattern that is space-optimal for the given measurement order.

The source is a StandardizedPattern, i.e., a pattern without interleaving of commands of different kinds.

Parameters:

pattern (StandardizedPattern) – The pattern to optimize.

Returns:

The pattern with optimal placement of N and E commands.

Return type:

Pattern

class SpaceMinimizationHeuristicResult(new_order: tuple[Node, ...], known_optimal: bool)[source]

Bases: object

The result of the application of a space minimization heuristic.

new_order

The new measurement order.

Type:

tuple[Node, …]

known_optimal

True if the new measurement order is known to be optimal. This will interrupt the search for a better heuristic.

Type:

bool

new_order: tuple[Node, ...]
known_optimal: bool
__init__(new_order: tuple[Node, ...], known_optimal: bool) → None
SpaceMinimizationHeuristic: TypeAlias = 'Callable[[StandardizedPattern], SpaceMinimizationHeuristicResult | None]'

Define a space minimization heuristic by returning a new measurement order or None if the heuristic cannot handle the given pattern.

A space minimization heuristic provides a measurement order for a given pattern. See DEFAULT_HEURISTICS for the default heuristics used for minimizing space.

Parameters:

pattern (StandardizedPattern) – The pattern to optimize for space.

Returns:

The result of the application of the space minimization heuristic.

Return type:

SpaceMinimizationHeuristicResult

class SpaceMinimizationHeuristics[source]

Bases: object

Predefined heuristics.

static causal_flow(pattern: StandardizedPattern) → SpaceMinimizationHeuristicResult | None[source]

Use the causal flow layer to minimize space.

This minimization heuristic is optimal but requires the pattern to have a causal flow.

static order_unchanged(pattern: StandardizedPattern) → SpaceMinimizationHeuristicResult | None[source]

Leave the measurement order unchanged.

Since this heuristic preserves the original measurement order, it cannot return a pattern with worse max space than the original.

Usually, this heuristic is included in the list of heuristics considered to ensure that the result of space minimization cannot have a worse max space than the original pattern. This is the case by default, but the user can remove this heuristic from the list to see the effect of the other heuristics even if they don’t reduce the max space of the pattern.

static greedy_degree(pattern: StandardizedPattern) → SpaceMinimizationHeuristicResult | None[source]

Choose greedily the nodes by minimal degree.

This minimization heuristic can improve but can also worsen the max space in some situations.

DEFAULT_HEURISTICS: tuple[SpaceMinimizationHeuristic, ...] = (<function SpaceMinimizationHeuristics.causal_flow>, <function SpaceMinimizationHeuristics.greedy_degree>, <function SpaceMinimizationHeuristics.order_unchanged>)

Default heuristics.

By default, the following heuristics will be tried in that order:

  • causal_flow() gives an optimal measurement order, but only for patterns with causal flow.

  • greedy_degree() can improve but can also worsen the max space in some situations.

  • order_unchanged() ensures that if the previous heuristics don’t improve the max space, at least the resulting pattern cannot have a worse max space than the original one.

minimize_space(pattern: StandardizedPattern, heuristics: Iterable[SpaceMinimizationHeuristic] | None = None) → StandardizedPattern[source]

Return a pattern with an optimized measurement order that reduces the maximal space, i.e. the number of qubits simultaneously required to execute the pattern.

The default heuristics are as follows:

  • If the pattern has a causal flow, then the layers of the flow are used to provide an optimal measurement order for the pattern. See causal_flow().

  • If the pattern has no causal flow, then a greedy algorithm is applied to choose at each step to measure the node with the minimal degree. This particular heuristic has no guarantee to produce an optimal pattern and can even increase the maximal space. See greedy_degree().

  • If the above heuristic does not give a pattern with a smaller maximal space than the original pattern, then the original measurement order is unchanged. See order_unchanged().

Parameters:
Returns:

The optimized pattern.

Return type:

StandardizedPattern