Two Quantum Algorithms accelerating traditional Machine Learning

With growing demands of complex models that requires increasing amount of training data and larger parameter space, the efficiency of traditional machine learning is limited by its communication and computational complexity. Here we present a communication-efficient quantum algorithm that tackles two traditional machine learning problems, the least-square fitting and SoftMax regression problem, in the scenario where the data set is distributed across two parties. Our quantum algorithm finds the model parameters by solving linear equations with a communication complexity of $O(frac{log_2(N)}{epsilon})$, where $N$ is the number of data points and $epsilon$ is the bound on fitting parameter errors. Compared to classical algorithms and other quantum algorithms that achieve the same task, our algorithm provides a communication advantage in the scaling with the data volume. Further, we show that the building block of our algorithm, the quantum-accelerated estimation of inner product and Hamming distance, has time complexity of $O(frac{log_2(N)}{epsilon})$. Using similar building block we also provide[BL2] an algorithm that accelerate the parameter optimization process of non-linear problems with time complexity $O(frac{log_2(N) log_2(N')}{epsilon^{3/2}})$, where $N$ is the size of parameter space.