IBM Announces Quantum Kernel Algorithm with Provable Exponential Speedup over Classical Machine Learning Algorithms for Certain Class of Classification Problems

(IBM.Research) IBM has announced 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.
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.
IBM’s 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 Physics2 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.