Optimising the information flow of one-way quantum computations

摘要: In the one-way quantum computing model, information processing is driven by measurements performed on an entangled state, called resource state. order to achieve parallelism, one aims increase number of simultaneous measurements, such that effects decoherence state are minimised due reduction time required run computation. At heart this question notion flow, which specifies dependency relations between in computations. There exist two well-known techniques for reducing perform a computation without changing its semantics. The first one, signal-shifting, transforms flow graph (representing state) within measurement calculus formalism, whereas second namely finding maximally-delayed generalised explores geometry operations can be simultaneously. paper, we show how these relate each other. We prove application signal-shifting rules pattern with results pattern. Then, particular case when input size equals output size, gflow obtained using has lowest possible depth. As side result, construct O(n3)- algorithm maximally delayed gflows graphs flow. For those graphs, our more efficient than best previously known same task, takes O(n4) complete.