flow and gflow

graphix.gflow module

graphix.gflow.gflow(g, v_in, v_out, meas_plane=None, timeout=1000)

Optimum generalized flow finding algorithm

For open graph g with input and output, this returns optimum 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).

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

Parameters

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

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

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

• timeout (int) – number of iterations allowed before timeout

Returns

• g (list of sets) – list of length |g| where each set is the correcting nodes for the measurements of each qubits. function g() in gflow.

• l_k (np.array) – 1D array of length |g|, where elements are layer of each qubits corresponds to the strict partial ordering < in gflow. Measurements must proceed in decreasing order of layer numbers.

graphix.gflow.flow(g, v_in, v_out, meas_plane=None, timeout=10000)

Causal flow finding algorithm

For open graph g with input and output, 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

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

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

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

• timeout (int) – number of iterations allowed before timeout

Returns

• f (list of nodes) – list of length |g| where each node corrects the measurements of each qubits. function f() in flow.

• l_k (np.array) – 1D array of length |g|, where elements are layer of each qubits corresponds to the strict partial ordering < in flow. Measurements must proceed in decreasing order of layer numbers.

graphix.gflow.solvebool(A, b)

solves linear equations of booleans

Solves Ax=b, where A is n*m matrix and b is 1*m array, both of booleans. for example, for A=[[0,1,1],[1,0,1]] and b=[1,0], we solve:

XOR(x1,x2) = 1

XOR(x0,x2) = 0

for which (one of) the solution is [x0,x1,x2]=[1,0,1]

Uses Z3, a theorem prover from Microsoft Research.

Parameters

• A (np.array) – n*m array of 1s and 0s, or booleans

• b (np.array) – length m array of 1s and 0s, or booleans

Returns

x – length n array of 1s and 0s satisfying Ax=b. if no solution is found, returns False.

Return type

np.array