On the expressivity of embedding quantum kernels

Abstract

One of the most natural connections between quantum and classical machine learning has been established in the context of kernel methods. Kernel methods rely on kernels, which are inner products of feature vectors living in large feature spaces. Quantum kernels are typically evaluated by explicitly constructing quantum feature states and then taking their inner product, here called embedding quantum kernels. Since classical kernels are usually evaluated without using the feature vectors explicitly, we wonder how expressive embedding quantum kernels are. In this work, we raise the fundamental question: can all quantum kernels be expressed as the inner product of quantum feature states? Our first result is positive: Invoking computational universality, we find that for any kernel function there always exists a corresponding quantum feature map and an embedding quantum kernel. The more operational reading of the question is concerned with efficient constructions, however. In a second part, we formalize the question of universality of efficient embedding quantum kernels. For shift-invariant kernels, we use the technique of random Fourier features to show that they are universal within the broad class of all kernels which allow a variant of efficient Fourier sampling. We then extend this result to a new class of so-called composition kernels, which we show also contains projected quantum kernels introduced in recent works. After proving the universality of embedding quantum kernels for both shift-invariant and composition kernels, we identify the directions towards new, more exotic, and unexplored quantum kernel families, for which it still remains open whether they correspond to efficient embedding quantum kernels.

arXiv comment17+12 pages, 4 figures

References in corpus (31)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Variational Quantum Algorithms
• Supervised learning with quantum enhanced feature spaces
• Machine learning and the physical sciences
• Barren plateaus in quantum neural network training landscapes
• Quantum support vector machine for big data classification
• Noisy intermediate-scale quantum (NISQ) algorithms
• Quantum machine learning in feature Hilbert spaces
• Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations
• Strong quantum computational advantage using a superconducting quantum processor
• Parameterized quantum circuits as machine learning models
• Quantum algorithms: an overview
• The effect of data encoding on the expressive power of variational quantum machine learning models
• Power of data in quantum machine learning
• Data re-uploading for a universal quantum classifier
• A rigorous and robust quantum speed-up in supervised machine learning
• A generative modeling approach for benchmarking and training shallow quantum circuits
• Implementing a distance-based classifier with a quantum interference circuit
• Provably efficient machine learning for quantum many-body problems
• Quantum machine learning beyond kernel methods
• Computational advantage of quantum random sampling
• Training Quantum Embedding Kernels on Near-Term Quantum Computers
• On the Quantum versus Classical Learnability of Discrete Distributions
• Automatic design of quantum feature maps
• Classical surrogates for quantum learning models
• Structural risk minimization for quantum linear classifiers
• Classically Approximating Variational Quantum Machine Learning with Random Fourier Features
• Deterministic and random features for large-scale quantum kernel machine
• Quantum Fisher kernel for mitigating the vanishing similarity issue

Cited by in corpus (10)

• Benchmarking quantum machine learning kernel training for classification tasks
• Neural quantum kernels: training quantum kernels with quantum neural networks
• Quantum Supervised Learning
• On the similarity of bandwidth-tuned quantum kernels and classical kernels
• Quantum enhanced stratification of Breast Cancer: exploring quantum expressivity for real omics data
• On the Differential Topology of Expressivity of Parameterized Quantum Circuits
• Double descent in quantum kernel methods
• New perspectives on quantum kernels through the lens of entangled tensor kernels
• Quantum generative classification with mixed states
• Quantum Deep Sets and Sequences