# Reliable quantum kernel classification using fewer circuit evaluations

Abhay Shastry  Department of Computer Science and Automation, Indian Institute
of Science, Bangalore 560012  Abhijith J  Theoretical Division, Los Alamos
National Lab, New Mexico, US 87545  Apoorva Patel  Center for High Energy
Physics, Indian Institute of Science, Bangalore 560012  Chiranjib
Bhattacharyya  Department of Computer Science and Automation, Indian Institute
of Science, Bangalore 560012

###### Abstract

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. 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 an $m\times m$ kernel matrix constructed using 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 reliable classification and 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 not vanishingly small. The uncertainty in the quantum kernel
arising from finite sampling leads to misclassifications over some kernel
instantiations, i.e., 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 any source of noise.

##  I Introduction

Kernel methods have been used extensively in a variety of machine learning
tasks like classification, regression, and dimensionality reduction [1]. The
core ingredient of such algorithms is the so-called kernel trick, which
implicitly embeds a datapoint into a higher (possibly infinite) dimensional
inner product space, known as the _feature space_. The embedding is implicit
because the vectors in the feature space are never explicitly computed.
Instead, a _kernel function_ is used to map any two input data points to the
inner product between their embeddings in the feature space. The key insight
that allows kernel methods to be used with quantum computers is the
identification of a vector in the feature space with the density matrix of a
many-body quantum system [2, 3].

Quantum computing allows us to efficiently compute the inner products of
exponentially large density matrices without the explicit computation of the
dentity matrices themselves. Naturally, such an extension into the quantum
setting has interested researchers to search for a quantum advantage in kernel
methods [4, 5, 6, 7, 8]. In particular, Ref. [4] analyses the spectral
properties of the reproducing kernel Hilbert space (RKHS) associated with a
quantum density matrix and suggests that a quantum advantage can be expected
if the RKHS is low-dimensional and has functions which are classically hard to
compute. This can still lead to exponentially large number of measurements, if
the task requires exponential precision in evaluating quantum kernels, thereby
making it hard to claim quantum advantage. The number of measurements $N$
needed for a kernel evaluation thus plays a critical role in the analysis of
quantum algorithms for machine learning and has been called the sampling
complexity [5].

In the present article, we look at the problem of quantum kernel
classification with particular emphasis on optimization of $N$. Suppose a
kernel function $K^{*}$, which may be classically hard to compute, has to be
implemented on a quantum machine. How many measurements would be needed to
construct a reliable classifier? Crucially, our goal is not to accurately
evaluate the kernel function itself but to construct a reliable classifier
with it. It is often possible to have a training dataset with few support
vectors $m_{\mathrm{sv}}$ [9], which do not scale with the number of training
data points $m$. Physically, $m_{\mathrm{sv}}\ll m$ is essentially a boundary
(support vectors) vs. bulk (all datapoints) comparison. In a Support Vector
Machine (SVM), the boundary carries the information relevant to the
classifier. Faithful reproduction of the training labels is shown to require
$N=\Omega\left(m_{\mathrm{sv}}\log m\right)$ measurements per kernel entry. In
contrast, bounds for $N$ derived over the error $\epsilon$ (in operator
distance) in the training kernel matrix [5],
$N=\Omega\left(m^{2}/\epsilon^{2}\right)$, scale quadradically with $m$.

We work in the hybrid quantum-classical setup [5, 2, 11], where the
optimization problem is solved on a classical machine and the kernel
evaluations are done on a quantum machine by repeated measurements of a
quantum logic circuit. In setting up the optimization problem, we assume that
we have access to the kernel matrix $\mathbf{K}^{*}$ over the training data.
We refer to quantum classifiers which use $N$ measurements of a quantum
circuit per kernel evaluation as stochastic kernel classifiers (SKC), and the
ideal quantum classifier ($N\to\infty$) as the exact kernel classifier or the
true classifier (EKC). Our aim is to reliably reproduce the output of the
exact kernel classifier using as few measurements as possible. In the results
presented in this article, we test the classifier over the training data
itself. This choice highlights the problem starkly, since it shows that the
stochastic kernel classifiers are incapable of reliably reproducing even the
training labels, when $N$ is not large enough. We show its generalization to
an independent test set in the Supplementary Information (Supp. Info.). Our
main findings are summarized in the next two paragraphs.

In Section V.1, we derive a bound for $N$ (Theorem 32) which ensures (with
high probability) that the classification error of the SKC is smaller than the
margin error of the EKC over any dataset. This constitutes a more useful bound
than the ones derived over the errors in the training kernel matrix [5, 10,
8], since the latter do not have any direct relationship with the performance
of the classifier. The bound is based on the observation that when the effect
of the kernel uncertainty is smaller than the margin of classification, the
classifier results do not change.

In Section V.2, we take a chance constraint approach [12] to handle the
stochastic parts of the SVM objective [13], and develop a convex cone program
which is robust to the sampling noise by construction (Theorem 3). Solving
this robust optimization problem allows us to construct two classifiers,
robust stochastic kernel classifier (RSKC) and robust exact kernel classifier
(REKC). The former employs the stochastic kernel and the latter employs the
true quantum kernel for classification. We show that the sampling noise
affects RSKC to a far lesser degree than the SKC. In particular, our
construction of the robust SVM objective is such that even for single-shot
measurements ($N=1$) RSKC reliably reproduces REKC, although there is a
corresponding trade-off in the accuracy of REKC for low $N$. Increasing $N$,
we show that RSKC reproduces the true quantum classifier EKC with
significantly less measurements per kernel entry compared to SKC. This result
is especially relevant for the current noisy intermediate-scale quantum (NISQ)
era [14] quantum devices, where the number of measurement shots are a resource
to be used frugally [15, 16, 17].

##  II Preliminaries

In this Section we introduce the relevant notation and discuss necessary
preliminaries.

Notation The set of natural numbers is denoted by $\mathbb{N}$. For any
$m\in\mathbb{N}$, $[m]$ denotes the set $\\{1,\ldots,m\\}$. ${\mathbb{R}}^{d}$
denotes a $d$ dimensional real vector space. For any
${\mathbf{v}}\in{\mathbb{R}}^{d}$, the euclidean norm is
$\|{\mathbf{v}}\|=\sqrt{{\mathbf{v}}^{\top}{\mathbf{v}}}$. A random variable
$X\in{\mathbb{R}}^{d}$ distributed according to probability distribution
${\mathcal{P}}$ is denoted as $X\sim{\mathcal{P}}$, and its expectation value
denoted as $\mathbb{E}(X)$. The binomial random variable is denoted by
$\textrm{Bin}(N,p)$, where $N\in\mathbb{N}$ is the number of independent
Bernoulli trials each with success probability $0\leq p\leq 1$. The number of
quantum measurements or circuit evaluations (per kernel estimation) is denoted
by $N$. The size of the training set is denoted by $m$. ${\mathbb{S}^{m}_{+}}$
denotes the space of $m\times m$ positive semidefinite and symmetric matrices.

######  Definition 1 (Subgaussian random variable).

A random variable $X\in{\mathbb{R}}$ is $X\sim\mathbf{\tt SubG}(\sigma^{2})$,
if $\mathbb{E}(X)=0$ and

$\mathbb{E}(e^{sX})\leq e^{\frac{1}{2}s^{2}\sigma^{2}}\quad\forall
s\in{\mathbb{R}}$ (1)

The smallest such $\sigma$ is called the subgaussian norm of $X$.

The following facts about subgaussian random variables will be used
subsequently.

######  Fact 1.

Define $Z=\frac{1}{N}X-p$, where $X\sim\textrm{Bin}(N,p)$. Then
$Z\sim\mathbf{\tt SubG}(\sigma^{2})$ for any $\sigma^{2}\geq\texttt{Var}(Z)$.

######  Fact 2.

Subgaussian random variables obey the following tail bounds [18]:

  1. 1.

If $X\sim\mathbf{\tt SubG}(\sigma^{2})$ then for every $t>0$,

$\mathrm{Prob}(X\geq
t)\leq\mbox{exp}\bigg{(}-\frac{t^{2}}{2\sigma^{2}}\bigg{)}.$

  2. 2.

Let $X_{i}\sim\mathbf{\tt SubG}(\sigma^{2}),\ i\in[n]$ be independent random
variables. Then for any $a\in{\mathbb{R}}^{d}$ the random variable
$Y=\sum_{i=1}^{n}a_{i}X_{i}$ satisfies

$\mathrm{Prob}\big{(}Y\geq t\big{)}\leq
exp\bigg{(}-\frac{t^{2}}{2\sigma^{2}\|a\|^{2}}\bigg{)}.$ (2)

This immediately leads to the following assertion.

######  Lemma 1.

Let $Y$ be defined as in Fact 2. For any $0<\delta\leq 1$,

$\mathrm{Prob}(Y\geq t)\leq\delta$ (3)

holds whenever

$t\geq\sigma\left\lVert a\right\rVert\kappa(\delta),$ (4)

where

$\kappa(\delta)=\sqrt{2\log\bigg{(}\frac{1}{\delta}\bigg{)}}.$ (5)

###  II.1 Support Vector Machines for Classification

A function $f:{\mathcal{X}}\subset{\mathbb{R}}^{d}\to\\{-1,1\\}$ is called a
binary classifier, which takes an _observation_ ${\mathbf{x}}$ and outputs a
label $y$. The problem of estimating $f$ from a training dataset

$\mathcal{D}_{\mathrm{train}}=\left\\{\left({\mathbf{x}}_{i},y_{i}\right)\left|{\mathbf{x}}_{i}\in{\mathcal{X}}\subset{\mathbb{R}}^{d},~{}y_{i}\in\\{-1,1\\},~{}i\in[m]\right.\right\\}$
(6)

consisting of $m$ i.i.d. (_observation_ ,  _label_) pairs drawn from a
distribution ${\mathcal{P}}$ is of great interest in machine learning. The aim
is to obtain an $f$ such that the generalization error,
$\mathrm{Prob}\left(f({\mathbf{x}})\neq y\right)$, is small for
$({\mathbf{x}},y)\sim{\mathcal{P}}$.

Support Vector Machines (SVM) are widely used classifiers [19], which have
been extremely successful in practical applications. For a dataset
$\mathcal{D}_{\mathrm{train}}$, a SVM kernel classifer is

$f({\mathbf{x}}|\alpha,b;K)=\mathrm{sgn}\bigg{(}\sum_{i=1}^{m}\alpha_{i}y_{i}K({\mathbf{x}}_{i},{\mathbf{x}})+b\bigg{)},$

where the $\alpha=[\alpha_{1},\ldots,\alpha_{m}]^{\top}$ is obtained by
solving the problem

$\displaystyle\max_{\alpha}$
$\displaystyle\left(\sum_{i=1}^{m}\alpha_{i}-\frac{1}{2}\sum_{i,j}\alpha_{i}\alpha_{j}y_{i}y_{j}K({\mathbf{x}}_{i},{\mathbf{x}}_{j})\right),$
(DUAL) s.t. $\displaystyle\sum_{i=1}^{m}\alpha_{i}y_{i}=0\ \textrm{and}\ \
0\leq\alpha_{i}\leq C,$

for some $C\geq 0$.

This optimization problem can be solved efficiently using convex quadratic
programming [1]. The kernel function
$K:{\mathcal{X}}\times{\mathcal{X}}\to{\mathbb{R}}$ is _positive semidefinite_
, and plays the role of a dot product in a suitably defined Reproducing Kernel
Hilbert Space (RKHS). One of the most interesting properties of the kernel
function is it implicitly defines an embedding of the observation that does
not need to be explicitly computed. For a comprehensive exposition, see Ref.
[20]. For brevity we introduce the kernel matrix
${\mathbf{K}}\in{\mathbb{R}}^{m\times m}$, whose entries are
$\mathbf{K}_{ij}=K({\mathbf{x}}_{i},{\mathbf{x}}_{j})$ for any $i,j\in[m]$.
Since the kernel function is positive semidefinite, the kernel matrix is also
positive semidefinite.

To help develop our ideas, we work with an equivalent setup. We consider
classifiers of the form

$f({\mathbf{x}}|\beta,b;K)=\mathrm{sgn}\bigg{(}\sum_{i=1}^{m}\beta_{i}K({\mathbf{x}}_{i},{\mathbf{x}})+b\bigg{)},$
(7)

where
$\beta=[\beta_{1},\ldots,\beta_{m}]^{\top}\in{\mathbb{R}}^{m},b\in{\mathbb{R}}$.
The parameters $\beta,b$ of the classifier are obtained by minimizing

$\displaystyle\begin{split}J(\beta,b;{\mathbf{K}})=C\sum_{i=1}^{m}\max\left(1-y_{i}(\sum_{j=1}^{m}\beta_{j}{\mathbf{K}}_{ij}+b),0\right)\\\
+\frac{1}{2}\sum_{ij}\beta_{i}\beta_{j}{\mathbf{K}}_{ij},\end{split}$ (8)

for some $C\geq 0$ (same as in DUAL) that sets the relative weights of the two
terms. The first term is known as the hinge loss, and the second term is
called the regularization term. Since the kernel function is positive
semidefinite, this is a convex quadratic function. The resulting problem,

$\min_{\beta\in{\mathbb{R}}^{m},b\in{\mathbb{R}}}J(\beta,b;{\mathbf{K}}),$ (9)

is thus again a convex optimization problem, and is dual to the standard SVM
formulation.

###  II.2 Quantum Embedding Kernels

Kernel methods have a natural extension into the quantum setting. A quantum
computer can be used to embed the data into a high dimensional Hilbert space
and the kernel function can be computed by estimating the state overlaps. This
also offers a path to obtain quantum advantage in machine learning, since
certain type of kernel functions are (conjectured to be) hard to evaluate
classically but easy to do so quantum mechanically [5, 6, 4]. A quantum
embedding circuit takes the classical input datapoint
${\mathbf{x}}\in\mathcal{X}\subset\mathbb{R}^{d}$, and maps it to a quantum
state $\ket{\phi({\mathbf{x}})}\in\mathcal{H}$, the computational Hilbert
space. A valid kernel function $K:\mathcal{X}\times\mathcal{X}\to\mathbb{R}$
can be chosen as

$K({\mathbf{x}},{\mathbf{x}}^{\prime})\equiv\operatorname{Tr}\left\\{\rho({\mathbf{x}})\rho({\mathbf{x}}^{\prime})\right\\}=|\braket{\phi({\mathbf{x}})}{\phi({\mathbf{x}}^{\prime})}|^{2},$
(10)

where
$\rho({\mathbf{x}})\equiv\ket{\phi({\mathbf{x}})}\bra{\phi({\mathbf{x}})}$ is
the density matrix that plays the role of a vector in the feature Hilbert
space $\mathcal{H}\otimes\mathcal{H}^{*}$. Such kernels are known as _quantum
embedding kernels_ (QEK) [2, 3].

The mapping into the computational Hilbert space
$\ket{\phi({\mathbf{x}})}=U({\mathbf{x}})\ket{0}^{n}$ is achieved by a unitary
operator $U({\mathbf{x}})$ using a quantum circuit dependent on
${\mathbf{x}}$. For example, we may use the elements of ${\mathbf{x}}$ as the
angles of rotation in the various $1$\- and $2$-qubit gates used to construct
the quantum circuit. Such an angle embedding circuit is shown in Supp. Info.,
and is one of the simplest ways to encode the input data ${\mathbf{x}}$ into a
quantum state $\ket{\phi({\mathbf{x}})}$. Given such a circuit, we can map
each datapoint to a quantum density matrix,
$\rho({\mathbf{x}})=U({\mathbf{x}})\ket{0\ldots 0}\bra{0\ldots
0}U^{\dagger}({\mathbf{x}})$. The kernel can then be expressed as the Hilbert-
Schmidt inner product
$K({\mathbf{x}},{\mathbf{x}}^{\prime})=\operatorname{Tr}\left\\{\rho{({\mathbf{x}})}\rho{({\mathbf{x}}^{\prime})}\right\\}$,
which can be evaluated using either the SWAP test or the GATES circuit that we
describe in the next Section.

##  III The quantum sampling noise in kernel evaluations

Let $K^{*}$ denote the true quantum kernel function and $K^{(N)}$ be the
stochastic kernel function estimated from $N$ quantum measurements for any
pair of inputs ${\mathbf{x}}_{i},{\mathbf{x}}_{j}\in{\mathcal{X}}$. We shall
use the shorthand notation
$K^{*}_{ij}=K^{*}({\mathbf{x}}_{i},{\mathbf{x}}_{j})$ and
$K^{(N)}_{ij}=K^{(N)}({\mathbf{x}}_{i},{\mathbf{x}}_{j})$. We denote their
difference at finite sampling as

$\Delta{K}^{(N)}_{ij}=K^{*}_{ij}-K^{(N)}_{ij},\ \textrm{for any}\
{\mathbf{x}}_{i},{\mathbf{x}}_{j}\in{\mathcal{X}}.$ (11)

In what follows, we demonstrate that the sampling noise depends on the quantum
logic circuit used to evaluate the kernel function.

(a)

(b)

Figure 1: (a) GATES circuit measures the probability of obtaining the final
state $\ket{0}^{\otimes n}$. The resulting distribution for
$K({\mathbf{x}},{\mathbf{x}}^{\prime})$ is given by (13). (b) SWAP circuit
measures the probability of obtaining the ancillary qubit (top line) in the
$\ket{0}$ state. The resulting kernel estimate is given by (16).

We consider the two different ways in which the overlaps
$K_{ij}=|\bra{\phi({\mathbf{x}}_{i})}\phi({\mathbf{x}}_{j})\rangle|^{2}$ can
be evaluated [5]. The data ${\mathbf{x}}_{i}\in\mathcal{X}$ is transformed
into a state in the computational Hilbert space $\mathcal{H}$ by starting with
all $n$ qubits in the $\ket{0}$ state and using the unitary operator

$\ket{\phi({\mathbf{x}}_{i})}=U({\mathbf{x}}_{i})\ket{0}^{\otimes n}.$ (12)

The first method is to express the kernel as
$K({\mathbf{x}}_{i},{\mathbf{x}}_{j})=|\bra{0}^{\otimes
n}U^{\dagger}({\mathbf{x}}_{i})U({\mathbf{x}}_{j})\ket{0}^{\otimes n}|^{2}$,
which can be evaluated by applying
$U^{\dagger}({\mathbf{x}}_{i})U({\mathbf{x}}_{j})$ to the initial state
$\ket{0}^{\otimes n}$ and then estimating the probability that the final state
is also $\ket{0}^{\otimes n}$. We refer to this as the GATES test, shown in
fig. 1(a). It has also been called the inversion test [21] and the adjoint
test [10]. The value of the kernel function
$K^{(N)}_{ij}=K^{(N)}({\mathbf{x}}_{i},{\mathbf{x}}_{j})$ is inferred using
$N$ independent Bernoulli trials, each of which gives the final state
$\ket{0}^{\otimes n}$ with probability $p=K^{*}_{ij}$. Hence,

$K^{(N)}_{ij}\sim\frac{1}{N}\ \textrm{Bin}\bigg{(}N,p=K^{*}_{ij}\bigg{)}.$
(13)

An alternate way to measure fidelity or state overlap is the SWAP test [22],
shown in fig. 1(b). In this case, the ancilla bit is read out, and the
probability of obtaining the state $\ket{0}$ can be written in terms of the
state overlap

$\displaystyle\mathrm{Prob}\big{(}\textrm{ancilla}=\ket{0}\big{)}=$
$\displaystyle\frac{1}{2}\big{(}1+|\bra{\phi({\mathbf{x}}_{i})}\phi({\mathbf{x}}_{j})\rangle|^{2}\big{)}$
(14) $\displaystyle=$ $\displaystyle\frac{1}{2}\left(1+K_{ij}^{*}\right).$
(15)

We infer $K_{ij}^{(N)}$ through $N$ independent Bernoulli trials that measure
the state of the ancilla bit, and therefore obtain

$K^{(N)}_{ij}\sim\frac{2}{N}\
\textrm{Bin}\bigg{(}N,p=\frac{1}{2}(1+K^{*}_{ij})\bigg{)}-1.$ (16)

In all the figures, we use the symbol ($\blacktriangleright$) and (✖) to
denote the (13) and (16) tests respectively.

It is obvious that in both (13) and (16) cases $K^{(N)}_{ij}$ is an _unbiased
estimator_ of $K^{*}_{ij}$,

$\mathbb{E}[K^{(N)}_{ij}]=K^{*}_{ij}\ \
\forall{\mathbf{x}}_{i},{\mathbf{x}}_{j}\in{\mathcal{X}}.$ (17)

The variance of the estimator, however, is linked to the specific circuit and
the number of measurements $N$.

######  Lemma 2 (Circuit Factor).

The variance of estimator $K_{ij}^{(N)}$ is upper-bounded by $\sigma_{0}^{2}$,
where

$\sigma_{0}=\frac{{\mathrm{c}}}{2\sqrt{N}},\quad\begin{aligned}
{\mathrm{c}}&=\begin{cases}1&(\textbf{GATES}),\\\
2&(\textbf{SWAP}).\end{cases}\end{aligned}$ (18)

The circuit factor ${\mathrm{c}}$ is a circuit-dependent constant.

For a derivation of the $\sigma_{0}$ value, see Supp. Info. B. For both the
circuits under consideration, $K^{(N)}_{ij}$ is an affine function of a
Binomial random variable. Direct application of Fact 1 then yields

$\Delta K^{(N)}_{ij}\sim\mathbf{\tt SubG}(\sigma_{0}^{2}).$ (19)

We study the problem of kernel based classification under this uncertainty
model, and only consider the fundamental sampling noise. We however note the
following in the presence of other sources of noise, and discuss the
modification to the uncertainty model in Supp. Info.

######  Remark 1.

The uncertainty model 19 subsumes all other sources of noise as well.

###### Proof.

Since all quantum kernel distributions $0\leq
K({\mathbf{x}},{\mathbf{x}}^{\prime})\leq 1$ have finite support, it is
subgaussian due to Hoeffding’s lemma (e.g. see 2.6 in [23]). ∎

We note that the kernel estimate given by (13) has a lower variance compared
to the estimate given by (16). This implies that, purely from the perspective
of sampling noise, the GATES test is preferable for any $N$. The GATES test
requires a circuit whose depth is twice that of the SWAP test, but the SWAP
test requires twice the number of qubits as the GATES test and additional
controlled SWAP operations. The practical choice of the test to use for
estimating QEKs can therefore depend on other factors like the coherence times
and the quality of the gates available. For example, a recent study [24] on
the IBM quantum hardware has shown that SWAP test is a poor choice compared to
the GATES test for estimating QEKs, owing to errors in the controlled SWAP
implementation. However, it appears that the authors have overlooked the
fundamental statistical reason (lemma 2) in their comparison of the GATES and
SWAP tests.

We next highlight the effect of finite $N$ on the SVM classification problem,
and motivate the performance metric of reliability as opposed to average
accuracy.

##  IV Reliability of quantum kernel classifiers

Problem Setup:

  1. 1.

We work in the hybrid quantum-classical setup where the SVM is trained on a
classical machine. It is assumed that we have access to the true training
kernel matrix $\mathbf{K}^{*}\in{\mathbb{S}^{m}_{+}}$. The optimal
coefficients minimizing $J(\beta,b;\mathbf{K}^{*})$ in (9) are denoted by
$\beta^{*},b^{*}$ and are determined on a classical machine.

  2. 2.

The kernel function $K^{(N)}$, used in the classification of an observation
${\mathbf{x}}\in{\mathcal{X}}$ is evaluated using $N$ measurements per kernel
entry $K^{(N)}\left({\mathbf{x}},{\mathbf{x}}_{i}\right)$, $i\in[m]$ on a
quantum machine using one of the circuits in Fig. 1. We assume no other noise
sources apart from the fundamental sampling noise. After the evaluation of the
kernel function, the classification is done on the classical machine by
computing $f\left({\mathbf{x}}|\beta^{*},b^{*};K^{(N)}\right)$ (Eq. 7).

Thus we compare the following two classifiers:

######  Definition 2 (Exact Kernel Classifier).

The exact kernel classifier or the true classifier is

$f^{*}({\mathbf{x}})=f\left({\mathbf{x}}|\beta^{*},b^{*};K^{*}\right),$ (20)

where $\beta^{*},b^{*}$ denote the optimal coefficients minimizing the (9)
objective $J(\beta,b;\mathbf{K}^{*})$.

######  Definition 3 (Stochastic Kernel Classifier).

Let $N$ denote the number of measurements performed to estimate the kernel
function $K({\mathbf{x}},{\mathbf{x}}_{i})$, for each $i\in[m]$. Then

$f^{(N)}({\mathbf{x}})=f\left({\mathbf{x}}|\beta^{*},b^{*};K^{(N)}\right),$
(21)

where, as in (20), $\beta^{*},b^{*}$ denote the optimal coefficients
minimizing the (9) objective $J(\beta,b;\mathbf{K}^{*})$.

Naturally, we would recover the true classifier (20) in the limit of
infinitely many measurements:

$\lim_{N\to\infty}f^{(N)}({\mathbf{x}})=f^{*}({\mathbf{x}}).$ (22)

But the convergence can be slow in practice, and would depend on the dataset
and choice of the kernel function $K^{*}$.

Classifier performance over a dataset is generally quantified by its accuracy.

######  Definition 4 (Accuracy).

The accuracy of a classifier $f({\mathbf{x}})$ over a dataset
$\mathcal{D}=\\{({\mathbf{x}}_{i},y_{i}),\ i\in[M]\\}$,

$\textrm{Acc}\left(f\right)=\frac{1}{M}\sum_{i=1}^{M}\mathbbm{1}_{f({\mathbf{x}}_{i})=y_{i}},$
(23)

is the fraction of datapoints classified correctly.

When $f({\mathbf{x}})=f^{(N)}({\mathbf{x}})$ is a stochastic kernel
classifier, the classification of any datapoint ${\mathbf{x}}\in{\mathcal{X}}$
depends upon the evaluation of kernels
$K^{(N)}({\mathbf{x}},{\mathbf{x}}_{i}),i\in[m]$ which are random variables.
The accuracy (23) is thus also a random variable and is therefore not a
suitable performance metric.

Given some datapoint ${\mathbf{x}}\in{\mathcal{X}}$, we would like the
classifier (21) to return the same label as (20) with high probability.

######  Definition 5 (Reliability of quantum classifier).

Let $f^{(N)}$ denote a stochastic kernel classifier where the quantum kernels
are evaluated with $N$ measurements per entry. We say the reliability of the
stochastic kernel classifier (21) at the datapoint
${\mathbf{x}}\in{\mathcal{X}}$ is at least $1-\delta$, if

${\mathcal{R}}({\mathbf{x}};f^{(N)},f^{*})\equiv\mathrm{Prob}\left(f^{(N)}({\mathbf{x}})=f^{*}({\mathbf{x}})\right)\geq
1-\delta,$ (24)

where $f^{*}({\mathbf{x}})$ denotes the true classifier (20).

When classifying the datapoint ${\mathbf{x}}\in{\mathcal{X}}$ using quantum
kernels, we thus seek $N$ that gives $\delta\ll 1$.

######  Theorem 1.

Let
$g^{*}({\mathbf{x}})=\sum_{j}\beta^{*}_{j}K^{*}({\mathbf{x}},{\mathbf{x}}_{j})+b^{*}$.
The stochastic kernel classifier $f^{(N)}({\mathbf{x}})$ agrees with the exact
kernel classifier
$f^{*}({\mathbf{x}})=\mathrm{sgn}\left({g^{*}({\mathbf{x}})}\right)$ (20),
with probability at least $(1-\delta)$, whenever

$N\geq\frac{1}{2}\left(\frac{{\mathrm{c}}\left\lVert\beta^{*}\right\rVert}{g^{*}({\mathbf{x}})}\right)^{2}\log\left(\frac{1}{\delta}\right),$
(25)

where ${\mathrm{c}}$ is the circuit factor.

###### Proof.

This bound is a direct application of lemma 1, along with the uncertainty
model for quantum kernel classifiers (19). ∎

We provide the following empirical metric to quantify the reliability (24)
over a number of trials. Let
$f^{(N)}{\\{1\\}},f^{(N)}{\\{2\\}},\ldots,f^{(N)}{\\{N_{\mathrm{trials}}\\}}$
denote the specific instantiations of a stochastic classifier (21) over
$N_{\mathrm{trials}}$ different trials.

  1. 1.

For a given input datapoint $({\mathbf{x}},y)$, the stochastic kernel
classifier $f^{(N)}$ has an empirical reliability

$\hat{{\mathcal{R}}}\left({\mathbf{x}};f^{(N)},f^{*}\right)=\frac{1}{N_{\mathrm{trials}}}\sum_{k=1}^{N_{\mathrm{trials}}}\mathbbm{1}_{f^{(N)}{\\{k\\}}({\mathbf{x}})=f^{{}^{*}}({\mathbf{x}})},$
(26)

with respect to that of the true classifier $f^{*}$.

  2. 2.

We extend the notation above and define the empirical reliability over a
dataset $\mathcal{D}$ ($|\mathcal{D}|=M$) as

######  Definition 6 (Empirical Reliability).

$\hat{{\mathcal{R}}}\left(f^{(N)},f^{*}\right)=\frac{1}{M}\sum_{s=1}^{M}\mathbbm{1}_{\hat{{\mathcal{R}}}\left({\mathbf{x}}_{s};f^{(N)},f^{*}\right)=1}.$
(27)

Thus, an observation ${\mathbf{x}}$ is considered to be reliably classified,
if the stochastic kernel classifier assigns it the same label for all
$N_{\mathrm{trials}}$ instantiations. (We find that relaxing this requirement
of the same label for $N_{\mathrm{trials}}$ instantiations to
$N_{\mathrm{trials}}(1-\delta)$ instantiations hardly affects our results.)
Henceforth, Eq. (27) shall simply be referred to as reliability. Over any
dataset, it quantifies the fraction of points which are classified reliably.
In our experiments, we set $N_{\mathrm{trials}}=200$.

Figure 2:  Reliability versus Accuracy. Performance of (21) over the training
dataset $\mathcal{D}_{\mathrm{train}}$ shown as a function of $N$. Both
quantities $\hat{{\mathcal{R}}}\left(f^{(N)},f^{*}\right)$ and
$\textrm{Acc}\left(f^{(N)}\right)$ are calculated over the same
$N_{\mathrm{trials}}=200$ instantiations of the kernel function $K^{(N)}$,
using the (13) circuit and the Circles dataset. Accuracy itself is a random
variable and the shaded area covers the range of observed accuracies of (21).
Notice that even when the average accuracy is high ($>85\%$ at $N=512$), the
reliability can be very low ($0\%$ at $N=512$).

Reliability versus Accuracy:

An illustration of our numerical experiments is shown in Figure 2. We observe
that a large number of measurements are needed for (21) to reliably reproduce
the labels even for the training data. Furthermore,

  1. 1.

The average accuracy is not a good performance metric. A high accuracy on
average carries little information regarding how reliably an observation
${\mathbf{x}}$ is classified by (21). There is a wide range of the obtained
accuracies over different instantiations of (21). For example, the average
accuracy $>85\%$ for $N=512$, but none of the points are classified reliably.

  2. 2.

Requiring high reliability, $\hat{{\mathcal{R}}}(f^{(N)},f^{*})\to 1$, as
opposed to high accuracy on average, requires larger $N$.

In NISQ devices, the effect of noise on the results is extremely important and
has received wide attention [14]. Recent works in quantum algorithms for the
NISQ era place special emphasis on the sampling noise, and treat the number of
measurements $N$ as a resource that should be used minimally [15, 16, 17].

There exists however a large discrepancy in the number of measurements used in
various studies of quantum classifiers [8, 10, 5]. In the freely accessible
IBM quantum processors, the default number of measurements per job is set to
$1024$. While Refs. [8, 10] work close to these restrictions, Ref. [5] works
with a much larger 50,000 measurements per kernel entry. Although the error
mitigation technique used in [5] results in higher requirements for the number
of measurements, 50,000 measurements is too large a number in practice for
those without an exclusive access to a quantum computer. Ref. [10] uses 175
measurements to obtain the training kernel matrix and get good accuracies over
the test set, but fails to mention the number of measurements used during the
classification of a test datapoint. Ref. [8] uses the same number of
measurements for both the training and the testing phases.

Our observations from Figure 2 and the constraints of NISQ devices raise the
following questions:

  1. 1.

The number of measurements $N$ needed to ensure accurate classification is
dependent on the dataset and the choice of the kernel function. Can we derive
a generic bound for $N$ that would reliably reproduce the predictions of an
ideal quantum kernel classifier?

  2. 2.

Can we construct a reliable classifier which uses fewer $N$?

We now answer both these questions in the affirmative.

##  V Results and Discussion

We here derive bounds over the number of measurements $N$ which can ensure a
small classification error, and perform numerical experiments showing the
validity and usefulness of the bounds. Using methods from robust optimization,
we then present a convex SVM program which is robust to the sampling noise by
construction, and show its performance over different datasets.

Datasets. We present our results over three datasets: (1) Circles, (2) Two
Moons, (3) Havlicek [5], generated over two qubits. All the figures in the
main article correspond to the Circles dataset. All other details, e.g. the
choice of quantum kernels and performance over an independent test set, are
provided in Supp. Info. Our results in the main article are illustrated over
the training data itself.

###  V.1 Bound on $N$ from the accuracy of (21)

We derive here a bound for $N$ which ensures, with high probability, that the
stochastic kernel classifier (21) has a classification error smaller than the
margin error of the exact kernel classifier (20).

######  Definition 7 ($\gamma$-margin violation error).

Given a dataset $\mathcal{D}\sim{\mathcal{P}}$, and a margin $\gamma\geq 0$,
the set of points in $\mathcal{D}$ which are $\gamma$-margin-misclassified by
the classifier $f({\mathbf{x}})=f({\mathbf{x}}|\beta,b;K)$ (7) is

${\mathcal{S}}_{\gamma}=\left\\{({\mathbf{x}}_{i},y_{i})\in\mathcal{D}~{}\left|~{}y_{i}\bigg{(}\sum_{j=1}^{m}\beta_{j}K({\mathbf{x}}_{j},{\mathbf{x}}_{i})+b\bigg{)}<\gamma\right.~{}\right\\}.$
(28)

The $\gamma$-margin violation error of the classifier $f$ over the dataset
$\mathcal{D}$ is defined as

$\epsilon_{\gamma}(f)=\frac{|{\mathcal{S}}_{\gamma}|}{|\mathcal{D}|}.$ (29)

With $\gamma=0$ in the above expression, the set ${\mathcal{S}}_{0}$ includes
all the misclassifications made by the classifier over the dataset
$\mathcal{D}$. Eq. (29) thus gives the _classification error_

$\epsilon_{0}\left(f\right)=1-\textrm{Acc}\left(f\right)$ (30)

of the classifier over dataset $\mathcal{D}$. On the other hand if $\gamma=1$,
the set ${\mathcal{S}}_{1}$ includes all those points
$({\mathbf{x}}_{i},y_{i})$ which lie on the wrong side of the two margins
$y_{i}\left(\sum_{j=1}^{m}\beta_{j}K({\mathbf{x}}_{j},{\mathbf{x}}_{i})+b\right)=1$.
The fraction of such points in $\mathcal{D}$ gives the _margin error_ of the
classifier. These are the points with nonzero contributions to the hinge loss
term in (8).

The main result of this Section is that the classification error
$\epsilon_{0}\left({f}^{(N)}\right)$ of the stochastic kernel classifier (21)
can be guaranteed, with high probability, to be smaller than the
$\gamma$-margin error $\epsilon_{\gamma}\left(f^{*}\right)$ of the true kernel
classifier (20) when $N$ is sufficiently large.

######  Theorem 2.

Let $\mathcal{D}\sim{\mathcal{P}}$ denote a dataset of size
$M=|{\mathcal{D}}|$. The classification error of the stochastic kernel
classifier
$f^{(N)}({\mathbf{x}})=f\left({\mathbf{x}}|\beta^{*},b^{*};K^{(N)}\right)$
(21) is bounded by the $\gamma$-margin error of the true classifier
$f^{*}({\mathbf{x}})=f\left({\mathbf{x}}|\beta^{*},b^{*};K^{*}\right)$ (20),

$\epsilon_{0}\left({f}^{(N)}\right)\leq{\epsilon}_{\gamma}\left(f^{*}\right),$
(31)

with probability at least $(1-\delta)$, whenever

$N\geq\frac{{\mathrm{c}}^{2}}{2\gamma^{2}}\left\lVert\beta^{*}\right\rVert^{2}\log\frac{M}{\delta}.$
(32)

Figure 3: Practical and theoretical bounds on $N$ as a function of the margin
$\gamma$ for the Circles dataset. The green shading represents the region
$\epsilon_{\gamma}\left(f^{*}\right)=0$ where the stochastic kernel function
(21) is expected to have perfect accuracy, with
$\delta_{\mathrm{target}}=0.01$. The red shading represents the region with
large margin error, $\epsilon_{\gamma}\left(f^{*}\right)>0.5$, and low
accuracy. The theoretical bound is smooth as a function of $\gamma$, but the
practical bound shows a rapid change in $N$ around $\gamma=1$. The positions
of the vertical green and red boundaries are expected to be problem dependent.
The theoretical bound on $N$ to obtain an accurate classifier (21) is optimal
when we choose the largest $\gamma$ in the green region.

The above theorem essentially extends the bound of Theorem 1 to any dataset of
size $M$. We make an important remark regarding Theorem 32.

######  Remark 2.

Given any dataset $\mathcal{D}\sim{\mathcal{P}}$ of size $M$, the number of
measurements,

$N=\frac{{\mathrm{c}}^{2}}{2\gamma^{2}}m_{\mathrm{sv}}C^{2}\log\frac{M}{\delta},$
(33)

is sufficient to ensure that (31) holds with probability at least $1-\delta$.
Here $m_{\mathrm{sv}}$ is the number of support vectors in the training set,
and $C$ is the SVM regularization parameter (9).

###### Proof.

The optimal primal and dual coefficients are related by
$\beta^{*}_{i}=y_{i}\alpha^{*}_{i}$ [1]. Since $0\leq\alpha_{i}\leq C$, we
have $\left\lVert\beta^{*}\right\rVert^{2}\leq m_{\mathrm{sv}}C^{2}$, and the
proof follows. ∎

This result provides guidance for choosing the kernel function. A good choice
of kernel $K^{*}$ should classify accurately with a large margin $\gamma$, a
small regularization parameter $C$, and few support vectors $m_{\mathrm{sv}}$.

######  Definition 8 (Theoretical and practical bounds on $N$).

Let the margin $\gamma\geq 0$ be specified for a dataset
$\mathcal{D}\sim{\mathcal{P}}$ of size $M=|\mathcal{D}|$.

  1. 1.

We define the theoretical bound from (32),

$N_{\textrm{theory}}=\frac{{\mathrm{c}}^{2}}{2\gamma^{2}}\left\lVert\beta^{*}\right\rVert^{2}\log\frac{M}{\delta_{\mathrm{target}}},$
(34)

where $\delta_{\mathrm{target}}\ll 1$ is set to a small value.

  2. 2.

We find the practical bound $N_{\textrm{practical}}$ by calculating the
empirical probability of satisfying (31),

$1-\delta_{\mathrm{emp}}=\frac{1}{N_{\mathrm{trials}}}\sum_{s=1}^{N_{\mathrm{trials}}}\mathbbm{1}_{\epsilon_{0}\left(f^{(N)}\\{s\\}\right)\leq\epsilon_{\gamma}\left(f^{*}\right)},$
(35)

starting with some small $N$ and increasing it until we obtain
$\delta_{\mathrm{emp}}<\delta_{\mathrm{target}}$. An explicit algorithm is
given in Appendix A.

Dataset |  $N$ needed for $\epsilon_{0}\left(f^{(N)}\right)=0$, $\delta_{\mathrm{target}}=0.01$ |  $\epsilon_{1}\left(f^{*}\right)$
---|---|---
GATES | SWAP
theory |  practical |  theory |  practical
Circles |  $2\times 10^{4}$ |  $\mathbf{5\times 10^{3}}$ $\ddagger$ |  $8\times 10^{4}$ |  $\mathbf{2.7\times 10^{4}\ddagger}$ | 0.133
Havlicek |  330 |  110 |  1310 |  540 | 0.125
Two Moons |  $2\times 10^{4}$ |  $\mathbf{2.5\times 10^{3}\ddagger}$ |  $7.8\times 10^{4}$ |  $\mathbf{9.7\times 10^{3}\ddagger}$ | 0.14
Table 1: The number of measurements $N$ needed to ensure that (21) reliably
reproduces (20) over the training set itself, with probability of at least
$99\%$. These numbers correspond to the green vertical line in Fig. 3. The
practical bound on $N$ is significantly smaller than the bound implied by
Theorem 32. The GATES test requires an $N$ which is about 4 times smaller than
the SWAP test, as implied by Lemma 2. $\ddagger$ indicates that $N$ exceeds
the IBMQ default value $1024$.

We are interested in obtaining reliable reproduction of (20) from (21). Note
that $\epsilon_{0}(f^{*})=0$ for all the datasets we have considered. Figure 3
shows the theoretical and practical bounds on $N$ as a function of the margin
$\gamma$ for the Circles dataset. The green shading in it represents the
region where $\epsilon_{0}(f^{(N)})=0$ is satisfied with
$\delta_{\mathrm{target}}=0.01$. It thus leads to SKC which reliably
reproduces EKC. In this region, the theoretical bound grows as $\gamma\to 0$
with an inverse quadratic dependence. The practical bound is insensitive to
$\gamma$ since it only depends on the value of the margin error and not the
margin itself. The two bounds are closest to each other at the right edge of
the region, and have been tabulated in Table 1. We notice that the practical
bound is about $3-5$ times smaller, for a fixed circuit. This looseness of the
theoretical bound is expected, since we used a subgaussian bound for the
binomial distribution and not its complete information. The GATES circuit
provides bounds (both theoretical and practical) which are about $4$ times
smaller than those for the SWAP circuit, consistent with Lemma 2.

######  Corollary 2.1.

Over a training set of size $m$, the empirical risk of (21)

$\epsilon_{0}\left(f^{(N)}\right)\leq\epsilon_{1}\left(f^{*}\right)$ (36)

is bounded by the margin error of (20), with probability $1-\delta$, whenever

$N\geq\frac{{\mathrm{c}}^{2}}{2}\left\lVert\beta^{*}\right\rVert^{2}\log\frac{m}{\delta}.$
(37)

The margin errors of (20) are listed in the right-most column of Table 1. The
corresponding mark is a black (dash-dotted) vertical line in Figure 3. We
stress that these values of $N$ (at the black vertical line) are quite small
compared to what is needed to ensure reliable reproduction of (20) (green
region). The corollary above ensures a small empirical risk for (21).

Very importantly, the bound $N=\Omega\left(m_{\mathrm{sv}}\log M\right)$,
needed for reliably reproducing (20), is logarithmic in the size $M$ of the
dataset and linear in the number of support vectors $m_{\mathrm{sv}}$ of the
training set. Often the number of support vectors is significantly smaller
than the size $m$ of the training set, $m_{\mathrm{sv}}\ll m$ [9]. When
applied over the training set itself, the number of circuit evaluations per
kernel entry becomes $N=\Omega\left(\log m\right)$. Contrast this with the
bound which can be derived to control the error in the training kernel matrix:
demanding $\left\lVert\mathbf{K}^{(N)}-\mathbf{K}^{*}\right\rVert\leq\epsilon$
in the operator or Frobenius distance gives
$N=\Omega\left(m^{2}/\epsilon^{2}\right)$ [5]. Indeed, the need to bring
$\mathbf{K}^{(N)}$ close to $\mathbf{K}^{*}$, in addition to their error
mitigation scheme, guided the choice of Ref. [5] of high $N=50,000$
measurements per kernel entry. The entries for the Havlicek dataset in Table 1
are considerably lower, partly due to the logarithmic dependence on $m$.

We now address the second question: Can we construct a reliable classifier
which uses fewer circuit evaluations?

###  V.2 Robust classifier for stochastic QEKs

The stochastic kernel classifier (21)
$f^{(N)}({\mathbf{x}})=f\left({\mathbf{x}}|\beta^{*},b^{*};K^{(N)}\right)$ is
constructed by solving (9) for the optimal coefficients $\beta^{*},b^{*}$ over
a training set given the exact training kernel matrix $\mathbf{K}^{*}$. The
optimization problem over training data is a convex quadratic program since
$\mathbf{K}^{*}\in{\mathbb{S}^{m}_{+}}$. In reality, the kernel matrix over a
training dataset suffers from the same underlying noise which affects the
classifier (21). If we measure the kernel matrix $\mathbf{K}^{(N)}$ with $N$
measurements per kernel entry, the resulting optimization problem (9) would
generally not be convex. Such situations are encountered in optimization
problems and can be handled by introducing a chance constraint [25, 26]. We
show here how we may use the noise information (19) of the training kernel
matrix to construct more reliable classifiers.

An optimization problem with stochastic terms can be turned into a chance
constraint problem as follows:

$\displaystyle\min_{\beta\in{\mathbb{R}}^{m},b,\tau\in{\mathbb{R}}}\quad\tau\
$ (38) $\displaystyle\textrm{s.t.\ }\mathrm{Prob}$
$\displaystyle\left(J(\beta,b;{\mathbf{K}}^{(N)})\leq\tau\right)\geq
1-\delta,$

where $\delta\ll 1$ ensures that for most instantiations of the quantum kernel
matrix $\mathbf{K}^{(N)}$, i.e. with high probability, the primal objective
$J\left(\beta,b;{\mathbf{K}}^{(N)}\right)$ is smaller than $\tau$. This $\tau$
is the new objective which we wish to minimize. It is in fact a dummy variable
that is the means to minimize the (stochastic) primal objective function with
high probability.

The feasible set of a chance constraint is generally non-convex and makes the
optimization problem intractable (although it is convex for some families of
distributions [12]). The natural strategy in such cases is to construct convex
approximations to the chance constraint [27, 13]. The chance constraint method
(38) has been applied to the dual SVM formulation by Bhadra et. al. [13],
where convex approximations were derived for the chance constraint for a few
different noise distributions. In the primal formulation (9) considered in the
present article, we note that there are two terms in the objective which are
stochastic, namely, the hinge loss term and the regularization term given in
the two lines of Eq. (8).

The hinge loss term penalizes margin errors in the training set. If a
datapoint ${\mathbf{x}}_{i}$ in the training set has a margin $\gamma_{i}\geq
1$, then it would not contribute to the hinge loss. If the regularization
parameter $C$ is set to a very large value, the hinge loss term essentially
behaves as a constraint that ensures that no point in the training set has a
margin violation. How can we minimize the hinge loss when dealing with a
stochastic kernel matrix $\mathbf{K}^{(N)}$?

######  Lemma 3.

Let ${\mathbf{x}}_{i}\in\mathcal{D}_{\mathrm{train}}$ and
$\beta\in{\mathbb{R}}^{m},b\in{\mathbb{R}}$. Datapoint ${\mathbf{x}}_{i}$
would have zero hinge loss with probability at least $1-\delta$,

$\mathrm{Prob}\left(y_{i}\bigg{(}\sum_{j}\beta_{j}\mathbf{K}^{(N)}_{ij}+b\bigg{)}\geq
1\right)\geq 1-\delta,$ (39)

if

$y_{i}\bigg{(}\sum_{j}\beta_{j}\mathbf{K}^{*}_{ij}+b\bigg{)}\geq
1+\frac{{\mathrm{c}}}{2\sqrt{N}}\left\lVert\beta\right\rVert\kappa(\delta).$
(40)

###### Proof.

This is a direct application of Lemma 1, using the subgaussian norm from Lemma
2. ∎

The SVM optimization, through the hinge loss term, finds coefficients
$\beta,b$ such that
$1-y_{i}\left(\sum_{j}\beta_{j}\mathbf{K}^{(N)}_{ij}+b\right)$ is minimized.
The above Lemma suggests how we may minimize the hinge loss, when the kernel
matrix is stochastic.

  1. 1.

Given a stochastic kernel matrix $\mathbf{K}^{(N)}$ during training, Lemma 3
[Eq. (40)] provides a sufficient condition for the hinge loss contribution of
${\mathbf{x}}_{i}$ to be minimized with probability $1-\delta$. Importantly,
Eq. (40) is convex in $\beta,b$ and is cone representable.

  2. 2.

The subgaussian bound (Lemma 1) for the quantum kernel distribution (Lemma 2)
provides a very favorable scaling with $\delta$ and an inverse square root
dependence with the number of measurements $N$.

The regularization term $\beta^{\top}\mathbf{K}^{(N)}\beta$ can be turned into
a convex approximation directly by the use of an appropriate tailbound. The
resulting chance constraint problem would thus be stated in terms of two
parameters $\delta_{1},\delta_{2}$ (see Supp. Info. C for a full derivation).

######  Theorem 3.

Let the kernel
$\mathbf{K}=\mathbf{K}^{(N)}\in{\mathbb{R}}^{m}\times{\mathbb{R}}^{m}$ be
inferred from $N$ measurements per entry. The optimal primal objective
$J^{*}(\mathbf{K}):=\min_{\beta,b}J(\beta,b;\mathbf{K})$ of (9) is upper
bounded by

$J^{*}({\mathbf{K}})\leq J^{*}_{\mathrm{rob}},$ (41)

with probability at least $1-\delta_{1}-\delta_{2}$, where

$J^{*}_{\mathrm{rob}}=\min_{\beta\in{\mathbb{R}}^{m},b\in{\mathbb{R}}}J_{\mathrm{rob}}\left(\beta,b;{\mathbf{K}}^{*}|N,\delta_{1},\delta_{2}\right)$
(42)

is the optimal value of a Second-order Cone Program (SOCP), whose objective is
given by

$\displaystyle
J_{\mathrm{rob}}\left(\beta,b;{\mathbf{K}}^{*}|N,\delta_{1},\delta_{2}\right):=$
(43) $\displaystyle
C\sum_{i=1}^{m}\max{\bigg{(}1+\frac{{\mathrm{c}}}{2\sqrt{N}}\kappa{\bigg{(}\frac{\delta_{1}}{m}\bigg{)}}\left\lVert\beta\right\rVert-
y_{i}(\sum_{j=1}^{m}\beta_{j}{\mathbf{K}}^{*}_{ij}+b),0\bigg{)}}$
$\displaystyle+\frac{1}{2}\beta^{\top}\left({\mathbf{K}}^{*}+\frac{{\mathrm{c}}}{2\sqrt{N}}\kappa(\delta_{2})\mathbf{I}_{m\times
m}\right)\beta.$

Note that the objective (43) is very similar to the objective in (8) with two
key differences:

  1. 1.

The hinge-loss has an additional term whose origin is precisely the
enforcement of
$y_{i}\big{(}\sum_{j}\beta_{j}\mathbf{K}^{(N)}_{ij}+b\big{)}\geq 1$, with high
probability as in Lemma 3, for all the $m$ datapoints. Thus a condition
against margin violation, which is robust against stochasticity in the kernel
matrix, is built into the optimization problem itself (42).

  2. 2.

The kernel matrix in the regularization term is made larger by adding to its
diagonal entries a term which arises precisely by requiring
$\beta^{\top}\mathbf{K}^{(N)}\beta\leq\beta^{\top}\mathbf{K}^{*}\beta+t$ with
probability $1-\delta_{2}$ for some $t>0$. The large deviation bound given by
Lemma 1 implies that
$t\geq\frac{{\mathrm{c}}}{2\sqrt{N}}\left\lVert\beta\right\rVert^{2}\kappa(\delta_{2})$
is sufficient.

Suppose now that $N$ is fixed to some preset value depending upon the
constraints/budget of the user of a quantum processor. The points above
suggest that a classifier constructed by solving (42) would be more robust to
the stochasticity of the training kernel matrix. We expect it to be a more
reliable classifier at least over the training dataset. Moreover, since the
kernel evaluations in a test dataset suffer from the same underlying noise (as
the training kernel matrix), we expect it to be more reliable even over a test
dataset (shown in Supp. Info.).

######  Definition 9.

The robust stochastic kernel classifier is

$h^{(N)}({\mathbf{x}})=f\left({\mathbf{x}}|\beta^{*}_{\mathrm{rob}},b^{*}_{\mathrm{rob}};K^{(N)}\right),$
(44)

where $\beta^{*}_{\mathrm{rob}},b^{*}_{\mathrm{rob}}$ are solutions to the
optimization problem (42) for some fixed $N$, and $\delta_{1},\delta_{2}\ll
1$.

######  Definition 10.

The robust exact kernel classifier is

$h^{*}({\mathbf{x}})=f\left({\mathbf{x}}|\beta^{*}_{\mathrm{rob}},b^{*}_{\mathrm{rob}};K^{*}\right),$
(45)

where $\beta^{*}_{\mathrm{rob}},b^{*}_{\mathrm{rob}}$ are solutions to the
optimization problem (42). $N$, and $\delta_{1},\delta_{2}\ll 1$ are the same
as in (44).

(a)

(b)

Figure 4: (a) Comparison of the reliabilities of classifiers found using (9)
and the robust formulation (42), for the Circles dataset. (b) The relative
accuracy $\textrm{RA}(h^{*},f^{*})$ for the same dataset. Looking at (a) and
(b) together, (i) the relative accuracy of $h^{*}$, and (ii) the reliability
$\hat{{\mathcal{R}}}(h^{(N)},h^{*})$, become 1 much before the reliability
$\hat{{\mathcal{R}}}(f^{(N)},f^{*})$ reaches 1.

Thus, we expect the reliability ${\mathcal{R}}(h^{(N)},h^{*})$ to be higher
than ${\mathcal{R}}(f^{(N)},f^{*})$ for the same value of $N$ and
appropriately chosen small parameters $\delta_{1},\delta_{2}$. Note that the
classifier $h^{*}$ is dependent on $N,\delta_{1},\delta_{2}$ via the
optimization problem (42), but it is not stochastic. (45) employs the exact
kernel function $K^{*}$ just as the true classifier (20). Fig. 4(a) shows
$\hat{{\mathcal{R}}}(h^{(N)},h^{*})$ and $\hat{{\mathcal{R}}}(f^{(N)},f^{*})$,
as functions of $N$ for the Circles dataset: it is clear that the robust
classifier $h^{(N)}$ reproduces $h^{*}$ far more reliably than $f^{(N)}$
reproduces $f^{*}$, especially in the high noise regime (low $N$). In
particular, $\hat{{\mathcal{R}}}(h^{(N)},h^{*})=1$ even with a single
measurement shot $N=1$, but it comes at the cost of the accuracy of 45.

Since our original aim was to implement the true classifier $f^{*}$ with as
few measurement shots per entry as possible, we define the relative accuracy
of classifier $h^{*}$ as follows.

######  Definition 11 (Relative Accuracy).

The relative accuracy of (45) with respect to (20) over any dataset is

$\textrm{RA}\left(h^{*},f^{*}\right)=\frac{\textrm{Acc}\left(h^{*}\right)}{\textrm{Acc}\left(f^{*}\right)}.$
(46)

Reliability-Accuracy trade-off:

The classifier $f^{*}$ has perfect accuracy over the training set in all the
datasets considered here (for independent test set, see Supp. Info.). Fig.
4(b) shows the reliability $\hat{{\mathcal{R}}}(h^{(N)},h^{*})$ as well as the
relative accuracy $\textrm{RA}(h^{*},f^{*})$, for the Circles dataset. For
small $N$, the classifier $h^{*}$ provides a low accuracy, but $h^{(N)}$
reproduces $h^{*}$ perfectly. The low accuracy, for small $N$, can be
understood from the expression for $J_{\mathrm{rob}}$ in Eq.(43); the data-
independent terms containing $\delta_{1},\delta_{2}$ dominate over the data-
dependent terms containing ${\mathbf{K}}^{*}$, leading to fixed but inaccurate
results.

With increasing $N$, increases in $\textrm{RA}(h^{*},f^{*})$ are accompanied
by slight decreases in the reliability $\hat{{\mathcal{R}}}(h^{(N)},h^{*})$,
constituting a trade-off between the two quantities. Finally, both these
quantities reach their maximum value $1$. The smallest value of $N$ required
to reliably agree with the results of (20) is tabulated in Table 2, for both
(21) and (44). We note that the values of $N$, where the classifier $h^{(N)}$
reaches perfect reliability as well as perfect accuracy, are considerably
smaller than those for the classifier $f^{(N)}$.

Note that (45) is the same as (20) in the limit of infinitely many
measurements,

$\lim_{N\to\infty}J_{\mathrm{rob}}(\beta,b;\mathbf{K}^{*}|N,\delta_{1},\delta_{2})=J(\beta,b;\mathbf{K}^{*}).$
(47)

However, we see from Figure 4(b) and Table 2 that predictions of (44) agree
with (20) for significantly smaller values of $N$ than what is needed for
(21). The robust optimization program (42) results in a classifier requiring
only a fraction (ranging from $\frac{1}{16}$ to $\frac{1}{4}$) of the number
of measurements $N$ to reliably implement the true classifier (20). We thus
recommend using the robust optimization problem (42) in place of the standard
SVM optimization (9).

(42) is second-order cone representable (details in Supp. Info. C), and
several efficient algorithms have been developed for such optimization
problems [28]. SOCP have found applications in many engineering areas such as
filter design, truss design and grasping force optimization in robotics (see
Ref. [28] for a survey of applications). SOCP has also been very useful for
many machine learning applications e.g. robust classification under
uncertainty [29, 13, 30].

Dataset |  $N$ needed for perfect reliability with (20)
---|---
GATES | SWAP
21 |  44 |  21 |  44
Circles |  $2^{13}$ $\ddagger$ |  $\mathbf{2^{10}}$ |  $2^{16}$ $\ddagger$ |  $\mathbf{2^{12}}$ $\ddagger$
Havlicek [5] |  $2^{7}$ |  $\mathbf{2^{5}}$ |  $2^{9}$ |  $\mathbf{2^{7}}$
Two Moons |  $2^{9}$ |  $\mathbf{2^{8}}$ |  $2^{12}$ $\ddagger$ |  $\mathbf{2^{10}}$
Table 2: The number of measurements $N$ at which perfect reliability222The
values for (21) in this table are the same as the corresponding entries for
$N_{\textrm{practical}}$ in Table 1, but expressed in exponential notation
$N=2^{n}$, $n=\lceil{\log_{2}(N_{\textrm{practical}})}\rceil$. with respect to
(20) is achieved over the training dataset for classifiers (21) and (44). The
instantiations of the kernel function $K^{(N)}$ are the same for both. The
robust classifier reduces the number of circuit evaluations needed (per kernel
entry) by a factor of $4$ to $16$. $\ddagger$ denotes that $N$ exceeds the
IBMQ default value $1024$.

##  VI Summary and Outlook

We have studied the role of $N$, the number of measurements used to evaluate a
quantum kernel, for a classification task. Our considerations have focused on
providing the same predictions as the ideal quantum kernel classifier
($N\to\infty$), not to closely approximate the kernel function itself. We
noted that the classification accuracy is a poor performance metric in the
presence of noise, and defined an empirical reliability that meaningfully
captures the effects of noise. The circuit used to evaluate the quantum kernel
plays an important role in the analysis, and we have shown that the GATES test
is preferable to the SWAP test for any $N$ (Lemma 2). We introduced a generic
uncertainty model (19) that can handle any source of noise. Our results in the
article have considered only the fundamental sampling noise; the modification
to the uncertainty model in presence of other noise sources is given in the
Supp. Info.

Our analysis assumed that we have access to the exact kernel matrix
$\mathbf{K}^{*}\in{\mathbb{S}^{m}_{+}}$ over the training dataset of size $m$.
We then showed that $N=\Omega\left(\log m\right)$ measurements are needed for
reliable reproduction of the ideal quantum classifier over the training
dataset. This is in contrast to the requirement that
$N=\Omega(m^{2}/\epsilon^{2})$, when one evaluates
$\left\lVert\mathbf{K}^{(N)}-\mathbf{K}^{*}\right\rVert\leq\epsilon$ up to a
precision of $\epsilon$. Physically, this arises from the fact that in an SVM
the boundary (and not the bulk) carries the information relevant to the
classifier.

Our main contributions are the following. We developed a bound on $N$ (Theorem
1), which ensures that a datapoint is reliably (i.e. with high probability)
classified the same way as an ideal quantum kernel classifier would do. We
then extended the result to any dataset of $M$ points (Theorem 32), deriving a
bound on $N$ which ensures that the classification error is smaller than the
margin error of the ideal classifier. We also computed a practical bound
(Definition 8) on $N$ which ensures high empirical reliability. We then
investigated whether it was possible to reduce $N$ further, while still
reliably reproducing the ideal classifier. We used the chance constraint
approach to the original SVM (robust formulation) and showed that it is indeed
possible to substantially reduce $N$.

Finally, we point out some open questions related to our results that are
worth exploring, especially in light of the limitations of near-term quantum
hardware.

  1. 1.

To optimize $N$ for an accurate stochastic classifier (21), we need to
maximize $\gamma$ while maintaining low $\gamma$-margin errors of the exact
classifier (20), i.e. stay just left of the vertical green line in Figure 3.
Such a value of $\gamma$ would be problem dependent, but can we develop a
criterion to identify it?

  2. 2.

To optimize $N$ for a robust stochastic classifier (44) while ensuring high
relative accuracy, we need to estimate where RA reaches 1 in Figure 4(b). Such
an $N$ would also be problem dependent, but can we find a method to identify
it?

  3. 3.

In practice, we may only have access to approximate $\mathbf{K}^{(N)}$ over
the training data, instead of the exact $\mathbf{K}^{*}$. Such a
$\mathbf{K}^{(N)}$ may not be positive, and modifications [10, 8] would be
needed to make it positive for the construction of the SVM classifier. How
sensitive would the optimal parameters $\beta,b$ of the SVM be, as a function
of $N$?

## Acknowledgments

Our simulations with quantum kernels are performed using the Pennylane python
package developed by Xanadu [31]. AS was supported by the National
Postdoctoral Fellowship, Science and Engineering Research Board (SERB),
Government of India. The work of AJ and AP was supported in part by the Centre
for Excellence in Quantum Technology funded by the Ministry of Electronics and
Information Technology, Government of India.

## References

  * Scholkopf and Smola [2001] B. Scholkopf and A. J. Smola,  _Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond_ (MIT Press, Cambridge, MA, USA, 2001).
  * Schuld and Killoran [2019] M. Schuld and N. Killoran, Phys. Rev. Lett. 122, 040504 (2019).
  * Schuld [2021] M. Schuld, (2021), arXiv:2101.11020 [quant-ph] .
  * Kübler  _et al._ [2021] J. Kübler, S. Buchholz, and B. Schölkopf, Advances in Neural Information Processing Systems 34 (2021).
  * Havlíček  _et al._ [2019] V. Havlíček, A. D. Córcoles, K. Temme, A. W. Harrow, A. Kandala, J. M. Chow, and J. M. Gambetta, Nature 567, 209 (2019).
  * Liu  _et al._ [2021] Y. Liu, S. Arunachalam, and K. Temme, Nature Physics 17, 1013 (2021).
  * Huang  _et al._ [2021] H.-Y. Huang, M. Broughton, M. Mohseni, R. Babbush, S. Boixo, H. Neven, and J. R. McClean, Nature Communications 12, 2631 (2021).
  * Wang  _et al._ [2021] X. Wang, Y. Du, Y. Luo, and D. Tao, Quantum 5, 531 (2021).
  * Steinwart [2003] I. Steinwart, Advances in Neural Information Processing Systems 16 (2003).
  * Hubregtsen  _et al._ [2021] T. Hubregtsen, D. Wierichs, E. Gil-Fuster, P.-J. H. S. Derks, P. K. Faehrmann, and J. J. Meyer, (2021), arXiv:2105.02276 [quant-ph] .
  * Blank  _et al._ [2020] C. Blank, D. K. Park, J.-K. K. Rhee, and F. Petruccione, npj Quantum Information 6, 41 (2020).
  * Prékopa [1995] A. Prékopa,  _Stochastic Programming_ (Kluwer Academic Publishers, Dordrecht, The Netherlands, 1995).
  * Bhadra  _et al._ [2010] S. Bhadra, S. Bhattacharya, C. Bhattacharyya, and A. Ben-Tal, Proceedings of the 27th International Conference on Machine Learning (2010).
  * Bharti  _et al._ [2022] K. Bharti, A. Cervera-Lierta, T. H. Kyaw, T. Haug, S. Alperin-Lea, A. Anand, M. Degroote, H. Heimonen, J. S. Kottmann, T. Menke, W.-K. Mok, S. Sim, L.-C. Kwek, and A. Aspuru-Guzik, Rev. Mod. Phys. 94, 015004 (2022).
  * Kübler  _et al._ [2020] J. M. Kübler, A. Arrasmith, L. Cincio, and P. J. Coles, Quantum 4, 263 (2020).
  * Arrasmith  _et al._ [2020] A. Arrasmith, L. Cincio, R. D. Somma, and P. J. Coles, Operator sampling for shot-frugal optimization in variational algorithms (2020).
  * Gu  _et al._ [2021] A. Gu, A. Lowe, P. A. Dub, P. J. Coles, and A. Arrasmith, Adaptive shot allocation for fast convergence in variational quantum algorithms (2021).
  * [18] V. V. Buldygin and Y. V. Kozachenko, Ukrainian Mathematical Journal 32, 483.
  * Cervantes  _et al._ [2020] J. Cervantes, F. Garcia-Lamont, L. Rodríguez-Mazahua, and A. Lopez, Neurocomputing 408, 189 (2020).
  * Vapnik [1998] V. N. Vapnik,  _Statistical Learning Theory_ (Wiley, New York, 1998).
  * Lloyd  _et al._ [2020] S. Lloyd, M. Schuld, A. Ijaz, J. Izaac, and N. Killoran, (2020), arXiv:2001.03622 [quant-ph] .
  * Nielsen and Chuang [2011] M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information: 10th Anniversary Edition_ , 10th ed. (Cambridge University Press, USA, 2011).
  * Massart [2007] P. Massart,  _Concentration Inequalities and Model Selection_, edited by J. Picard (Springer Berlin Heidelberg, 2007).
  * Nghiem  _et al._ [2021] N. A. Nghiem, S. Y.-C. Chen, and T.-C. Wei, Phys. Rev. Research 3, 033056 (2021).
  * Charnes  _et al._ [1958] A. Charnes, W. W. Cooper, and G. H. Symonds, Management Science 4, 235 (1958).
  * Prékopa [1970] A. Prékopa, On probabilistic constrained programming, in  _Proceedings of the Princeton Symposium on Mathematical Programming_ (Princeton University Press, 1970) pp. 113–138.
  * Nemirovski and Shapiro [2007] A. Nemirovski and A. Shapiro, SIAM Journal on Optimization 17, 969 (2007), https://doi.org/10.1137/050622328 .
  * Lobo  _et al._ [1998] M. S. Lobo, L. Vandenberghe, S. Boyd, and H. Lebret, Linear Algebra and its Applications 284, 193 (1998), international Linear Algebra Society (ILAS) Symposium on Fast Algorithms for Control, Signals and Image Processing.
  * Lanckriet  _et al._ [2003] G. R. Lanckriet, L. E. Ghaoui, C. Bhattacharyya, and M. I. Jordan, J. Mach. Learn. Res. 3, 555–582 (2003).
  * Ben-Tal  _et al._ [2011] A. Ben-Tal, S. Bhadra, C. Bhattacharyya, and J. Saketha Nath, Mathematical Programming 127, 145 (2011).
  * Bergholm  _et al._ [2018] V. Bergholm, J. Izaac, M. Schuld, C. Gogolin, M. S. Alam, S. Ahmed, J. M. Arrazola, C. Blank, A. Delgado, S. Jahangiri, K. McKiernan, J. J. Meyer, Z. Niu, A. Száva, and N. Killoran, Pennylane: Automatic differentiation of hybrid quantum-classical computations (2018).
  * Goldberg and Guo [2017] L. A. Goldberg and H. Guo, computational complexity 26, 765 (2017).
  * Buldigīn and Moskvichova [2011] V. V. Buldigīn and K. K. Moskvichova, Teor. Ĭmovīr. Mat. Stat. , 28 (2011).
  * Arbel  _et al._ [2019] J. Arbel, O. Marchal, and H. D. Nguyen, On strict sub-gaussianity, optimal proxy variance and symmetry for bounded random variables (2019), arXiv:1901.09188 [math.PR] .
  * Boole [2009] G. Boole,  _The Mathematical Analysis of Logic: Being an Essay Towards a Calculus of Deductive Reasoning_, Cambridge Library Collection - Mathematics (Cambridge University Press, 2009).

##  Appendix A Computing the number of measurements needed for kernel
evaluation

We follow the algorithm below to compute the practical bound on $N$, from the
Definition 8. Fig. 3 shows that this practical bound on $N$ is always below
the theoretical bound given by Theorem 32.

Algorithm 1 Computing $N_{\mathrm{practical}}$

$\mathcal{D}$, $K^{*}$, $\gamma$

/* Given: $\beta^{*}$, $b^{*}$ over training data
$\mathcal{D}_{\mathrm{train}}$ */

Initialize $N_{\mathrm{start}}$, $N_{\mathrm{step}}$,
$\delta_{\mathrm{target}}=0.01$, $N_{\mathrm{trials}}=200$

for $i\leftarrow 1$ to $|\mathcal{D}|$ do

for $j\leftarrow 1$ to $|\mathcal{D}_{\mathrm{train}}|$ do

${\mathbf{K}}[i,j]\leftarrow K^{*}({\mathbf{x}}_{i},{\mathbf{x}}_{j})$

/* Above $K^{*}_{ij}$ needed for computation of $f^{*}({\mathbf{x}}_{i})$ */

$\epsilon_{\gamma}\leftarrow\sum_{i\in[|\mathcal{D}|]}\mathbb{1}_{y_{i}f^{*}({\mathbf{x}}_{i})<\gamma}$

$N\leftarrow N_{\mathrm{start}}$

while $\delta_{\mathrm{emp}}\geq\delta_{\mathrm{target}}$ do

$N\leftarrow N+N_{\mathrm{step}}$

for $t\leftarrow 1$ to $N_{\mathrm{trials}}$ do

$c\leftarrow 0$

for $i\leftarrow 1$ to $|\mathcal{D}|$ do

for $j\leftarrow 1$ to $|\mathcal{D}_{\mathrm{train}}|$ do

${\mathbf{K}}[i,j]\leftarrow
K^{(N)}\\{t\\}\left({\mathbf{x}}_{i},{\mathbf{x}}_{j}\right)$

/* $K^{(N)}\\{t\\}({\mathbf{x}}_{i},{\mathbf{x}}_{j})$ for computing
$f^{(N)}\\{t\\}({\mathbf{x}}_{i})$ */

$\epsilon_{0}\leftarrow\sum_{i\in[|\mathcal{D}|]}\mathbb{1}_{y_{i}{f}^{(N)}\\{t\\}({\mathbf{x}}_{i})<0}$

if $\epsilon_{0}>\epsilon_{\gamma}$ then

$c\leftarrow c+1$

$\delta_{\mathrm{emp}}\leftarrow{c}/{N_{\mathrm{trials}}}$ return $N$

Supplementary Information

Reliable quantum kernel classification using fewer circuit evaluations

##  Appendix A Datasets and Kernel Embedding choices

Datasets. Our simulations with quantum kernels are performed using the
PennyLane python package developed by Xanadu [31]. We use three datasets to
illustrate our results: make_circles (Circles) and make_moons (Moons) dataset
from sklearn and the Havlicek generated dataset. The latter is generated by
using IQPEmbedding and following the procedure outlined in ref. [5]. We then
use the same embedding kernel to classify the generated dataset. Our choice of
kernel functions for the other two datasets (Circles and Moons) are based on a
trial and error process where we tried different embedding kernels and chose
the one that returned the highest test accuracies. Our choice of the kernel
function for the dataset Circles is the simple AngleEmbedding circuit shown in
fig. (S1) in the main article. The Moons dataset was found to give very high
test accuracies by using a X-rotation (AngleEmbedding) after the application
of the IQPEmbedding. All of these kernels are defined over 2-qubits (all
datasets here are 2-dimensional) with no repeating layers and no tunable
circuit parameters. We have chosen a smaller number of training samples,
keeping in view the restrictions placed by near-term devices [8].

Table S1 shows training and test sizes. For the Havlicek dataset we use $m=40$
(20 labels per class as used in ref. [5]), and a equal test size $M=40$,
exactly as used in their study. All the training and test datasets used here
are balanced. These kernel choices were used in the main article and all of
them lead to nearly perfect test accuracies for the exact kernel classifier
(20).

Quantum Kernel embeddings.

It is easy to see that the kernel function is equivalent to an inner product
in the feature Hilbert space $\mathcal{H}\otimes\mathcal{H}^{*}$ since, for
every pair
$\ket{\phi({\mathbf{x}}_{i})},\ket{\phi({\mathbf{x}}_{j})}\in\mathcal{H}$, we
have
$\ket{\phi({\mathbf{x}}_{i})}\otimes\ket{\phi^{*}({\mathbf{x}}_{i})},\ket{\phi({\mathbf{x}}_{j})}\otimes\ket{\phi^{*}({\mathbf{x}}_{j})}\in\mathcal{H}\otimes\mathcal{H}$,
whose inner product is the quantum kernel
$K({\mathbf{x}}_{i},{\mathbf{x}}_{j})=|\bra{\phi({\mathbf{x}}_{i})}\phi({\mathbf{x}}_{j})\rangle|^{2}$.
One can express this in terms of an outer product
$\ket{\phi({\mathbf{x}}_{j})}\otimes\bra{\phi({\mathbf{x}}_{j})}\in\mathcal{H}\otimes\mathcal{H^{*}}$
where the embedding vectors are density matrices and the kernel can be
described via the Hilbert-Schmidt inner product as given in (10).

Figure S1: Example: Angle Embedding. A simple quantum embedding circuit which
is embedding the input vector ${\mathbf{x}}=(x_{1},x_{2})\in{\mathbb{R}}^{2}$
into a quantum state $\ket{\phi({\mathbf{x}})}$ in the 2-qubit Hilbert space
$\mathcal{H}$, by applying a rotation along the X-axis by angle $x_{i}$ over
the corresponding qubit starting in the state $\ket{0}$. The transition
probability between two such quantum states
$K({\mathbf{x}},{\mathbf{x}}^{\prime})=|\langle{\phi({\mathbf{x}}^{\prime})}|\phi({\mathbf{x}})\rangle|^{2}$
is a valid kernel function and is known as a Quantum Embedding Kernel (QEK).

Note that the AngleEmbedding shown in fig. S1 is a simple quantum embedding
circuit which can in fact be simulated efficiently on a classical machine [32,
5]. However, our study does not directly concern the debate regarding quantum
advantage. Rather, our focus is on the number of measurements $N$ needed to
reliably implement a quantum kernel classifier.

All the figures presented in the main article used the Circles dataset with
the AngleEmbedding kernel.

Change of kernel embedding. Our results derived in the main article over the
bounds on $N$ as well as the improved performance of the robust classifiers
hold regardless of the choice of kernel. We illustrate this using Moons
dataset with the IQPEmbedding which does not classify the test set with as
high accuracy as when used in conjuction with a X-rotation (AngleEmbedding).
The training and test sets are held the same. The accuracy over the test set
for the true classifier (20) in this case is $88.3\%$, as opposed to $99.72\%$
for the kernel choice in TableS1. Figure 2(c) shows that the reliabilities of
the robust classifiers are far higher for both the kernel choices. The top
panel shows the performance of the original kernel choice and the bottom panel
shows the performance of the IQPEmbedding alone over the same test set.

We see that the choice of kernel has made the $N$ much higher than if we had
used the IQPEmbedding along with the X-rotation (as done in the main article).
The classifier (21) requires far more circuit evaluations to ensure a
reliability close to one. Bad kernel choices may thus result in very large
overheads for $N$. However, the advantages of the robust classifiers are still
valid.

Dataset |  Kernel Embedding |  Training size $m$ |  Test size $M$ | Test Accuracy
---|---|---|---|---
Havlicek [5] | IQPEmbedding | 40 | 40 | 100%
Circles (make_circles) | AngleEmbedding | 30 | 370 | 100%
Moons (make_moons) |  IQPEmbedding + AngleEmbedding | 40 | 360 | 99.7%
Table S1: Summary of datasets and quantum kernel embedding choices. The Moons
dataset is encoded using the IQPEmbedding followed by a X-rotation by an angle
given by the corresponding values of the feature vector. All embedding
circuits are defined over 2 qubits with no layer repetitions and no tunable
parameters. These choices lead to very high test accuracy for the true kernel
classifier (20).

(a)

(b)

(c)

(d)

Figure S2: The test accuracy of the true classifier (20) over the same test set is $88.3\%$ when we the kernel choice is IQPEmbedding alone (bottom panel) for the Moons dataset and is $99.7\%$ when the embedding circuit has an additional X-rotation (top panel). The $N$ requirement for (21) has gone up in the bottom panel. However, the robust classifier still provides a large advantage: It can provide very high reliability and reproduce (20) for much smaller $N$. Dataset |  $N$ needed for perfect reliability with (20)
---|---
GATES | SWAP
21 |  44 |  21 |  44
Circles |  $2^{14}$ $\ddagger$ |  $\mathbf{2^{10}}$ |  $2^{16}$ $\ddagger$ |  $\mathbf{2^{12}}$ $\ddagger$
Havlicek [5] |  $2^{9}$ |  $\mathbf{2^{6}}$ |  $2^{11}$ $\ddagger$ |  $\mathbf{2^{8}}$
Two Moons |  $2^{13}$ |  $\mathbf{2^{9}}$ |  $2^{15}$ $\ddagger$ |  $\mathbf{2^{11}}$ $\ddagger$
Table S2: $N$ at which perfect reliability, with respect to $f^{*}$, is
achieved over the test dataset for classifiers (21) and (44). Training test is
the same as considered in the main article. The instantiations of the kernel
function $K^{(N)}$ are the same for both. The Robust classifier reduces the
number of circuit evaluations needed (per kernel evaluation) by a factor of
$4$ to $16$ in the datasets considered here. $\ddagger$ denotes $N$ exceeding
IBM default value of $1024$. The Moons dataset needs very large $N$ to reach
“perfect” reliability with (20). For this case, we report $N$ for which it
achieves $>98\%$ reliability with (20). See Figure 2(a) and 2(b).

Total circuit evaluations. We have so far discussed the reduction in the
number of circuit evaluations per kernel entry. TableS2 shows the $N$ needed
per kernel entry. However, we note that the number of support vectors increase
when one solves the robust optimization problem (42). If the size of the test
set is $M$, we need $m_{\mathrm{sv}}M$ total circuit evaluations where
$m_{\mathrm{sv}}$ is the number of support vectors. However, an advantage is
still maintained by the robust classifier in terms of the total number of
measurements needed. For the circles and moons dataset, we still find a
$>75\%$ reduction in the total circuit evaluations and $>50\%$ for the
Havlicek dataset.

Other sources of noise. Recently, kernel estimates have been introduced that
correct for depolarizing error as well [10]. These estimates are not unbiased,
i.e. $\mathbb{E}[K^{(N)}\left({\mathbf{x}}_{i},{\mathbf{x}}_{j}\right)]\neq
K^{*}({\mathbf{x}}_{i},{\mathbf{x}}_{j})$, and requires separate treatment. In
such a case, we may write the final kernel function $K_{ij}$ as

$K_{ij}=\hat{K}_{ij}+\Delta{K}^{(N)}_{ij}+\Delta{K}^{(\textrm{other})}_{ij},$
(S1)

where $\mathbb{E}[{K_{ij}}]=\hat{K}_{ij}\neq K^{*}_{ij}$ which must be
estimated using a bias-correcting procedure (such as the one for depolarizing
noise in ref. [10]). All other noise contributions have been subsumed into
$\Delta{K}^{(\textrm{other})}_{ij}$ whose expectation value is taken as zero
without loss of generality. Assuming they are independent sources of noise, we
would have

$\sigma_{0}^{2}=\sigma^{2}(K_{ij})=\frac{{\mathrm{c}}^{2}}{4N}+\sigma^{2}(\textrm{other}),$
(S2)

and the methods we develop in the article can be applied with the above
$\sigma_{0}$ in the uncertainty model 19. However, if the noise biases the
kernel value, we would need to compare all our results to $\hat{K}$ instead of
$K^{*}$. All our results in this article were in the presence of the sampling
noise alone to clarify its contribution.

##  Appendix B Subgaussian property of Bernoulli random variables

A random variable $\xi$ (centered, $\mathbb{E}{\xi}=0$) is called subgaussian
if there exists $a\in[0,\infty)$ such that

$\mathbb{E}{e^{\lambda\xi}}\ \leq e^{\frac{a^{2}\lambda^{2}}{2}},\
\forall\lambda\in\mathbb{R}$ (S3)

and the smallest such $a$

$\sigma(\xi)=\textrm{inf}\ \big{\\{}a\geq
0\big{|}\mathbb{E}{\exp{\\{\lambda\xi\\}}}\leq\exp{\big{\\{}{a^{2}\lambda^{2}}/{2}\big{\\}}},\
\forall\lambda\in\mathbb{R}\big{\\}}$ (S4)

is called the subgaussian norm of $\xi$ (smallest such $a^{2}=\sigma^{2}(\xi)$
has been called the optimal variance proxy). We note two straight-forward
properties of the subgaussian norm [33]: (1) _Scaling_ , i.e.
$\sigma^{2}(\lambda X)=\lambda^{2}\sigma^{2}(X)$ for any
$\lambda\in\mathbb{R}$, and (2) _Sub-additivity_ , i.e. for any independent
$X_{k},\ k=\\{1,2,...,N\\}$,
$\sigma^{2}(\sum_{k=1}^{N}(X_{k}))\leq\sum_{k=1}^{N}\sigma^{2}(X_{k})$.
Equality holds for independent and identical random variables $\xi_{k},\
k=\\{1,2,...,N\\}$, $\sigma^{2}(\sum_{k=1}^{N}\xi_{k})=N\sigma^{2}(\xi_{1})$.

For both GATES and SWAP, the mean of the estimated kernel matches the true
kernel
$\mathbb{E}[K_{N}({\mathbf{x}}_{i},{\mathbf{x}}_{j})]=K^{*}({\mathbf{x}}_{i},{\mathbf{x}}_{j})$.
The variances of these two estimates are given by

$\operatorname{\textrm{Var}}(K_{N}({\mathbf{x}}_{i},{\mathbf{x}}_{j}))=\begin{cases}\frac{K^{*}_{ij}\big{(}1-K^{*}_{ij}\big{)}}{N}&\text{(GATES)}\\\
\frac{\big{(}1-(K^{*}_{ij})^{2}\big{)}}{N}~{}~{}~{}&\text{(SWAP)}.\end{cases}$
(S5)

In Eq. (S5) since $0\leq K^{*}_{ij}\leq 1$, we have
$K^{*}_{ij}(1-K^{*}_{ij})\leq 1-(K^{*}_{ij})^{2}$, implying a lower variance
for the GATES circuit for the same $N$. Thus the SWAP circuit is affected more
by the sampling noise. The maximum value of $K^{*}_{ij}(1-K^{*}_{ij})$ is
$0.25$ whereas $1-(K^{*}_{ij})^{2}$ can take a maximum value of $1$. This
bounds the variance of $K^{(N)}_{ij}$ in Eq. (S5) (equivalently the variance
of $\Delta{K}^{(N)}_{ij}$).

We note that the distributions given by (13) and (16) are subgaussian.
Furthermore, we note that $\Delta{K}^{(N)}_{ij}$ in (11) can be expressed as
the sum of $N$ i.i.d. centered Bernoulli random variables $X_{k}(p)\sim
B^{(0)}(1,p)=p-B(1,p),\ k=\\{1,2,...,N\\}$ for both the GATES and the SWAP
tests

$N\Delta{K}^{(N)}_{ij}=\begin{cases}\sum_{k=1}^{N}X_{k}(p),\
p=K^{*}_{ij}&(\textbf{GATES})\\\ 2\sum_{k=1}^{N}X_{k}(p),\
p=\frac{1+K^{*}_{ij}}{2}&(\textbf{SWAP}).\end{cases}$ (S6)

Stated another way, the prefactor of 2 above for the SWAP test would have the
effect of increasing its variance and thus makes it less reliable for the same
number of measurements $N$. Bernoulli random variables are subgaussian [33,
34] and their properties are covered in section B. We use these properties to
derive tail bounds over the kernel distributions.

We omit the random variable $\xi\sim B^{(0)}(1,p)$ while denoting the
subgaussian norm for a centered Bernoulli distribution and simply write
$\sigma(p)$. The optimal variance proxy for a centered Bernoulli distribution
was derived in [33] and is given by ($q=1-p$)

$\sigma^{2}(p)=\begin{cases}0&\ \ p=\\{0,1\\}\\\ 0.25&\ \ p=0.5\\\
\frac{p-q}{2(\ln(p)-\ln(q))}&\ \ \textrm{otherwise}.\end{cases}$ (S7)

Its properties were derived in lemma 2.1 of [33] from which we note that
$\sigma^{2}(p)$ is monotonically increasing for $p\in(0,1/2)$ and
monotonically decreasing for $p\in(1/2,1)$. It is also symmetrical
$\sigma^{2}(p)=\sigma^{2}(q)$ (where $q=1-p$). It takes on its maximum value
of 1/4 when $p=q=1/2$. Using the maximum value of the subgaussian norm for
Bernoulli random variables above and eq. (S6) for the two different circuits
gives us the bound used in (18).

##  Appendix C Chance constraint programming for (9)

We shall assume below that the kernel matrix
$\mathbf{K}=\mathbf{K}^{(N)}=\mathbf{K}^{*}-\Delta\mathbf{K}^{(N)}$ is
stochastic and entries of $\Delta{\mathbf{K}}^{(N)}$ satisfy the uncertainty
model (19) with the bound given by Eq. (18).

The hinge loss given by

$L(\beta,b;{\mathbf{K}})=\sum_{i=1}^{m}\max\bigg{(}1-y_{i}(\sum_{j}{\mathbf{K}}_{ij}\beta_{j}+b),0\bigg{)}$
(S8)

is also subject to the stochasticity of the kernel matrix ${\mathbf{K}}$.
Whether the term is zero or positive depends on the particular instantiation
of the kernel matrix. This will have to be handled by a chance constraint
approach. The same objective in the SVM primal problem (8) can be written as

$\min_{t,\xi,\beta,b}J(t,\xi,\beta,b;\mathbf{K}):=C\sum_{i=1}^{m}\xi_{i}+t,$
(S9)

with the hinge-loss term as the two constraints

$\textrm{IE}_{i}:\ \xi_{i}\geq
1-y_{i}\big{(}\sum_{j=1}^{m}{\mathbf{K}}_{ij}\beta_{j}+b\big{)},$ (S10)

and

$\xi_{i}\geq 0,\ i\in[m].$ (S11)

The quadratic term is translated to the constraint

$\frac{1}{2}\beta^{\operatorname{\intercal}}{\mathbf{K}}\beta\leq t.$ (S12)

The constraints (S10) and (S12) are dependent on the particular instantiation
of the stochastic kernel matrix ${\mathbf{K}}_{N}$ and we thus advocate the
strategy of satisfying them with high probability. We denote the probability
of violation of any one constraint $\textrm{IE}_{i}$ in (S10) by
$\delta_{1}\ll 1$ and the probability of violating the constraint (S12) by
$\delta_{2}\ll 1$. The intersection of all the inequalities $\textrm{IE}_{i}$
is satisfied with a high probability $1-\delta_{1}$, which gives us a
sufficient condition that each inequality be satisfied with the higher
probability of $1-\delta_{1}/m$ (union bound C.1)

$\mathrm{Prob}\bigg{(}\xi_{i}\geq
1-y_{i}\big{(}\sum_{j}{\mathbf{K}}_{ij}\beta_{j}+b\big{)}\bigg{)}\geq
1-\frac{\delta_{1}}{m},$ (S13)

and

$\mathrm{Prob}\bigg{(}\frac{1}{2}\beta^{\operatorname{\intercal}}{\mathbf{K}}\beta\leq
t\bigg{)}\geq 1-\delta_{2}.$ (S14)

We derive sufficient conditions for the constraints (S13) and (S14) below
which lead to theorem 3. At optimality, we shall denote
$J(t,\xi,\beta,b;\mathbf{K})=J^{*}(\mathbf{K})$, dropping the optimal
variables $t^{*},\xi^{*},\beta^{*},b^{*}$ from the notation.

###  C.1 Chance constraint: Union bound

When multiple chance constraints are present, we have invoked the well-known
union bound to derive our results [35]. Suppose the chance constraints to be
satisfied are some inequalities $A_{i},\ i\in[m]$, we denote its conjugate as
$\bar{A}_{i}$ which is the violation of inequality $A_{i}$. We would like all
the constraints $A_{i}$, i.e. $\cap_{i}^{m}A_{i}$, to be satisfied and derive
a sufficient condition for it. Since
$\overline{\cap_{i}^{m}A_{i}}=\cup_{i}\bar{A}_{i}$, we consider the
probability of the union of all constraint violations

$\displaystyle\mathrm{Prob}\big{(}\bar{A}_{1}\cup\bar{A}_{2}\cup...\bar{A}_{m}\big{)}$
$\displaystyle\leq\sum_{i=1}^{m}\mathrm{Prob}\big{(}\bar{A}_{i}\big{)},$ (S15)
$\displaystyle\leq\delta,$

for some small parameter $0<\delta\ll 1$. This provides the sufficient
condition

$\displaystyle\mathrm{Prob}(\bar{A}_{i})$ $\displaystyle\leq\frac{\delta}{m},$
(S16) $\displaystyle\mathrm{Prob}(A_{i})$ $\displaystyle\geq
1-\frac{\delta}{m}.$

###  C.2 Proofs

Theorem 32 follows a procedure similar to that of theorem 1 but additionally
uses the Union bound mentioned above. We provide a detailed proof of theorem 3
below. The proof follows a similar procedure as that for theorem 32 and is
detailed here for clarity.

###### Proof of Theorem 3.

The optimization problem (S9) subject to the chance constraints (S13) and
(S14) is in general nonconvex and we now derive sufficient conditions for the
chance constraints (S13) and (S14) using the uncertainty model
${\mathcal{P}}_{N}$. We first write the random kernel $K$ as the sum of its
expected and stochastic parts $K_{ij}=K^{*}_{ij}-\Delta K^{(N)}_{ij}$ in the
chance constraint (S13)

$P\bigg{(}y_{i}\sum_{j}\beta_{j}\Delta K^{(N)}_{ij}\leq h\bigg{)}\geq
1-\frac{\delta_{1}}{m},$ (S17)

where $h=y_{i}\big{(}\sum_{j}K^{*}_{ij}\beta_{j}+b\big{)}+\xi_{i}-1$. We
derive a tail bound for the constraint violation probability for the random
variable $X=y_{i}\sum_{j}\beta_{j}\Delta K^{(N)}_{ij}$ using lemma 1 and find
the sufficient condition

$\xi_{i}\geq
1-y_{i}\bigg{(}\sum_{j}K^{*}_{ij}\beta_{j}+b\bigg{)}+\frac{{\mathrm{c}}}{2\sqrt{N}}\kappa\bigg{(}\frac{\delta_{1}}{m}\bigg{)}\left\lVert\beta\right\rVert,$
(S18)

for satisfying the chance constraint (S13).

We similarly derive a sufficient condition for the chance constraint (S14).
With the kernel matrix
$\mathbf{K}_{ij}=\mathbf{K}^{*}_{ij}-\Delta\mathbf{K}^{(N)}_{ij}$, we define
the random variable

$R=-\frac{1}{2}\beta^{\operatorname{\intercal}}\Delta{\mathbf{K}}_{N}\beta=-\frac{1}{2}\sum_{ij}\Delta{K}^{(N)}_{ij}\beta_{i}\beta_{j}.$
(S19)

We rewrite (S14) as $P(R\leq t^{\prime})\leq\delta_{2}$ and apply lemma 1 to
find the sufficient condition. We detail it below for clarity:

$\displaystyle t^{\prime}$
$\displaystyle\geq\frac{{\mathrm{c}}}{4\sqrt{N}}\left\lVert\beta\right\rVert^{2}\kappa(\delta_{2})$
(S20) $\displaystyle t$
$\displaystyle\geq\frac{1}{2}\beta^{\operatorname{\intercal}}\mathbf{K}^{*}\beta+\frac{{\mathrm{c}}}{4\sqrt{N}}\left\lVert\beta\right\rVert^{2}\kappa(\delta_{2})$
$\displaystyle=\frac{1}{2}\beta^{\operatorname{\intercal}}\bigg{(}\mathbf{K}^{*}+\frac{{\mathrm{c}}}{2\sqrt{N}}\kappa(\delta_{2})I\bigg{)}\beta$

for satisfying the chance constraint (S14).

Use sufficient conditions (S18), (S20) for the objective (S9) and eliminate
(dummy) variable $t$. Apply the union bound (C.1) for conditions (S13) and
(S14) to show $\forall\beta,b$:

$\mathrm{Prob}\big{(}J(\beta,b;\mathbf{K})\leq
J_{\mathrm{rob}}(\xi,\beta,b;\mathbf{K}^{*})\big{)}\geq
1-\delta_{1}-\delta_{2}.$ (S21)

At optimality $J^{*}(\mathbf{K})=\min_{\beta,b}J(\beta,b;\mathbf{K})$ and
$J^{*}_{\mathrm{rob}}=\min_{\xi,\beta,b}J_{\mathrm{rob}}(\xi,\beta,b;\mathbf{K}^{*})$
to get (41). Eliminating $\xi\geq 0$ from the constraints (S18) give us the
hinge-loss form of the objective used in Eq. (43).

∎

###  C.3 Second-order cone programming

A second-order cone program (SOCP) involves a linear objective function with
one or more second-order cone constraints and any additional linear inequality
constraints. An example of a second-order cone constraint in $d+1$ dimensions
is $\left\lVert x\right\rVert_{2}\leq t$, where
${\mathbf{x}}\in{\mathbb{R}}^{d},\ t\in{\mathbb{R}}$. The convex
approximations we developed for the chance constraints (S13) and (S14), i.e.
(S18) and (S20) respectively, are second-order cone representable. This was
shown for the chance constraint approach involving the SVM Dual in Ref. [13].
We show it for the SVM Primal (42) below.

The constraint (S18) can be represented as a second-order cone (SOC)
constraint by simply introducing an additional variable $r$ with the SOC
constraint $\left\lVert\beta\right\rVert\leq r$, and replacing
$\left\lVert\beta\right\rVert$ by $r$ in (S18) which is an additional linear
inequality constraint. Similarly, (S20) is a quadratic constraint which can be
straight-forwardly expressed as a SOC constraint $\left\lVert
A\beta\right\rVert\leq t$, where $A\in{\mathbb{S}^{m}_{+}}$ is the positive-
definite square root of the matrix
$A^{2}=\left(\mathbf{K}^{*}+\frac{{\mathrm{c}}}{2\sqrt{N}}\kappa(\delta_{2})I\right)\in{\mathbb{S}^{m}_{+}}$.
The primal objective (S9) along with the linear and SOC constraints stated
above forms a second-order cone program (SOCP) which can be solved efficiently
[28]. We use the MOSEK solver for its numerical implementation in Python using
the convex programming package cvxpy.