The Inductive Bias of Quantum Kernels

A field of quantum information that has gained a lot of attention recently is Quantum Machine Learning (QML). One of the reasons that QML is considered an exciting direction is that quantum information processing promises scaling advantages over classical methods which means that usual machine learning tasks may enjoy an improved efficiency when they are carried out on a quantum computer. In early works, the primary focus of research in Quantum Machine Learning was on speeding up linear algebra subroutines, although it was later proved that they exhibit an inverse polynomial scaling of the runtime in the error, and practical use-cases are limited because of the large pre-factor overhead of FTQC requirements. An alternative approach could be using a quantum device to define and implement the function class and further optimizing on a classical computer. This can be achieved by employing Quantum Neural Networks (QNNs) or parameterized quantum circuits, however the optimization of QNNs is challenging because of the non-convex nature of the optimization landscape, and because of gradient based optimization inefficiencies known as Barren Plateaus. An approach related to the QNN that allows for convex optimization is known as a quantum kernel, which uses a predefined way of encoding the data in the quantum system and defines a quantum kernel as the inner product of two quantum states.

It is generally accepted that any given algorithm cannot efficiently solve many different types of problems, even if it can efficiently solve some of them. Likewise, a standard inductive bias in ML will suffer to learn discontinuous functions as it primarily prefers continuous functions. In order for QML models to outperform classical ML models, an inductive bias is required that cannot be encoded (efficiently) with a classical machine.
The authors in this work provide theoretical analysis of the inductive bias of quantum machine learning models based on the spectral properties of quantum kernels along with experimental verification. The objective is to explore quantum advantages to the classical concept of inductive bias. The class of functions which is considered for this work are Reproducing kernel Hilbert Spaces (RKHS) functions, where the kernel is expressed by a quantum computation.
Interestingly, these RKHS are classically tractable in some regimes even for high-dimensional or infinite dimensional cases, which implies that such ability on a quantum device by itself does not guarantee a quantum advantage. Rather, a more strict requirement needs to be formulated.

For kernel methods, the qualitative concept of inductive bias can be formalized by analyzing the spectrum of the kernel and relating it to the target function. The results in this work show that the generalization of quantum kernel methods fails as soon as the data embedding into the quantum Hilbert space becomes expressive. By projecting the quantum kernel, it is possible to construct inductive biases that are hard to create classically; however, the fluctuations of the reduced density matrix around its mean are observed to be exponentially vanishing in the number of qubits. Since the value of the kernel would be determined by measurements, in order to attain exponential accuracy of the kernel function, exponential measurements are needed. Thus, there is the same limitation as with other QNN architectures that as the size of the quantum system (number of qubits) becomes large, the vanishing gradient problem (Barren Plateaus) is introduced again.

In contrast to other methods, the spectral properties of the RKHS determine the feasibility of learning instead of its dimensionality. To enable learning, it is required to consider models with a stronger inductive bias. The results indicate that an exponential advantage can be achieved, in a particular example case shown where one knows that the data comes from a single qubit observable and constrains the RKHS accordingly.
The results suggest that one can only achieve a quantum advantage if the data generating process is known and cannot be encoded easily by classical methods, and the information can be used to bias the quantum model.

This work provides guidance in obtaining quantum advantage on a classical dataset based on a quantum architecture known as a quantum kernel. Unfortunately, for large quantum systems quantum kernels cannot avoid the requirement of exponentially many measurements to evaluate the value of the kernel. Therefore, unless one knows how the data generation occurs, no advantage over classical algorithms can be obtained. Quantum computers with error correction can potentially assist in defining kernels with a strong bias that do not require exponentially many measurements. However, even for fully coherent quantum computers, it is still considered a challenge is to efficiently encode a strong inductive bias about a classical dataset. It is speculated that the efficiency of quantum kernels can be improved when working with quantum data instead of classical data. However, regardless of the nature of the data, it is still unclear whether utilizing QNN architectures can improve supervised learning on classical datasets.