Classification of the MNIST data set with quantum slow feature analysis

Quantum machine learning is a research discipline intersecting quantum algorithms and machine learning. While a number of quantum algorithms with potential speedups have been proposed, it is quite difficult to provide evidence that quantum computers will be useful in solving real-world problems. Our work makes progress towards this goal. In this work we design quantum algorithms for dimensionality reduction and for classification and combine them to provide a quantum classifier that we test on the MNIST data set of handwritten digits. We simulate the quantum classifier, including errors in the quantum procedures, and show that it can provide classification accuracy of $98.5\%$. The running time of the quantum classifier is only polylogarithmic in the dimension and number of data points. Furthermore, we provide evidence that the other parameters on which the running time depends scale favorably, ascertaining the efficiency of our algorithm.

Figure 1

Accuracy of our quantum classifier (QSFA with QFDC) versus the classical classifier (SFA with KNN) for polynomial expansions 2 and 3, using different numbers of pixels via PCA. For polynomial expansion 2, our quantum classifier (bottom dotted line) reaches the accuracy of the classical one (dashed line) for large enough dimensions. For polynomial expansion 3 (upper solid line), the two are almost indistinguishable. In this experiment, the error for the quantum classifier on the quantum linear algebra subroutines is $\epsilon ={10}^{-5}$ and ${\kappa }_t$ is less than 200.

Figure 2

Sensitivity analysis of the parameter $\mu$ of the data set while increasing $n$. The graph shows the value of the Frobenius norm and the ${\ell }_{\infty }$-norm as two options for $\mu$. The two upper dotted lines represent the Frobenius norm of $X$ and $\dot{X}$ (lower and upper line, respectively) for polynomial expansion of degree 2. The solid horizontal lines above 10 shows the trend of the Frobenius norm for the polynomial expansion of degree 3 of $X$ and $\dot{X}$ (lower and upper line, respectively). The two lines at the bottom represent the ${\ell }_{\infty }$-norm for $\dot{X}$ for the polynomial expansion of degrees 2 (dashed) and 3 (solid), respectively. The central slanting lines are the ${\ell }_{\infty }$-norm of $X$, for polynomial expansion of degrees 2 (dashed) and 3 (solid). For the MNIST data set, we see that both the Frobenius norm and the ${\ell }_{\infty }$-norm are practically constant when we increase the number of data points in the training set.

Figure 3

Sensitivity analysis of the parameter $\mu$ for the matrices $X$ and $\dot{X}$ while increasing $d$, the number of pixels for an image, by changing the PCA dimension, which is performed before the polynomial expansion. The plot shows the value of the Frobenius norm and the ${\ell }_{\infty }$-norm (i.e., max ${\ell }_1$-norm of the rows) as two options for $\mu$. The dashed lines are for the polynomial expansion of degree 2: The two upper lines are (from top to bottom) $\parallel \dot{X}{\parallel }_F$ and ${\parallel X\parallel }_F$ and the two lower dashed lines are (from top to bottom) ${\parallel X\parallel }_{\infty }$ and $\parallel \dot{X}{\parallel }_{\infty }$. The two dotted central lines track the Frobenius norm of the polynomial expansion of degree 3: $\parallel \dot{X}{\parallel }_F$ and ${\parallel X\parallel }_F$ (from top to bottom). The bottom solid lines represent the ${\ell }_{\infty }$-norm for the polynomial expansion of degree 3 of $\parallel \dot{X}\parallel$ and $\parallel X\parallel$ (from bottom to top). In general, the ${\ell }_{\infty }$-norm is always smaller than the Frobenius norm.

Figure 4

Sensitivity analysis of the condition number of $X$ and $\dot{X}$ while increasing $d$, the number of pixels, and discarding the 0 singular values. We plot the condition number of a polynomial expansion of degree 2: The upper dashed line is $\kappa \left(\dot{X}\right)$ and the lower dashed line is $\kappa \left(X\right)$. The upper solid lines are for a polynomial expansion of degree 3. In both cases, the condition number of $\dot{X}$ dominates the condition number of $X$. For the case of a polynomial expansion of degree 3, this happens after approximately 3500 pixels.

Figure 5

Sensitivity analysis of the condition numbers (after discarding the 0 singular values) while increasing the size of the training set (by adding the test set). The first two lines from the top represent the polynomial expansion of degree 3, with $\kappa \left(\dot{X}\right)$ bigger than $\kappa \left(X\right)$. The two central lines are the condition numbers for the polynomial expansion of degree 3, while discarding $0.5\%$ of the smallest singular values [again $\kappa \left(\dot{X}\right)$ is bigger than $\kappa \left(X\right)$]. The two bottom lines represent the condition numbers for polynomial expansion of degree 2. In all three cases, the condition number of $\dot{X}$ is bigger than the condition number of $X$.

Figure 6

The QRAM tree for matrices $X_k$ and for the Frobenius norms of the submatrices of each class.