Quantum machine learning and linear algebra algorithms from spectral graph theory

The problem of recognizing hidden structures in data is a fundamental one in a vast range of fields. Over the last two decades information technology has began to intensively rely on it. One of the main reasons is the increasing amount of data that is becoming available. In order to keep the pace with the amount of data we need to analyse, more efficient methods need to be found. The idea of quantum machine learning is to use the inherent properties of quantum mechanics to improve or speedup the process of algorithmic learning. Even though a quantum computer is not expected to solve NP-complete problems in polynomial time, it can non-trivially speedup classical algorithms for NP-complete problems. Many machine learning problems, as for example k-nearest-neighbour clustering, fall in the worst case scenario into this category. Therefore the hope is that these problems can obtain a non-trivial speed up in the quantum setting. In this project we specifically want to consider possible new ways of utilising insights from spectral graph theory in the area of quantum machine learning to design algorithms that can outperform their classical counterparts and potentially demonstrate 'supremacy' of quantum technologies.