In measurement-based quantum computation (MBQC), elementary quantum operations can be more parallelized than the quantum circuit model by employing a larger Hilbert space of graph states used as the resource. Thus MBQC can be regarded as a method of quantum computation where the temporal resource described by the depth of quantum operations can be reduced compared to the quantum circuit model by using the extra spatial resource described by graph states. To analyze the trade-off relationship of the spatial and temporal resources, we consider a method to obtain quantum circuit decompositions of general unitary transformations represented by MBQC on graph states with a certain underlying geometry called generalized flow. We present a method to translate any MBQC with generalized flow into quantum circuits without extra spatial resource. We also show an explicit way to unravel acausal gates without postselection that appear in the quantum circuit decomposition derived by a translation method [V. Danos and E. Kashefi, Phys. Rev. A 74, 052310 (2006)] and that represents an effect of the reduction of the temporal resource in MBQC. Finally, by considering a way to deterministically simulate these acausal gates, we investigate a general framework to analyze the trade-off between the spatial and temporal resources for quantum computation.

• Received 29 September 2014

DOI:https://doi.org/10.1103/PhysRevA.91.052302