flow and gflow

graphix.gflow module

graphix.gflow.generate_from_graph(graph, angles, inputs, outputs, timeout=100)[source]

Generate the measurement pattern from open graph and measurement angles.

This function takes an open graph G = (nodes, edges, input, outputs), specified by networks.Graph and two lists specifying input and output nodes. Currently we support XY-plane measurements.

Searches for the flow in the open graph using flow() and if found, construct the measurement pattern according to the theorem 1 of [NJP 9, 250 (2007)].

Then, if no flow was found, searches for gflow using gflow(), from which measurement pattern can be constructed from theorem 2 of [NJP 9, 250 (2007)].

The constructed measurement pattern deterministically realize the unitary embedding

\[U = \left( \prod_i \langle +_{\alpha_i} |_i \right) E_G N_{I^C},\]

where the measurements (bras) with always \(\langle+|\) bases determined by the measurement angles \(\alpha_i\) are applied to the measuring nodes, i.e. the randomness of the measurement is eliminated by the added byproduct commands.

See also

flow() gflow() graphix.pattern.Pattern

Parameters

  • graph (networkx.Graph) – graph on which MBQC should be performed

  • angles (dict) – measurement angles for each nodes on the graph (unit of pi), except output nodes

  • inputs (list) – list of node indices for input nodes

  • outputs (list) – list of node indices for output nodes

  • timeout (int) – optional argument for flow and gflow search depth

Returns

pattern – constructed pattern.

Return type

graphix.pattern.Pattern object

graphix.gflow.gflow(g, v_in, v_out, meas_plane=None, timeout=100)[source]

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=100)[source]

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)[source]

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