Logical Approaches to Computational Barriers

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 |