YANG SIYICENTRE FOR QUANTUM TECHNOLOGIES2021-12-312021-12-312021-08-20YANG SIYI (2021-08-20). QUANTUM ALGORITHMS FOR PROVABLE MACHINE LEARNING. ScholarBank@NUS Repository.https://scholarbank.nus.edu.sg/handle/10635/212696The 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.enquantum speedup, amplitude amplification, p-concept learnable, inner product estimation, samplingThesis