Quantum kernels can solve machine learning problems that are hard for all classical methods
IBM researchers have found mathematical proof of a potential quantum advantage for quantum machine learning.
IBM researchers have found mathematical proof of a potential quantum advantage for quantum machine learning.
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 nearterm 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.^{1}
Despite the popularity of these quantum kernel methods, the central question remains:
Are quantum algorithms using kernel methods actually capable of delivering a provable advantage over classical machine learning algorithms?
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^{2} 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 timeproven 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.
We prove the advantage by employing a wellknown 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 higherdimensional 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 faulttolerant 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.
Allinall, however, this paper can be viewed as a milestone in the field of quantum machine learning, since it proves an endtoend quantum speedup for a quantum kernel method implemented faulttolerantly 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.
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.
References

Havlíček, V., Córcoles, A.D., Temme, K. et al. Supervised learning with quantumenhanced feature spaces. Nature 567, 209–212 (2019). ↩

Liu, Y., Arunachalam, S. & Temme, K. A rigorous and robust quantum speedup in supervised machine learning. Nat. Phys. (2021). ↩