# On the expressivity of embedding quantum kernels

arXiv: https://arxiv.org/abs/2309.14419 · HTML: https://mlsanity.com/paper/2309.14419/

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 59 references that are in the map.
- First posted on arXiv 25 Sep 2023.

## Builds on (most cited first, 20 of 20)

- [Variational Quantum Algorithms](https://mlsanity.com/paper/2012.09265/) (2020)
- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [Barren plateaus in quantum neural network training landscapes](https://mlsanity.com/paper/1803.11173/) (2018)
- [Power of data in quantum machine learning](https://mlsanity.com/paper/2011.01938/) (2020)
- [The effect of data encoding on the expressive power of variational quantum machine learning models](https://mlsanity.com/paper/2008.08605/) (2020)
- [Parameterized quantum circuits as machine learning models](https://mlsanity.com/paper/1906.07682/) (2019)
- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [Supervised quantum machine learning models are kernel methods](https://mlsanity.com/paper/2101.11020/) (2021)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Quantum machine learning beyond kernel methods](https://mlsanity.com/paper/2110.13162/) (2021)
- [The Inductive Bias of Quantum Kernels](https://mlsanity.com/paper/2106.03747/) (2021)
- [Provably efficient machine learning for quantum many-body problems](https://mlsanity.com/paper/2106.12627/) (2021)
- [Encoding-dependent generalization bounds for parametrized quantum circuits](https://mlsanity.com/paper/2106.03880/) (2021)
- [Training Quantum Embedding Kernels on Near-Term Quantum Computers](https://mlsanity.com/paper/2105.02276/) (2021)
- [On the Quantum versus Classical Learnability of Discrete Distributions](https://mlsanity.com/paper/2007.14451/) (2020)
- [Classical surrogates for quantum learning models](https://mlsanity.com/paper/2206.11740/) (2022)
- [Automatic design of quantum feature maps](https://mlsanity.com/paper/2105.12626/) (2021)
- [Structural risk minimization for quantum linear classifiers](https://mlsanity.com/paper/2105.05566/) (2021)
- [Potential and limitations of random Fourier features for dequantizing quantum machine learning](https://mlsanity.com/paper/2309.11647/) (2023)
- [Learning with Optimized Random Features: Exponential Speedup by Quantum Machine Learning without Sparsity and Low-Rank Assumptions](https://mlsanity.com/paper/2004.10756/) (2020)

## Built on by (most cited first, 17 of 17)

- [On the relation between trainability and dequantization of variational quantum learning models](https://mlsanity.com/paper/2406.07072/) (2024)
- [A Unified Framework for Trace-induced Quantum Kernels](https://mlsanity.com/paper/2311.13552/) (2023)
- [A Primer on Quantum Machine Learning](https://mlsanity.com/paper/2511.15969/) (2025)
- [Benchmarking quantum machine learning kernel training for classification tasks](https://mlsanity.com/paper/2408.10274/) (2024)
- [Reinforcement learning-based architecture search for quantum machine learning](https://mlsanity.com/paper/2406.02717/) (2024)
- [Double descent in quantum kernel methods](https://mlsanity.com/paper/2501.10077/) (2025)
- [Quantum Supervised Learning](https://mlsanity.com/paper/2407.17161/) (2024)
- [Concept learning of parameterized quantum models from limited measurements](https://mlsanity.com/paper/2408.05116/) (2024)
- [On the similarity of bandwidth-tuned quantum kernels and classical kernels](https://mlsanity.com/paper/2503.05602/) (2025)
- [Benign Overfitting with Quantum Kernels](https://mlsanity.com/paper/2503.17020/) (2025)
- [Quantum enhanced stratification of Breast Cancer: exploring quantum expressivity for real omics data](https://mlsanity.com/paper/2409.14089/) (2024)
- [Quantum Deep Sets and Sequences](https://mlsanity.com/paper/2504.02241/) (2025)
- [Quantum Fourier Transform Based Kernel for Solar Irrandiance Forecasting](https://mlsanity.com/paper/2511.17698/) (2025)
- [Optimal algorithmic complexity of inference in quantum kernel methods](https://mlsanity.com/paper/2604.15214/) (2026)
- [Connecting phases of matter to the flatness of the loss landscape in analog variational quantum algorithms](https://mlsanity.com/paper/2506.13865/) (2025)
- [Distributed Quantum Gaussian Processes for Multi-Agent Systems](https://mlsanity.com/paper/2602.15006/) (2026)
- [Statevector-to-Hardware Reconstruction of a Four-Qubit ZZ Quantum Kernel: A Single-Backend Case Study of Three Execution Jobs](https://mlsanity.com/paper/2607.20377/) (2026)

## Abstract (arXiv)

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.