Quantum support vector machine based on regularized Newton method

An elegant quantum version of least-square support vector machine, which is exponentially faster than the classical counterpart, was given by Rebentrost et al. using the matrix inversion algorithm (HHL). However, the application of the HHL algorithm is restricted when the structure of the input matrix is not well. The iteration algorithms such as the Newton method are widespread in training the classical support vector machine. This paper demonstrates a quantum support vector machine based on the regularized Newton method (RN-QSVM), which achieves an exponential speed-up over classical algorithm. At first, the regularized quantum Newton algorithm is proposed to get rid of the constraint of input matrix. Then we train the RN-QSVM by using the regularized quantum Newton algorithm and classify a query sample by constructing the quantum state. Experiments demonstrate that RNQSVM respectively provides advantages in terms of accuracy, robustness, and complexity compared to QSLS-SVM, LS-QSVM, and the classical method.