Quantum machine learning for supervised pattern recognition.

Abstract

Humans are experts at recognising patterns in past experience and applying them to new tasks. For example, after seeing pictures of a face we can usually tell if another image contains the same person or not. Machine learning is a research discipline at the intersection of computer science, statistics and mathematics that investigates how pattern recognition can be performed by machines and for large amounts of data. Since a few years machine learning has come into the focus of quantum computing in which information processing based on the laws of quantum theory is explored. Although large scale quantum computers are still in the first stages of development, their theoretical description is well-understood and can be used to formulate `quantum software' or `quantum algorithms' for pattern recognition. Researchers can therefore analyse the impact quantum computers may have on intelligent data mining. This approach is part of the emerging research discipline of quantum machine learning that harvests synergies between quantum computing and machine learning. The research objective of this thesis is to understand how we can solve a slightly more specific problem called supervised pattern recognition based on the language that has been developed for universal quantum computers. The contribution it makes is twofold: First, it presents a methodology that understands quantum machine learning as the combination of data encoding into quantum systems and quantum optimisation. Second, it proposes several quantum algorithms for supervised pattern recognition. These include algorithms for convex and non-convex optimisation, implementations of distance-based methods through quantum interference, and the preparation of quantum states from which solutions can be derived via sampling. Amongst the machine learning methods considered are least-squares linear regression, gradient descent and Newton's method, k-nearest neighbour, neural networks as well as ensemble methods. Together with the growing body of literature, this thesis demonstrates that quantum computing offers a number of interesting tools for machine learning applications, and has the potential to create new models of how to learn from data.