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 input and output vertices, I O) have a certain "flow" property introduced by Danos Kashefi one-way measurement model quantum computation. The existence flow triple (G,I,O) allows unitary embedding to be derived from any choice bases allowed in model. prove upper bound on number edges that graph may have, order $I, O \subseteq V(G)$, terms vertices O. This implies finding when |I| = |O| k (corresponding transformations model) |V(G)| n can performed time O(k^2 n), improving earlier known O(km) given [quant-ph/0611284], where m |E(G)|.