graphix.optimization module

Optimization procedures for patterns.

standardize(pattern: Pattern) → Pattern

Return a standardized form to the given pattern.

A standardized form is an equivalent pattern where the commands appear in the following order: N, E, M, Z, X, C.

Note that a standardized form does not always exist in presence of C commands. For instance, there is no standardized form for the following pattern (written in the right-to-left convention): E(0, 1) C(0, H) N(1) N(0).

The function raises NotImplementedError if there is no standardized form. This behavior can change in the future.

Parameters:

pattern (Pattern) – The original pattern.

Returns:

standardized – The standardized pattern, if it exists.

Return type:

Pattern

class StandardizedPattern(input_nodes: Iterable[Node], output_nodes: Iterable[Node], n_list: Iterable[command.N], e_set: Iterable[Iterable[Node]], m_list: Iterable[command.M], z_dict: Mapping[Node, Iterable[Node]], x_dict: Mapping[Node, Iterable[Node]], c_dict: Mapping[Node, Clifford])

Bases: _StandardizedPattern, Simulable[Measurement]

Pattern in standardized form.

Use the method to_pattern() to get the standardized pattern.

This class uses immutable data structures for its fields (tuple, frozenset and Mapping).

Instances can be generated with the constructor from any compatible data structures, and an instance can be generated directly from a pattern with the class method from_pattern().

The constructor instantiates the Mapping fields as MappingProxyType objects over fresh dictionaries, ensuring their immutability. We expose the type Mapping instead of MappingProxyType for the readability, as they provide the same interface.

input_nodes

Input nodes.

Type:

tuple[Node, …]

output_nodes

Output nodes.

Type:

tuple[Node, …]

n_list

The N commands.

Type:

tuple[command.N]

e_set

Set of edges. Each edge is a set with two elements.

Type:

frozenset[frozenset[Node]]

m_list

The M commands.

Type:

tuple[command.M]

z_dict

Mapping associating Z-domains to some nodes.

Type:

Mapping[Node, frozenset[Node]]

x_dict

Mapping associating X-domains to some nodes.

Type:

Mapping[Node, frozenset[Node]]

c_dict

Mapping associating Clifford corrections to some output nodes.

Type:

Mapping[Node, Clifford]

__init__(input_nodes: Iterable[Node], output_nodes: Iterable[Node], n_list: Iterable[command.N], e_set: Iterable[Iterable[Node]], m_list: Iterable[command.M], z_dict: Mapping[Node, Iterable[Node]], x_dict: Mapping[Node, Iterable[Node]], c_dict: Mapping[Node, Clifford]) → None

Return a new StandardizedPattern with immutable data structures.

classmethod from_pattern(pattern: Pattern) → Self

Compute the standardized form of the given pattern.

graph() → nx.Graph[int]

Return the graph state from the command sequence, extracted from ‘N’ and ‘E’ commands.

Returns:

graph_state

Return type:

nx.Graph

perform_pauli_pushing(leave_nodes: AbstractSet[Node] | None = None, *, stacklevel: int = 1) → StandardizedPattern

Move Pauli measurements before the other measurements.

If you need to recover the cut between Pauli measurements and non-Pauli measurements or the shifted signal, you can use from_standardizedpattern() instead.

Parameters:

• leave_nodes (AbstractSet[Node], optional) – Nodes that should not be moved. This constraint only applies to Pauli nodes and has no effect on non-Pauli nodes.

• stacklevel (int, optional) – Stack level to use for warnings. Defaults to 1, meaning that warnings are reported at this function’s call site.

Returns:

The pattern in which Pauli measurements have been moved before the other measurements.

Return type:

StandardizedPattern

max_space() → int

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 to_space_optimal_pattern().max_space().

Returns:

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

Return type:

int

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

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.

Note that standardized patterns always have a maximal space equal to the total number of nodes in the open graph, because standardization requires the entire graph to be prepared before measurement.

Space reduction is specifically realized when the optimized order is applied via to_space_optimal_pattern().

See graphix.space_minimization.minimize_space() for default heuristics.

Parameters:

heuristics (Iterable[SpaceMinimizationHeuristic] | None, default None) – The heuristics to apply sequentially. Defaults to DEFAULT_HEURISTICS.

Returns:

The optimized pattern.

Return type:

StandardizedPattern

to_pattern() → Pattern

Return the standardized pattern.

to_standardizedpattern() → StandardizedPattern

Return self.

to_space_optimal_pattern() → Pattern

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

This method treats the measurement order as fixed, performing node preparations (N) and entanglements (E) as late as possible to minimize space usage. While the resulting pattern is guaranteed to be optimal for this specific order, the method does not explore alternative orders.

To find an alternative measurement order that further reduces space, use minimize_space().

to_opengraph() → OpenGraph[Measurement]

Extract the underlying resource-state open graph from the pattern.

Return type:

OpenGraph[Measurement]

Raises:

ValueError – If N commands in the pattern do not represent a \(\ket{+}\) state.

partial_order_layers() → tuple[frozenset[int], ...]

Extract the measurement order of the pattern in the form of layers.

This method builds a directed acyclical graph (DAG) from the pattern and then performs a topological sort.

Returns:

Measurement partial order between the pattern’s nodes in a layer form.

Return type:

tuple[frozenset[int], …]

Raises:

ValueError – If the correction domains in the pattern form closed loops. This implies that the pattern is not runnable.

Notes

The returned object follows the same conventions as the partial_order_layers attribute of PauliFlow and XZCorrections objects:

• Nodes in the same layer can be measured simultaneously.

• Nodes in layer i must be measured after nodes in layer i + 1.

• All output nodes (if any) are in the first layer.

• There cannot be any empty layers.

to_xzcorrections() → XZCorrections[Measurement]

Extract the XZ-corrections from the current measurement pattern.

Returns:

The XZ-corrections associated with the current pattern.

Return type:

XZCorrections[Measurement]

Raises:

• XZCorrectionsError – If the extracted correction dictionaries are not well formed.

• ValueError – If N commands in the pattern do not represent a \(\ket{+}\) state or if the pattern corrections form closed loops.

map(f: Callable[[Measurement], Measurement]) → StandardizedPattern

Return a pattern where the function f has been applied to each measurement.

Parameters:

f (Callable[[Measurement], Measurement]) – Function applied to each measurement.

Returns:

The resulting pattern.

Return type:

StandardizedPattern

to_bloch() → StandardizedPattern

Return an equivalent pattern in which all measurements are represented as Bloch measurements.

infer_pauli_measurements(*, rel_tol: float = 1e-09, abs_tol: float = 0.0) → StandardizedPattern

Return a pattern where Bloch measurements close to a Pauli measurement are replaced by Pauli measurements.

Parameters:

• rel_tol (float, optional) – Relative tolerance for comparing angles, passed to math.isclose(). Default is 1e-9.

• abs_tol (float, optional) – Absolute tolerance for comparing angles, passed to math.isclose(). Default is 0.0.

Returns:

A pattern in which Bloch measurements close to a Pauli measurement are replaced by Pauli measurements. If copy is False, the result is self.

Return type:

StandardizedPattern

remove_pauli_measurements(*, stacklevel: int = 1) → StandardizedPattern

Remove non-input Pauli measurements from the given pattern.

See remove_pauli_measurements() for more information.

Parameters:

stacklevel (int, optional) – Stack level to use for warnings. Defaults to 1, meaning that warnings are reported at this function’s call site.

Returns:

The pattern in which Pauli measurements have been moved before the other measurements.

Return type:

StandardizedPattern

input_nodes

output_nodes

n_list

e_set

m_list

z_dict

x_dict

c_dict

remove_useless_domains(pattern: Pattern) → Pattern

Return an equivalent pattern where measurement domains that are not used given the specific measurement angles and planes are removed.

single_qubit_domains(pattern: Pattern) → Pattern

Return an equivalent pattern where domains contains at most one qubit.

remove_local_clifford_commands(pattern: Pattern) → Pattern

Return an equivalent pattern where local Clifford commands have been replaced by MBQC commands.

This function transpiles MBQC+LC patterns into MBQC patterns.