Quantum algorithms for optimisation problems in machine learning

In the emerging discipline of quantum-enhanced machine learning, quantum computing is applied to machine learning tasks in order to improve the complexity, performance or robustness of the learning algorithms. In most cases the approach is to translate the training procedure into an optimisation problem which can be tackled by means of quantum information processing. Here we present two quantum algorithms that follow such an approach. The first one uses quantum techniques for density matrix exponentiation and matrix inversion for least-squares optimisation in linear regression. The second method considers the much more difficult realm of non-convex optimisation and proposes a quantum algorithm for gradient descent and Newton's method, with special application to optimisation of homogeneous polynomials. In the best case, both quantum algorithms have a logarithmic dependency on the dimensions of the dataset which makes them particularly interesting for big data applications.