Phase map decompositions for unitaries

de Beaudrap, Niel; Danos, Vincent; Kashefi, Elham

Phase map decompositions for unitaries

Authors

de Beaudrap, Niel

Danos, Vincent

Kashefi, Elham

Description

We propose a universal decomposition of unitary maps over a tensorial power of C^2, introducing the key concept of "phase maps", and investigate how this decomposition can be used to implement unitary maps directly in the measurement-based model for quantum computing. Specifically, we show how to extract from such a decomposition a matching entangled graph state (with inputs), and a set of measurements angles, when there is one. Next, we check whether the obtained graph state verifies a "flow" condition, which guarantees an execution order such that the dependent measurements and corrections of the pattern yield deterministic results. Using a graph theoretic characterization of flows, we can determine whether a flow can be constructed for a graph state in polynomial time. This approach yields an algorithmic procedure which, when it succeeds, may produce an efficient pattern for a given unitary.
17 pages: earlier version submitted to ICALP 2006