Quantum walk search: from grids to networks

Overview & Synopsis

Quantum computing is a new field of computer science that leverage the quan- tum properties of atomic and subatomic particles for solving computational tasks. However, quantum computing provides very little intuition on how it works. This makes the identification of computational tasks with a potential quantum speedup and the elaboration of quantum algorithms for said tasks very difficult. In this context, this thesis focuses on a quantum dynamical system called Discrete Time Quantum Walk (DTQW). DTQWs are dynamical systems with discrete time and space which are inspired from random walks. This thesis focuses on the problem of searching an element in an unstructured database. It is known in the literature that searching p an element with a DTQW on a grid has a quasi-square-root (i.e. O( n poly-log n)) complexity in the dataset size n. This provides a significant quantum speedup over the linear complexity of classical brute-force or random walk based algorithms. A first contribution of this thesis shows that, when two elements are searched, the worst case complexity becomes quasi-linear while the average case complexity remains quasi- square-root. Moving on from grids to arbitrary topologies, a second contribution introduces a new model of DTQW onto the edges of an arbitrary graph. This model unique features are: (i) the position which is on the edges; (ii) a polarity on each edge that generalizes the notion of right and left we have on a line. A third contribution introduces a model of quantum distributed computing and shows how this model on an arbitrary graph can reproduce the dynamic of a DTQW on the same graph.