IBMのNISQデバイスでK-Meansクラスタリング

この記事の概要

この記事はKhan et al., 2019, "K-Means Clustering on Noisy Intermediate Scale Quantum Computers"を読んだので、その理解を深めるためのアウトプットとして作成したものです。

この記事の概要
この論文の概要
関連した話題
数値実験
- 使用したデータ
- 実験結果
古典と比べてどのくらい速いのか？
結言
参考文献
文責

この論文の概要

以下に示す話題でのアルゴリズムをIBMQX2クラスタリングを行い、どのアルゴリズムが有用であるかを調べたものです。

関連した話題

基本的な量子K-Means法

こちらの記事を参照jijtech.hatenablog.com

距離指標に基づいた分類器

基本的な実装

こちらの記事を参照jijtech.hatenablog.com

量子回路の最適化

この距離指標に基づいた分類器(Distance-based classifier)の量子回路のdepthを減らす方法をご紹介します。4量子ビットでの実装を例に考えてみましょう。

まず以下のような量子状態を準備します。

$\displaystyle{ | \psi \rangle = \frac{1}{\sqrt{2}} (| 0 \rangle | a \rangle + |1 \rangle | b \rangle) }$

$\displaystyle{ |\theta_{|a\rangle} - \theta_{| b \rangle}| = |\theta_{| a_1 \rangle} - \theta_{| b_1 \rangle}| }$

が成り立つならば

$\displaystyle{ | \psi_1 \rangle = \frac{1}{\sqrt{2}} (| 0 \rangle | a_1 \rangle + | 1 \rangle | b_1 \rangle) }$

のような状態も分類分けには有効であるはずです。よって、量子回路のdepthが少なくても、 $| \psi_1 \rangle$ さえ作り出せれば良いことがわかります。これを叶える量子ゲート群を以下に示します。

$\displaystyle{ t: R_y (\theta_{c_2}/2) R_y(\theta_{c_1}/2) X R_y(\theta_t) \left( \begin{array}{c} 1 \\ 0 \end{array} \right) \\ t': R_y (\theta_{c_2}/2) X R_y(\theta_{c_1}/2)R_y(\theta_t) \left( \begin{array}{c} 1 \\ 0 \end{array} \right) \\ c_1: R_y (\theta_{c_2}/2) R_y(-\theta_{c_1}/2) X \left( \begin{array}{c} 1 \\ 0 \end{array} \right) \\ c_2: R_y (- \theta_{c_2}/2) X R_y(\theta_{c_1}/2) \left( \begin{array}{c} 1 \\ 0 \end{array} \right) }$

ここで $t$ は分類分けしたい入力データベクトル、 $t'$ はそのコピー、そして $c_1, c_2$ はそれぞれ2つのクラスター重心ベクトルです。このゲート群で分類分けができるのかどうかを簡単に確認するために、以下の例を考えましょう。

教師データベクトル1: x軸から $0^\circ$ 回転した方向のベクトル
教師データベクトル2: x軸から $180^\circ$ 回転した方向のベクトル
分類分けしたい入力データベクトル: x軸から $45^\circ$ 回転した方向のベクトル

上述のベクトルの方向関係を図示すると以下のようになります。

この図と等価となるようなゲート群であることを見てみましょう。
まずは $t$ を考えます。 $|0 \rangle = (1, 0)^T$ から $R_y (\theta_t)$ だけ回転させます。次に $X$ ゲートを作用させて $y=x$ に対してベクトルを反転させます。さらに $R_y(\theta_{c_1}/2), R_y(\theta_{c_2}/2)$ だけ回転させて、最終的な $t$ を得ます。

$t'$ についても考えましょう。 $|0 \rangle = (1, 0)^T$ からスタートして、まずは $R_y (\theta_t)$ だけ回転します。

次に $R_y (\theta_{c_1}/2)$ だけ回転し、その後 $X$ で反転します。最後に $R_y(\theta_{c_2}/2)$ だけ回転させて、最終的な $t'$ を得ます。

続いて $c_1$ です。 $c_1$ は最初に $X$ で反転させます。次に $R_y (-\theta_{c_1}/2), R_y (\theta_{c_2}/2)$ 回転させて最終的な $c_1$ を得ます。

Quantum state vector of c1 — c1の量子状態ベクトル

最後に $c_2$ を見ましょう。 $R_y(\theta_{c_1}/2)$ 回転した後に、 $X$ で反転させます。そして $R_y(-\theta_{c_2}/2)$ 回転させれば、最終的な $c_2$ を得ます。

Quantum state vector of c2 — c2の量子状態ベクトル

最終的な $t, c_1, c_2$ の方向関係は以下のようになります。

Final states of Quantum state vectors — 最終的な量子状態

このとき $\theta_3 = \theta_1, \theta_4 = \theta_2$ となり、このゲート郡でも正しく分類できることがわかります。
以上の議論から、最適化されたdistance-based classifierの量子回路は以下のようになります。

Negative Rotations

基本構成

この手法は、分類わけしたい入力データから一番近い重心を見つけるために、量子ビットを負方向(あるいは正方向)に回転させます。
ある入力データのベクトル $v$ と2つの分類重心 $\{c_1, c_2\}$ があるとします。どちらの重心がベクトルに近いかを求めてみましょう。入力データ・1つ目の重心・2つ目の重心の偏角をそれぞれ $\theta_t, \theta_{c1}, \theta_{c2}$ とすると、 $c_1$ の方が近い場所にあるとき

$\displaystyle{ |\theta_t - \theta_{c1}| \leq |\theta_t - \theta_{c2}| }$

の関係が成り立ちます。
ここで量子ビットの状態 $|0 \rangle, | 1 \rangle$ を考えましょう。これらを先ほどの重心に対するメトリックと考えます。すなわち $| 0 \rangle$ が測定される確率が高い事象を、片方の重心に近い状態というようにします。2つのベクトルのなす角の最大値は180度なので、一般に

$\displaystyle{ |\theta_t - \theta_c | \leq 180^o \ \Longrightarrow \ \left| \frac{\theta_t}{2} - \frac{\theta_c}{2} \right| \leq 90^o }$

が成り立ちます。よって $R_y(\theta_t)$ によって $\theta_t/2$ だけ回転させたのちに、 $R_y(-\theta_c)$ によって $-\theta_c/2$ だけ回転させれば、重心とのなす角を90度以下にすることができます。
これを ${c_1, c_2}$ の2つの重心がある場合に分類分けする量子回路を示すと以下のようになります。

Negative rotation quantum circuit for 2-qubits — 2量子ビットのNegative rotation

2つの量子ビットのうち $|q_1 \rangle$ で $| 0 \rangle$ が測定される確率が高ければ重心 $c_1$ に近く、 $|q_2 \rangle$ で $| 0 \rangle$ が測定される確率が高ければ重心 $c_2$ に近いことがわかります。

これを一般に、n個の入力データをk個のクラスターに分類したい場合は以下のような量子回路を用います。

nk qubits negative rotation — nk量子ビットのNegative rotation

1つのデータにつき、k個のクラスター重心のうちどれに近いかどうかを判断するためにk個の量子ビットが必要になります。よって必要な量子ビットの総数はnk個となります。

Negative Rotationの利点と欠点

上図からわかるように、このアルゴリズムでは分類したいクラスターの数が増えてもdepthは変化しません。しかし、必要な量子ビット数、すなわちwidthが線形で大きくなるというデメリットがあります。

Distance Calculation using Destructive Interference

基本構成

2つのベクトル $t=(t_x, t_y), c=(c_x, c_y)$ のユークリッド距離を計算すると

$\displaystyle{ d(t, c) = \sqrt{(t_x - c_x)^2 + (t_y - c_y)^2} }$

となります。ここで

$\displaystyle{ | \psi \rangle = (t_x' , t_y', c_x', c_y')^T }$

という量子ビットの状態を考えましょう。ここで $t_x', t_y', c_x', c_y'$ はそれぞれ

$\displaystyle{ t_x' = \frac{t_x}{\rm Norm}, \ t_y' = \frac{t_y}{\rm Norm}, \ c_x' = \frac{c_x}{\rm Norm}, \ c_y' = \frac{c_y}{\rm Norm}, \ {\rm Norm} = \sqrt{t_x^2 + t_y^2 + c_x^2 + c_y^2} }$

です。この状態にアダマールゲート $H \otimes I$ を作用させましょう。

$\displaystyle{ | \phi \rangle = \frac{1}{\sqrt{2}} \left( \begin{array}{cccc} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1 \end{array} \right) \left( \begin{array}{c} t_x' \\ t_y' \\ c_x' \\ c_y' \end{array} \right) = \frac{1}{\sqrt{2}} \left( \begin{array}{c} t_x' + c_x' \\ t_y' + c_y' \\ t_x' - c_x' \\ t_y' - c_y' \end{array} \right) \begin{array}{c} | 00 \rangle \\ | 01 \rangle \\ | 10 \rangle \\ | 11 \rangle \\ \end{array} }$

よって最初の量子ビットを測定すると、 $| 1 \rangle$ の状態が得られる確率は

$\displaystyle{ P | 1 \rangle = \frac{1}{2} ((t_x' -c_x')^2 + (t_y' - c_y')^2) }$

となります。これより

$\displaystyle{ d(t,c) = {\rm Norm} \times \sqrt{2} \sqrt{P | 1 \rangle} }$

です。よって $| \psi \rangle$ を最初に作成すれば良いことがわかります。
これを実現する量子回路を以下に示します。

2-qubits quantum interference circuit — 2量子ビットの干渉量子回路

$| q_1 \rangle$ の状態 $| 0\rangle$ と入力データ $t$ をエンタングルさせます。その後、 $| q_1 \rangle$ の状態 $| 1 \rangle$ とクラスターの重心 $c$ をエンタングルさせます。

K-Means法によってk個のクラスターに分類したい場合、ある入力データとk個のクラスター重心との距離 $(d_1, d_2, \dots, d_k)$ を計算します。そしてそれらの最小となる要素を選出することで、入力データが含まれるクラスターを同定します。

この手法の利点

すでに提案されている量子K-Means法では $| \psi \rangle, | \phi \rangle$ の両方を同時に用意する必要がありました。しかしこの手法では測定前の最後の状態 $| \phi \rangle$ のみ準備すれば良いので、比較すると簡単です。またSwapTestの必要がなくなったため、その分の量子演算回数を減らすことができます。

数値実験

使用したデータ

以下にテストデータとして用いたものを示します。

ランダムに生成したデータセット
Irisデータセット
MNISTデータセット

実験結果

以下にIBMQX2による実験結果と、比較として古典コンピュータ上でのScikit-learnでのK-Means法の結果を示します。

Numerical result of implementation — 数値実験結果

上から順に、1. 距離指標に基づいた分類、2. 距離指標分類の量子回路を最適化したもの、3. Negative Rotation、4. Distance Calculation using Destructive Interference、5. 古典によるScikit-learn K-Meansの結果です。数値実験の結果、Negative RotationとDistance Calculation using Destructive Interferenceによる実装が少ないdepthで良い精度を出せていることがわかりました。

古典と比べてどのくらい速いのか？

この論文によればNegative Rotationの計算量は $\mathcal{O}(\frac{1}{2} NMk)$ 、Distance Calculation using Destructive Interferenceの計算量は $\mathcal{O}(MK \log (N))$ です。Negative Rotationは少ないdepthで良い精度が達成できているのに対して、線形高速化しか達成できていません。しかしDistance Calculation using Destructive Ingerferenceは指数で高速化が達成されています。