Physics – Quantum Physics
Scientific paper
2007-02-26
Physics
Quantum Physics
9 pages, 2 figures: numerous minor revisions to presentation. Version to appear in QIC vol. 8 #5
Scientific paper
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 \subseteq 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 |I| = |O| = k (corresponding to unitary transformations in the measurement model) and |V(G)| = n can be performed in time O(k^2 n), improving the earlier known bound of O(km) given in [quant-ph/0611284], where m = |E(G)|.
Beaudrap Niel de
Pei Martin
No associations
LandOfFree
An extremal result for geometries in the one-way measurement model does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An extremal result for geometries in the one-way measurement model, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An extremal result for geometries in the one-way measurement model will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-132011