An extremal result for geometries in the one-way measurement model
We present an extremal result for the class of graphs G which (together with some specified sets of input and output vertices, I and O) have a certain "flow" property introduced by Danos and Kashefi for the one-way measurement model of quantum computation. The existence of a flow for a triple (G, I, O) allows a unitary embedding to be derived from any choice of measurement bases allowed in the one-way measurement model. We prove an upper bound on the number of edges that a graph G may have, in order for a triple (G, I, O) to have a flow for some I, O subset of V(G), in terms of the number of vertices in G and O. This implies that finding a flow for a triple (G, I, O) when vertical bar I vertical bar = vertical bar O vertical bar = k (corresponding to unitary transformations in the measurement model) and IV(G)l = n can be performed in time O(k(2)n), improving the earlier known bound of O(km) given in [8], where m = vertical bar E(G)vertical bar.
flows measurement-based quantum computing