量子カーネルを用いたSVM (scikit learn + PennyLane)

# 量子カーネルによるSVM?

https://pennylane.ai/qml/demos/tutorial_kernel_based_training.html

量子機械学習の一種である、量子カーネルによるSVMを考えて、実装してみます。

SVMは、データを高次元に射影した上で線形分離を行う機械学習です。
（分離平面を機械学習で決定します）
分離平面は、あるコスト関数$L$が最小になるように決めます。
$L$には入力データの内積（カーネル）の計算が含まれます。

高次元空間での内積を計算するには、その次元数で決まる計算量（一般に大きい）が必要となってしまいます。
そこで、高次元空間への射影の仕方を「高次元空間での内積が既知の公式で求まるもの」に限定してやることで
計算量を大幅にカットします。


よくわからないので、イメージで書きます。
$1+x+x^{2}+x^{3}... +x^{n} = 1/(1-x^{n})$ という公式を知っている人にとっては、左辺を真面目に計算（1項ずつ足す）する必要はなくて、
右辺を計算するほうが遥かに楽です。
同じように、高次元の内積計算を公式で終わらせます。
この方法はカーネルトリックと呼ばれます。

量子カーネルでも、基本は同じです。
高次元空間への射影としては、量子ゲート操作で構成できるものだけを考えます。
そして、内積計算を簡単に終わらせるために、巧みな量子ゲートの構成と射影測定で代用します。
カーネルの計算が出来れば、分離平面が求められます。ここは古典的なソルバーで行えます。


# 量子カーネルに対するカーネルトリック

入力データ$x$と$x'$の高次元空間での内積を計算するカーネルトリックは以下のような回路と測定からなります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/878664/9881e1a3-d9a0-6efc-94f1-3153160e0a77.png)

ここで$S(x)$が高次元空間への写像に相当します。ここはユーザーが好きに決めます。（写像の選び方の自由度です）
$S(x)$はユニタリ操作（量子ゲート）である必要があります。
$S^{\dagger}$は$S$の複素共役です。
最後に、量子状態を測定し、$|00...0>$が出た頻度（確率）を数えます。
すると、大変不思議なことに、内積の値が得られます。[^1]

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/878664/cd87c924-4531-418a-f355-0bbc6c86c68c.png)


ここで、$S(x)|00...0>$を$|\phi(x) \rangle$と置いています。
$|00...0>$を$S(x)$によって高次元空間（量子状態）の元 $|\phi(x) \rangle$へ写像した時の内積が知りたいわけです。
それは（なぜか）上記回路の$|00...0>$が出た頻度（確率）である、ということです。
今はそういう公式が導出できるということを受け入れましょう。

# 実装

では、実装します。量子ゲートによるカーネル定義・カーネル計算の部分はpennylane、最適化はscikit-learnで行います。

pennylane : Version: 0.16.0
pennylane-lightning : Version: 0.15.1
scikit-learn : Version: 0.24.1

二次元データを2値分類します。
量子ゲート部分は2量子ビットを用います。
今回の$S(x)$の定義だと、量子ビット数は、入力データ次元以上が必要です。
多いほど、射影先が高次元になります。
訓練データ数は100とします。

```python
import numpy as np

from sklearn.svm import SVC
from sklearn.datasets import load_iris
from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

import pennylane as qml
from pennylane.templates import AngleEmbedding, StronglyEntanglingLayers
from pennylane.operation import Tensor

import matplotlib.pyplot as plt

np.random.seed(42)

X, y = load_iris(return_X_y=True)

# pick inputs and labels from the first two classes only,
# corresponding to the first 100 samples
X = X[:100,0:2]
y = y[:100]

# scaling the inputs is important since the embedding we use is periodic
scaler = StandardScaler().fit(X)
X_scaled = scaler.transform(X)

# scaling the labels to -1, 1 is important for the SVM and the
# definition of a hinge loss
y_scaled = 2 * (y - 0.5)

X_train, X_test, y_train, y_test = train_test_split(X_scaled, y_scaled)

n_qubits = len(X_train[0])

```

カーネル定義とカーネル計算を行います。

```python
dev_kernel = qml.device("lightning.qubit", wires=n_qubits)

#|00...0><0.....00|
projector = np.zeros((2**n_qubits, 2**n_qubits))
projector[0, 0] = 1

@qml.qnode(dev_kernel)
def kernel(x1, x2):
    """The quantum kernel."""
    AngleEmbedding(x1, wires=range(n_qubits)) #S(x)
    qml.adjoint(AngleEmbedding)(x2, wires=range(n_qubits)) #S^{\dagger}(x')
    return qml.expval(qml.Hermitian(projector, wires=range(n_qubits)))

def kernel_matrix(A, B):
    """Compute the matrix whose entries are the kernel
       evaluated on pairwise data from sets A and B."""
    return np.array([[kernel(a, b) for b in B] for a in A])
```

SVMを学習させます。10秒ぐらいで終わります。

```python
svm = SVC(kernel=kernel_matrix).fit(X_train, y_train)
```

結果を確認します。

```python
predictions = svm.predict(X_test)
accuracy_score(predictions, y_test)
```

`1.0`

誤り無く分類できました。

分離平面を見てみます。

```python
def plot_decision_boundaries(classifier, ax, N_gridpoints=14):
    _xx, _yy = np.meshgrid(np.linspace(-3, 3, N_gridpoints), np.linspace(-3, 3, N_gridpoints))

    _zz = np.zeros_like(_xx)
    for idx in np.ndindex(*_xx.shape):
        _zz[idx] = classifier.predict(np.array([_xx[idx], _yy[idx]])[np.newaxis, :])

    plot_data = {"_xx": _xx, "_yy": _yy, "_zz": _zz}
    ax.contourf(
        _xx,
        _yy,
        _zz,
        cmap=mpl.colors.ListedColormap(["#FF0000", "#0000FF"]),
        alpha=0.2,
        levels=[-1, 0, 1],
    )
    for ii in range(len(X_test)):
        if y_test[ii] > 0:
            plt.plot(X_test[ii,0],X_test[ii,1], marker="o", color='black')
        else:
            plt.plot(X_test[ii,0],X_test[ii,1], marker="x", color='black')
    return plot_data
```

```python
import matplotlib as mpl
init_plot_data = plot_decision_boundaries(svm, plt.gca())
```

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/878664/eb58cbd1-426f-763c-67a8-2d9800aaace0.png)

確かにそれっぽい分類が出来ました。
ただ、これが古典的なカーネルよりも賢いのかは定かでは有りません。
あくまで、「量子”でも”出来ますよ」というだけです。

# 量子変分分類器との違い
量子変分分類器(VQC)との大きな違いは、量子ゲートには一切パラメータが無いということです。
カーネルの定義と計算は静的なものです。
分離平面を求める部分だけが（古典的な）最適化です。
もちろん、量子ゲートにパラメータをもたせる、つまりカーネルの定義に自由度をもたせて、それも最適化対象とすることは考えられます。
VQCと量子カーネルSVMのハイブリッドのようなものです。
そのような例は以下を参照ください。
https://pennylane.ai/qml/demos/tutorial_kernels_module.html



# まとめ

量子カーネルを用いたSVMを実装した。


[^1]: もちろん、SWAPテストやdestructive swapテストで内積を出しても構いません。が、ここでは内積計算するベクトル同士が同じ写像$\phi$から出来ているという事前知識を使ったこの方法のほうが短いゲートで書けます。