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.

graphix.gflow.find_flow(graph: Graph, input: set[int], output: set[int], meas_planes: Optional[dict[int, str]] = None) → tuple[dict[int, set[int]], dict[int, int]][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 (nx.Graph) – graph (incl. in and out)

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

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

  • meas_planes (int(optional)) – 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 “XY”. If not specified, all measurement planes are interpreted as “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: Graph, input: set[int], output: set[int], meas_planes: dict[int, str], mode: str = 'single') → tuple[dict[int, set[int]], dict[int, int]][source]

Maximally delayed gflow finding algorithm

For open graph g with input, output, and measurement planes, this returns maximally delayed gflow.

gflow consist of function g(i) where i is the qubit labels, and strict partial ordering < or layers labels l_k where each element specify the order of qubits to be measured to maintain determinism in MBQC. In practice, we must measure qubits in order specified in array l_k (increasing order of l_k from 1), and for each measurements of qubit i we must perform corrections on qubits in g(i), depending on the measurement outcome.

For more details of gflow, see Browne et al., NJP 9, 250 (2007). We use the extended gflow finding algorithm in Backens et al., Quantum 5, 421 (2021).

Parameters

  • graph (nx.Graph) – graph (incl. in and out)

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

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

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

  • mode (str(optional)) –

    The gflow finding algorithm can yield multiple equivalent solutions. So there are three options

    • ”single”: Returrns a single solution

    • ”all”: Returns all possible solutions

    • ”abstract”: Returns an abstract solution. Uncertainty is represented with sympy.Symbol objects, requiring user substitution to get a concrete answer.

    Default is “single”.

Returns

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

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

graphix.gflow.find_pauliflow(graph: Graph, input: set[int], output: set[int], meas_planes: dict[int, str], meas_angles: dict[int, float], mode: str = 'single') → tuple[dict[int, set[int]], dict[int, int]][source]

Maximally delayed Pauli flow finding algorithm

For open graph g with input, output, measurement planes and measurement angles, this returns maximally delayed Pauli flow.

Pauli flow consist of function p(i) where i is the qubit labels, and strict partial ordering < or layers labels l_k where each element specify the order of qubits to be measured to maintain determinism in MBQC. In practice, we must measure qubits in order specified in array l_k (increasing order of l_k from 1), and for each measurements of qubit i we must perform corrections on qubits in p(i), depending on the measurement outcome.

For more details of Pauli flow and the finding algorithm used in this method, see Simmons et al., EPTCS 343, 2021, pp. 50-101 (arXiv:2109.05654).

Parameters

  • graph (nx.Graph) – graph (incl. in and out)

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

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

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

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

  • mode (str(optional)) –

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

    • ”single”: Returrns a single solution

    • ”all”: Returns all possible solutions

    • ”abstract”: Returns an abstract solution. Uncertainty is represented with sympy.Symbol objects, requiring user substitution to get a concrete answer.

    Default is “single”.

Returns

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

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

graphix.gflow.verify_flow(graph: Graph, input: set[int], output: set[int], flow: dict[int, set], meas_planes: dict[int, str] = {}) → bool[source]

Check whether the flow is valid.

Parameters

  • graph (nx.Graph) – graph (incl. in and out)

  • 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: Graph, input: set[int], output: set[int], gflow: dict[int, set], meas_planes: dict[int, str]) → bool[source]

Check whether the gflow is valid.

Parameters

  • graph (nx.Graph) – graph (incl. in and out)

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

  • output (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:: gflow.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: Graph, input: set[int], output: set[int], pauliflow: dict[int, set[int]], meas_planes: dict[int, str], meas_angles: dict[int, float]) → bool[source]

Check whether the Pauliflow is valid.

Parameters

  • graph (nx.Graph) – graph (incl. in and out)

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

  • output (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, str]) – 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]][source]

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

Parameters

pattern (graphix.Pattern object) – pattern to be based on

Returns

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

  • l_k (dict) – 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]][source]

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

Parameters

pattern (graphix.Pattern object) – pattern to be based on

Returns

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

  • l_k (dict) – 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]][source]

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

Parameters

  • pattern (graphix.Pattern object) – pattern to be based on

  • mode (str(optional)) –

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

    • ”single”: Returrns a single solution

    • ”all”: Returns all possible solutions

Returns

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

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