graphix.opengraph module

Class for open graph states.

class OpenGraph(graph: nx.Graph[int], input_nodes: Sequence[int], output_nodes: Sequence[int], measurements: Mapping[int, _AM_co], output_cliffords: Mapping[int, Clifford] = <factory>)[source]

Bases: Parameterizable, Simulable[_AM_co], Generic[_AM_co]

An unmutable dataclass providing a representation of open graph states.

graph

The underlying resource-state graph. Nodes represent qubits and edges represent the application of \(CZ\) gate on the linked nodes.

Type:

networkx.Graph[int]

input_nodes

An ordered sequence of node labels corresponding to the open graph inputs.

Type:

Sequence[int]

output_nodes

An ordered sequence of node labels corresponding to the open graph outputs.

Type:

Sequence[int]

measurements

A mapping between the non-output nodes of the open graph (key) and their corresponding measurement label (value). Measurement labels can be specified as Measurement, Plane or Axis instances.

Type:

Mapping[int, _AM_co]

output_cliffords

A mapping between output nodes of the open graph (key) and Clifford operators. This attribute allows to preserve the semantics of (deterministic) patterns with local-clifford commands when extracting the open graph. See Pattern.to_opengraph().

Type:

Mapping[int, Clifford]

Notes

The inputs and outputs of OpenGraph instances in Graphix are defined as ordered sequences of node labels. This contrasts the usual definition of open graphs in the literature, where inputs and outputs are unordered sets of nodes labels. This restriction facilitates the interplay with Pattern objects, where the order of input and output nodes represents a choice of Hilbert space basis.

Example

>>> import networkx as nx
>>> from graphix.opengraph import OpenGraph
>>> from graphix.measurements import Measurement
>>>
>>> graph = nx.Graph([(0, 1), (1, 2)])
>>> measurements = {i: Measurement.XY(0.5 * i) for i in range(2)}
>>> input_nodes = [0]
>>> output_nodes = [2]
>>> og = OpenGraph(graph, input_nodes, output_nodes, measurements)
graph: nx.Graph[int]
input_nodes: Sequence[int]
output_nodes: Sequence[int]
measurements: Mapping[int, _AM_co]
output_cliffords: Mapping[int, Clifford]
to_pattern(*, stacklevel: int = 1) → Pattern[source]

Extract a deterministic pattern from an OpenGraph[Measurement] if it exists.

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:

A deterministic pattern on the open graph.

Return type:

Pattern

Raises:

OpenGraphError – If the open graph does not have flow.

Notes

  • The open graph instance must be of parametric type Measurement to allow for a pattern extraction, otherwise it does not contain information about the measurement angles.

  • This method proceeds by searching a flow on the open graph and converting it into a pattern as prescripted in Ref. [1_to_pattern]. It first attempts to find a causal flow because the corresponding flow-finding algorithm has lower complexity. If it fails, it attemps to find a Pauli flow because this property is more general than a generalised flow, and the corresponding flow-finding algorithms have the same complexity in the current implementation.

References

[1_to_pattern]

Browne et al., NJP 9, 250 (2007)

draw(**options: Unpack[DrawKwargs]) → None[source]

Visualize the opengraph.

Parameters:

options (Unpack[DrawKwargs]) – Options controlling graph visualization. See VisualizationOptions.

map(f: Callable[[_A], _B]) → OpenGraph[_B][source]

Apply a function to every measurement of the open graph and return the resulting open graph.

Parameters:

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

Returns:

The resulting open graph.

Return type:

OpenGraph[_B]

Notes

The types of measurements can be changed by f.

Example

>>> import networkx as nx
>>> from graphix.opengraph import OpenGraph
>>> from graphix.measurements import Measurement
>>> graph = nx.Graph([(0, 1), (1, 2)])
>>> measurements = {0: Measurement.XY(0.5), 1: Measurement.YZ(1)}
>>> og = OpenGraph(graph, [0], [2], measurements)
>>> og.map(lambda m: m.plane).measurements
{0: Plane.XY, 1: Plane.YZ}
to_bloch() → OpenGraph[BlochMeasurement][source]

Return the open graph where all measurements are converted to Bloch.

Example

>>> import networkx as nx
>>> from graphix.opengraph import OpenGraph
>>> from graphix.measurements import Measurement
>>> graph = nx.Graph([(0, 1), (1, 2)])
>>> measurements = {0: Measurement.X, 1: Measurement.Y}
>>> og = OpenGraph(graph, [0], [2], measurements)
>>> og.to_bloch().measurements
{0: Measurement.XY(0), 1: Measurement.XY(0.5)}
downcast_bloch() → OpenGraph[BlochMeasurement][source]

Return the open graph if all measurements are described as Bloch measurements; raise TypeError otherwise.

If this method succeeds, the returned graph is identical to the original one, but this function narrows the static type of the measurements. The returned graph can be used with functions that require all measurements are described as Bloch measurements, such as OpenGraph.to_causalflow().

Example

>>> import networkx as nx
>>> from graphix.opengraph import OpenGraph
>>> from graphix.measurements import Measurement
>>> graph = nx.Graph([(0, 1), (1, 2)])
>>> measurements = {0: Measurement.XY(0.5), 1: Measurement.YZ(1)}
>>> og = OpenGraph(graph, [0], [2], measurements)
>>> og.downcast_bloch().measurements
{0: Measurement.XY(0.5), 1: Measurement.YZ(1)}
>>> measurements = {0: Measurement.X, 1: Measurement.Y}
>>> og = OpenGraph(graph, [0], [2], measurements)
>>> og.downcast_bloch()
Traceback (most recent call last):
    ...
TypeError: Bloch measurement expected, but Pauli measurement was found.
infer_pauli_measurements(rel_tol: float = 1e-09, abs_tol: float = 0.0) → OpenGraph[Measurement][source]

Return an equivalent open graph in which Bloch measurements close to a Pauli measurement are replaced by Pauli measurements.

Pauli measurements are measurements with a Pauli angle, i.e. an integer multiple of \(\pi/2\).

This method can be used before calling methods such as OpenGraph.to_pauliflow_or_none, that deal with Pauli measurements in a special way.

Parameters:

  • pattern (pattern) – Source pattern.

  • 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:

An equivalent open graph in which Bloch measurements close to a Pauli measurement are replaced by Pauli measurements.

Return type:

Pattern

Example

>>> import networkx as nx
>>> from graphix.opengraph import OpenGraph
>>> from graphix.measurements import Measurement
>>> graph = nx.Graph([(0, 1), (1, 2)])
>>> measurements = {0: Measurement.XY(0.5), 1: Measurement.YZ(1)}
>>> og = OpenGraph(graph, [0], [2], measurements)
>>> og.infer_pauli_measurements().measurements
{0: Measurement.Y, 1: -Measurement.Z}
isclose(other: OpenGraph[_AM_co], rel_tol: float = 1e-09, abs_tol: float = 0.0) → bool[source]

Check if two open graphs are equal within a given tolerance.

Parameters:

  • other (OpenGraph[_AM_co])

  • rel_tol (float) – Relative tolerance. Optional, defaults to 1e-09.

  • abs_tol (float) – Absolute tolerance. Optional, defaults to 0.0.

Returns:

True if the two open graphs are approximately equal.

Return type:

bool

Notes

This method verifies the open graphs have:

  • Truly equal underlying graphs (not up to an isomorphism).

  • Equal input and output nodes.

  • Same measurement planes or axes and approximately equal measurement angles if the open graph is of parametric type Measurement.

  • Equal output_cliffords mappings.

The static typer does not allow an isclose comparison of two open graphs with different parametric type. For a structural comparison, see OpenGraph.is_equal_structurally().

is_equal_structurally(other: OpenGraph[AbstractMeasurement]) → bool[source]

Compare the underlying structure of two open graphs.

Parameters:

other (OpenGraph[AbstractMeasurement])

Returns:

True if self and og have the same structure.

Return type:

bool

Notes

This method verifies the open graphs have:

  • Truly equal underlying graphs (not up to an isomorphism).

  • Equal input and output nodes. This assumes equal types as well, i.e., if self.input_nodes is a list and other.input_nodes is a tuple, this method will return False.

  • Equal output_cliffords mappings.

It assumes the open graphs are well formed.

The static typer allows comparing the structure of two open graphs with different parametric type.

neighbors(nodes: Collection[int]) → set[int][source]

Return the set containing the neighborhood of a set of nodes in the open graph.

Parameters:

nodes (Collection[int]) – Set of nodes whose neighborhood is to be found

Returns:

neighbors_set – Neighborhood of set nodes.

Return type:

set[int]

odd_neighbors(nodes: Collection[int]) → set[int][source]

Return the set containing the odd neighborhood of a set of nodes in the open graph.

Parameters:

nodes (Collection[int]) – Set of nodes whose odd neighborhood is to be found

Returns:

odd_neighbors_set – Odd neighborhood of set nodes.

Return type:

set[int]

to_causalflow() → CausalFlow[_PM_co][source]

Try to extract a causal flow on the open graph.

This method is a wrapper over OpenGraph.to_causalflow_or_none() with a single return type.

This method requires all measurements to be planar: to extract the causal flow from a graph that contains Pauli measurements, you can apply OpenGraph.to_bloch() first.

Returns:

A causal flow object if the open graph has causal flow.

Return type:

CausalFlow[_PM_co]

Raises:

OpenGraphError – If the open graph does not have a causal flow.

See also

OpenGraph.to_causalflow_or_none()

to_gflow() → GFlow[_PM_co][source]

Try to extract a maximally delayed generalised flow (gflow) on the open graph.

This method is a wrapper over OpenGraph.to_gflow_or_none() with a single return type.

This method requires all measurements to be planar: to extract a gflow from a graph that contains Pauli measurements, you can apply OpenGraph.to_bloch() first.

Returns:

A gflow object if the open graph has gflow.

Return type:

GFlow[_PM_co]

Raises:

OpenGraphError – If the open graph does not have a gflow.

See also

OpenGraph.to_gflow_or_none()

to_pauliflow(*, stacklevel: int = 1) → PauliFlow[_AM_co][source]

Try to extract a maximally delayed Pauli on the open graph.

This method is a wrapper over OpenGraph.to_pauliflow_or_none() with a single return type.

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:

A Pauli flow object if the open graph has Pauli flow.

Return type:

PauliFlow[_AM_co]

Raises:

OpenGraphError – If the open graph does not have a Pauli flow.

See also

OpenGraph.to_pauliflow_or_none(), OpenGraph.infer_pauli_measurements()

to_causalflow_or_none() → CausalFlow[_PM_co] | None[source]

Return a causal flow on the open graph if it exists.

This method requires all measurements to be planar: to find the causal flow from a graph that contains Pauli measurements, you can apply OpenGraph.to_bloch() first.

Returns:

A causal flow object if the open graph has causal flow or None otherwise.

Return type:

CausalFlow[_PM_co] | None

See also

OpenGraph.to_causalflow()

Notes

  • The open graph instance must be of parametric type Measurement or Plane since the causal flow is only defined on open graphs with \(XY\) measurements.

  • This function implements the algorithm presented in Ref. [1] with polynomial complexity on the number of nodes, \(O(N^2)\).

References

[1] Mhalla and Perdrix, (2008), Finding Optimal Flows Efficiently, doi.org/10.1007/978-3-540-70575-8_70

to_gflow_or_none() → GFlow[_PM_co] | None[source]

Return a maximally delayed Pauli on the open graph if it exists.

This method requires all measurements to be planar: to find a gflow in a graph that contains Pauli measurements, you can apply OpenGraph.to_bloch() first.

Returns:

A gflow object if the open graph has gflow or None otherwise.

Return type:

GFlow[_PM_co] | None

See also

OpenGraph.to_gflow()

Notes

  • The open graph instance must be of parametric type Measurement or Plane since the gflow is only defined on open graphs with planar measurements. Measurement instances with a Pauli angle (integer multiple of \(\pi/2\)) are interpreted as Plane instances, in contrast with OpenGraph.to_pauliflow_or_none().

  • This function implements the algorithm presented in Ref. [1] with polynomial complexity on the number of nodes, \(O(N^3)\).

References

[1] Mitosek and Backens, 2024 (arXiv:2410.23439).

to_pauliflow_or_none(*, stacklevel: int = 1) → PauliFlow[_AM_co] | None[source]

Return a maximally delayed Pauli on the open graph if it exists.

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:

A Pauli flow object if the open graph has Pauli flow or None otherwise.

Return type:

PauliFlow[_AM_co] | None

See also

OpenGraph.to_pauliflow(), OpenGraph.infer_pauli_measurements()

Notes

  • Measurements are considered to be Pauli only if they are represented as graphix.measurements.PauliMeasurement. The method OpenGraph.infer_pauli_measurements() can be called first to convert all measurements with a Pauli angle (integer multiple of \(\pi/2\)) into Pauli measurements.

  • This function implements the algorithm presented in Ref. [1] with polynomial complexity on the number of nodes, \(O(N^3)\).

References

[1] Mitosek and Backens, 2024 (arXiv:2410.23439).

Example

>>> import warnings
>>> import networkx as nx
>>> from graphix.opengraph import OpenGraph
>>> from graphix.measurements import Measurement
>>> graph = nx.Graph([(0, 1), (1, 2)])
>>> measurements = {0: Measurement.XZ(0.5), 1: Measurement.XZ(0.5)}
>>> og = OpenGraph(graph, [0], [2], measurements)
>>> with warnings.catch_warnings():
...     warnings.filterwarnings("ignore", message="Open graph with non-inferred Pauli measurements.")
...     og.to_pauliflow()
Traceback (most recent call last):
    ...
graphix.opengraph.OpenGraphError: The open graph does not have a Pauli flow.
>>> og.infer_pauli_measurements().measurements
{0: Measurement.X, 1: Measurement.X}
>>> str(og.infer_pauli_measurements().to_pauliflow())
'p(0) = {1}, p(1) = {2}; {0, 1} < {2}'
to_circuit(pexp_cp: Callable[[PauliExponentialDAG, Circuit], None] | None = None, cm_cp: Callable[[CliffordMap, Circuit], None] | None = None, *, stacklevel: int = 1) → Circuit[source]

Extract a unitary in the form of a circuit from an open graph resource state.

This method acts as a wrapper around the circuit extraction routine, simplifying its usage. It first attempts to extract the Pauli flow of the open graph, then applies the circuit extraction procedure described in Ref. [1_to_circuit], and finally compiles the resulting circuit using the provided passes. To obtain the open graph’s unitary in the form of a Pauli exponential DAG along with a Clifford transformation, as presented in Ref. [1_to_circuit], one should instead operate directly on the flow object using PauliFlow.extract_circuit().

Parameters:
Returns:

Quantum circuit represented as a set of instructions.

Return type:

Circuit

Notes

  • The open graph instance must be of parametric type Measurement to allow for a circuit extraction, otherwise it does not contain information about the measurement angles.

  • This wrapper extracts a Pauli flow rather than a gflow, as the former is more general while the underlying extraction algorithms have the same computational complexity in both cases. The resulting unitary is identical whether it is obtained from a GFlow or from a PauliFlow with inferred Pauli measurements. However, compilation passes that simultaneously diagonalize Pauli exponentials within the same layer of the Pauli exponential DAG may benefit from flows of lower depth, which is often the case for Pauli flow. The pass graphix.circ_ext.compilation.pexp_ladder_pass() does not take into account the flow’s depth.

References

[1_to_circuit] (1,2)

Simmons, 2021 (arXiv:2109.05654).

Examples

>>> import warnings
>>> import networkx as nx
>>> from graphix.opengraph import OpenGraph
>>> from graphix.measurements import Measurement
>>> og = OpenGraph(
...     graph=nx.Graph([(0, 1), (1, 2), (3, 4), (4, 5), (6, 7), (7, 8), (1, 3), (4, 6)]),
...     input_nodes=(0, 3, 6),
...     output_nodes=(2, 5, 8),
...     measurements=dict.fromkeys((0, 1, 3, 4, 6, 7), Measurement.XY(angle=0)),
... )
>>> with warnings.catch_warnings():
...     warnings.filterwarnings("ignore", message="Open graph with non-inferred Pauli measurements.")
...     og.to_circuit()
Circuit(width=3, instr=[H(2), H(1), CNOT(2, 1), H(1), H(1), H(0), CNOT(2, 0), CNOT(1, 0), H(2), H(1), H(0)])
>>> # The default compilation passes do not exploit the lower depth of the Pauli flow
>>> # compared the gflow.
>>> og.infer_pauli_measurements().to_circuit()
Circuit(width=3, instr=[H(2), H(1), CNOT(2, 1), H(1), H(1), H(0), CNOT(2, 0), CNOT(1, 0), H(2), H(1), H(0)])
compose(other: OpenGraph[_AM_co], mapping: Mapping[int, int]) → tuple[OpenGraph[_AM_co], dict[int, int]][source]

Compose two open graphs by merging subsets of nodes from self and other, and relabeling the nodes of other that were not merged.

Parameters:

  • other (OpenGraph[_AM_co]) – Open graph to be composed with self.

  • mapping (dict[int, int]) – Partial relabelling of the nodes in other, with keys and values denoting the old and new node labels, respectively.

Returns:

  • og (OpenGraph[_AM_co]) – Composed open graph.

  • mapping_complete (dict[int, int]) – Complete relabelling of the nodes in other, with keys and values denoting the old and new node label, respectively.

Notes

Let’s denote \(\{G(V_1, E_1), I_1, O_1\}\) the open graph self, \(\{G(V_2, E_2), I_2, O_2\}\) the open graph other, \(\{G(V, E), I, O\}\) the resulting open graph og and {v:u} an element of mapping.

We define \(V, U\) the set of nodes in mapping.keys() and mapping.values(), and \(M = U \cap V_1\) the set of merged nodes.

The open graph composition requires that

  • \(V \subseteq V_2\).

  • If both v and u are measured, the corresponding measurements must have the same plane and angle.

The returned open graph follows this convention:

  • \(I = (I_1 \cup I_2) \setminus M \cup (I_1 \cap I_2 \cap M)\),

  • \(O = (O_1 \cup O_2) \setminus M \cup (O_1 \cap O_2 \cap M)\),

  • If only one node of the pair {v:u} is measured, this measure is assigned to \(u \in V\) in the resulting open graph.

  • Input (and, respectively, output) nodes in the returned open graph have the order of the open graph self followed by those of the open graph other. Merged nodes are removed, except when they are input (or output) nodes in both open graphs, in which case, they appear in the order they originally had in the graph self.

  • Clifford operations on output nodes:

    • if two output nodes \(o_1\) and \(o_2\) are merged, then \(C(o_1) = C_2(o_2) \circ C_1(o_1)\);

    • if an output node \(o_1\) is merged with a measured node \(m_2\), then \(M(o_1) = M_2(m_2) \circ C_1(o_1)\);

    • if a measured node \(m_1\) is merged with an output node \(o_2\), then \(M(m_1) = M_1(m_1) \circ C_2(o_2)\).

with_parameter(variable: Parameter, substitute: ExpressionOrSupportsFloat) → OpenGraph[_M][source]

Substitute a parameter with a value or expression in all measurement angles.

Creates a new open graph where every measurement angle containing the specified variable is updated using the provided substitution. The original open graph instance remains unmodified.

Parameters:

  • variable (Parameter) – The symbolic expression to be replaced within the measurement angles.

  • substitute (ExpressionOrSupportsFloat) – The value or symbolic expression to substitute in place of variable.

Returns:

A new instance of OpenGraph with the updated measurement parameters.

Return type:

OpenGraph[Measurement]

Notes

Substitution relies on object identity. You must provide the exact parameter object instance currently stored in the measurements. Passing a new object with the same name will not trigger a substitution if it is not the same instance in memory.

Examples

>>> import networkx as nx
>>> from graphix.fundamentals import Plane
>>> from graphix.measurements import Measurement
>>> from graphix.opengraph import OpenGraph
>>> from graphix.parameter import Placeholder
>>> # Initialize placeholders and open graph
>>> parametric_angles = [Placeholder(f"alpha{i}") for i in range(2)]
>>> measurements = {node: Measurement.XY(angle) for node, angle in enumerate(parametric_angles)}
>>> og = OpenGraph(
...     graph=nx.Graph([(0, 1), (1, 2)]),
...     input_nodes=[0],
...     output_nodes=[2],
...     measurements=measurements,
... )
>>> # To perform substitution, use the actual object in memory
>>> new_og = og.with_parameter(parametric_angles[0], 0.3)
>>> # Note: og.with_parameter(Placeholder("alpha0"), 0.3) would not trigger any substitution.
with_parameters(assignment: Mapping[Parameter, ExpressionOrSupportsFloat]) → OpenGraph[_M][source]

Perform parallel substitution of multiple parameters in measurement angles.

Creates a new open graph where occurrences of parameters defined in the assignment mapping are replaced by their corresponding values. The original open graph instance remains unmodified.

Parameters:

assignment (Mapping[Parameter, ExpressionOrSupportsFloat]) – A dictionary-like mapping where keys are the Parameter objects to be replaced and values are the new expressions or numerical values.

Returns:

A new instance of OpenGraph with the updated measurement angles.

Return type:

OpenGraph[Measurement]

Notes

The notes provided in self.subs() apply here as well.

Examples

>>> import networkx as nx
>>> from graphix.fundamentals import Plane
>>> from graphix.measurements import Measurement
>>> from graphix.opengraph import OpenGraph
>>> from graphix.parameter import Placeholder
>>> # Initialize placeholders
>>> alpha = Placeholder("alpha")
>>> beta = Placeholder("beta")
>>> measurements = {0: Measurement.XY(alpha), 1: Measurement.XY(beta)}
>>> og = OpenGraph(nx.Graph([(0, 1)]), [0], [], measurements)
>>> # Substitute multiple parameters at once
>>> subs_map = {alpha: 0.5, beta: 1.2}
>>> new_og = og.with_parameters(subs_map)
__init__(graph: nx.Graph[int], input_nodes: Sequence[int], output_nodes: Sequence[int], measurements: Mapping[int, _AM_co], output_cliffords: Mapping[int, Clifford] = <factory>) → None
exception OpenGraphError[source]

Bases: Exception

Exception subclass to handle open graphs errors.