A supervised machine learning problem with a provable quantum speed-up

Quantum machine learning is touted as one of the big potential applications of quantum computers. In quantum machine learning kernel methods are a topic attracting increasing interest as a means of circumventing the barren plateau problem that makes training of variational neural network-like quantum circuits challenging if not impossible.

The idea behind the kernel trick is to map data to a high-dimensional feature space. Owing to the curse (or blessing in this case) of dimensionality, complex datasets can become linearly separable in the high-dimensional space, allowing one to perform supervised classification using simple linear models. Quantum circuits generate states belonging to a huge (exponentially large) Hilbert space, suggesting that they may be naturally suited towards computing high dimensional feature maps. At least, this is what many researchers hope.

The challenge is that having a high dimensional feature space is a necessary but not sufficient condition for performing accurate classification. Therefore one needs to come up with a kernel that is not only hard to compute on a classical computer, but is also able to achieve a classification performance superior to any efficiently classically-computable kernel. A daunting task to prove, and a study by researchers at Google published recently suggests quantum kernels for classical machine learning tasks may be hard to find.

Yesterday researchers from IBM published a study in Nature Physics which is the first to my knowledge to propose a machine learning problem for which a quantum kernel can provide a rigorous advantage compared to classical kernel methods. The clever trick used by the authors is to consider a feature map that uses Shor's algorithm as a subroutine, which has a proven quantum advantage. The authors show that this feature map can be used efficiently classify a dataset whose labels are related to the classically-hard discrete logarithm problem. In the original space the data appear to be randomly distributed, such classical algorithms are limited to random guessing. On the other hand, the quantum feature map leads to a clear hyperplane distinguishing the data classes.

Like many recent rigorous demonstrations of quantum speed ups for machine learning, the problem considered by the authors was chosen specifically for its ability to exhibit a quantum speed up, and does not have any known practical applications. It is interesting to note that the hardness of the discrete logarithm problem underlies certain cryptographic protocols. So this is work may be a promising step towards potential useful applications of quantum machine learning. Worth a closer read!