  Kernel methods in Quantum Machine Learning (QML) have recently gained
significant attention as a potential candidate for achieving a quantum
advantage in data analysis. Among other attractive properties, when training a
kernel-based model one is guaranteed to find the optimal model's parameters due
to the convexity of the training landscape. However, this is based on the
assumption that the quantum kernel can be efficiently obtained from quantum
hardware. In this work we study the performance of quantum kernel models from
the perspective of the resources needed to accurately estimate kernel values.
We show that, under certain conditions, values of quantum kernels over
different input data can be exponentially concentrated (in the number of
qubits) towards some fixed value. Thus on training with a polynomial number of
measurements, one ends up with a trivial model where the predictions on unseen
inputs are independent of the input data. We identify four sources that can
lead to concentration including: expressivity of data embedding, global
measurements, entanglement and noise. For each source, an associated
concentration bound of quantum kernels is analytically derived. Lastly, we show
that when dealing with classical data, training a parametrized data embedding
with a kernel alignment method is also susceptible to exponential
concentration. Our results are verified through numerical simulations for
several QML tasks. Altogether, we provide guidelines indicating that certain
features should be avoided to ensure the efficient evaluation of quantum
kernels and so the performance of quantum kernel methods.
