  Quantum kernel methods are a candidate for quantum speed-ups in supervised
machine learning. The number of quantum measurements N required for a
reasonable kernel estimate is a critical resource, both from complexity
considerations and because of the constraints of near-term quantum hardware. We
emphasize that for classification tasks, the aim is reliable classification and
not precise kernel evaluation, and demonstrate that the former is far more
resource efficient. Furthermore, it is shown that the accuracy of
classification is not a suitable performance metric in the presence of noise
and we motivate a new metric that characterizes the reliability of
classification. We then obtain a bound for N which ensures, with high
probability, that classification errors over a dataset are bounded by the
margin errors of an idealized quantum kernel classifier. Using chance
constraint programming and the subgaussian bounds of quantum kernel
distributions, we derive several Shot-frugal and Robust (ShofaR) programs
starting from the primal formulation of the Support Vector Machine. This
significantly reduces the number of quantum measurements needed and is robust
to noise by construction. Our strategy is applicable to uncertainty in quantum
kernels arising from any source of unbiased noise.
