flow and gflow

graphix.gflow module

graphix.gflow.gflow(graph, input, output, meas_planes, mode='single')[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.flow(graph, input, output, meas_planes=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 (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.