Unitary-circuit semantics for measurement-based computations
arXiv:0906.4261
Abstract
One-way measurement based quantum computations (1WQC) may describe unitary transformations, via a composition of CPTP maps which are not all unitary themselves. This motivates the following decision problems: Is it possible to determine whether a ``quantum-to-quantum'' 1WQC procedure (having non-trivial input and output subsystems) performs a unitary transformation? Is it possible to describe precisely how such computations transform quantum states, by translation to a quantum circuit of comparable complexity? In this article, we present an efficient algorithm for transforming certain families of measurement-based computations into a reasonable unitary circuit model, in particular without employing the principle of deferred measurement.
92 pages, 14 figures, 2 appendices. This article consists of a more general, more concisely written presentation of the main result of Chapter 3 of [arXiv:0812.2869]. (This version: improved introduction and bibliographical references, slight improvement of analysis.)