Quantum Searching in Random Networks

Project description

The project deals with properties of quantum networks, that is, of networks on which unitary (wave-) evolution takes place along edges with scattering at the vertices. Such systems have been studied in the context of quantum information as well as in quantum chaos. It has been noted that a quadratic speed up of quantum random walks on these networks over classical random walks can be found on certain graphs with applications for search algorithms and search engines. The speed up has often be traced back to wave interference effects due to symmetries in the quantum propagation.

Recently, it has been shown, that quantum searching can also been undertaken on random graphs, that is, graphs for which connections between edges are given only wth a certain probability - so called Erdös-Rényi graphs. We will explore this new set-up for quantum searching and develop statisticsal models for the arrival times and success probabilities as well extend the model to realistic graph set-ups.

The project will be a good mix of graph theory, quantum mechanics and will require both analytical and numerical skills.