Abstract

The one-way quantum computer was proposed in 2001 by Raussendorf and Briegel as a potential framework for actually constructing quantum computers, but captured the interest of a number of theorists for the unusual way in which computations are described: primarily by single-qubit measurements. In the original way of regarding it, for instance, any unitary transformations which are performed involve mutually commuting operations to prepare a generic resource state which is completely independent of what is being computed; the “real work” is done by an adaptive strategy of single-spin measurement with classical communication. Nevertheless, it is often understood in terms of simulating unitary dynamics by a correspondance with the circuit model. Even so, not all measurement-based computations need arise from unitary circuits. This suggests the questions of

• determining when a measurement-based computation indeed simulates a unitary transformation in a meaningful sense;
• in the case that it does, determining if it can be said to be simulating a particular circuit which performs the same unitary; and
• finding additional ways to describe measurement-based computation in higher-level terms, should unitary circuits fail to adequately provide semantics for all measurement based computations.

I will give a brief overview of measurement-based computation (as a theoretical model), and describe some of the results and tools surrounding these problems, which consist largely of the well-publicized “flow” methods developed by Kashefi et al. I will also describe what I consider to be the natural research directions for these topics.