Study demonstrates the quantum speed up of supervised machine learning on a new classification task

In recent years, several computer scientists and physicists have been exploring the potential of quantum-enhanced machine learning algorithms. As their name suggests, quantum machine learning approaches combine quantum algorithms with machine learning techniques.

Most researchers investigating quantum machine learning algorithms have been trying to understand whether they could solve tasks faster than conventional machine learning techniques. One of the tasks that machine learning algorithms are commonly trained to complete are classification tasks, such as arranging images into different categories or accurately classifying specific objects or living creatures in an image.

Among the machine learning algorithms that achieved promising results in classification tasks are kernel methods, which include a renowned supervised learning technique called support-vector machine. Over the past few years, some scientists specialized in quantum algorithms have thus been exploring the potential of quantum kernel methods, which were first introduced by Havlicek and his colleagues at IBM.

Researchers at IBM Quantum have recently carried out a study further investigating the potential of quantum kernel methods. Their paper, published in Nature Physics, demonstrates that these methods could provide a robust quantum speed up over conventional kernel methods.

"Despite the popularity of quantum kernel methods, a fundamental question remained unanswered: Can quantum computers employ kernel methods to provide a provable advantage over classical learning algorithms?" Srinivasan Arunachalam, one of the researchers who carried out the study, told Phys.org. "Understanding this question was the starting point of our work. In this Nature Physics paper, along with my collaborators Yunchao Liu and Kristan Temme, we resolved this question in the affirmative."

As part of their study, Arunachalam and his colleagues constructed a classification problem that could be used to rigorously evaluate heuristic quantum kernel methods. Using this problem as an example, they proved the existence of a quantum kernel algorithm that can classify a set of points significantly faster than classical algorithms when trained on the same data and implemented on a fault-tolerance machine.

In the quantum kernel approach considered by the researchers a quantum computer steps in to run all the algorithm's computations, except for one specific portion. When given a set of classical data points, such as bit strings generated by a classical computer, the quantum kernel approach maps them into a higher dimensional space, where quantum computers can find patterns in data and extract characterizing features, using a technique called quantum kernel estimation (QKE).

"In order to use this technique for a separation between quantum and classical kernels, our starting point is a well-known problem that is often used to separate classical and quantum computing, the discrete logarithm problem," Arunachalam said. "This problem can be solved in polynomial time on a quantum computer using the famous Shor's algorithm but is strongly believed to require superpolynomial time for every classical algorithm."

Arunachalam and his colleagues were the first to construct a classification problem based on the hardness assumption of the discrete logarithm problem. Interestingly, they showed that the performance achieved by all classical machine learning techniques on this problem is worst or equal to random guessing, which is far from satisfactory.

"Subsequently, we constructed a kernel function that maps these classical data points onto a complex high dimensional feature space and show that QKE can solve this classification problem with very high precision in polynomial time," Arunachalam said. "An additional bonus is that we are able to show that this quantum speedup exists even if there is finite sampling noise while taking measurements, which is an important consideration for near-term and even fault-tolerant quantum computers."

Past studies have introduced several new quantum algorithms that could solve classification tasks faster than conventional machine learning techniques. However, most of these algorithms required strong input assumptions to achieve promising results or the researchers were unable to rigorously demonstrate their advantage over classical machine learning techniques.

"Our QKE algorithm can be viewed as an end-to-end quantum advantage for quantum kernel methods implemented on a fault-tolerant device (with realistic assumptions), since we start with classical data points and produce a classical solution for the classification problem using a quantum computer in the middle," Arunachalam said. "Of course, this is not the end of the road and instead only is reason to further understand quantum kernels better."

The recent work by this team of researchers provides a confirmation that quantum kernel methods could help to complete classification tasks faster and more efficiently. In their future studies, Arunachalam and his colleagues plan to investigate the potential of using these algorithms to tackle real world classification problems.

"The classification problem that we used to prove this advantage is artificially constructed to provide a theoretical underpinning for the usefulness of quantum kernels," Arunachalam said. "There is room to obtain further quantum speedups using quantum kernel methods for other (hopefully) practically relevant problems. We believe our result is interesting because it provides us with a direction to look for more learning problems that can benefit from kernel methods. In our future work we hope to understand how generalizable the structure of our classification problem is and if there are further speedups obtainable using similar structures."

© 2021 Science X Network