  A key problem in the field of quantum computing is understanding whether
quantum machine learning (QML) models implemented on noisy intermediate-scale
quantum (NISQ) machines can achieve quantum advantages. Recently, Huang et al.
[arXiv:2011.01938] partially answered this question by the lens of quantum
kernel learning. Namely, they exhibited that quantum kernels can learn specific
datasets with lower generalization error over the optimal classical kernel
methods. However, most of their results are established on the ideal setting
and ignore the caveats of near-term quantum machines. To this end, a crucial
open question is: does the power of quantum kernels still hold under the NISQ
setting? In this study, we fill this knowledge gap by exploiting the power of
quantum kernels when the quantum system noise and sample error are considered.
Concretely, we first prove that the advantage of quantum kernels is vanished
for large size of datasets, few number of measurements, and large system noise.
With the aim of preserving the superiority of quantum kernels in the NISQ era,
we further devise an effective method via indefinite kernel learning. Numerical
simulations accord with our theoretical results. Our work provides theoretical
guidance of exploring advanced quantum kernels to attain quantum advantages on
NISQ devices.
