QUANTUM ALGORITHMS FOR PROVABLE MACHINE LEARNING

Abstract

The thesis explores the quantum speedups for various machine learning algorithms, including the neural network, the Hedge algorithm, the Ising model and Markov Random Fields, with provable learning guarantees. A main subroutine in these quantizations is the inner product estimation of vectors. The exact computation of inner product is first replaced with estimation. Then the estimation is sped-up using quantum amplitude amplification. Then a quadratic speedup in terms of the data dimension is obtained.