Reliable quantum kernel classification using fewer circuit evaluations

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. A kernel evaluation up to a precision of $\epsilon$ can be shown to require $N= \Omega(1/\epsilon^{2})$ quantum measurements. The argument can be extended to all pairs of entries in a dataset of size $m$ and it can be shown that $N=\Omega(m^{2}/\epsilon^{2})$ are required per kernel evaluation, where the precision $\epsilon$ is now stated in terms of operator distance. We emphasize that for classification tasks, the aim is {\em reliable} classification and {\em not precise} kernel evaluation, and demonstrate that the former is exponentially more resource efficient requiring $N = \Omega\left(\log(m)/\gamma^{2}\right)$ quantum measurements per kernel entry. Here $\gamma$ is the margin of classification for an ideal quantum kernel classifier and plays a role analogous to the precision $\epsilon$ but is {\em not vanishingly small}. The accuracy of classification is itself a random variable for finite $N$. We therefore introduce a suitable performance metric that characterizes the robustness or reliability of classification over a dataset, and 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 techniques of robust optimization, we then show that the number of quantum measurements can be significantly reduced by a robust formulation of the original support vector machine. We consider the SWAP test and the GATES test quantum circuits for kernel evaluations, and show that the SWAP test is always less reliable than the GATES test for any $N$. Our strategy is applicable to uncertainty in quantum kernels arising from {\em any} source of noise.