Quantum algorithm for support matrix machines

We propose a quantum algorithm for support matrix machines (SMMs) that efficiently addresses an image classification problem by introducing a least-squares reformulation. This algorithm consists of two core subroutines: a quantum matrix inversion (Harrow-Hassidim-Lloyd, HHL) algorithm and a quantum singular value thresholding (QSVT) algorithm. The two algorithms can be implemented on a universal quantum computer with complexity $O\left[log\left(npq\right)\right]$ and $O\left[log\left(pq\right)\right]$, respectively, where $n$ is the number of the training data and $pq$ is the size of the feature space. By iterating the algorithms, we can find the parameters for the SMM classfication model. Our analysis shows that both HHL and QSVT algorithms achieve an exponential increase of speed over their classical counterparts.

Figure 1

Entire process of SMM learning algorithm.

Figure 2

Loss functions in a SMM. The blue dashed line represents the hinge loss ${\ell }^{\mathrm{hinge}}$ in the original objective function and the red solid line the square loss ${\ell }^{\mathrm{square}}$ used in our method. Here we introduce a new parameter $\mu$ to make ${\ell }^{\mathrm{hinge}}$ upper bounded by ${\ell }^{\mathrm{square}}$ strictly.