Continuous-time quantum walks

Statistical Physics and Complexity Group meeting

Continuous-time quantum walks

Event details

Given a graph, classical random walks evolve a probability distribution over its vertices. Quantum walks do the same but for wave functions, which are described by giving the wave's amplitude at each vertex. A photon traversing an array of crystals is a physical example of a quantum walk. Here, it's not just a particle walking a graph, but a wave propagating through it and interfering with itself. Interference changes the behaviour of the walk in surprising ways and it has been shown to provide powerful computational advantages.

In this talk I'll introduce the topic of continuous-time quantum walks. We will focus on studying the scattering of wave packets on open graphs. The final goal is to explain Andrew M. Child's paper "Universal computation by quantum walk" (2009), which provides a method to execute any quantum computation (i.e. simulate any quantum evolution) using quantum walks. If there's time left, I will briefly discuss some of the algorithms that have been proposed using quantum walks.