# In Search of Quantum Advantage: Estimating the Number of Shots in Quantum Kernel Methods

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 56 references that are in the map.
- First posted on arXiv 22 Jul 2024.

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

- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [Power of data in quantum machine learning](https://mlsanity.com/paper/2011.01938/) (2020)
- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [Connecting ansatz expressibility to gradient magnitudes and barren plateaus](https://mlsanity.com/paper/2101.02138/) (2021)
- [Exponential concentration in quantum kernel methods](https://mlsanity.com/paper/2208.11060/) (2022)
- [Does provable absence of barren plateaus imply classical simulability?](https://mlsanity.com/paper/2312.09121/) (2023)
- [Training Quantum Embedding Kernels on Near-Term Quantum Computers](https://mlsanity.com/paper/2105.02276/) (2021)
- [A Framework for Demonstrating Practical Quantum Advantage: Racing Quantum against Classical Generative Models](https://mlsanity.com/paper/2303.15626/) (2023)
- [Mixed Quantum-Classical Method For Fraud Detection with Quantum Feature Selection](https://mlsanity.com/paper/2208.07963/) (2022)
- [Detecting Clouds in Multispectral Satellite Images Using Quantum-Kernel Support Vector Machines](https://mlsanity.com/paper/2302.08270/) (2023)
- [Numerical evidence against advantage with quantum fidelity kernels on classical data](https://mlsanity.com/paper/2211.16551/) (2022)
- [Assessing requirements to scale to practical quantum advantage](https://mlsanity.com/paper/2211.07629/) (2022)

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

- [Benchmarking quantum machine learning kernel training for classification tasks](https://mlsanity.com/paper/2408.10274/) (2024)
- [AQKA: Active Quantum Kernel Acquisition Under a Shot Budget](https://mlsanity.com/paper/2605.14672/) (2026)
- [QuXAI: Explainers for Hybrid Quantum Machine Learning Models](https://mlsanity.com/paper/2505.10167/) (2025)
- [Adaptive Measurement Allocation for Learning Kernelized SVMs Under Noisy Observations](https://mlsanity.com/paper/2605.22275/) (2026)
- [A Versatile Variational Quantum Kernel Framework for Non-Trivial Classification](https://mlsanity.com/paper/2511.10831/) (2025)
- [Maritime object classification with SAR imagery using quantum kernel methods](https://mlsanity.com/paper/2512.11367/) (2025)

## Abstract (arXiv)

Quantum Machine Learning (QML) has gathered significant attention through approaches like Quantum Kernel Machines. While these methods hold considerable promise, their quantum nature presents inherent challenges. One major challenge is the limited resolution of estimated kernel values caused by the finite number of circuit runs performed on a quantum device. In this study, we propose a comprehensive system of rules and heuristics for estimating the required number of circuit runs in quantum kernel methods. We introduce two critical effects that necessitate an increased measurement precision through additional circuit runs: the spread effect and the concentration effect. The effects are analyzed in the context of fidelity and projected quantum kernels. To address these phenomena, we develop an approach for estimating desired precision of kernel values, which, in turn, is translated into the number of circuit runs. Our methodology is validated through extensive numerical simulations, focusing on the problem of exponential value concentration. We stress that quantum kernel methods should not only be considered from the machine learning performance perspective, but also from the context of the resource consumption. The results provide insights into the possible benefits of quantum kernel methods, offering a guidance for their application in quantum machine learning tasks.