量子線形回帰

はじめに

線形回帰

　 ${\bf x} \in \mathbb{R}^{M}$ , ${\bf x}=\{x_j\}_{j=1}^{M}$ と $y\in\mathbb{R}$ の組 $({\bf x},y)$ が $N$ 個与えられたとき

${\displaystyle \begin{equation} y={\bf w}^T{\bf x} \end{equation} }$

を満たすベクトル ${\bf w}$ を求めることが目的である（ $x_1=1$ としてあり、バイアス項は考慮されているとする）。最小化すべき損失関数は

${\displaystyle \begin{eqnarray} L({\bf w}) &=& \dfrac{1}{2}\sum_{i=1}^N\left( {\bf w}^T{\bf x}_i-y_i \right)^2\\ &=& \dfrac{1}{2}\sum_{i=1}^N\left( \sum_{j=1}^{M}w_jx_{ij} -y_i \right)^2 \end{eqnarray} }$

である。 $w_k$ で偏微分した値を0と置くと

${\displaystyle \begin{eqnarray} \dfrac{\partial L({\bf w})}{\partial w_k} &=& \sum_i\left( \sum_jw_jx_{ij}-y_i \right)\sum_l\delta_{lk}x_{il}\\ &=& \sum_i\left( \sum_jw_jx_{ij}-y_i \right)x_{ik}\\ &=&0 \end{eqnarray} }$

を得る。いま行列 $X=\{x_{ij}\}$ を定義すると上式より

${\displaystyle \begin{eqnarray} && \sum_i\sum_jw_jX_{ij}X_{ik}=\sum_iy_iX_{ik}\\ &\iff& \sum_i\sum_jX^T_{ki}X_{ij}w_j=\sum_iX^T_{ki}y_i\\ &\iff& \sum_j\left(X^TX\right)_{kj}w_j=\sum_iX^T_{ki}y_i\\ &\iff& \left(X^TX{\bf w}\right)_k=\left(X^T{\bf y}\right)_k\\ \end{eqnarray} }$

を得る。任意の $k$ について上式が成り立つから

${\displaystyle \begin{equation} X^TX{\bf w}=X^T{\bf y} \end{equation} }$

となり、これより

${\displaystyle \begin{equation} {\bf w}=\left(X^TX\right)^{-1}X^T{\bf y}\tag{1} \end{equation} }$

を得る。 ${\bf w}\in\mathbb{R}^M,{\bf y}\in\mathbb{R}^N$ である。ところで、任意の行列は特異値分解できるから（特異値分解の詳細はこちらの説明を見てほしい）

${\displaystyle \begin{equation} X=U\Sigma V^T\tag{2} \end{equation} }$

と書くことができる。ここで、 $X\in\mathbb{R}^{N\times M},U\in\mathbb{R}^{N\times N},\Sigma\in\mathbb{R}^{N\times M},V\in\mathbb{R}^{M\times M}$ である。 $U$ と $V$ は直交行列であり

${\displaystyle \begin{eqnarray} U^TU=UU^T&=&I\\ V^TV=VV^T&=&I \end{eqnarray} }$

を満たす。また、 $r\leq M$ として

${\displaystyle \begin{equation} \Sigma={\rm diag}\left(\sigma_1,\cdots,\sigma_r,0,\cdots,0\right) \end{equation} }$

と書くことができる（ $\sigma_i> 0,i=1,\cdots,r$ ）。式(2)を使うと

${\displaystyle \begin{equation} \left(X^TX\right)^{-1}X^T=V{\rm diag}\left( \dfrac{1}{\sigma_1},\cdots,\dfrac{1}{\sigma_r},0,\cdots,0 \right)U^{T}\tag{3} \end{equation} }$

を示すことができる。 $V\in\mathbb{R}^{M\times M},U\in\mathbb{R}^{N\times N}$ であり、(3)式右辺の $V,U$ に挟まれた行列は $M$ 行 $N$ 列なので、上の行列は全体として $M$ 行 $N$ 列の行列になる。式(3)を式(1)に代入すれば ${\bf w}$ の解析解を得ることができる。

　未知のデータ $\tilde{{\bf x}}$ が与えられたときの出力値 $\tilde{y}$ は以下のように計算される。

${\displaystyle \begin{eqnarray} \tilde{y}&=&{\bf w}^T\tilde{{\bf x}}\\ &=& \sum_{j=1}^{M}\biggl( V{\rm diag}\left( \dfrac{1}{\sigma_1},\cdots,\dfrac{1}{\sigma_r},0,\cdots,0 \right)U^{T} {\bf y} \biggr)_j\; \tilde{x}_j\\ &=& \sum_{k=1}^{r}\sum_{i=1}^{N}\sum_{j=1}^{M}(V)_{jk}\dfrac{1}{\sigma_k}(U^T)_{ki}y_i\tilde{x}_j\\ &=& \sum_{k=1}^{r}\dfrac{1}{\sigma_k}\left(\sum_{j=1}^{M}v_{jk}\tilde{x}_j\right) \left( \sum_{i=1}^{N}u_{ik}y_i \right)\tag{4} \end{eqnarray} }$

ここで、 $U,V$ の成分を $u_{ij},v_{ij}$ とした。また、式(2)より

${\displaystyle \begin{eqnarray} &&X^TX=V\;{\rm diag}\left(\sigma_1^2,\cdots,\sigma_r^2,0,\cdots,0\right)V^T\\ &\iff&X^TXV=V\;{\rm diag}\left(\sigma_1^2,\cdots,\sigma_r^2,0,\cdots,0\right) \end{eqnarray} }$

成分をとると

${\displaystyle \begin{eqnarray} &&\left(X^TXV\right)_{ij}=\left(V\;{\rm diag}\left(\sigma_1^2,\cdots,\sigma_r^2,0,\cdots,0\right)\right)_{ij}\\ &\iff& \sum_k\left(X^TX\right)_{ik}V_{kj}=\sum_{m=1}^rV_{im}\;\sigma_m^2\;\delta_{mj}\\ &\iff& \sum_{k}\left(X^TX\right)_{ik}V_{kj}=\sigma_j^2V_{ij}\\ &\iff& \big(\left(X^TX\right)V_{:j}\bigr)_i=\sigma_j^2\left(V_{:j}\right)_i \end{eqnarray} }$

ここで、行列 $V$ の第j列の列ベクトル $V_{:j}$ を ${\bf v}_j$ と書くと

${\displaystyle \begin{equation} X^TX{\bf v}_j=\sigma_j^2{\bf v}_j \tag{5} \end{equation} }$

を得る。すなわち、 $X^TX$ の固有値は $\sigma^2_j$ であり、それに対応する固有ベクトルは ${\bf v}_j$ である。

線形回帰の量子アルゴリズム

　ここでは、前節の定式化を量子コンピュータ上で行う手順を示す。まず最初に、入力データ ${\bf x}_i(i=1,\cdots,N)$ を振幅エンコーディングした状態を用意する。

${\displaystyle \begin{eqnarray} |\psi_X\rangle &=& \sum_{i=1}^N|{\bf x}_i\rangle_A\otimes|i\rangle_B\\ &=& \sum_{i=1}^N\sum_{j=1}^Mx_{ij}\;|j\rangle_A\otimes|i\rangle_B\\ \end{eqnarray} }$

ここで、添字の $A,B$ は量子ビットを収めるレジスタであり、独立した2つの状態空間であることを示す。式(2)より

${\displaystyle \begin{eqnarray} |\psi_X\rangle &=& \sum_{i=1}^N\sum_{j=1}^M\sum_{k=1}^r u_{ik}\sigma_kv_{jk} \;|j\rangle_A\otimes|i\rangle_B\\ &=& \sum_{k=1}^r\sigma_k \sum_{j=1}^Mv_{jk}|j\rangle_A\otimes \sum_{i=1}^M u_{ik}|i\rangle_B\\ &=& \sum_{k=1}^r\sigma_k |{\bf v}_k\rangle_A\otimes|{\bf u}_k\rangle_B\tag{6} \end{eqnarray} }$

を得る。ここで、 ${\bf v}_k,{\bf u}_k$ はそれぞれ行列 $V,U$ の第 $k$ 列の列ベクトルである。 $|\psi_X\rangle$ の密度行列は

${\displaystyle \begin{eqnarray} \rho_{AB}&=&|\psi_X\rangle\langle\psi_X|\\ &=&\sum_{i=1}^N\sum_{j=1}^N|{\bf x}_i\rangle_A\langle{\bf x}_j|_A\otimes|i\rangle_B\langle j|_B \end{eqnarray} }$

となり、Bレジスタの空間でトレースを取ると以下のようになる。

${\displaystyle \begin{eqnarray} {\rm Tr}_B\left(\rho_{AB}\right) &=& \sum_{i=1}^N\sum_{j=1}^N|{\bf x}_i\rangle_A\langle{\bf x}_j|_A\otimes \sum_{m=1}^N\langle m|_B |i\rangle_B\langle j|_B|m\rangle_B\\ &=& \sum_{i=1}^N\sum_{j=1}^N|{\bf x}_i\rangle_A\langle{\bf x}_j|_A\otimes \sum_{m=1}^N\delta_{mi}\delta_{mj}\\ &=& \sum_{i=1}^N\sum_{j=1}^N|{\bf x}_i\rangle_A\langle{\bf x}_j|_A\otimes \delta_{ij}\\ &=& \sum_{i=1}^N|{\bf x}_i\rangle_A\langle{\bf x}_i|_A\\ &=& \sum_{i=1}^N|{\bf x}_i\rangle\langle{\bf x}_i|\\ &=& \sum_{i=1}^N\sum_{j=1}^M\sum_{k=1}^Mx_{ij}x_{ik}|j\rangle\langle k|\\ &=& \sum_{i=1}^N\sum_{j=1}^M\sum_{k=1}^M(X^T)_{ji}(X)_{ik}|j\rangle\langle k|\\ &=& \sum_{j=1}^M\sum_{k=1}^M(X^TX)_{jk}|j\rangle\langle k|\\ &\equiv&\rho_A \end{eqnarray} }$

すなわち、行列 $X^TX$ を埋め込んだ密度行列 $\rho_A$ を得ることできる。式(5)より次式が成り立つことも分かる。

${\displaystyle \begin{equation} \rho_A|{\bf v}_k\rangle=\sigma_k^2|{\bf v}_k\rangle \end{equation} }$

　さて、式(6)に、複数ビットからなる3つ目のレジスタ $C$ を加える。

${\displaystyle \begin{equation} |\psi_X\rangle =\sum_{k=1}^r\sigma_k |{\bf v}_k\rangle_A\otimes|{\bf u}_k\rangle_B\otimes|0\rangle_C\tag{7} \end{equation} }$

上の状態の $A$ レジスタにユニタリー行列 $e^{i2\pi\rho_A}$ を施し、 $\rho_A$ の固有値 $\sigma_k^2$ を $C$ レジスタに入れる（量子位相推定）。

${\displaystyle \begin{equation} \sum_{k=1}^r\sigma_k |{\bf v}_k\rangle_A\otimes|{\bf u}_k\rangle_B\otimes|\sigma_k^2\rangle_C \end{equation} }$

4つ目のレジスタ $D$ を加え $C$ レジスタの値を入力とし算術演算を行う（算術演算や次の回転ゲートの詳細な手順はここを参照のこと）。

さらに、1ビットからなる $E$ レジスタを加え、 $D$ レジスタの各ビットを制御ビットとし $E$ レジスタに回転ゲートを施す。

${\displaystyle \begin{equation} \sum_{k=1}^r\sigma_k |{\bf v}_k\rangle_A\otimes|{\bf u}_k\rangle_B\otimes|\sigma_k^2\rangle_C\otimes|\dfrac{1}{\pi}\cos^{-1}{\dfrac{1}{\sigma_k^2}}\rangle_D\otimes \left( \dfrac{1}{\sigma_k^2}|0\rangle_E+\sqrt{1-\left(\dfrac{1}{\sigma_k^2}\right)^2}|1\rangle_E \right) \end{equation} }$

$E$ レジスタを測定し0が観測されたとき、上の状態は次の状態に収縮する。

${\displaystyle \begin{equation} c\sum_{k=1}^r\dfrac{1}{\sigma_k} |{\bf v}_k\rangle_A\otimes|{\bf u}_k\rangle_B\otimes|\sigma_k^2\rangle_C\otimes|\dfrac{1}{\pi}\cos^{-1}{\dfrac{1}{\sigma_k^2}}\rangle_D\otimes |0\rangle_E \end{equation} }$

$c$ は規格化定数

${\displaystyle \begin{equation} c=\dfrac{1}{\sum_k\sigma_k^{-2}} \end{equation} }$

である。各種演算の逆演算を施し $C,D$ レジスタを初期化する。

${\displaystyle \begin{equation} c\sum_{k=1}^r\dfrac{1}{\sigma_k} |{\bf v}_k\rangle_A\otimes|{\bf u}_k\rangle_B\otimes|0\rangle_C\otimes|0\rangle_D\otimes |0\rangle_E \end{equation} }$

$A,B$ レジスタ部分を取り出し、これを $|\psi_1\rangle$ と置く。

${\displaystyle \begin{equation} |\psi_1\rangle=c\sum_{k=1}^r\dfrac{1}{\sigma_k} |{\bf v}_k\rangle_A\otimes|{\bf u}_k\rangle_B \end{equation} }$

ここまでの計算で式(3)を振幅に埋め込んだ状態が得られたことになる。さて、未知データ $\tilde{{\bf x}}$ が与えられたときの出力値 $\tilde{y}$ を計算するため次の状態を用意する。

${\displaystyle \begin{eqnarray} |\psi_2\rangle&=&|\tilde{{\bf x}}\rangle_A\otimes|{\bf y}\rangle_B\\ &=& \sum_{j=1}^M\tilde{x}_j|j\rangle_A\otimes\sum_{i=1}^Ny_i|i\rangle_B \end{eqnarray} }$

内積 $\langle\psi_1|\psi_2\rangle$ を計算すると

${\displaystyle \begin{eqnarray} \langle\psi_1|\psi_2\rangle&=& \left( c\sum_{k=1}^r\dfrac{1}{\sigma_k}\langle{\bf v}_k|_A\otimes\langle{\bf u}_k|_B\right) \left( \sum_{j=1}^M\tilde{x}_j|j\rangle_A\otimes\sum_{i=1}^Ny_i|i\rangle_B \right)\\ &=& c\sum_{k=1}^r\dfrac{1}{\sigma_k} \sum_{j=1}^M \tilde{x}_j \langle{\bf v}_k|_A|j\rangle_A \otimes \sum_{i=1}^Ny_i \langle{\bf u}_k|_B|i\rangle_B\\ &=& c\sum_{k=1}^r\dfrac{1}{\sigma_k} \sum_{j=1}^M v_{jk}\tilde{x}_j \sum_{i=1}^Nu_{ik}y_i \end{eqnarray} }$

を得る。これは式(4)で得た出力値 $\tilde{y}$ を $c$ 倍したものである。 $c$ は求めることができる値なので、内積 $\langle\psi_1|\psi_2\rangle$ を計算できれば、未知データに対する出力を得ることができる。今回は、内積計算の量子アルゴリズムには言及しない。

まとめ

　線形回帰の量子アルゴリズムについて説明した。上の量子位相推定を行う際に $e^{i2\pi\rho_A}$ を $|{\bf v}_k\rangle$ に施す必要がある。このとき、ここで説明したDensity Matrix Exponentiationを利用する。

Tech Blog

勉強したことをまとめます。

量子線形回帰

はじめに

線形回帰

線形回帰の量子アルゴリズム

まとめ

参考文献