Quantum Random Walks

Summary Random walks figure prominently in mathematics, computer science, physics,chemistry and biology, where they are used to model diffusion processes.Recently, the random walk paradigm has been carried over to the quantum setting. Here, the random walk is carried out "in superposition", with the possibility of negative amplitudes. The behavior of a quantum random walk is very different from that of a classical random walk, and its theory and potential applications are poorly understood. The quantum paradigm has led to efficient algorithms for fundamental computer science tasks, such as element distinctness, matrix multiplication and several search problems.It is therefore urgent to develop a proper theory of quantum random walks,which are tools for developing such algorithms. 

The project will investigate well known results from classical random walk theory and develops techniques to translate them to the quantum setting.

Supervisors Harry Buhrman (CWI/UvA), Frank den Hollander (UL)
PhD Student Tom Bannink (CWI)
Location Center for Mathematics and Computer Science (CWI)