Quantum-Inspired Support Vector Machine
  Support vector machine (SVM) is a particularly powerful and flexible
supervised learning model that analyzes data for both classification and
regression, whose usual algorithm complexity scales polynomially with the
dimension of data space and the number of data points. To tackle the big data
challenge, a quantum SVM algorithm was proposed, which is claimed to achieve
exponential speedup for least squares SVM (LS-SVM). Here, inspired by the
quantum SVM algorithm, we present a quantum-inspired classical algorithm for
LS-SVM. In our approach, a improved fast sampling technique, namely indirect
sampling, is proposed for sampling the kernel matrix and classifying. We first
consider the LS-SVM with a linear kernel, and then discuss the generalization
of our method to non-linear kernels. Theoretical analysis shows our algorithm
can make classification with arbitrary success probability in logarithmic
runtime of both the dimension of data space and the number of data points for
low rank, low condition number and high dimensional data matrix, matching the
runtime of the quantum SVM.
