Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
Non-unitary quantum walks: exploring the space between classical and quantum computing

Speaker: Viv Kendon
Author(s): Viv Kendon
Slot: Array, 10:50-11:10, col. 3


Quantum versions of random walks have markedly different properties from
classical random walks.  For example:
-  on a line, they spread quadratically faster,
- they generally do not mix, and if they do, they generally do not
mix to the uniform distribution,
- on a hypercube or similar graph, they can hit the opposite corner
exponentially faster.
These properties have been exploited to create several quantum algorithms.  It
has also been observed that making the quantum walk slightly less than perfectly
quantum can actually improve the useful behaviour, for example producing faster
than classical mixing to the uniform distribution.  In this talk I will explain
how to generalise a quantum walk into a non-unitary dynamics that can
interpolate between classical and quantum behaviours by tuning a single
parameter.  In this way, the transition between quantum and classical behaviour
can be located and characterised.

websites: Arnold Beckmann 2006-04-28