  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.
