In recent years, several computer scientists and physicists have been exploring the potential of quantum improved algorithms for machine learning. As the name suggests, quantum machine learning approaches combine quantum algorithms with machine learning techniques. Most of the researchers studying quantum machine learning algorithms have tried to understand whether they could solve tasks faster than traditional machine learning techniques. One of the tasks that machine learning algorithms are usually fully trained is classification tasks, such as organizing images in different categories or classifying precisely certain objects or living beings in an image.
Machine learning algorithms that have shown promising results on classification tasks include kernel methods, which include a well-known supervised learning technique called the Support vector machine. In recent years, some scientists who specialize in quantum algorithms have explored the potential of quantum nuclear techniques, which were first introduced by Havlicek and his colleagues at IBM. IBM Quantum researchers recently conducted a study to further explore the potential of quantum kernel methods. Their paper, published in Nature Physics, shows that these methods could offer robust quantum acceleration over conventional kernel methods.
“Despite the popularity of quantum kernel methods, one fundamental question remained unanswered: Can quantum computers with kernel methods offer a proven advantage over traditional learning algorithms?” Srinivasan Arunachalam, one of the researchers who conducted 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 with which the heuristic methods of the quantum kernel can be rigorously evaluated. Using this problem as an example, they demonstrated the existence of a quantum kernel algorithm that can meaningfully classify a set of points faster than classic algorithms if they are trained with 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 perform all of the algorithm computations except for a certain part. 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 the data and extract characterization features using a technique called quantum kernel estimation (QKE) . ” 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 classic machine learning techniques on this problem is worse than or equal to the random estimate, which is nowhere near 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.”
Previous studies have presented several new quantum algorithms that could solve classification problems faster than traditional machine learning techniques. However, most of these algorithms required strong input assumptions to produce promising results, or the researchers were unable to rigorously demonstrate their advantage over classic 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.”
Recent work by this research team confirms that quantum kernel methods could help to complete classification tasks faster and more efficiently. In their future studies, Arunachalam and his colleagues plan to explore the potential of using these algorithms to solve classification problems in the real world. “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 for more quantum accelerations with quantum kernel methods for others (hopefully)practically relevant problems. We practically think our result is interesting because it gives us a direction to look for more learning problems that can benefit from kernel methods. In our future work we will hope to understand how generalizable the structure of our classification problem is and whether there are more accelerations that can be achieved with similar structures.”
