The Inductive Bias of Quantum Kernels

Abstract

It has been hypothesized that quantum computers may lend themselves well to applications in machine learning. In the present work, we analyze function classes defined via quantum kernels. Quantum computers offer the possibility to efficiently compute inner products of exponentially large density operators that are classically hard to compute. However, having an exponentially large feature space renders the problem of generalization hard. Furthermore, being able to evaluate inner products in high dimensional spaces efficiently by itself does not guarantee a quantum advantage, as already classically tractable kernels can correspond to high- or infinite-dimensional reproducing kernel Hilbert spaces (RKHS). We analyze the spectral properties of quantum kernels and find that we can expect an advantage if their RKHS is low dimensional and contains functions that are hard to compute classically. If the target function is known to lie in this class, this implies a quantum advantage, as the quantum computer can encode this inductive bias, whereas there is no classically efficient way to constrain the function class in the same way. However, we show that finding suitable quantum kernels is not easy because the kernel evaluation might require exponentially many measurements. In conclusion, our message is a somewhat sobering one: we conjecture that quantum machine learning models can offer speed-ups only if we manage to encode knowledge about the problem at hand into quantum circuits, while encoding the same bias into a classical model would be hard. These situations may plausibly occur when learning on data generated by a quantum process, however, they appear to be harder to come by for classical datasets.

arXiv commentAccepted version. 9 pages main paper. Total 25 pages

References in corpus (21)

• Scikit-learn: Machine Learning in Python
• A variational eigenvalue solver on a quantum processor
• Quantum algorithm for solving linear systems of equations
• Barren plateaus in quantum neural network training landscapes
• Quantum support vector machine for big data classification
• A Quantum Approximate Optimization Algorithm
• Quantum machine learning in feature Hilbert spaces
• Quantum Circuit Learning
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Evaluating analytic gradients on quantum hardware
• Quantum Computational Supremacy
• The effect of data encoding on the expressive power of variational quantum machine learning models
• Quantum algorithms for supervised and unsupervised machine learning
• Quantum Data Fitting
• Algorithms for Learning Kernels Based on Centered Alignment
• Information-theoretic bounds on quantum advantage in machine learning
• PennyLane: Automatic differentiation of hybrid quantum-classical computations
• Quantum gradient descent for linear systems and least squares
• Training Quantum Embedding Kernels on Near-Term Quantum Computers
• Towards understanding the power of quantum kernels in the NISQ era
• Statistical Limits of Supervised Quantum Learning

Cited by in corpus (5)

• Quantum machine learning beyond kernel methods
• Theory of overparametrization in quantum neural networks
• Variational Quantum Anomaly Detection: Unsupervised mapping of phase diagrams on a physical quantum computer
• Entangled Datasets for Quantum Machine Learning
• Playing Atari with Hybrid Quantum-Classical Reinforcement Learning