  Among the models of quantum computation, the One-way Quantum Computer is oneof the most promising proposals of physical realization, and opens newperspectives for parallelization by taking advantage of quantum entanglement.Since a one-way quantum computation is based on quantum measurement, which is afundamentally nondeterministic evolution, a sufficient condition of globaldeterminism has been introduced as the existence of a causal flow in a graphthat underlies the computation. A O(n^3)-algorithm has been introduced forfinding such a causal flow when the numbers of output and input vertices in thegraph are equal, otherwise no polynomial time algorithm was known for decidingwhether a graph has a causal flow or not. Our main contribution is to introducea O(n^2)-algorithm for finding a causal flow, if any, whatever the numbers ofinput and output vertices are. This answers the open question stated by Danosand Kashefi and by de Beaudrap. Moreover, we prove that our algorithm producesan optimal flow (flow of minimal depth.)  Whereas the existence of a causal flow is a sufficient condition fordeterminism, it is not a necessary condition. A weaker version of the causalflow, called gflow (generalized flow) has been introduced and has been provedto be a necessary and sufficient condition for a family of deterministiccomputations. Moreover the depth of the quantum computation is upper bounded bythe depth of the gflow. However, the existence of a polynomial time algorithmthat finds a gflow has been stated as an open question. In this paper we answerthis positively with a polynomial time algorithm that outputs an optimal gflowof a given graph and thus finds an optimal correction strategy to thenondeterministic evolution due to measurements.
A O(n^3)-algorithm has been introduced for finding such a causal flow when the numbers of output and input vertices in the graph are equal, otherwise no polynomial time algorithm was known for deciding whether a graph has a causal flow or not. Our main contribution is to introduce a O(n^2)-algorithm for finding a causal flow, if any, whatever the numbers of input and output vertices are.