# Optimal algorithmic complexity of inference in quantum kernel methods

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 46 references that are in the map.
- First posted on arXiv 16 Apr 2026.

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

- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [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)
- [Exponential concentration in quantum kernel methods](https://mlsanity.com/paper/2208.11060/) (2022)
- [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)
- [Understanding quantum machine learning also requires rethinking generalization](https://mlsanity.com/paper/2306.13461/) (2023)
- [Classical surrogates for quantum learning models](https://mlsanity.com/paper/2206.11740/) (2022)
- [Towards provably efficient quantum algorithms for large-scale machine-learning models](https://mlsanity.com/paper/2303.03428/) (2023)
- [Quantum machine learning of large datasets using randomized measurements](https://mlsanity.com/paper/2108.01039/) (2021)
- [On the relation between trainability and dequantization of variational quantum learning models](https://mlsanity.com/paper/2406.07072/) (2024)
- [The complexity of quantum support vector machines](https://mlsanity.com/paper/2203.00031/) (2022)
- [Potential and limitations of random Fourier features for dequantizing quantum machine learning](https://mlsanity.com/paper/2309.11647/) (2023)
- [On the expressivity of embedding quantum kernels](https://mlsanity.com/paper/2309.14419/) (2023)
- [Exponential quantum advantage in processing massive classical data](https://mlsanity.com/paper/2604.07639/) (2026)
- [Towards efficient quantum algorithms for diffusion probabilistic models](https://mlsanity.com/paper/2502.14252/) (2025)
- [Quantum computing and artificial intelligence: status and perspectives](https://mlsanity.com/paper/2505.23860/) (2025)
- [Amplitude amplification and estimation require inverses](https://mlsanity.com/paper/2507.23787/) (2025)
- [Conjugate queries can help](https://mlsanity.com/paper/2510.07622/) (2025)
- [Non-variational supervised quantum kernel methods: a review](https://mlsanity.com/paper/2604.07896/) (2026)

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

- [Adaptive Measurement Allocation for Learning Kernelized SVMs Under Noisy Observations](https://mlsanity.com/paper/2605.22275/) (2026)

## Abstract (arXiv)

Quantum kernel methods are among the leading candidates for achieving quantum advantage in supervised learning. A key bottleneck is the cost of inference: evaluating a trained model on new data requires estimating a weighted sum sumi=1N αi k(x,xi) of N kernel values to additive precision varepsilon, where α is the vector of trained coefficients. The standard approach estimates each term independently via sampling, yielding a query complexity of O(NlVertαrVert22/varepsilon2). In this work, we identify two independent axes for improvement: (1) How individual kernel values are estimated (sampling versus quantum amplitude estimation), and (2) how the sum is approximated (term-by-term versus via a single observable), and systematically analyze all combinations thereof. The query-optimal combination, encoding the full inference sum as the expectation value of a single observable and applying quantum amplitude estimation, achieves a query complexity of O(lVertαrVert1/varepsilon), removing the dependence on N from the query count and yielding a quadratic improvement in both lVertαrVert1 and varepsilon. We prove a matching lower bound of Omega(lVertαrVert1/varepsilon), establishing query-optimality of our approach up to logarithmic factors. Beyond query complexity, we also analyze how these improvements translate into gate costs and show that the query-optimal strategy is not always optimal in practice from the perspective of gate complexity. Our results provide both a query-optimal algorithm and a practically optimal choice of strategy depending on hardware capabilities, along with a complete landscape of intermediate methods to guide practitioners. All algorithms require only amplitude estimation as a subroutine and are thus natural candidates for early-fault-tolerant implementations.