The discrete time quantum walk: Universality, transport and searching - Neil Lovett

Quantum walks have played an important role in the development of new quantum algorithms and also in other applications. In this talk, we show how the discrete time quantum walk can be shown to be universal for quantum computation. This work highlights structures on which perfect state transfer can be achieved with the quantum walk, an important property for both quantum communication and computing. High fidelity transport is also important in other fields including quantum biology. For example, charge transfer in photosynthetic bacteria can essentially be viewed as a quantum walk with decoherence. Finally, we move on to the application of the discrete time quantum walk to searching. Previous work has highlighted a dependence on the dimension of the dataset to be searched. Here, we investigate a secondary dependence on the underlying connectivity of the structure. We consider regular lattices, showing how the algorithmic efficiency is increased by additional connectivity. In addition, we study the effect of disorder on the algorithm using randomly generated percolation lattices. We show this disorder reduces, and eventually removes, the quantum speed up provided by the quantum algorithm.