Characterization of the deterministic one-way computation
Simon Perdrix
Laboratoire Leibniz, Grenoble, France
Abstract: We extend the notion of quantum information flow defined by Danos and Kashefi for the one-way model and present a necessary and sufficient condition for the deterministic computation in this model. The generalized flow also applied in the extended model with (X,Y), (X,Z) and (Y,Z) measurements. We apply both measurement calculus and the stabilizer formalism to derive our main theorem which for the first time gives a full characterization of the deterministic computation in the one-way model. We present several examples to show how our result improves over the tradition notation of flow. There are several geometries (entanglement graph with input and output) with no flow but having generalized flow. More importantly one can also obtain a better quantum computation depth with the generalized flow rather than with flow. We further discuss how the generalized flow can be connected to the notation of the error correction for the quantum computing and translate a given measurement-based computing to a projection-based computing. We believe our characterization result is particularly essential for the study of the algorithms and complexity in the one-way model as generalized flow is the only way to obtain a deterministic computation in the extended one-way model.