Description

Quantum (random) walks are the quantum mechanics version of classical random walks. They can be either discrete or continuous time walks. There are some similarities between quantum and classical walks, but also striking differences.

A simple example of a classical discrete random walk is a particle on a line, initially at the origin. Each time step, the particle moves either 1 unit to the left or to the right, with equal probability. After N steps the position of the particle is random but (for large N) given by a Gaussian distribution of width square root of N, centred at the origin.

In quantum mechanics time evolution is unitary, hence reversible, so how can we have any randomness? One way is to evolve so that the particle at the origin becomes a superposition of particles one step to the left and one to the right. If we now measured the position we would find the particle either one step to the left or one step to the right. Repeating this process would just reproduce the classical random walk. For a quantum walk, we don't measure after each step but just keep evolving so that each position eigenstate evolves into a linear combination of the neighbouring positions.

The quantum walk sounds similar to the classical one, so what's interesting? Actually, they behave completely differently! In the quantum case because we have linear superposition, cancellations can (and do) occur. The effect is that after N steps the probability distribution for the position is not Gaussian. In fact the many different paths which end up with the particle near the origin mostly cancel in the linear superposition, with the result that the particle is almost equally likely to be found anywhere on an interval [-n, n] where n = N/(square root 2) and actually the distribution peaks near the ends of this interval. Another feature of quantum walks is that (because the evolution is reversible) the result can depend on the initial condition. E.g. in the simple particle on a line example some small changes to the initial state can result in a final probability distribution which is symmetric or very asymmetric.

What can I do in this project?

You can look at the behaviour of quantum walks by writing some code, e.g. in python. The line is the simplest example, but the walk can be on a circle or a more complicated graph. You can also do some analytic calculations, but simulating walks is very useful to explore different possibilities. You could look at applications to quantum computing. Essentially, random walks give a method to explore a space looking for a solution, and in some cases quantum walks give a much more efficient way to do that (if you have a quantum computer). You could also look at the relation between quantum and classical walks, something that comes under the theme of decoherence. E.g. as described above, measuring after every step turns a quantum walk into a classical one. But suppose you measure only occasionally, or do some partial measurements, does the final distribution look like a quantum or a classical walk? You could also explore similarities and differences between discrete and continuous time quantum walks.

Prerequisites

Quantum Computing III or Quantum Mechanics III (or equivalent Physics modules covering Dirac notation) is required. Willingness to write some simple programs to explore walks. Nothing more sophisticated that what was covered in first year Programming is required (so any other programming experience is fine if you didn't take the Programming I module in Maths). Quantum Computing III may be useful for applications to quantum computing, but it is not essential. Some knowledge of classical random walks may also be useful (e.g. as covered in some probability modules) but again this is not essential.

Corequisites

None.

Resources

A good place to start to get a few details and pictures is Wikipedia-Quantum walk. There is an excellent introductory review by Julia Kempe: Quantum random walks - an introductory overview.