Quantum kernels can solve machine learning problems that are hard for all classical methods

Few concepts in computer science cause as much excitement—and perhaps as much potential for hype and misinformation—as quantum machine learning. Several algorithms in this space have hinted at exponential speedups over classical machine learning approaches, by assuming that one can provide classical data to the algorithm in the form of quantum states. However, we don't actually know whether a method exists that can efficiently provide data in this way.

Many proposals for quantum machine learning algorithms have been made that can be best characterized as “heuristics,” meaning that these algorithms have no formal proof that supports their performance. These proposals are motivated by the challenge to find algorithms that are friendly towards near-term experimental implementation with only conventional access to data. One such class of algorithms was the proposal for quantum enhanced feature spaces—also known as quantum kernel methods, where a quantum computer steps in for just a part of the overall algorithm—by Havlíček et al.¹ 

Despite the popularity of these quantum kernel methods, the central question remains:

Today, we're excited to announce a quantum kernel algorithm that, given only classical access to data, provides a provable exponential speedup over classical machine learning algorithms for a certain class of classification problems. Classification problems are one of the most fundamental problems in machine learning. They begin by training an algorithm on data, called a training set, where data points include one of two labels. Following the training phase is a testing phase where the algorithm needs to classify a new data point that has not been seen before.

A standard example is when we give a computer pictures of dogs and cats, and from this dataset it classifies all future images as a dog or a cat. Ultimately, the goal of an efficient machine learning algorithm for classification should be to generate an accurate label in an amount of time that scales polynomially with the size of the input.

Our team successfully developed a specific classification task for which quantum kernel methods are provably better than classical methods. The article describing this work was recently published in Nature Physics² by Yunchao Liu from University of California, Berkeley and IBM research intern, alongside coauthors Srinivasan Arunachalam and Kristan Temme at IBM.

The quantum algorithm, based on a quantum kernel method, employs a time-proven conventional machine learning model to learn the kernel function, which finds the relevant features in the data to use for classification. Its quantum advantage comes from the fact that we can construct a family of datasets for which only quantum computers can recognize the intrinsic labeling patterns, while for classical computers the dataset looks like random noise.

Solving the discrete log problem

We prove the advantage by employing a well-known problem that separates classical and quantum computation: computing logarithms in a cyclic group, where you can generate all the members of the group using a single mathematical operation. This problem—known as the discrete log problem—can be efficiently solved on a quantum computer by using Shor's famous algorithm, a problem widely believed to take a superpolynomial amount of time on a classical computer. 

In order to use this technique, our team constructed a family of classification problems based on discrete log, and showed that no efficient classical algorithm can do better than random guessing when attempting to solve this family of problems, based on the standard hardness assumption of the discrete log problem. Furthermore, we constructed a quantum feature map—a way to view complicated data in a higher-dimensional space to pull out patterns—alongside the corresponding kernel function, in order to predict the labels with high accuracy. Moreover, one can show that the high accuracy persists in the presence of finite sampling noise from taking measurements, a form of noise that needs to be considered even for fault-tolerant quantum computers. 

There are caveats, of course. There will still be many real life problems for which this quantum algorithm does not perform better than conventional classical machine learning algorithms. To obtain an advantage, the classification problem must first adhere to this cyclical structure described above. We've left it to an upcoming work to discuss how generalizable this structure is. Additionally, performing this quantum kernel estimation algorithm for useful cases is perhaps beyond the reach of the quantum hardware available today.

Quantum machine learning progress

All-in-all, however, this paper can be viewed as a milestone in the field of quantum machine learning, since it proves an end-to-end quantum speed-up for a quantum kernel method implemented fault-tolerantly with realistic assumptions. Prior to this work, there existed proposed quantum machine learning algorithms, but most of these algorithms either required strong input assumptions or didn't rigorously prove their advantage. But now, there is a set of machine learning problems for which there really exists a quantum speedup with the quantum kernel estimation algorithm—and an exponential speedup, at that.

As our team continues to research in this space, we've prioritized delivering rigorously proven quantum advantages with robust speedups, while making an effort to present our results in a widely accessible way to the community.

Quantum machine learning eduction

Machine learning is the theme of this year's Qiskit Global Summer School, focusing specifically on the quantum kernel estimation algorithm plus its strengths and limitations. We hope to continue building and disseminating quantum computing research for the wider quantum community, and hope that we can develop a quantum ecosystem that can generate more research, together with the help and feedback from the community.