Logical Approaches to Computational Barriers

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 |