  To witness quantum advantages in practical settings, substantial efforts are
required not only at the hardware level but also on theoretical research to
reduce the computational cost of a given protocol. Quantum computation has the
potential to significantly enhance existing classical machine learning methods,
and several quantum algorithms for binary classification based on the kernel
method have been proposed. These algorithms rely on estimating an expectation
value, which in turn requires an expensive quantum data encoding procedure to
be repeated many times. In this work, we calculate explicitly the number of
repetition necessary for acquiring a fixed success probability and show that
the Hadamard-test and the swap-test circuits achieve the optimal variance in
terms of the quantum circuit parameters. The variance, and hence the number of
repetition, can be further reduced only via optimization over data-related
parameters. We also show that the kernel-based binary classification can be
performed with a single-qubit measurement regardless of the number and the
dimension of the data. Finally, we show that for a number of relevant noise
models the classification can be performed reliably without quantum error
correction. Our findings are useful for designing quantum classification
experiments under limited resources, which is the common challenge in the noisy
intermediate-scale quantum era.
