Unitary-circuit semantics for measurement-based computations

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.)

References in corpus (11)

• Quantum Teleportation is a Universal Computational Primitive
• Measurement-based quantum computation with cluster states
• Determinism in the one-way model
• Unified derivations of measurement-based schemes for quantum computation
• Generalized Flow and Determinism in Measurement-based Quantum Computation
• A Quantum Algorithm for the Hamiltonian NAND Tree
• Quantum computing via measurements only
• Robust and parsimonious realisations of unitaries in the one-way model
• One-way Quantum Computation - a tutorial introduction
• Finding Optimal Flows Efficiently
• Finding flows in the one-way measurement model

Cited by in corpus (2)

• Many Worlds, the Cluster-state Quantum Computer, and the Problem of the Preferred Basis
• On the Physical Explanation for Quantum Computational Speedup