5
$\begingroup$

I'm confused about the relationship between kernel methods and SVM methods used in quantum machine learning. Sometimes the two seem to be used interchangeably, but often I'll see them both in the same sentence. I understand what an SVM is in the classical context. So is a kernel just the quantum equivalent? Or is there such thing as a 'classical' kernel and a 'quantum' SVM?

$\endgroup$
6
$\begingroup$

Consider a simple implementation of a Support Vector Machine (SVM) that finds a hyperplane (defined by its normal vector $w$) that maximally separates vectors $\{v_1, \dots, v_m\}$ according to their labels $\{y_1, \dots, y_m\}$, where each $y$ is either $-1$ or $1$. For simplicity we'll assume that such a $w$ exists (i.e. the vectors $\{v_k\}$ are linearly seperable , or that the hard margin SVM is realizable). Training the SVM results in a linear prediction function, which assigns a label to some new vector $v_i$ according to $$\tag{1} f(v_i) = \text{sign}(\langle w, v_i\rangle) $$

If $\langle w, v_i\rangle$ comes out positive, it means that $v_i$ lives on the half of the plane $w$ where the set of positively-labeled vectors $\{v_k: y_k=+1\}$ also live, and so the best inference we can make is that $v_i$ should also be assigned a positive label.

Up to this point I have not explicitly stated what space the vectors $v, w$ live in, but that space should at least have an associated inner product. Without losing much generality we can enforce that $v, w$ live in a Hilbert space to make the following comparison simpler. Then imagine two different applications of this algorithm:

  1. Define our dataset $\{v_k\}$ to be a set of $d$-dimensional real vectors $\{x_1, \dots, x_m\} = \mathcal{X}\subset \mathbb{R}^d$, so that we end up doing linear classification with hyperplane $w$ on $\mathcal{X}$ according to the label of each datapoint $x_i$.
  2. Define our dataset $\{v_k\}$ to be a set of $p$-dimensional complex vectors $\{\phi_1, \dots, \phi_m\} = \mathcal{\Phi}\subset \mathbb{C}^p$, so that we end up doing linear classification with hyperplane $w'$ on $\mathcal{\Phi}$ according to the label of each $\phi_i$.

These are still both linear classifiers. But now we make a connection between the two by defining

$$\tag{2} \phi_i \equiv \phi(x_i) $$ such that $\phi: \mathbb{R}^d \rightarrow \mathbb{C}^p$ is a feature map that sends each real datapoint $x_i$ in my $d$-dimensional space to some other element $\phi(x_i)$ in my (possibly much higher-dimensional) $p$-dimensional space. The feature map $\phi$ will generally be non-linear. This has the powerful side effect of making application #2 a nonlinear version of application #1, that is

$$\tag{3} f'(x_i) = \text{sign}(\langle w', \phi(x_i)\rangle) $$ will result in a decision boundary that is more expressive in our input space $\mathbb{R}^d$ than the corresponding linear decision boundary $f(x_i) = \text{sign}(\langle w, x_i\rangle)$.


So to answer some of your questions

  • Why do I see SVM and quantum kernel methods used interchangeably - they should generally not be. A quantum kernel method describes (a) constructing the feature map $\phi$ to map input data $x_i$ into a state $\phi(x_i)$ that lives in quantum state space, typically (but not quite rigorously correct) of the form $$\tag{4} \phi(x) \equiv U(x)|0\rangle $$ for some unitary $U(x)$ that you can run on a quantum circuit, and then (b) processing our input data $\{x_i\}$ by evaluating inner products of the form $\langle \phi(x_i), \phi(x_j)\rangle \equiv k(x_i, x_j)$. This $k$ is the kernel we define with respect to our data, hence quantum kernel method. Running an SVM on our data using this quantum kernel is just the very specific choice of learning a function of the form of Equation (3). In general we can decompose $w'$ as $$\tag{5} w' = \sum_{k=1}^m \alpha_k \phi(x_k) $$ and so the classifier (3) can indeed be expressed strictly in terms of $k(x_i, x_j)$

  • Is a kernel just the quantum equivalent [of a classical SVM]? No! The only thing special about a quantum kernel method is that $k$ is computed (or $\phi$ is constructed) using a quantum computer. There are plenty of classical kernels (Gaussian, polynomial, Laplace, etc.) you can efficiently compute on a classical machine to do nonlinear classification. Implementing an SVM using a quantum kernel just means making a choice not to use one of those out-of-the-box classical kernel functions and instead use a feature map like Equation (4). Furthermore, not all kernel methods involve an SVM; consider Kernel Nearest Neighbors, Kernel Principal Component Analysis, Kernel Spectral Clustering, etc. One could choose to compute $k$ on a quantum computer and then use it as input to one of the other algorithms instead of an SVM and still have something called a ``quantum kernel method''.

  • Is there such thing as a 'classical' kernel and a 'quantum' SVM? I'm not sure; its hard for me to imagine what that setup would look like but quantum kernels are an active area of research so maybe something like this will be proposed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.