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.