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 cannot have any randomness. However, the measurement process is probabilistic, so is this how we get random walks in QM? Not really! Instead we use quantum superposition.

One way is to define a quantum walk on a line is to evolve so that a particle at the origin becomes a superposition of particles one step to the left and one to the right. (This is obviously quantum and not classical!) If we now measured the position we would find the particle either one step to the left or one step to the right. So the measurement has introduced a random element. However, 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 the state evolves into a superposition of the particle at many 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 of (complex valued) wavefunctions, cancellations can (and do) occur. The effect is that after \(N\) steps the probability distribution for the position is not Gaussian (which is the classical probability distribution). 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/\sqrt{2}, N/\sqrt{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

Mathematical Physics II (or equivalent Physics module covering Quantum Mechanics) 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).

Corequisites

Quantum Computing III or Quantum Mechanics III (or equivalent Physics modules covering Dirac notation). Quantum Computing III may be useful for applications to quantum computing, but it is not essential.

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.