Computability in Europe 2006
Logical Approaches to Computational Barriers

Special Session Talk:
A classical analogue of measurement-based quantum computation?

Speaker: Dan Browne


Measurement-based quantum computation (MBQC) is an important model of quantum
computation, which has delivered both new insights and practical advantages. In
measurement-based quantum computation, more specifically the ``one-way
model'' of computation, the computation proceeds in the following way.
A large number of quantum bits (qubits) are prepared in a special entangled 
state called a cluster state. The qubits are then measured in a particular basis
and particular order, the measurements are adaptive, some bases depending on the
outcome of previous measurements. A classical control computer processes the
measurement results in order to feed forward the bases for future measurements.

Unlike the more traditional ``circuit model'', which is a
straightforward generalisation of classical reversible gate networks to the
quantum domain, there is no clear classical analogue of MBQC. In this talk I
shall present some new results which shed some light on why this is the case. By
focussing on the computational power present in the classical computer, we are
able to analyse this question in a structured way. The talk shall be prefaced
with an introduction to measurement-based quantum computation for those
unfamiliar with this model.

The work presented here is joint work with Janet Anders (UCL) and has benefitted
from discussions with Akimasa Miyake (Innsbruck), Robin Blume-Kohout (Perimeter
Institute) and Debbie Leung (University of Waterloo).

websites: Arnold Beckmann 2008-03-25