Quantum Machine Learning techniques have become quite popular in recent years among many computer scientists and physicists investigating their potential.
Machine learning algorithms have achieved promising results in several tasks, including classification. In recent years, many scientists specializing in quantum algorithms have been exploring using quantum methods to solve these tasks faster than ML methods. However, the question of quantum computer’s ability to employ kernel methods to provide a provable advantage over classic ML algorithms remains unanswered.
A recent study at IBM Quantum reveals that the quantum kernel methods could provide a robust quantum acceleration over traditional kernel methods.
During their research, the team built a classification problem that could rigorously evaluate heuristic quantum kernel methods. This experiment helped them demonstrate 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.
According to the researchers, a quantum computer is used in their quantum kernel technique to conduct all of the algorithm’s computations except one. The quantum kernel approach translates a set of classical data points (such as bit strings created by a classical computer) into higher-dimensional spaces. This helps quantum computers to discover patterns in data and extract define features using a process known as quantum kernel estimation (QKE).
They used the discrete logarithm problem to separate quantum and conventional kernels utilizing this technique. This explains how the famous Shor’s algorithm can solve the problem in polynomial time on a quantum computer, yet every classical approach is thought to take superpolynomial time.
The team is the first to create a classification problem based on the discrete logarithm problem’s hardness assumption. Surprisingly, they discovered that all classical machine learning algorithms perform worse or equivalent to random guessing on this problem.
They also created a kernel function to map these traditional data points onto a complicated high-dimensional feature space. This shows that QKE can handle this classification task in polynomial time with very high precision. With this, they also demonstrate that this quantum speedup exists even when there is finite sampling noise during measurements, which is a critical concern for near-term and even fault-tolerant quantum computers.
Several previous studies have proposed new quantum algorithms for solving classification tasks quicker than regular ML techniques. However, to generate promising results, most of these algorithms required strong input assumptions, or many times the researchers were unable to demonstrate their superiority to traditional ML techniques objectively.
In their study, the IBM team started with classical data points and produced a classical solution for the classification problem using a quantum computer in the middle. Therefore, the newly proposed 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).
The team hopes that their study will allow scientists to understand the quantum kernels better. They plan to explore the potential of using these algorithms to tackle real-world classification problems in the coming future. Furthermore, they aim to focus on generalizing the structure of their classification problem to obtain further plausible speedups.
Paper: https://www.nature.com/articles/s41567-021-01287-z
Source: https://phys.org/news/2021-08-quantum-machine-classification-task.html
Tanushree Shenwai is a consulting intern at MarktechPost. She is currently pursuing her B.Tech from the Indian Institute of Technology(IIT), Bhubaneswar. She is a Data Science enthusiast and has a keen interest in the scope of application of artificial intelligence in various fields. She is passionate about exploring the new advancements in technologies and their real-life application.
