8.5in 11in

# Quantum Semi-Supervised Kernel Learning

Seyran Saeedi e-mail<EMAIL_ADDRESS>Department of Computer Science, Virginia
Commonwealth UniversityRichmond, VA, USA Aliakbar Panahi e-mail:
<EMAIL_ADDRESS>Department of Computer Science, Virginia Commonwealth
UniversityRichmond, VA, USA Tom Arodz Corresponding author. e-mail:
<EMAIL_ADDRESS>Department of Computer Science, Virginia Commonwealth
UniversityRichmond, VA, USA

###### Abstract

Quantum computing leverages quantum effects to build algorithms that are
faster then their classical variants. In machine learning, for a given model
architecture, the speed of training the model is typically determined by the
size of the training dataset. Thus, quantum machine learning methods have the
potential to facilitate learning using extremely large datasets. While the
availability of data for training machine learning models is steadily
increasing, oftentimes it is much easier to collect feature vectors that to
obtain the corresponding labels. One of the approaches for addressing this
issue is to use semi-supervised learning, which leverages not only the labeled
samples, but also unlabeled feature vectors. Here, we present a quantum
machine learning algorithm for training Semi-Supervised Kernel Support Vector
Machines. The algorithm uses recent advances in quantum sample-based
Hamiltonian simulation to extend the existing Quantum LS-SVM algorithm to
handle the semi-supervised term in the loss. Through a theoretical study of
the algorithm’s computational complexity, we show that it maintains the same
speedup as the fully-supervised Quantum LS-SVM.

##  1 Introduction

Building computing machines that can exploit quantum effects has lead to
faster algorithms in many fields, including number theory [1], database search
[2], and linear algebra [3]. One of the fields where quantum computing has
potential to offer substantial gains is machine learning. Quantum algorithms
for training machine learning models have expanded into an active field of
research [4, 5, 6, 7]. The study of quantum algorithms has also led to
discovery of more efficient classical methods [8, 9, 10, 11].

Quantum machine learning aims to provide quantum algorithms that can speed up
training of the machine learning models on large datasets. An early example of
this approach is Quantum Least-Squares Support Vector Machine (LS-SVM) [12],
which achieves exponential speedup compared to classical LS-SVM algorithm.
Quantum LS-SVM uses quadratic least-squares loss and squared-$L_{2}$
regularizer, and the optimization problem can be solved using the seminal HHL
[3] algorithm for solving quantum linear systems of equations. More recently,
a quantum training algorithm that solves a maximin problem resulting from a
maximum – not average – loss over the training set has been proposed [13]. A
sparse SVM method that uses quantum linear programming solvers and achieves
quadratic speedup for certain families of input problems has also been
introduced recently [14]. Most recently, a quantum algorithm that uses
efficient quantum approximations of inner products in the kernel space within
the SVM-perf frameworks has also been introduced [15], achieving complexity
linear in the number of samples. All these variants of quantum SVM are aimed
at supervised problems, where each training sample is accompanied by its true
class label. While progress has been made in quantum algorithms for supervised
learning, it has been recently advocated that the focus should shift to
unsupervised and semi-supervised setting [16].

In many domains, the most laborious part of assembling a training set is
collecting sample labels. Thus, in many scenarios, in addition to the labeled
training set, we have access to many more feature vectors with missing labels.
One way of utilizing these additional data points to improve the
classification model is through semi-supervised learning. In semi-supervised
learning, we are given $m$ observations $x_{1},...,x_{m}\in\mathcal{X}$ drawn
from the marginal distribution $p(x)$ over some input space $\mathcal{X}$. The
first $l$ ($l\ll m$) data points come with labels $y_{1},...,y_{l}$ drawn from
conditional distribution $p(y|x)$. Semi-supervised learning algorithms exploit
the underlying marginal distribution of the data, $p(x)$, estimated using both
labeled and unlabeled data points, to improve classification accuracy on
unseen samples.

Here, we introduce a quantum algorithm for semi-supervised training of a
kernel support vector machine classification model. We start with the existing
Quantum LS-SVM [12], and use techniques from sample-based Hamiltonian
simulation [17] to add a semi-supervised term based on Laplacian SVM [18]. As
is standard in quantum machine learning [13], the algorithm accesses training
points and the adjacency matrix of the graph connecting samples via a quantum
oracle. We show that, with respect to the oracle, the proposed algorithm
achieves the same quantum speedup as LS-SVM, that is, adding the semi-
supervised term does not lead to increased computational complexity.

##  2 Preliminaries

In this section, we setup the background that we need for describing quantum
semi-supervised algorithm. We first describe briefly the semi-supervised
kernel machines and show that training a semi-supervised LS-SVM problem can be
reformulated as a system of linear equations. Second, we describe the quantum
subroutines used in the Quantum LS-SVM [12], which minimizes quadratic loss
and quadratic regularizer
$\sum_{i=1}^{m}(y_{i}-\beta^{T}x_{i})^{2}+\lambda\lVert\beta\rVert_{2}^{2}$
over the training set $\left\\{(x_{i},y_{i})\right\\}$ and with standard
techniques can be re-written as a system of linear equations that can be
solved using quantum linear algebra approaches. Third, we describe the basic
quantum subroutines we utilize such as the HHL algorithm [3] and the LMR
protocol [19].

###  2.1 Semi-Supervised Kernel Machines

#### Reproducing Kernel Hilbert Spaces.

Binary classification models take the form of a function
$f:\mathcal{X}\rightarrow{\mathbb{R}}$. Consider functions from
$L_{2}(\mathcal{X})$, the space of all square-integrable functions
$\mathcal{X}\rightarrow{\mathbb{R}}$. In $L_{2}$, closeness in norm does not
imply everywhere pointwise closeness of two functions. Difference between
$f(x)$ and $g(x)$ can be arbitrary large for $x\in S\subset\mathcal{X}$ even
if $||f-g||_{\mathcal{H}}=0$, as long as $S$ has measure of zero.

One large class of functions that does not exhibit this problem is the
Reproducing Kernel Hilbert Space (RKHS) of functions. Its construction is
based on Dirac evaluation functionals in the following way. For a Hilbert
space $\mathcal{F}$ of functions $f:\mathcal{X}\rightarrow{\mathbb{R}}$,
consider a family of Dirac evaluation functionals $F$ consisting of mappings
$F_{t}:\mathcal{F}\rightarrow{\mathbb{R}}$ parameterized by a specific
argument $t\in\mathcal{X}$ and, for any $f\in\mathcal{F}$, returning the value
of $f$ evaluated at $t$; that is, ${F}_{t}[h]=f(t)$. Dirac evaluation
functionals with the same parameter $t$ are linear, that is, $\alpha
F_{t}[f]+\beta F_{t}[g]=F_{t}[\alpha f+\beta g]=\alpha f(t)+\beta g(t)$. Any
linear functional ${F}:\mathcal{F}\rightarrow{\mathbb{R}}$ is bounded if
$\exists M\in{\mathbb{R}}:{\;\;\;}\forall f\in\mathcal{F}{\;\;\;}|{F}[f]|\leq
M||f||_{\mathcal{H}}$. If in the space $\mathcal{F}$ all Dirac evaluation
functionals for all $t\in X$ are bounded, then, for any $f,g\in\mathcal{F}$,
small $||f-g||_{\mathcal{F}}$ implies small $|f(t)-g(t)|$, everywhere on $X$;
closeness of functions in norm implies pointwise closeness. Riesz
representation theorem guarantees that for each bounded evaluation functional
${F}_{t}$, there exists a unique function $K_{t}\in\mathcal{F}$ such that
${F}_{t}[h]=fh(t)=\langle K_{t},f\rangle_{\mathcal{F}}$. Function
$K_{t}:\mathcal{X}\rightarrow{\mathbb{R}}$ is called the representer of
$t\in\mathcal{X}$. Any space of functions in which every Dirac evaluation
operator ${F}_{t}$ is bounded, and thus has a corresponding representer
$K_{t}$, is called a Reproducing Kernel Hilbert Space.

In RKHS, by symmetry of inner product, $K_{t}(s)=\langle
K_{t},K_{s}\rangle_{\mathcal{F}}=K_{s}(t)$. We can thus define a function
$K:\mathcal{X}\times\mathcal{X}\rightarrow{\mathbb{R}}$ with values
$K(s,t)=K_{s}(t)$, such that $\forall x,y\in\mathcal{X}{\;\;\;}\exists
K_{x},K_{y}\in\mathcal{F}:{\;\;\;}\langle
K_{x},K_{y}\rangle_{\mathcal{F}}=K(x,y)$. Any symmetric and positive definite
function $K:\mathcal{X}\times\mathcal{X}\rightarrow{\mathbb{R}}$ (that is, a
function that fulfills the Mercer condition,
$\int_{\mathcal{X}}\int_{\mathcal{X}}c(x)K(x,y)c(y)dxdy\geq 0{\;\;\;}\forall
c\in\mathcal{F}$ ) is called a reproducing kernel. A reproducing kernel gives
rise to functions $K_{t}:\mathcal{X}\rightarrow{\mathbb{R}}$ defined by fixing
$t$ and defining $K_{t}(x)=K(t,x)$. Given the input space $\mathcal{X}$, we
can construct an inner product space that is an RKHS in the following way. The
RKHS space will consist of all possible finite linear combinations of
representers, that is, of all functions of the form
$f=\sum_{j=1}^{n}c_{j}K_{t_{j}}$ for some finite $n$, some representers
$\left\\{K_{t_{j}}\right\\}$ and some weights $\left\\{c_{j}\right\\}$, with
$j=1,...,n$. Given two functions $f=\sum_{j=1}^{n}c_{j}K_{t_{j}}$ and
$g=\sum_{i=1}^{n^{\prime}}c^{\prime}_{i}K_{t^{\prime}_{i}}$ for some finite
$n$ and $n^{\prime}$, representer sets $\left\\{K_{t_{j}}\right\\}$ and
$\left\\{K_{t^{\prime}_{i}}\right\\}$, and their linear combination weights
$\left\\{c_{j}\right\\}$ and $\left\\{c^{\prime}_{i}\right\\}$, the inner
product in RKHS is defined through the reproducing kernel $K$ as $\langle
f,g\rangle_{\mathcal{F}}=\sum_{j=1}^{n}\sum_{i=1}^{n^{\prime}}c_{j}c^{\prime}_{i}K(t_{j},t^{\prime}_{i})$.
The Moore-Aronszajn theorem states that the space defined this way can be
completed, the resulting RKHS space is unique, and $K$ is the reproducing
kernel in that space. Kernel method, including kernel SVM, involve functions
from RKHS as predictors $f(x)\rightarrow y$, and rely on expressing the inner
product via the reproducing kernel $\langle
K_{x},K_{y}\rangle_{\mathcal{F}}=K(x,y)$ to have the efficient way of working
with functions from RKHS.

#### Discrete-topology Gradients of Functions in RKHS.

Kernel methods including SVMs are regularized by penalizing for high local
variability of the predictor function $f$. This makes the predictions more
stable to small changes in input, and leads to improved generalization
capabilities of the trained classifier. A simple way of measuring local
variability of a function $\mathcal{X}\rightarrow{\mathbb{R}}$ is through its
gradient; for example, functions with Lipschitz-continuous gradient cannot
change too rapidly. In manifold learning [20], instead of or in addition to
analyzing gradient using the topology of $\mathcal{X}$, some other, more
relevant topology is used. In particular, in Laplacian SVM [18] and related
semi-supervised learning methods, a discrete topology of a graph $G$
connecting training points in $\mathcal{X}$ is used. In training semi-
supervised models, we assume that we have information on the similarity of the
training samples, in a form of a graph $G$ that uses $n$ edges to connect
similar training samples, represented as $m$ vertices. The graph includes
vertices with and without labels, providing a consistent view of the
underlying manifold on which all available samples lie. For each sample $i$,
by $d_{i}$ we denote the number of its neighbors in graph $G$, that is, the
degree of vertex $i$ is $d_{i}$. The graph connecting samples can be available
a priori, or can be constructed as a pre-processing step by adding an edge
between each vertex and its $d_{i}$ nearest neighbors, or connecting a vertex
to all neighbors with similarity above a user-defined threshold. In general,
degree in graph $G$ may differ for different vertices. Ultimately, in training
a semi-supervised classifier, we assume that the graph $G$ is given on input,
and it has all training samples, including those without class labels, as
vertices.

For a given undirected graph $G$ with a set of $m$ vertices, $V$, and a set of
$n$ edges, $E$, let us define a Hilbert space $\mathcal{F}_{V}$ of functions
$f:V\rightarrow{\mathbb{R}}$ with inner product $\langle
f,g\rangle_{{V}}=\sum_{v\in V}f(v)g(v)$, and a Hilbert space $\mathcal{F}_{E}$
of functions $\psi:E\rightarrow{\mathbb{R}}$ with inner product
$\langle\psi,\phi\rangle_{{E}}=\sum_{e\in E}\psi(e)\phi(e)=\sum_{u\sim
v}\psi([u,v])\phi([u,v])$, where $u\sim v$ represents an undirected edge
connecting vertices $u$ and $v$ in the input graph $G$. Given these two
spaces, we define a linear operator
$\nabla:\mathcal{F}_{V}\rightarrow\mathcal{F}_{E}$ such that

$\displaystyle\nabla f([u,v])=\sqrt{G_{u,v}}f(u)-\sqrt{G_{u,v}}f(v)=-\nabla
f([v,u]),$

where $G_{u,v}$ represents the weight of the edge $u\sim v$; in semi-
supervised learning explored here, all weights are uniform, $G_{u,v}=1$ for
any edge $u\sim v$. We set $G_{u,v}=0$ if $u$ and $v$ are not connected by an
edge.

The operator $\nabla$ can be seen as a discrete counterpart to the gradient of
a function – given a function $f$ with values for training samples or,
equivalently, the corresponding vertices, for a given sample/vertex $u$ in the
domain of $f$, $\nabla$ over different samples/vertices $v$ gives us a set of
values showing the change of $f$ over all directions from $u$, that is, all
edges incident to it. Based on the operator $\nabla$, we can define the
equivalent of divergence over the graph topology, a linear operator
$\mathrm{div}:\mathcal{F}_{E}\rightarrow\mathcal{F}_{V}$ such that
$-\mathrm{div}$ is the adjoint of $\nabla$, that is,
$\langle\nabla[f],\psi\rangle_{{E}}=\langle
f,-\mathrm{div}[\psi]\rangle_{{V}}$. Finally, we define graph Laplacian, a
linear operator $\Delta:\mathcal{F}_{V}\rightarrow\mathcal{F}_{V}$

$\displaystyle\Delta[f]$
$\displaystyle=-\frac{1}{2}\mathrm{div}[\nabla[f]]=D_{v}f(v)-\sum_{u\sim
v}G_{u,v}f(u).$

The graph Laplacian operator $\Delta$ is self-adjoint and positive semi-
definite, and the squared norm of the graph gradient can be captured through
it as

$\displaystyle\frac{1}{2}||\nabla f||^{2}_{E}$
$\displaystyle=\langle\Delta[f],f\rangle_{{V}}=\frac{1}{2}\sum_{u\sim
v}G_{u,v}(\bar{f}_{u}-\bar{f}_{v})^{2}=\bar{f}^{T}L\bar{f}.$

In the above definition, we used $\bar{f}$ to denote an $m$-dimensional vector
indexed by the graph vertices and consisting of values of $f$ for the samples
corresponding to the vertices; that is, $\bar{f}_{u}=f(u)$. Then, $\Delta[f]$
can be expressed as $\Delta[f]=L\bar{f}$, a multiplication of vector of
function values $\bar{f}$ by the combinatorial graph Laplacian matrix $L$ such
that ${L}[i,i]=D_{i}$ and ${L}[i,j]=-G_{i,j}$.

In semi-supervised learning, we use the norm $||\nabla f||^{2}_{E}$ as another
regularization factor. While the regularization factor $||f||^{2}$ used in the
regular SVM promotes smoothness of the predictive model $f$ in the original
topology, the additional Laplacian-based term promotes smoothness of $f$ over
the graph topology. Vertices that may be relatively close in the original
topology may be distant in terms of graph topology, providing for a more
appropriate regularization. Further, the graph topology is often better at
capturing the manifold on which the input samples reside [20]. The graph
Laplacian is based on the graph connecting the samples, and the degrees of the
vertices may span a wide range of value, for example if a similarity threshold
in the input space is used to define connectivity of samples and the density
of samples varies in the input space. Therefore, in practical usage, instead
of the combinatorial graph Laplacian, one often employs its degree-normalized
version, with ${L}[i,i]=1$ and ${L}[i,j]=-G_{i,j}/\sqrt{D_{i}D_{j}}$.

#### Semi-Supervised Least-Squares Kernel Support Vector Machines.

Our goal is to find predictors $f(x):\mathcal{X}\rightarrow{\mathbb{R}}$ that
are functions from a RKHS $\mathcal{F}$ defined by a kernel $K$. In Semi-
Supervised LS-SVMs in RKHS, we are looking for a function $f\in\mathcal{F}$
that minimizes

$\displaystyle\mathrm{argmin}_{f\in\mathcal{F}}\frac{\gamma}{2}\sum_{i=1}^{l}\left(y_{i}-f(x_{i})\right)^{2}+\frac{1}{2}||f||^{2}_{\mathcal{F}}+\frac{1}{2}||\nabla
f||^{2}_{E},$ (1)

where $l\leq m$ is the number of training points with labels (these are
grouped at the beginning of the training set of size $m$), and $\gamma$ is a
user-defined constant allowing for adjusting the regularization strength. The
first two terms are the same as in the standard LS-SVM – they include a least-
squares penalty for predictions, $\left(y_{i}f(x_{i})\right)^{2}$, and an
$L_{2}$ regularization of predictions in the kernel space,
$||f||^{2}_{\mathcal{F}}$. Compared to standard LS-SVM, the objective function
contains additional, third term: $||\nabla f||^{2}_{E}$; as indicated above,
this term corresponds to a quadratic term involving the graph Laplacian of a
graph connecting all available labeled and unlabeled samples. It promotes a
smoothness of the predictive function $f$ over the graph, that is, if promotes
solutions $f$ in which similar training samples $x$ and $x^{\prime}$ have
similar predictions $f(x)$ and $f(x^{\prime})$ if the two samples are
connected by an edge in the graph.

The Representer Theorem [21] states that if $\mathcal{F}$ is RKHS defined by
kernel $K:\mathcal{X}\times\mathcal{X}\rightarrow{\mathbb{R}}$, then the
solution minimizing the problem above is achieved for a function $f$ that uses
only the representers of the training points, that is, a function of the form
$f(x)=\sum_{{j}=1}^{m}\alpha_{j}K_{x_{j}}(x)=\sum_{{j}=1}^{m}\alpha_{j}K(x_{j},x)$;
there is nothing to be gained by utilizing representers of points not in the
training set. Here, coefficients $\alpha_{j}$ can assume arbitrary real
values; in some equivalent specifications of SVM, we alternatively see terms
$y_{j}\alpha_{j}$ instead, with $\alpha_{j}\geq 0$. Also, as advocated for
kernel SVMs [22], we do not use any offset term. By using the definitions from
the paragraphs above, we can translate the problem

$\displaystyle\mathrm{argmin}_{f\in\mathcal{F}}\frac{\gamma}{2}\sum_{i=1}^{l}\left(1-2y_{i}f(x_{i})+f(x_{i})^{2}\right)+\frac{1}{2}||f||^{2}_{\mathcal{F}}+\frac{1}{2}||\nabla
f||^{2}_{E}$

into a quadratic optimization problem over finite, real vectors ${\alpha}$

$\displaystyle\mathrm{argmin}_{\alpha}\sum_{i=1}^{l}\left(-\gamma
y_{i}\sum_{j=1}^{m}\alpha_{j}K[i,j]+\frac{\gamma}{2}\left(\sum_{j=1}^{m}\alpha_{j}K[i,j]\right)^{2}\right)+\frac{1}{2}{\alpha}^{T}K{\alpha}+\frac{1}{2}{\bar{f}}L{\bar{f}},$

where ${\bar{f}}$ is the vector of function $f$ values at all training points;
we have ${\bar{f}}=K{\alpha}$, or $f(x_{i})=\sum_{j=1}^{m}\alpha_{j}K[i,j]$,
since function $f$ is defined using representers $K_{{x_{i}}}$ of all training
points. The semi-supervised term, the squared norm of the graph gradient of
$f$, $1/2||\nabla
f||^{2}_{E}={\bar{f}}^{T}L{\bar{f}}={\alpha}^{T}KLK{\alpha}$, penalizes large
changes of function $f$ over edges of graph $G$. In defining the kernel $K$
and the Laplacian $L$ and in the two regularization terms, we use all $m$
samples. On the other hand, in calculating the empirical quadratic loss, we
only use the first $l$ samples.

To simplify notation, we introduce $y_{i}=0$ for the samples that lack labels,
that is, for $l<i\leq m$, leading to $m$-dimensional vector ${y}$. The
quadratic problem can then be equivalently expressed in matrix form as

$\displaystyle\mathrm{argmin}_{\alpha}-\gamma{\alpha}^{T}K{y}+\frac{\gamma}{2}{\alpha}^{T}K^{T}K{\alpha}+\frac{1}{2}{\alpha}^{T}K{\alpha}+\frac{1}{2}{\alpha}^{T}KLK{\alpha}.$

Since matrices $K$ and $L$ involved in this quadratic problem are positive
semidefinite, the problem is convex, and the minimum can be obtained by
equating the gradient to null, that is, by solving the following system of
linear equations

$\displaystyle\frac{1}{\gamma}K{\alpha}+KK{\alpha}+\frac{1}{\gamma}KLK{\alpha}=K{y},$
(2)

where ${y}=(y_{1},...,y_{m})^{T}$, $K$ is an $m\times m$ kernel matrix, $L$ is
the an $m\times m$ graph Laplacian matrix, $\gamma$ is a hyperparameter and
${\alpha}=(\alpha_{1},...,\alpha_{m})^{T}$ is the unknown vector of sample
weights in the kernel SVM.

###  2.2 Quantum Computing and Quantum LS-SVM

#### Quantum Linear Systems of Equations.

Given an input matrix $A\in{\mathbb{C}}^{m\times m}$ and a vector
$b\in{\mathbb{C}}^{m}$, the goal of linear system of equations problem is
finding $x\in{\mathbb{C}}^{m}$ such that $Ax=b$. When $A$ is Hermitian and
full rank, the unique solution is $x=A^{-1}b$. If $A$ is not a full rank
matrix then $A^{-1}$ is replaced by the Moore-Penrose pseudo-inverse. HHL
algorithm introduced an analogous problem in quantum setting: assuming an
efficient algorithm for preparing $b$ as a quantum state
$b=\sum_{i=1}^{m}b_{i}\ket{i}$ using $\lceil\log m\rceil+1$ qubits, the
algorithm applies quantum subroutines of phase estimation, controlled
rotation, and inverse of phase estimation to obtain the state

$\ket{x}=\frac{A^{-1}\ket{b}}{\left\|\,A^{-1}\ket{b}\,\right\|}.$

Intuitively, HHL algorithm works as follows: if $A$ has spectral decomposition
$A=\sum_{i=1}^{m}\lambda_{i}v_{i}v_{i}^{T}$ (where $\lambda_{i}$ and $v_{i}$
are corresponding eigenvalues and eigenstates of $A$), then $A^{-1}$ maps
$\lambda_{i}v_{i}\mapsto\dfrac{1}{\lambda_{i}}v_{i}$. The vector $b$ also can
be written as the linear combination of the $A$’s eigenvectors $v_{i}$ as
$b=\sum_{i=1}^{m}\beta_{i}v_{i}$ (we are not required to compute $\beta_{i}$).
Then $A^{-1}b=\sum_{i=1}^{m}\beta_{i}\dfrac{1}{\lambda_{i}}v_{i}$. In general
$A$ and $A^{-1}$ are not unitary (unless all $A$’s eigenvalues have unit
magnitude), therefore we are not able to apply $A^{-1}$ directly on $\ket{b}$.
However, since $U=e^{iA}=\sum_{i=1}^{m}e^{i\lambda_{i}}v_{i}v_{i}^{T}$ is
unitary and has the same eigenvectors as $A$ and $A^{-1}$, one can implement
$U$ and powers of $U$ on a quantum computer by Hamiltonian simulation
techniques; clearly for any expected speed-up, one need to enact $e^{iA}$
efficiently. The HHL algorithm uses the phase estimation subroutine to
estimate an approximation of $\lambda_{i}$ up to a small error. The next step
computes a conditional rotation on the approximated value of $\lambda_{i}$ and
an auxiliary qubit $\ket{0}$ and outputs
$\dfrac{1}{\lambda_{i}}\ket{0}+\sqrt{1-\dfrac{1}{\lambda_{i}^{2}}}\ket{1}$.
The last step involves the inverse of phase estimation and quantum measurement
for eliminating of garbage qubits and for returning the desired state
$\ket{x}=A^{-1}\ket{b}=\sum_{i=1}^{m}\beta_{i}\dfrac{1}{\lambda_{i}}v_{i}$.
The conditional rotation can be also implemented in a manner that does not
result in the inverse of the eignevalues [23], to produce
$\lambda_{i}\ket{0}+\sqrt{1-\lambda_{i}^{2}}\ket{1}$, leading to quantum
matrix multiplication, $\ket{x}=\frac{A\ket{b}}{\left\|\,A\ket{b}\,\right\|}$.

#### Quantum Estimation of the Kernel Matrix.

Quantum LS-SVM uses density operator formalism and partial trace to represent
the computation involving the kernel matrix. Given $m$ training samples, to
obtain the corresponding $m\times m$ kernel matrix as a density matrix,
quantum LS-SVM [12] relies on partial trace, and on a quantum oracle that can
convert, in superposition, each data point $\\{x_{i}\\}_{i=1}^{m}$,
$x_{i}\in\mathbb{R}^{p}$ to a quantum state
$\ket{x_{i}}=\frac{1}{\left\|\,x_{i}\,\right\|}\sum_{k=1}^{p}(x_{i})_{k}\ket{k}$,
where $(x_{i})_{k}$ refers to the $k$-th feature value in data point $x_{i}$
and assuming the oracle is given $\left\|\,x_{i}\,\right\|$ and $y_{i}$.
Vector of the labels is given in the same fashion as
$\ket{y}=\frac{1}{\left\|\,y\,\right\|}\sum_{i=1}^{m}y_{i}\ket{i}$. For
preparation the normalized kernel matrix
$K^{\prime}=\frac{1}{\operatorname{tr}(K)}K$ where $K=X^{T}X$, we need to
prepare a quantum state combining all data points in quantum superposition
$\ket{X}=\frac{1}{\sqrt{\sum_{i=1}^{m}\left\|\,x_{i}\,\right\|^{2}}}\sum_{i=1}^{m}\ket{i}\otimes\left\|\,x_{i}\,\right\|\ket{x_{i}}$.
The normalized Kernel matrix is obtained by discarding the training set part
of the quantum system,

$\begin{split}K^{\prime}&=\operatorname{Tr}_{2}(\ket{X}\bra{X})=\frac{1}{\sum_{i=1}^{m}\left\|\,x_{i}\,\right\|^{2}}\sum_{i,j=1}^{m}\left\|\,x_{i}\,\right\|\left\|\,x_{j}\,\right\|\braket{x_{i}}{x_{j}}\ket{i}\bra{j}.\end{split}$
(3)

The approach used above to construct density matrix corresponding to linear
kernel matrix can be extended to polynomial kernels [12].

#### LMR Protocol for Density Operator Exponentiation.

In HHL-based quantum machine learning algorithms that involve matrix inversion
or matrix multiplication, including in the method proposed here, matrix $A$
for the Hamiltonian simulation within the HHL algorithm is based on data. For
example, $A$ can contain the kernel matrix $K$ captured in the quantum system
as a density matrix. Then, one needs to be able to efficiently compute
$e^{-iK\Delta t}$, where $K$ is scaled by the trace of kernel matrix. Since
$K$ is not sparse, the LMR protocol [19] for the exponentiation of a non-
sparse density matrix is used instead. The protocol involves simulation with a
sparse operator $S$ to simulate the application of $e^{-iK\Delta t}$ to a
state $\sigma$ in the following way:

$\operatorname{Tr}_{1}\left\\{e^{-iS\Delta t}(K\otimes\sigma)e^{iS\Delta
t}\right\\}=\sigma-i\Delta t[K,\sigma]+O\left(\Delta t^{2}\right)\approx
e^{-iK\Delta t}\sigma e^{iK\Delta t}.$ (4)

The operator $S=\sum_{i,j}\ket{i}\bra{j}\otimes\ket{j}\bra{i}$ is the swap
operator. The procedure relies on
$\operatorname{Tr}_{1}\left\\{S(K\otimes\sigma)\right\\}=K\sigma$ and
$\operatorname{Tr}_{1}\left\\{(K\otimes\sigma)S\right\\}=\sigma K$. The
equation (4) summarizes the LMR protocol: approximating $e^{-iK\Delta t}\sigma
e^{iK\Delta t}$ up to error $O(\Delta t^{2})$ is equivalent to simulating a
swap operator $S$, applying it to the state $K\otimes\sigma$ and discarding
the first system by taking partial trace operation. Since the swap operator is
sparse, its simulation is efficient. Therefore the LMR protocol provides an
efficient way to approximate exponentiation of a non-sparse density matrix and
can be readily used in HHL-based algorithms.

#### Quantum LS-SVM.

Quantum LS-SVM [12] uses partial trace to construct density operator
corresponding to the kernel matrix $K$, as described above. Once the kernel
matrix $K$ becomes available as a density operator, it proceeds by applying
the HHL algorithm for solving the system of linear equations associated with
LS-LSVM, using the LMR protocol described above for performing the density
operator exponentiation $e^{-iK\Delta t}$.

##  3 Quantum Semi-Supervised Least Square SVM

We proposed here a quantum algorithm for solving Semi-Supervised Least-
Squares SVM. As mentioned in Section 2.1, semi-supervised LS-SVM involves
solving the following system of linear equations

$\displaystyle\left(\frac{1}{\gamma}K+KK+\frac{1}{\gamma}KLK\right){\alpha}=K{y}.$

In quantum setting the task is to generate
$\ket{\boldsymbol{\alpha}}=\hat{A}^{-1}\ket{\textbf{Ky}}$, where the
normalized $\hat{A}=\dfrac{A}{Tr(A)}$ for
$A=\frac{1}{\gamma}K+KK+\frac{1}{\gamma}KLK$. The linear system differs from
the one in LS-SVM, $(\gamma^{-1}K+KK)\alpha=Ky$ or simply
$(K+\gamma^{-1}I)\alpha=y$. We have additional $KLK$ term in the matrix to be
inverted, and instead of the input vector of labels ${y}$, we have the vector
$K{y}$. While this difference is of little significance for classical solvers,
in quantum systems we cannot just multiply matrices and then apply quantum LS-
SVM – we are limited by the unitary nature of quantum transformations.

In order to obtain the solution to the quantum Semi-Supervised Least Square
SVM, we will use the following steps. First, as shown in Section 3.1, we will
read in the graph information to obtain normalized graph Laplacian matrix in a
quantum form as a density matrix $L$. We will also read in the kernel matrix
as a density matrix, as described above. Given $K$, we will perform matrix
multiplication $K{y}$, using the variant of HHL and LMR protocol for matrix
multiplication [23] described above. Finally, as shown in Section 3.2, we will
use polynomial Hermitian exponentiation for performing the matrix inverse
$(K+KK+KLK)^{-1}$, as described below.

###  3.1 Quantum Input Model for the Graph Laplacian

Semi-supervised learning assumes that in addition to the training set, we have
access to a graph $G$ connecting the $m$ training samples using $n$ edges. The
connectivity structure of the graph captures the similarity of the samples,
represented as vertices in the graph – for example, each sample has an edge to
$d$ samples most similar to it for some small $d$, often being chosen as a
small fraction of the training size, $n$. More generally, the degrees of the
vertices in the graph may differ, with each vertex $i$ having being connected
to $d_{i}$ other vertices. We assume that the graph is given as a graph
adjacency lists data structure that can be accessed, in superposition, to
create states corresponding to rows of the degree-normalized graph incidence
matrix $G_{I}$, an $m\times n$, vertices-by-edges matrix. For an edge $e$
connecting vertices $i$ and $j$, with $i<j$, the incidence matrix will have
entry $G_{I}[i,e]=-1/d_{i}$ and $G_{I}[j,e]=1/d_{j}$; we have $G_{I}[k,e]=0$
if edge $e$ does not involve vertex $k$.

To have the graph available as a quantum density matrix for the quantum Semi-
Supervised SVM, we observe that the normalized graph Laplacian $L$ is the Gram
matrix of the rows of the $m\times n$ normalized graph incidence matrix
$G_{I}$, that is, $L=G_{I}G_{I}^{T}$. Using oracle access to the graph, we can
construct states $\ket{v_{i}}$ corresponding to rows of the graph incidence
matrix $G_{I}$ for vertices $i$, $i=1,...,m$

$\displaystyle\ket{v_{i}}=\frac{1}{\sqrt{d_{i}}}\sum_{e=1}^{n}G_{I}[i,e]\ket{e}.$

That is, state $\ket{v_{i}}$ has probability amplitude
$\frac{1}{\sqrt{d_{i}}}$ for each edge $e$, identified as $\ket{e}$, that is
incident with vertex $i$, and null probability amplitude for all other edges
in the graph.

Based on the oracle that can construct individual rows of the incidence
matrix, in superposition, we prepare a quantum state $\ket{G_{I}}$ that
encodes all rows of the incidence matrix $G_{I}$ by preparing $\ket{v_{i}}$
states for all vertices in the graph

$\displaystyle\ket{G_{I}}=\frac{1}{\sqrt{m}}\sum_{i=1}^{m}\ket{i}\otimes\ket{v_{i}}=\frac{1}{\sqrt{m}}\sum_{i=1}^{m}\frac{1}{\sqrt{d_{i}}}\sum_{t=1}^{n}G_{I}[i,t]\ket{i}\otimes\ket{t}.$

The normalized graph Laplacian matrix $L=G_{I}G_{I}^{T}$, composed of inner
products of the rows of $G_{I}$, is obtained in a form a density matrix by
discarding the second part of the quantum system

$\begin{split}L&=Tr_{2}(\ket{G_{I}}\bra{G_{I}})=\frac{1}{m}\sum_{i,j=1}^{m}\ket{i}\bra{j}\otimes\frac{1}{\sqrt{d_{i}d_{j}}}\braket{v_{i}}{v_{j}}=\frac{1}{m}\sum_{i,j=1}^{m}\frac{1}{\sqrt{d_{i}d_{j}}}\braket{v_{i}}{v_{j}}\ket{i}\bra{j}.\end{split}$
(5)

The density matrix $L$, representing the Laplacian, will be used together with
density matrix $K$, representing the kernel matrix, in the quantum method for
training the Semi-Supervised SVM.

###  3.2 Polynomial Hermitian Exponentiation for Semi-Supervised Learning

In quantum Semi-Supervised SVM, for computing the matrix inverse
$(\gamma^{-1}K+KK+\gamma^{-1}KLK)^{-1}$ via the HHL subroutine, we need to be
able to efficiently compute $e^{-i(\gamma^{-1}K+KK+\gamma^{-1}KLK)\Delta
t}\sigma e^{i(\gamma^{-1}K+KK+\gamma^{-1}KLK)\Delta t}$ given the ability to
construct matrices $K$ and $L$ as quantum density matrices. For this purpose
we adapt the Generalized LMR protocol for simulating Hermitian polynomials
proposed in [17] to the specific case of Semi-Supervised SVM. For clarity, we
first focus on simulation of $e^{-iKLK\Delta t}$; the other two terms, $K$ and
$KK$, are also Hermitian polynomials and can be seen as special cases. Then,
we discuss how the final dynamics involving the three-term sum
$\gamma^{-1}K+KK+\gamma^{-1}KLK$ can be obtained by creating a mixed state
density corresponding to the sum of the three terms through sampling.

#### Simulating $\boldsymbol{e^{iKLK\Delta t}}$.

Let $D(\mathcal{H})$ denote the space of density operators associated with
state space $\mathcal{H}$. Let $K^{\dagger},K,L\in D(\mathcal{H})$ be the
density operators associated with the kernel matrix and the graph Laplacian,
respectively. We will need two separate systems with the kernel matrix $K$; to
distinguish between them we will denote the first as $K^{\dagger}$ and the
second as $K$; since $K$ is real and symmetric, these are indeed equal. The
kernel and Laplacian matrices $K^{\dagger},K,L$ are not sparse therefore we
adapt the Generalized LMR technique for simulating Hermitian polynomials for
the specific case $B=K^{\dagger}LK$.

For adapting the Generalized LMR technique to our problem, we need to be able
to generate a quantum state
$\rho^{\prime}=\ket{0}\bra{0}\otimes\rho^{\prime\prime}\mkern-1.2mu+\ket{1}\bra{1}\otimes\rho^{\prime\prime\prime}\mkern-1.2mu$
with
$Tr(\rho^{\prime\prime}\mkern-1.2mu+\rho^{\prime\prime\prime}\mkern-1.2mu)=1$,
such that

$\begin{split}\operatorname{Tr}_{1}\left\\{\operatorname{Tr}_{3}\left\\{e^{-iS^{\prime}\Delta}\left(\rho^{\prime}\otimes\sigma\right)e^{iS^{\prime}\Delta}\right\\}\right\\}=\sigma-i[B,\sigma]+O(\Delta^{2})=e^{-iBt}\sigma
e^{iBt}+O(\Delta^{2}),\ \end{split}$ (6)

where
$B=\rho^{\prime\prime}\mkern-1.2mu-\rho^{\prime\prime\prime}\mkern-1.2mu=\frac{1}{2}K^{\dagger}LK+\frac{1}{2}KLK^{\dagger}=KLK$,
and where $S^{\prime}:=\ket{0}\bra{0}\otimes S+\ket{1}\bra{1}\otimes(-S)$ is a
controlled partial swap in the forward $(+S)$ and backward direction $(-S)$ in
time. We have

$e^{-iS^{\prime}\Delta}=\ket{0}\bra{0}\otimes
e^{-iS\Delta}+\ket{1}\bra{1}\otimes e^{iS\Delta}.$

Therefore, with one copy of $\rho^{\prime}$, we obtain the simulation of
$e^{-iB\Delta}$ up to error $O(\Delta^{2})$. If we choose the time slice
$\Delta=\delta/t$ and repeat the above procedure for $t^{2}/\delta$ times, we
are able to simulate $e^{-iBt}$ up to error $O(\delta)$ using
$n=O(t^{2}/\delta)$ copies of $\rho^{\prime}$.

#### Generating
$\boldsymbol{\rho^{\prime}=\ket{0}\bra{0}\otimes\rho^{\prime\prime}\mkern-1.2mu+\ket{1}\bra{1}\otimes\rho^{\prime\prime\prime}\mkern-1.2mu}$.

Figure 1 shows the quantum circuit for creating
$\rho^{\prime}=\ket{0}\bra{0}\otimes\rho^{\prime\prime}\mkern-1.2mu+\ket{1}\bra{1}\otimes\rho^{\prime\prime\prime}\mkern-1.2mu$
such that
$Tr(\rho^{\prime\prime}\mkern-1.2mu+\rho^{\prime\prime\prime}\mkern-1.2mu)=1$
and
$B=\rho^{\prime\prime}\mkern-1.2mu-\rho^{\prime\prime\prime}\mkern-1.2mu=KLK$.

Figure 1:  Quantum circuit for creating
$\rho^{\prime}=\ket{0}\bra{0}\otimes\rho^{\prime\prime}\mkern-1.2mu+\ket{1}\bra{1}\otimes\rho^{\prime\prime\prime}\mkern-1.2mu$
by utilizing the Generalized LMR protocol [17] for density matrices
representing the SVM kernel matrix $K$ and the graph Laplacian $L$. The
circuit is to be read from left-to-right. Each wire at left shows its
corresponding input state. The vertical rectangle denotes the cyclic
permutation operator $\operatorname{P}$ on $K,L,K$ defined in (7). H is the
Hadamard gate, and the waste bins show partial trace. The measurement on the
first quantum state is in computational basis.

The analysis of the steps preformed by the circuit depicted in Fig.1 adapts
the Generalized LMR protocol to the Semi-Supervised SVM problem. Let
$\operatorname{P}$ be the cyclic permutation of three copies of
$\mathcal{H_{A}}$ that operates as
$\operatorname{P}\ket{j_{1},j_{2},j_{3}}=\ket{j_{3},j_{1},j_{2}}$. In operator
form it can be written as

$\operatorname{P}:=\sum_{j_{1},j_{2},j_{3}=1}^{\operatorname{dim}\mathcal{H}_{\mathrm{A}}}\left|j_{3}\right\rangle\left\langle
j_{1}|\otimes|j_{1}\right\rangle\left\langle
j_{2}|\otimes|j_{2}\right\rangle\left\langle j_{3}\right.|$ (7)

The input state to the circuit depicted in Fig. 1 is

$\ket{+}\bra{+}\otimes K^{\dagger}\otimes L\otimes
K=\dfrac{1}{2}\sum_{i,j\in\\{0,1\\}}\ket{i}\bra{j}\otimes K^{\dagger}\otimes
L\otimes K.$

Applying $\operatorname{P}$ on $K^{\dagger},L,K$ gives

$\begin{split}I&=\frac{1}{2}[\ket{0}\bra{0}\otimes K^{\dagger}\otimes L\otimes
K+\ket{0}\bra{1}\otimes\left(K^{\dagger}\otimes L\otimes
K\right)\operatorname{P}\\\
&+\ket{1}\bra{0}\otimes\operatorname{P}\left(K^{\dagger}\otimes L\otimes
K\right)+\ket{1}\bra{1}\otimes\operatorname{P}\left(K^{\dagger}\otimes
L\otimes K\right)\operatorname{P}.\end{split}$

After discarding the third and second register sequentially by applying
corresponding partial trace operators, we get

$\begin{split}II=\operatorname{Tr}_{2}\left[\operatorname{Tr}_{3}(I)\right]&=\ket{0}\bra{0}\otimes\frac{1}{2}K^{\dagger}+\ket{0}\bra{1}\otimes\frac{1}{2}K^{\dagger}LK\\\
&+\ket{1}\bra{0}\otimes\frac{1}{2}KLK^{\dagger}+\ket{1}\bra{1}\otimes\frac{1}{2}K,\end{split}$

in this step $KLK$ term where the last line obtained from

$\operatorname{Tr}_{2}\left[\operatorname{Tr}_{3}\left[\left(K^{\dagger}\otimes
L\otimes K\right)\operatorname{P}\right]\right]=K^{\dagger}LK,$
$\operatorname{Tr}_{2}\left[\operatorname{Tr}_{3}\left[\operatorname{P}(K^{\dagger}\otimes
L\otimes K)\right]\right]=KLK^{\dagger},$
$\operatorname{Tr}_{2}\left[\operatorname{Tr}_{3}\left[\operatorname{P}(K^{\dagger}\otimes
L\otimes K)\operatorname{P}\right]\right]=K.$

After applying a Hadamard gate
$H=\frac{1}{\sqrt{2}}[(|0\rangle+|1\rangle)\langle
0|+(|0\rangle-|1\rangle)\langle 1|]$ on the first qubit of $II$, we get

$\begin{split}III=H\otimes\mathds{1}(II)H\otimes\mathds{1}&=\frac{1}{2}\left(\ket{0}\bra{0}+\ket{0}\bra{1}+\ket{1}\bra{0}+\ket{1}\bra{1}\right)\otimes\frac{1}{2}K^{\dagger}\\\
&+\frac{1}{2}\left(\ket{0}\bra{0}-\ket{0}\bra{1}+\ket{1}\bra{0}-\ket{1}\bra{1}\right)\otimes\frac{1}{2}K^{\dagger}LK\\\
&+\frac{1}{2}\left(\ket{0}\bra{0}+\ket{0}\bra{1}-\ket{1}\bra{0}-\ket{1}\bra{1}\right)\otimes\frac{1}{2}KLK^{\dagger}\\\
&+\frac{1}{2}\left(\ket{0}\bra{0}-\ket{0}\bra{1}-\ket{1}\bra{0}+\ket{1}\bra{1}\right)\otimes\frac{1}{2}K\\\
&=\ket{0}\bra{0}\otimes\frac{1}{2}\left(\frac{1}{2}K^{\dagger}+\frac{1}{2}K^{\dagger}LK+\frac{1}{2}KLK^{\dagger}+\frac{1}{2}K\right)\\\
&+\ket{0}\bra{1}\otimes\frac{1}{2}\left(\frac{1}{2}K^{\dagger}-\frac{1}{2}K^{\dagger}LK+\frac{1}{2}KLK^{\dagger}-\frac{1}{2}K\right)\\\
&+\ket{1}\bra{0}\otimes\frac{1}{2}\left(\frac{1}{2}K^{\dagger}+\frac{1}{2}K^{\dagger}LK-\frac{1}{2}KLK^{\dagger}-\frac{1}{2}K\right)\\\
&+\ket{1}\bra{1}\otimes\frac{1}{2}\left(\frac{1}{2}K^{\dagger}-\frac{1}{2}K^{\dagger}LK-\frac{1}{2}KLK^{\dagger}+\frac{1}{2}K\right).\end{split}$

The last step is applying a measurement in computational basis
$\\{\ket{0}\bra{0},\ket{1}\bra{1}\\}$ on the first register to obtain our
desired state $\rho^{\prime}$,

$\begin{split}IV&=\ket{0}\bra{0}\otimes\frac{1}{2}\left(\frac{1}{2}K^{\dagger}+\frac{1}{2}K^{\dagger}LK+\frac{1}{2}KLK^{\dagger}+\frac{1}{2}K\right)\\\
&+\ket{1}\bra{1}\otimes\frac{1}{2}\left(\frac{1}{2}K^{\dagger}-\frac{1}{2}K^{\dagger}LK-\frac{1}{2}KLK^{\dagger}+\frac{1}{2}K\right)\end{split}$

We can see that by defining
$\rho^{\prime\prime}\mkern-1.2mu=\frac{1}{2}\left(\frac{1}{2}K^{\dagger}+\frac{1}{2}K^{\dagger}LK+\frac{1}{2}KLK^{\dagger}+\frac{1}{2}K\right)$
and
$\rho^{\prime\prime\prime}\mkern-1.2mu=\frac{1}{2}\left(\frac{1}{2}K^{\dagger}-\frac{1}{2}K^{\dagger}LK-\frac{1}{2}KLK^{\dagger}+\frac{1}{2}K\right)$
the final state is in the form of
$\rho^{\prime}=\ket{0}\bra{0}\otimes\rho^{\prime\prime}\mkern-1.2mu+\ket{1}\bra{1}\otimes\rho^{\prime\prime\prime}\mkern-1.2mu$
where
$Tr(\rho^{\prime\prime}\mkern-1.2mu+\rho^{\prime\prime\prime}\mkern-1.2mu)=1$,
and we obtain
$\rho^{\prime\prime}\mkern-1.2mu-\rho^{\prime\prime\prime}\mkern-1.2mu=\frac{1}{2}K^{\dagger}LK+\frac{1}{2}KLK^{\dagger}=B$.

Now with having the output state $\rho^{\prime}$ we are ready to apply the
generalized LMR in (6) to simulate $e^{-iKLK\Delta t}\sigma e^{iKLK\Delta t}$
up to error $O(\Delta^{2})$. Comparing the LMR technique in equation (4) with
the generalized LMR for the special case of $KLK$ in equation (6), we see
approximating $e^{-iKLK\Delta t}\sigma e^{iKLK\Delta t}$ up to error $O(\Delta
t^{2})$ is equivalent to simulating the controlled partial swap operator
$S^{\prime}$, applying it to the state $\rho^{\prime}\otimes\sigma$ and
discarding the third and first systems by taking partial trace operations,
respectively. Since $S^{\prime}$ is also sparse, and its simulation is
efficient, the generalized LMR technique offers an efficient approach for
simulating $e^{iKLK\Delta t}$.

#### Simulating joint evolution involving $K$, $KK$, and $KLK$.

Simulation involving a sum $\gamma^{-1}K+KK+\gamma^{-1}KLK$ can be obtained,
in the generalized LMR protocol, by creating a mixed state
$\rho^{\prime}_{joint}=\ket{0}\bra{0}\otimes\rho^{\prime\prime}\mkern-1.2mu_{joint}+\ket{1}\bra{1}\otimes\rho^{\prime\prime\prime}\mkern-1.2mu_{joint}$
such that
$\rho^{\prime\prime}\mkern-1.2mu_{joint}-\rho^{\prime\prime\prime}\mkern-1.2mu_{joint}=\gamma^{-1}K+KK+\gamma^{-1}KLK$,
with equality up to normalization of the term coefficients. As describe above
for the case of $KLK$ term alone, ability to construct copies of this state
translates to the ability of simulating the Hermite polynomial.

To extend the process beyond just the $KLK$ term, in addition to
$\rho^{\prime\prime}\mkern-1.2mu_{KLK}=\rho^{\prime\prime}\mkern-1.2mu$ and
$\rho^{\prime\prime\prime}\mkern-1.2mu_{KLK}=\rho^{\prime\prime\prime}\mkern-1.2mu$
leading to
$\rho^{\prime}_{KLK}=\ket{0}\bra{0}\otimes\rho^{\prime\prime}\mkern-1.2mu_{KLK}+\ket{1}\bra{1}\otimes\rho^{\prime\prime\prime}\mkern-1.2mu_{KLK}$
construction shown above, we need to be able to construct copies of the state
$\rho^{\prime}_{KK}=\ket{0}\bra{0}\otimes\rho^{\prime\prime}\mkern-1.2mu_{KK}+\ket{1}\bra{1}\otimes\rho^{\prime\prime\prime}\mkern-1.2mu_{KK}$
involving pairs of densities $\rho^{\prime\prime}\mkern-1.2mu_{KK}$,
$\rho^{\prime\prime\prime}\mkern-1.2mu_{KK}$, and copies of
$\rho^{\prime}_{K}=\ket{0}\bra{0}\otimes\rho^{\prime\prime}\mkern-1.2mu_{K}+\ket{1}\bra{1}\otimes\rho^{\prime\prime\prime}\mkern-1.2mu_{K}$
involving $\rho^{\prime\prime}\mkern-1.2mu_{K}$,
$\rho^{\prime\prime\prime}\mkern-1.2mu_{K}$; these states can be constructed
in a similar fashion as described above for $KLK$.

In simulating the evolution $e^{-i(\gamma^{-1}K+KK+\gamma^{-1}KLK)\Delta
t}\sigma e^{i(\gamma^{-1}K+KK+\gamma^{-1}KLK)\Delta t}$, which involves
constructing and using multiple copies of state $\rho^{\prime}_{joint}$, the
generalized LMR protocol uses individual states corresponding
$\rho^{\prime}_{K}$, $\rho^{\prime}_{KK}$, and $\rho^{\prime}_{KLK}$ with
probabilities given by the coefficients of the three terms,
$\frac{1}{\gamma}$, 1, $\frac{1}{\gamma}$, respectively. This probabilistic
process is then equivalent to using a single mixed state
$\rho^{\prime}_{joint}$.

###  3.3 Classification using a Trained Quantum Model

The result of the procedure for training a quantum semi-supervised LS-SVM is a
quantum state

$\ket{{\alpha}}=\frac{1}{\sqrt{\sum_{j=1}^{m}\alpha_{j}^{2}}}\left(\sum_{j=1}^{m}\alpha_{j}\ket{j}\right),$
(8)

representing the normalized solution vector $\alpha$. Unlike in classical
semi-supervised kernel SVM, $\alpha$ is not readily accessible. In the quantum
setting, we can follow the swap test-based approache proposed for quantum LS-
SVM [12]. We first construct a query state based on new data point
$\ket{{x_{new}}}$

$\ket{{x_{q}}}=\frac{1}{\sqrt{m\left\|\,\ket{{x_{new}}}\,\right\|^{2}+1}}\left(\sum_{j=1}^{m}\ket{j}\otimes\left\|\,\ket{{x_{new}}}\,\right\|\ket{{x_{new}}}\right).$
(9)

Then, based on the ability to construct $\ket{{\alpha}}$ and oracle access to
the training data, we construct the following state

$\ket{{s}}=\frac{1}{\sqrt{\sum_{j=1}^{m}\alpha_{j}^{2}\left\|\,{x_{j}}\,\right\|^{2}}}\left(\sum_{j=1}^{m}\alpha_{j}\ket{j}\otimes\left\|\,\ket{{x_{j}}}\,\right\|\ket{{x_{j}}}\right).$
(10)

Similarly to classical setting, where class prediction is performed via inner
products between the new samples and the training samples, we can utilize sign
of the inner product the states $\ket{{x_{q}}}$ and $\ket{{s}}$ for obtaining
the class of the new data point ${x_{new}}$

$y_{{x_{new}}}=\mathrm{sign}(\braket{{x_{q}}}{{s}})=\mathrm{sign}\left(C\left(\sum_{j=1}^{m}\alpha_{j}\left\|\,\ket{{x_{new}}}\,\right\|\left\|\,\ket{{x_{j}}}\,\right\|\braket{{x_{new}}}{{x_{j}}}\right)\right),$
(11)

where
$C=1/{\sqrt{(m\left\|\,\ket{{x_{new}}}\,\right\|^{2}+1)(\sum_{j=1}^{m}\alpha_{j}^{2}\left\|\,{x_{j}}\,\right\|^{2})}}$.
For implementing (11) on a quantum computer, we perform a procedure similar to
swap test [12]. Given two quantum states $\ket{\psi}$ and $\ket{\phi}$, the
swap test is a quantum operation that measures the overlap between the two
states. For this aim, using an ancilla qubit, we construct
$\ket{\psi}=\frac{1}{\sqrt{2}}\left(\ket{0}\ket{{s}}+\ket{1}\ket{{x_{q}}}\right)$.
Next, we apply Hadamard gate on the first qubit (the ancilla) of $\ket{\psi}$.
We repeat the process multiple times and quantify the probability of
successfully measuring the ancilla in the state
$\ket{-}=\frac{1}{\sqrt{2}}(\ket{0}-\ket{1})$; the success probability is
$P=\dfrac{1}{2}(1-\braket{{x_{q}}}{{s}})$ and can be approximated up to
$\epsilon$ error with $O(P(1-P)/\epsilon^{2})$ tries. Once $P$ is estimated,
it allows for predicting the class, since $P=\frac{1}{2}$ is the threshold
separating positive from negative prediction.

Algorithm 1 Quantum Semi-Supervised LS-SVM

1:The datapoint set $\\{x_{1},...x_{l},...x_{m}\\}$ with the first $l$ data
points labeled and the rest unlabeled, $\textbf{y}=(y_{1},...,y_{l})$ and the
graph $G$

2:The classifier $\ket{\alpha}=A^{-1}\ket{y}$

3:Quantum data preparation. Encode classical data points into quantum data
points using quantum oracles
$O_{x}:\\{x_{1},...x_{l},...x_{m}\\}\mapsto\ket{X}=\frac{1}{\sqrt{\sum_{i=1}^{m}\left\|\,x_{i}\,\right\|^{2}}}\sum_{i=1}^{m}\ket{i}\otimes\left\|\,x_{i}\,\right\|\ket{x_{i}}$
and $O_{x}:\textbf{y}\mapsto\ket{y}$.

4:Quantum Laplacian preparation. Prepare quantum density matrix using oracle
access to $G$ (Section 3.1).

5:Matrix multiplication. Compute the matrix multiplication $\ket{Ky}=K\ket{y}$
via [23].

6:Matrix inversion. Compute the matrix inversion
$\ket{\alpha,}=A^{-1}\ket{\kappa}$ via HHL algorithm. A quantum circuit for
the HHL algorithm has three main steps:

7:  _Phase estimation_ , including efficient Hamiltonian simulation (Section
3.2)

8:  _Controlled rotation_

9:  _Uncomputing_

10:Classification. Based on Swap test algorithm, same as in Quantum LS-SVM
(Section 3.3).

##  4 Complexity of Quantum Semi-Supervised LS-SVM

The complexity of the algorithm is $O(\kappa^{3}\varepsilon^{-3}\log mp)$,
where $\varepsilon$ is the desired error and $\kappa=1/\sigma$ is the
effective conditioning number, defined by filtering out eigenvalues of the
matrix to be inverted that are below $\sigma$. The quantum method offers
exponential speedup over the classical time complexity for solving SVM as a
quadratic problem, which requires time $O(\log(\epsilon^{-1})poly(p,m))$,
where $\epsilon$ is the desired error. The exponential speedup in $p$ occurs
as the result of fast quantum computing of kernel matrix, and relies on the
existence of efficient oracle access to data. The speedup on $m$ is due to
applying quantum matrix inversion for solving LS-SVM, which is inherently due
to fast algorithm for exponentiation of a resulting non-sparse matrix.
However, to achieve the exponential speedup in $m$, the matrix to be inverted
has to be very low-rank; for more typical low- to medium-rank matrices, the
speedup is polynomial in $m$. Compared to quantum LS-SVM [12], our algorithm
introduces three additional steps: preparing the Laplacian density matrix,
quantum matrix multiplication $Ky$, and Hamiltonian simulation for
$\gamma^{-1}K+KK+\gamma^{-1}KLK$ instead of just $K$. The first step involves
oracle access to a sparse graph adjacency list representation, which is at
least as efficient as the oracle access to non-sparse data points. The matrix
multiplication step is a variant of the HHL and LMR protocol and is dominated
in term of complexity by the Hamiltionian simulation step. The Hamiltonian
simulation involving HHL and generalized LMR protocol involves simulating a
sparse conditional partial swap operator, which results an efficient strategy
for simulating Hermite polynomials in time $\tilde{O}(\log(m)\Delta t)$, where
the notation $\tilde{O}$ hides more slowly growing factors in the Hamiltonian
simulation [24].

The quantum Semi-Supervised SVM, similarly to other quantum machine learning
methods, relies on a strong assumptions about the input-output model: the
existence of an efficient approach for preparing input data (mainly via QRAM),
and learning partially from the quantum output state (via quantum
measurement). Recently, the consequences of adopting similar input-output
assumptions for classical algorithms have been explored under the umbrella of
quantum-inspired algorithms [9], also known as a dequantized algorithms. These
algorithms solve a classical equivalent of a quantum machine learning problem
in a setting where the data input/output model is designed to mimic the
assumptions underlying QRAM and quantum measurements. Specifically, analogous
to using QRAM input model and quantum measurement, these classical algorithms
exploit _$\ell^{2}$ -norm sampling and query access_, also known as
_importance sampling_ or _length-square sampling_ in randomized linear algebra
literature. These assumptions make the comparison between quantum algorithms
and their classical, dequantized counterparts more fair.

Analogous to the assumption one can efficiently prepare a quantum state
$\ket{x}$ proportional (up to normalization) to some input vector $x$, a
quantum-inspired algorithm is assisted by an input model called sampling and
query access. One has sampling and query access to a vector
$x\in{\mathbb{C}}^{n}$ if the following queries can be done in
$\tilde{O}\left({1}\right)$:

  1. (a)

given an index $i\in[n]$, output the $i$th element $x_{i}$,

  2. (b)

sample an index $j\in[n]$ with probability
$\frac{|x_{j}^{2}|}{\left\|\,x\,\right\|^{2}}$,

  3. (c)

output the $\ell^{2}$-norm $\left\|\,x\,\right\|$.

For a matrix $A\in{\mathbb{C}}^{m\times n}$ the model gives the sampling and
query access to each row $A(i,.)$ and access to a vector with elements
corresponding to $\ell^{2}$-norm of $A$’s rows.
The fundamental difference between quantum-inspired algorithms and traditional
classical algorithms is that via importance sampling, their runtime is
independent of the dimension of input data, and thus it builds a setting
comparable with quantum machine learning algorithms aided by QRAM. Recently
[25] introduced an algorithmic framework for quantum-inspired classical
algorithms on low-rank matrices that generalizes a series of previous work,
recovers existing quantum-inspired algorithms such as quantum-inspired
recommendation systems [9], quantum-inspired principal component analysis
[26], quantum-inspired low-rank matrix inversion [27], and quantum-inspired
support vector machine [28].

It is natural to ask how our proposed quantum algorithm’s complexity compares
to the quantum-inspired classical setting. Quantum Semi-supervised SVM has
complexity

$\displaystyle\tilde{O}\left({\sigma^{-3}\varepsilon^{-3}\log mp}\right)$

The value of $\sigma$ is a crucial parameter that may increase the complexity
above logarithmic factors in $m$ and $p$. It is user controlled, and denotes a
constant such that that the magnitudes of $\hat{F}$’s eigenvalues
$\lambda_{i}$ that are used in the computations satisfy
$\sigma\leq|\lambda_{i}|$, and smaller eigenvalues are ignored. Here, matrix
$\hat{F}={F}/{tr(F)}$ is a normalized matrix that needs to be inverted to find
the solution to the SVM problem.

Quantum-inspired SVM [28, 25] for the same $\hat{F}$ with trace, operator
norm, and Froebenius norm bounded by 1, and with threshold $\sigma$ on the
singular values retained in the computation, has complexity

$\displaystyle\widetilde{O}\left(\frac{\|\hat{F}\|_{\mathrm{F}}^{6}\|\hat{F}\|^{22}}{\sigma^{28}\varepsilon^{6}}\eta^{6}\log^{3}\frac{1}{\delta}\right),$

where $\varepsilon$ is the error, as in Quantum SVM. Parameters $\eta$ and
$\delta$ have no corresponding meaning in quantum SVM; without loss of
generality we consider their values as a constant.

To illustrate the differences in complexity of the quantum and dequantized
algorithms, we construct a family of examples where the input $m\times m$
matrix $F$ is a diagonal matrix with $q$ ones and $m-q$ zeros on the diagonal.
The trace of $F$ is $q$, and thus $\hat{F}$ is a diagonal matrix with value
$1/q$ and null on the diagonal. The operator norm
$\left\|\,\hat{F}\,\right\|=\lambda_{max}=1/q$, while the Froebenius norm
$\left\|\,\hat{F}\,\right\|_{F}=\sqrt{\sum_{i}\lambda_{i}^{2}}=\sqrt{q\frac{1}{q}^{2}}=1/\sqrt{q}$.
Since all nonzero singular values are equal to $1/q$, setting $\sigma=1/q$ is
the only reasonable choice. For a given $q$, the complexity of the quantum
algorithm is

$\displaystyle\tilde{O}\left({q^{3}\varepsilon^{-3}\log mp}\right),$

while the complexity of the dequantized algorithm is

$\displaystyle\tilde{O}\left({\frac{(1/q)^{6}(1/\sqrt{q})^{22}}{(1/q)^{28}\varepsilon^{-6}}\eta^{6}\log^{3}\frac{1}{\delta}}\right)=\tilde{O}\left({q^{-6-11+28}\varepsilon^{-6}\eta^{6}\log^{3}\frac{1}{\delta}}\right)=\tilde{O}\left({q^{9}\varepsilon^{-6}\eta^{6}\log^{3}\frac{1}{\delta}}\right),$

In the full-rank case, $q=m$, we have
$\tilde{O}\left({m^{3}\varepsilon^{-3}\log mp}\right)$ complexity for the
quantum method, and
$\tilde{O}\left({m^{9}\varepsilon^{-6}\eta^{6}\log^{3}\frac{1}{\delta}}\right)$
for the dequantized algorithm; both are polynomial in terms of $m$, and do not
offer advantage in terms of $m$ over classical methods involving matrix
inversion. Such a full-rank case is unlikely to appear in practice in Semi-
Supervised SVMs, where

In the extremely low-rank case of $q=1$, the complexity of both methods is
similar, we have $\tilde{O}\left({\varepsilon^{-3}\log mp}\right)$ complexity
for the quantum method, and
$\tilde{O}\left({\varepsilon^{-6}\eta^{6}\log^{3}\frac{1}{\delta}}\right)$ for
the dequantized algorithm; both are sublinear in terms of $m$ and $p$; the
quantum method has better dependency on the error $\varepsilon$ but includes
logarithmic factor $\log mp$ that is absent in the dequantized method.

Consider also a more realistic low-rank case where the rank slowly grows with
$m$, for example $q=\sqrt[6]{m}$. In this case, we have
$\tilde{O}\left({\sqrt{m}\varepsilon^{-3}\log mp}\right)$ complexity for the
quantum method, and
$\tilde{O}\left({m^{3/2}\varepsilon^{-6}\eta^{6}\log^{3}\frac{1}{\delta}}\right)$
for the dequantized algorithm. The quantum algorithm is sublinear, while the
dequantized one is not. Based on the distribution of eigenvalues of the
Laplacian for real-world graphs [29] and for kernel matrices [30], which decay
fast, we can expect this is the most realistic case.

These observations agree with a recent work [31] that studied the performance
of quantum-inspired algorithms in practice and concluded that their
performance degrades significantly when the rank and condition number of the
input matrix are increased, and high performance requires very low rank and
condition number.

##  5 Conclusions

Quantum Semi-Supervised SVM uses unlabeled training samples to gain more
information about the underlying distribution over the sample input space,
which helps improve the decision boundary between the classes compared to only
using labeled samples. In classical algorithms, the Laplacian of the graph
that connects labeled and unlabeled samples can be incorporated into the SVM
objective function in a straightforward way. However, in the quantum SVM,
where the kernel matrix is represented by a density matrix and Hamiltonian
simulation is used for minimizing the objective function, incorporating the
graph Laplacian, also represented as a density matrix, becomes a challenge. We
address this difficulty by adapting the Generalized LMR protocol to the Semi-
Supervised SVM objective function, composed of the quadratic terms that
involve the kernel and graph Laplacian matrices. We compared the complexity of
the resulting algorithm with the complexity of classical methods, as well as
with recently proposed dequantized algorithms, and showed that in the most
realistic, low-rank case, the proposed quantum method achieves sublinear
complexity, providing polynomial speedup over classical solvers.

## Acknowledgments

T.A. is supported by NSF grant IIS-1453658.

## References

  * [1] Peter W Shor.  Algorithms for quantum computation: discrete logarithms and factoring.  In Proceedings 35th annual symposium on foundations of computer science, pages 124–134. Ieee, 1994.
  * [2] Lov K Grover.  A fast quantum mechanical algorithm for database search.  arXiv preprint quant-ph/9605043, 1996.
  * [3] Aram W Harrow, Avinatan Hassidim, and Seth Lloyd.  Quantum algorithm for linear systems of equations.  Physical Review Letters, 103(15):150502, 2009.
  * [4] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd.  Quantum machine learning.  Nature, 549(7671):195, 2017.
  * [5] Vedran Dunjko and Hans J Briegel.  Machine learning & artificial intelligence in the quantum domain: a review of recent progress.  Reports on Progress in Physics, 81(7):074001, 2018.
  * [6] M. Schuld and F. Petruccione.  Supervised Learning with Quantum Computers.  Springer Nature, 2018.
  * [7] Srinivasan Arunachalam and Ronald de Wolf.  A survey of quantum learning theory.  ACM SIGACT News, 48(2):41–67, 2017.
  * [8] Edwin Stoudenmire and David J Schwab.  Supervised learning with tensor networks.  Advances in Neural Information Processing Systems, 29, 2016.
  * [9] Ewin Tang.  A quantum-inspired classical algorithm for recommendation systems.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 217–228, 2019.
  * [10] Aliakbar Panahi, Seyran Saeedi, and Tom Arodz.  word2ket: Space-efficient word embeddings inspired by quantum entanglement.  In International Conference on Learning Representations, 2019.
  * [11] Aliakbar Panahi, Seyran Saeedi, and Tom Arodz.  Shapeshifter: a parameter-efficient transformer using factorized reshaped matrices.  Advances in Neural Information Processing Systems, 34, 2021.
  * [12] Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd.  Quantum support vector machine for big data classification.  Physical Review Letters, 113(13):130503, 2014.
  * [13] Tongyang Li, Shouvanik Chakrabarti, and Xiaodi Wu.  Sublinear quantum algorithms for training linear and kernel-based classifiers.  In Proceedings of the 36th International Conference on Machine Learning, pages 3815–3824, 2019.
  * [14] Tom Arodz and Seyran Saeedi.  Quantum sparse support vector machines.  arXiv preprint arXiv:1902.01879, 2019.
  * [15] Jonathan Allcock and Chang-Yu Hsieh.  A quantum extension of SVM-perf for training nonlinear SVMs in almost linear time.  Quantum, 4:342, 2020.
  * [16] Alejandro Perdomo-Ortiz, Marcello Benedetti, John Realpe-Gómez, and Rupak Biswas.  Opportunities and challenges for quantum-assisted machine learning in near-term quantum computers.  Quantum Science and Technology, 3(3):030502, 2018.
  * [17] Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols, and Theodore J Yoder.  Hamiltonian simulation with optimal sample complexity.  npj Quantum Information, 3(1):13, 2017.
  * [18] Stefano Melacci and Mikhail Belkin.  Laplacian support vector machines trained in the primal.  Journal of Machine Learning Research, 12(Mar):1149–1184, 2011.
  * [19] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost.  Quantum principal component analysis.  Nature Physics, 10(9):631, 2014.
  * [20] Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani.  Manifold regularization: A geometric framework for learning from labeled and unlabeled examples.  Journal of machine learning research, 7(11), 2006.
  * [21] Bernhard Schölkopf, Ralf Herbrich, and Alex J Smola.  A generalized representer theorem.  In International Conference on Computational Learning Theory, COLT’01, pages 416–426. Springer, 2001.
  * [22] Ingo Steinwart, Don Hush, and Clint Scovel.  Training svms without offset.  Journal of Machine Learning Research, 12(1), 2011.
  * [23] Nathan Wiebe, Daniel Braun, and Seth Lloyd.  Quantum algorithm for data fitting.  Physical Review Letters, 109(5):050505, 2012.
  * [24] Dominic W Berry, Graeme Ahokas, Richard Cleve, and Barry C Sanders.  Efficient quantum algorithms for simulating sparse Hamiltonians.  Communications in Mathematical Physics, 270(2):359–371, 2007.
  * [25] Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang.  Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 387–400, 2020.
  * [26] Ewin Tang.  Quantum-inspired classical algorithms for principal component analysis and supervised clustering.  arXiv preprint arXiv:1811.00414, 2018.
  * [27] András Gilyén, Seth Lloyd, and Ewin Tang.  Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension.  arXiv preprint arXiv:1811.04909, 2018.
  * [28] Chen Ding, Tian-Yi Bao, and He-Liang Huang.  Quantum-inspired support vector machine.  arXiv preprint arXiv:1906.08902, 2019.
  * [29] Nicole Eikmeier and David F Gleich.  Revisiting power-law distributions in spectra of real world networks.  In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 817–826, 2017.
  * [30] Andrew J Wathen and Shengxin Zhu.  On spectral distribution of kernel matrices related to radial basis functions.  Numerical Algorithms, 70(4):709–726, 2015.
  * [31] Juan Miguel Arrazola, Alain Delgado, Bhaskar Roy Bardhan, and Seth Lloyd.  Quantum-inspired algorithms in practice.  arXiv preprint arXiv:1905.10415, 2019.