Finding flows in the one-way measurement model

The one-way measurement model is a framework for universal quantum computation in which algorithms are partially described by a graph G of entanglement relations on a collection of qubits. A sufficient condition for an algorithm to perform a unitary embedding between two Hilbert spaces is for the graph G, together with input and output I, O vertices I,O⊆V(G), to have a flow in the sense introduced by Danos and Kashefi Phys. Rev. A 74 052310 (2006)]. For the special case of |I|=|O|, using a graph-theoretic characterization, I show that such flows are unique when they exist. This leads to an efficient algorithm for finding flows by a reduction to solved problems in graph theory.