flow and gflow

graphix.gflow module

This provides functions to find flow structures (causal flow, gflow, Pauli flow) in a graph, to verify if a given flow structure is valid, and to extract flow structures from a given pattern.

Flow finding algorithm.

For a given underlying graph (G, I, O, meas_plane), this method finds a (generalized) flow [NJP 9, 250 (2007)] in polynomial time. In particular, this outputs gflow with minimum depth, maximally delayed gflow.

Ref: Mhalla and Perdrix, International Colloquium on Automata, Languages, and Programming (Springer, 2008), pp. 857-868. Ref: Backens et al., Quantum 5, 421 (2021).

graphix.gflow.find_flow(graph: nx.Graph[int], iset: set[int], oset: set[int], meas_planes: dict[int, Plane] | None = None) → tuple[dict[int, set[int]], dict[int, int]] | tuple[None, None][source]

Causal flow finding algorithm.

For open graph g with input, output, and measurement planes, this returns causal flow. For more detail of causal flow, see Danos and Kashefi, PRA 74, 052310 (2006).

Original algorithm by Mhalla and Perdrix, International Colloquium on Automata, Languages, and Programming (2008), pp. 857-868.

Parameters:

  • graph (networkx.Graph) – Graph (incl. input and output)

  • iset (set) – set of node labels for input

  • oset (set) – set of node labels for output

  • meas_planes (dict(int, Plane)) – measurement planes for each qubits. meas_planes[i] is the measurement plane for qubit i. Note that an underlying graph has a causal flow only if all measurement planes are Plane.XY. If not specified, all measurement planes are interpreted as Plane.XY.

Returns:

  • f (list of nodes) – causal flow function. f[i] is the qubit to be measured after qubit i.

  • l_k (dict) – layers obtained by gflow algorithm. l_k[d] is a node set of depth d.

graphix.gflow.find_gflow(graph: nx.Graph[int], iset: AbstractSet[int], oset: AbstractSet[int], meas_planes: Mapping[int, Plane], mode: str = 'single') → tuple[dict[int, set[int]], dict[int, int]] | tuple[None, None][source]

Return a maximally delayed general flow (gflow) of the input open graph if it exists.

Parameters:

  • graph (networkx.Graph) – Graph (including input and output).

  • iset (AbstractSet[int]) – Set of input nodes.

  • oset (AbstractSet[int]) – Set of output nodes.

  • meas_planes (Mapping[int, Plane]) – Measurement planes for each qubit. meas_planes[i] is the measurement plane for qubit i.

  • mode (str) – Deprecated. Reminiscent of old API, it will be removed in future versions.

Returns:

  • dict[int, set[int]] – Gflow correction function. In a given pair (key, value), value is the set of qubits to be corrected for the measurement of qubit key.

  • dict[int, int] – Partial order between corrected qubits, such that the pair (key, value) corresponds to (node, depth).

  • or None, None – if the input open graph does not have gflow.

Notes

This function implements the algorithm in [1], see module graphix.find_pflow. See [1] or [2] for a definition of gflow.

References

[1] Mitosek and Backens, 2024 (arXiv:2410.23439). [2] Backens et al., Quantum 5, 421 (2021).

graphix.gflow.find_pauliflow(graph: nx.Graph[int], iset: AbstractSet[int], oset: AbstractSet[int], meas_planes: Mapping[int, Plane], meas_angles: Mapping[int, ExpressionOrFloat], mode: str = 'single') → tuple[dict[int, set[int]], dict[int, int]] | tuple[None, None][source]

Return a maximally delayed Pauli flow of the input open graph if it exists.

Parameters:

  • graph (networkx.Graph) – Graph (including input and output).

  • iset (AbstractSet[int]) – Set of input nodes.

  • oset (AbstractSet[int]) – Set of output nodes.

  • meas_planes (Mapping[int, Plane]) – Measurement planes for each qubit. meas_planes[i] is the measurement plane for qubit i.

  • meas_angles (Mapping[int, ExpressionOrFloat]) – Measurement angles for each qubit. meas_angles[i] is the measurement angle for qubit i.

  • mode (str) – Deprecated. Reminiscent of old API, it will be removed in future versions.

Returns:

  • dict[int, set[int]] – Pauli flow correction function. In a given pair (key, value), value is the set of qubits to be corrected for the measurement of qubit key.

  • dict[int, int] – Partial order between corrected qubits, such that the pair (key, value) corresponds to (node, depth).

  • or None, None – if the input open graph does not have gflow.

Notes

This function implements the algorithm in [1], see module graphix.find_pflow. See [1] or [2] for a definition of Pauli flow.

References

[1] Mitosek and Backens, 2024 (arXiv:2410.23439). [2] Browne et al., 2007 New J. Phys. 9 250 (arXiv:quant-ph/0702212)

graphix.gflow.verify_flow(graph: nx.Graph, iset: set[int], oset: set[int], flow: dict[int, set], meas_planes: dict[int, Plane] | None = None) → bool[source]

Check whether the flow is valid.

Parameters:

  • graph (networkx.Graph) – Graph (incl. input and output)

  • flow (dict[int, set]) – flow function. flow[i] is the set of qubits to be corrected for the measurement of qubit i.

  • meas_planes (dict[int, str]) – optional: measurement planes for each qubits. meas_planes[i] is the measurement plane for qubit i.

Returns:

valid_flow – True if the flow is valid. False otherwise.

Return type:

bool

graphix.gflow.verify_gflow(graph: nx.Graph, iset: set[int], oset: set[int], gflow: dict[int, set], meas_planes: dict[int, Plane]) → bool[source]

Check whether the gflow is valid.

Parameters:

  • graph (networkx.Graph) – Graph (incl. input and output)

  • iset (set) – set of node labels for input

  • oset (set) – set of node labels for output

  • gflow (dict[int, set]) – gflow function. gflow[i] is the set of qubits to be corrected for the measurement of qubit i. .. seealso:: find_gflow()

  • meas_planes (dict[int, str]) – measurement planes for each qubits. meas_planes[i] is the measurement plane for qubit i.

Returns:

valid_gflow – True if the gflow is valid. False otherwise.

Return type:

bool

graphix.gflow.verify_pauliflow(graph: nx.Graph, iset: set[int], oset: set[int], pauliflow: dict[int, set[int]], meas_planes: dict[int, Plane], meas_angles: dict[int, float]) → bool[source]

Check whether the Pauliflow is valid.

Parameters:

  • graph (networkx.Graph) – Graph (incl. input and output)

  • iset (set) – set of node labels for input

  • oset (set) – set of node labels for output

  • pauliflow (dict[int, set]) – Pauli flow function. pauliflow[i] is the set of qubits to be corrected for the measurement of qubit i.

  • meas_planes (dict[int, Plane]) – measurement planes for each qubits. meas_planes[i] is the measurement plane for qubit i.

  • meas_angles (dict[int, float]) – measurement angles for each qubits. meas_angles[i] is the measurement angle for qubit i.

Returns:

valid_pauliflow – True if the Pauliflow is valid. False otherwise.

Return type:

bool

graphix.gflow.flow_from_pattern(pattern: Pattern) → tuple[dict[int, set[int]], dict[int, int]] | tuple[None, None][source]

Check if the pattern has a valid flow. If so, return the flow and layers.

Parameters:

pattern (Pattern) – pattern to be based on

Returns:

  • None, None – The tuple (None, None) is returned if the pattern does not have a valid causal flow.

  • f (dict[int, set[int]]) – flow function. g[i] is the set of qubits to be corrected for the measurement of qubit i.

  • l_k (dict[int, int]) – layers obtained by flow algorithm. l_k[d] is a node set of depth d.

graphix.gflow.gflow_from_pattern(pattern: Pattern) → tuple[dict[int, set[int]], dict[int, int]] | tuple[None, None][source]

Check if the pattern has a valid gflow. If so, return the gflow and layers.

Parameters:

pattern (Pattern) – pattern to be based on

Returns:

  • None, None – The tuple (None, None) is returned if the pattern does not have a valid gflow.

  • g (dict[int, set[int]]) – gflow function. g[i] is the set of qubits to be corrected for the measurement of qubit i.

  • l_k (dict[int, int]) – layers obtained by gflow algorithm. l_k[d] is a node set of depth d.

graphix.gflow.pauliflow_from_pattern(pattern: Pattern, mode='single') → tuple[dict[int, set[int]], dict[int, int]] | tuple[None, None][source]

Check if the pattern has a valid Pauliflow. If so, return the Pauliflow and layers.

Parameters:

  • pattern (Pattern) – pattern to be based on

  • mode (str) –

    The Pauliflow finding algorithm can yield multiple equivalent solutions. So there are two options

    • ”single”: Returns a single solution

    • ”all”: Returns all possible solutions

    Optional. Default is “single”.

Returns:

  • None, None – The tuple (None, None) is returned if the pattern does not have a valid Pauli flow.

  • p (dict[int, set[int]]) – Pauli flow function. p[i] is the set of qubits to be corrected for the measurement of qubit i.

  • l_k (dict[int, int]) – layers obtained by Pauli flow algorithm. l_k[d] is a node set of depth d.