量子サポートベクターマシンによる2値分類(理論)

近年、量子コンピューターを利用して機械学習を行う手法が提案されています。量子コンピューターを使うことで古典コンピューターでは実装できないような機械学習モデルを設計することができます。ここでは量子サポートベクターマシンを紹介します。

# サポートベクターマシン

$y=\pm 1$で2値分類できる学習データを

```math
D = \{ d^{(i)} = (x^{(i)},y^{(i)}) \mid x^{(i)} \in \mathbb{R}^n, y^{(i)} \in \{\pm 1\}\}
```

とします。また

```math
Y_+ = \{ (x^{(i)},1) \in D \} \\
Y_- = \{ (x^{(i)},-1) \in D \} =D-Y_+\\
```

とします。テストデータは

```math
T = \{ x^{(j)} \in \mathbb{R}^n \}
```

です。

これに対してパラメーター$\theta=(w,b)$で決まるあるモデル

```math
y = F_\theta(x) = w^T \cdot x - b
```

を定めます。そして

```math
y = 1 \Rightarrow F_\theta(x) > \epsilon \\
y = -1 \Rightarrow F_\theta(x) < -\epsilon
```

で特徴量$x$を持つデータが２つのグループのどちらに入るかを求める手法をサポートベクターマシン(SVM)と言います(バッファ$ \epsilon \geq 0 $を設けています)。このとき、$F_\theta(x)$を分類器と言います。

学習では各データ$(x^{(i)},y^{(i)})$に対して

```math
y^{(i)} = 1 \Rightarrow F_\theta(x^{(i)}) > \epsilon \\
y^{(i)} = -1 \Rightarrow F_\theta(x^{(i)}) < -\epsilon
```

となるようにパラメーター$\theta$を最適化していきます。

また、必要に応じて非線形変換$\phi: \mathbb{R}^n \rightarrow \mathbb{R}^m$によって$x \rightarrow \phi(x)$と変形して使います。

# 量子サポートベクターマシン(QSVM)

量子サポートベクターマシン(QSVM)はモデル$y=F_\theta(x)$を量子コンピューター上の回路に置き換えたものです。

特徴量$x$は状態$|x\rangle$、モデルはユニタリ変換$U_\theta$、$y$の出力は測定に置き換えられます。概念的にQSVMのモデル$F^Q_\theta$を書くと次のようになります。

```math
F^Q_\theta(x) : U_\theta |x\rangle \xrightarrow{\text{measure }y} y	
```

ここで量子コンピューターを使うのはあくまでモデルの計算であってパラメーターの最適化は古典的な最適化手法で行うということを断っておきます。

実際には密度行列を使って計算します。以下、$n_{bit}$量子ビットのコンピューターで計算するとし、$N=2^{n_{bit}}$とします。ただし、特徴量の次元$n$に対して$n \leq N^2-1$となるようにします。

まず$ (x^{(i)},y^{(i)}) \in D $に対して、特徴量を表す密度演算子は$SU(N)$の生成子

```math
\lambda_i \in SU(N) = \{ \sigma_1 \otimes \sigma_2 \otimes \cdots \otimes \sigma_{n_{bit}} \mid \sigma_i = 1,\sigma_x,\sigma_y,\sigma_z \}
```

を使って($\lambda_i\ \neq 1$に注意)、

```math
\rho^{(i)} = \frac{1}{N} \left( I + \sqrt{ \frac{N(N-1)}{2} } \sum_{j=1}^{n} \frac{\min\left(|x^{(i)}|^{-1},1 \right)}{N-1} x^{(i)}_j \lambda_j \right)
```

と表します。

次に測定量は

```math
E_1 = \left( \frac{1}{2} + \beta b \right)I + \beta \sum_{i=1}^{n} w_i \lambda_i = I-E_0\\
\beta = \frac{1}{2} \left[ |b| + |w|\sqrt{ \frac{2(N-1)}{N} } \right]^{-1}
```

とします。このとき、$E_1$を測定すると、

```math
\alpha = \sqrt{ \frac{N-1}{N} } \beta \min_i \gamma_i
```

として

```math
d^{(i)} \in Y_+ \Rightarrow Tr(E_1\rho_i) = \frac{1}{2} + \alpha(w^T \cdot x + b) \geq \frac{1}{2} + \alpha \\
d^{(i)} \in Y_- \Rightarrow Tr(E_1\rho_i) = \frac{1}{2} + \alpha(w^T \cdot x + b) \leq \frac{1}{2} - \alpha
```

となります。全ての$d^{(i)} \in D$に対してこの測定を行い、その結果からパラメーターを更新していくことで学習ができます。このプロセスを実際に回路上でどう行うのか、ステップごとに見ていきましょう。

## 非線形変換
非線形変換は適当なユニタリ行列$\mathcal{U}\_\phi$を作用させることで実現されます。アダマール変換$H$と対角成分だけ非ゼロのユニタリ行列$U_\phi$（Zゲート、control Zゲート、Toffoliゲートなどの対角なゲートで構成される)を使って

```math
\mathcal{U}_\phi = U_\phi H^{\otimes n_{bit}} U_\phi H^{\otimes n_{bit}}
```

という風に構成します。回路で書くと次図のようになります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2445529/e29f0ff2-d6e0-fe1e-6bd5-254433cffef5.png)

$U_\phi$はZゲートの積の線形結合を肩に乗せた指数演算子で表されます。

```math
U_{\phi(x)} = \exp \left[ i\sum_{ S \subset \{1,2,\cdots,n_{bit}\} } c_S(x) \prod_{i\in S}Z_i \right]
```

これは対角成分しかないので、対角なゲートを組み合わせて表現することができます。また係数は$c_S(x) \in \mathbb{R}$です。

これによって非線形変換された特徴量を表す状態

```math
|\phi(x)\rangle = \mathcal{U}_{\phi(x)}|0\rangle^{\otimes n_{bit}}
```

が生成されます。

ここに量子サポートベクターマシンの個性が出ていて、$U_\phi$の種類によっては古典コンピューターでは多項式時間で計算できない(＝NP困難な)あるものの、量子コンピューターでは多項式時間で計算できる変換になっています(IQPクラスと言います)。

## 分類器
次に分類器に相当するユニタリ変換を構成します。これは以下の2つの手順の繰り返しになっています。

### ステップ１：エンタングルメントゲート
まずcontrol Zゲートをすべての量子ビットのペアに作用させて量子ビットをエンタングルさせます。

```math
U_{ent} = \prod_{(i,j)}CZ(i,j)
```

### ステップ2：各量子ビットの操作

次にそれぞれの量子ビットをユニタリ変換します。１量子ビットのユニタリ変換は

```math
U(\theta) = \exp \left( -\frac{i}{2}\theta \cdot \sigma \right) \in SU(2)
```

で表させます(X,Zゲートで構築するので$\theta$はx、z成分のみあります)。$t$回目のステップでの$i$番目の量子ビットの回転を$U(\theta^{(t)}_i)$と表し、この操作は

```math
U^{(t)}_{loc}(\theta^{(t)}=\{ \theta^{(t)}_1, \cdots, \theta^{(t)}_{n_{bit}} \}) = \bigotimes_i U(\theta^{(t)}_i)
```

となります。全部でこのプロセスを$L$回繰り返すとすると分類器は

```math
W(\theta = \{ \theta^{(t)}_i \}_{i,t}) = \prod_{t=1}^L U^{(t)}_{loc}(\theta^{(t)} ) U_{ent}
```

と書けます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2445529/b6af815d-203b-3128-4018-5b21206699c1.png)

## 測定

得られた状態$W(\theta)U_{\phi(x)}|0\rangle^{\otimes n_{bit}}$に対して各ビットでZ測定を行うとZの列

```math
z=(\sigma_1,\cdots,\sigma_{n_{bit}}) \in \{0,1\}^{\otimes n_{bit}}
```

を得ます。これを２つのグループ$y=\pm 1$と対応させる適当な関数

```math
f:\{0,1\}^{\otimes n_{bit}} \rightarrow {\pm 1}
```

を使って変換すると、$y=\pm 1$に属するデータかどうかは

```math
\frac{1+yf(z)}{2}
```

で判定できます。

これを演算子で書くと
 
```math
\hat{f}= \sum_{z \in \{0,1\}^{\otimes n_{bit}} } f(z) | z \rangle \langle z | \\
M_y = \frac{1}{2} \left( 1 + \hat{f}  \right)
```

となります。最終的に得られる結果は特徴量$x$がグループ$y$に属す確率

```math
p_y(x) = \langle 0|^{\otimes n_{bit}} U^\dagger_{\phi(x)} W^\dagger(\theta) M_y  W(\theta) U_{\phi(x)} |0\rangle^{\otimes n_{bit}}
```

です。どちらのグループに属すかの推定値$\tilde{m}(x)$は

```math
\tilde{m}(x) = 
1 \quad \text{if } p_y >p_{-y} - yb
```

と判定します。ここで用いたバッファ$b \in [-1,1]$も最適化パラメータです。

## 最終的な表式
以上をまとめると

```math
\tilde{m}(x) = sgn[\langle\phi(x)|W^\dagger(\theta) \hat{f} W(\theta) |\phi(x) \rangle + b]
```

となります。ここで

```math
sgn(x) = \frac{x}{|x|}
```

です。ちなみに古典SVMのモデル(非線形変換も含める)を再掲しておくと

```math
\tilde{m}_{classic}(x) = sgn(w^T \phi(x) + b)
```

です。$w^T \phi(x)$の部分がQSVMでは変わっていますね。


## 最適化

学習データに対して推定値が間違っている確率$Pr[\tilde{m}(x^{(i)}) \neq y^{(i)})]$はシグモイド関数

```math
\sigma(x)=\frac{1}{1+e^{-x}}
```
と十分大きなサンプル数$R\gg1$(  https://arxiv.org/pdf/1804.11326.pdf の実際の計算ではサンプル数に関係なく$R=200$で固定していました )を用いて

```math
Pr[\tilde{m}(x^{(i)}) \neq y^{(i)})] \simeq \sigma\left( \frac{\sqrt{R}(1/2 - (p_y(x)-yb/2))}{ \sqrt{2(1-p_y(x))p_y(x))} }  \right)
```

となり、経験損失は

```math
R_{emp}(\theta,b) = \frac{1}{|D|} \sum_{d=(x,y) \in D} Pr[\tilde{m}(x) \neq y]
```

となります。これを確率勾配降下法などで最小化して

```math
\theta^*,b^* = \text{argmin}_{\theta,b} [R_{emp}(\theta,b)]
```
を求めます。

# コメント
この方法だと最適化の部分で何度も量子計算が必要となりますが、このやり方をベースにしたカーネル法を使うともっとシンプルな回路で学習ができます。

https://qiita.com/hiro949/items/200f82c285a040fb3ded


# 参考
- https://qiskit.org/documentation/machine-learning/locale/ja_JP/tutorials/index.html
- https://arxiv.org/pdf/1804.11326.pdf
- https://arxiv.org/pdf/0706.3265.pdf
- https://arxiv.org/pdf/1005.1407.pdf