Quantum walks and cellular automata

Quantum walk vs classical random walk

In a simple classical random walk a single particle moves one step to the right or left, depending on the outcome of a single coin toss. It is commonly known that after many steps of such a walk the position of the particle is described by a normal probability distribution. However, if both, the coin and the particle, are quantum then the system is described by probability amplitudes which can interfere and the final probability distribution is far from normal.

Quantum simulator

Quantum walks are something more than just a quantized version of a random walk. They are rather quantum versions of classical cellular automata which are capable of simulating many complex physical processes. Therefore, quantum walks can play a role of a quantum simulator – a dynamical quantum process which is universal enough to be able to emulate dynamics of different quantum systems.

Eksperiments

Quantum walks were recently implemented in laboratories on various physical platforms. Some of the experiments involve single photons performing a quantum walk in specially designed and manufactured photonic crystals, cold atoms walking in optical lattices, or quantum walks of ions in magnetic traps. This shows that a true quantum simulator is practically available.  

Simulation of physical phenomena

It was shown that quantum walks are capable of simulating quantum chaos, relativistic quantum phenomena, or condensed matter effects like Bloch oscillations and Anderson localisation. At the moment we investigate quantum walks capable of simulating dynamics of a charged particle in a magnetic field, multipartite interactions, and dynamics of a system interacting with a heath bath. 

Other open problems

We are also interested in: how entangled initial conditions influence the dynamics of quantum walks, modelling of an arbitrary open system dynamics, and in application of the above quantum walk properties in quantum computation.