Quantum Algorithms for Linear Algebra and Machine Learning

Most quantum algorithms offering speedups over classical algorithms are based on the three techniques of phase estimation, amplitude estimation and Hamiltonian simulation. In spite of the linear algebraic nature of the postulates of quantum mechanics, until recent work by Lloyd and coauthors no quantum algorithms achieving speedups for linear algebra or machine learning had been proposed.;A quantum machine learning algorithm must address three issues: encoding of classical data into a succinct quantum representation, processing the quantum representation and extraction of classically useful information from the processed quantum state. In this dissertation, we make progress on all three aspects of the quantum machine learning problem and obtain quantum algorithms for low rank approximation and regularized least squares.;The oracle QRAM, the standard model studied in quantum query complexity, requires time O(sqrt n) to encode vectors v in Rn into quantum states. We propose simple hardware augmentations to the oracle QRAM, , that enable vectors ;Using the augmented QRAM, for vector state preparation, we present two different algorithms for singular value estimation where given singular vector ;{mtimes n};{3}};{-irho};We use quantum singular value estimation to obtain algorithms for low rank approximation by column selection, the algorithms are based on importance sampling from the leverage score distribution. We obtain quadratic speedups for a large class of linear algebra algorithms that rely on importance sampling from the leverage score distribution including approximate least squares and CX and CUR decompositions. Classical algorithms for these problems require time O(mn log n + poly(1/epsilon)), the quantum algorithms have running time O(sqrt mpoly(1/epsilon, k, Delta)) where k, Delta are the rank and spectral gap. The running time of the quantum CX decomposition algorithm does not depend on m, it is polynomial in problem parameters. We also provide quantum algorithms for ℓ2 regularized regression problems, the quantum ridge regression algorithm requires time O (1/mu2 delta) to output a quantum state that is delta close to the solution, where mu is the regularization parameter.