Quantum Algorithms for Linear Algebra and Machine Learning by Anupam Prakash
Most quantum algorithms o ering 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 (23; 22; 24) 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(pn) to encode vectors v2Rn into quantum states. We propose simple hardware augmentations to the oracle QRAM, that enable vectors v2Rn to be encoded in time O(logn), with pre-processing. The augmented QRAM incurs minimal hardware overheads, the pre-processing can be parallelized and is a exible model that allows storage of multiple vectors and matrices. It provides a framework for designing quantum algorithms for linear algebra and machine learning.
Using the augmented QRAM for vector state preparation, we present two di erent algorithms for singular value estimation where given singular vector jvi forA2 Rm n, the singular value i is estimated within additive error kAkF. The rst algorithm requires time eO(1= 3 ) and uses the approach for simulating e CX and CUR decompositions. Classical algorithms for these problems require time O(mnlog n+poly(1= )), the quantum algorithms have running time O(p mpoly(1 = ;k; )) where k; 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 eO(1= 2 )to output a quantum state that is close to the solution, where is the regularization parameter.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
No comments:
Post a Comment