量子振幅増幅

はじめに

　今回は量子振幅増幅と呼ばれる手法を解説し、その応用例としてグローバーのアルゴリズムを紹介する。グローバーのアルゴリズムは、ソートされていないデータベースから特定のデータを探索する手法であり、N個のデータに対し\mathcal{O}(\sqrt{N})回の問い合わせで目的とするデータを発見できる。古典コンピュータの場合、ソートされていないデータベースから目的のデータを見つけるには線形探索するしかなく、その問い合わせ回数は\mathcal{O}(N)である。したがって量子コンピュータを用いることで検索速度を加速させることができる。

量子振幅増幅

　本節では量子振幅増幅について説明する。グローバーのアルゴリズムについては次節で解説する。
　n個の量子ビットからなる量子状態|\psi\rangleが次式で与えられているとする。

(1)   \begin{equation*} |\psi\rangle=\sum_{k=0}^{N-1}a_k|k\rangle \end{equation*}

ここで、振幅a_kは複素数である。a_kに対しては次の規格化条件が成り立っている。

(2)   \begin{equation*} \sum_{k=0}^{N-1}|a_k|^2=1 \end{equation*}

例えば、n=2（2量子ビット）のときは次式となる。

(3)   \begin{eqnarray*} |\psi\rangle &=& a_0|0\rangle+a_1|1\rangle+a_2|2\rangle+a_3|3\rangle \\ &=& a_0|00\rangle+a_1|01\rangle+a_2|10\rangle+a_3|11\rangle \end{eqnarray*}

式(3)の2行目の式に見るように量子状態は2進数で表されることに注意する。いまの場合は2ビットの2進数である。また、式(2)より

(4)   \begin{equation*} |a_0|^2+|a_1|^2+|a_2|^2+|a_3|^2=1 \end{equation*}

が成り立つ。量子状態|\psi\rangleを測定したとき、kが測定される確率が|a_k|^2となるのが量子力学の原理であった。
　さて、ある2値関数f(k)\in\{0,1\}が定義されているとき、f(k)=1となる量子状態|k\rangleを検索したい。それを行うため、式(1)の右辺を、f(k)=0を満たす状態|k\rangleとf(k)=1を満たす状態|k\rangleに分ける。

(5)   \begin{eqnarray*} |\psi\rangle&=&\sum_{k=0}^{N-1} a_k |k\rangle \\ &=&\sum_{k:f(k)=0} a_k |k\rangle+\sum_{k:f(k)=1} a_k |k\rangle \\ &=&A\frac{1}{A}\sum_{k:f(k)=0} a_k |k\rangle+B\frac{1}{B}\sum_{k:f(k)=1} a_k |k\rangle \end{eqnarray*}

ここで

(6)   \begin{eqnarray*} A&=&\sqrt{\sum_{k:f(k)=0}|a_k|^2} \\ B&=&\sqrt{\sum_{k:f(k)=1}|a_k|^2} \end{eqnarray*}

とした。いま

(7)   \begin{eqnarray*} |\psi_0\rangle&=&\frac{1}{A}\sum_{k:f(k)=0}a_k|k\rangle \\ |\psi_1\rangle&=&\frac{1}{B}\sum_{k:f(k)=1}a_k|k\rangle \end{eqnarray*}

とし、さらに式(2)から

(8)   \begin{eqnarray*} A&=&\cos\theta \\ B&=&\sin\theta \end{eqnarray*}

と置けることを使うと

(9)   \begin{equation*} |\psi\rangle=\cos\theta|\psi_0\rangle+\sin\theta|\psi_1\rangle \end{equation*}

と書くことができる。2つのベクトル|\psi_0\rangleと|\psi_1\rangleに対し

(10)   \begin{eqnarray*} \langle\psi_0|\psi_0\rangle&=&1 \\ \langle\psi_1|\psi_1\rangle&=&1 \\ \langle\psi_0|\psi_1\rangle&=&0 \end{eqnarray*}

が成り立つことから（\langle x|y\rangleは2つのベクトルの内積を表す）、2つのベクトル|\psi_0\rangle,|\psi_1\rangleが張る2次元ベクトル空間でアルゴリズムを考えることができる。ここでは

(11)   \begin{eqnarray*} |\psi_0\rangle&=& \left( \begin{array}{c} 1 \\ 0 \end{array} \right) \\ |\psi_1\rangle &=& \left( \begin{array}{c} 0 \\ 1 \end{array} \right) \end{eqnarray*}

と置いて考える。いま見つけたいのはf(k)=1となる状態である。つまり、|\psi\rangleの|\psi_1\rangle軸成分である\sin\thetaを増幅させれば良い。増幅の手順は以下の通り（下図参照）。

  1. |\psi\rangle（赤いベクトル）を軸|\psi_0\rangleに関して反転し、S_{\alpha}|\psi\rangle（緑のベクトル）を作る。
  2. S_{\alpha}|\psi\rangle（緑のベクトル）を軸|\psi\rangleに関して反転し、S_{\beta}S_{\alpha}|\psi\rangle（青いベクトル）を作る。

この手順を経ると\thetaは3\thetaに増えるので振幅も\sin{3\theta}に増えることになる。具体的に、演算S_{\alpha},S_{\beta}の中身を見ていく。

　S_{\alpha}の導出：軸|\psi_0\rangleに関する反転なので、|\psi\rangleの|\psi_1\rangle軸成分が反転すればよい。したがって

(12)   \begin{eqnarray*} S_{\alpha}|\psi_0\rangle&=&|\psi_0\rangle\\ S_{\alpha}|\psi_1\rangle&=&-|\psi_1\rangle \end{eqnarray*}

が成り立てばよい。すなわち

(13)   \begin{equation*} S_{\alpha}=\left( \begin{array}{rr} 1 & 0 \\ 0 & -1 \end{array} \right) \end{equation*}

である。

　S_{\beta}の導出：今考えている状態ベクトル|\psi\rangleは次式である。

(14)   \begin{equation*} |\psi\rangle=\cos\theta|\psi_0\rangle+\sin\theta|\psi_1\rangle \end{equation*}

振幅は一般に複素数であることを考慮すると

(15)   \begin{equation*} |\psi\rangle=\cos\theta|\psi_0\rangle+e^{i\phi}\sin\theta|\psi_1\rangle \end{equation*}

と一般化できる（上式において\phi=0とおけば式(14)を得る）。いま

(16)   \begin{eqnarray*} |\psi_0\rangle&=& \left( \begin{array}{c} 1 \\ 0 \end{array} \right) \\ |\psi_1\rangle &=& \left( \begin{array}{c} 0 \\ 1 \end{array} \right) \end{eqnarray*}

としたから

(17)   \begin{equation*} |\psi\rangle= \left( \begin{array}{c} \cos{\theta} \\ e^{i\phi}\sin{\theta} \end{array} \right) \end{equation*}

となる。天下り的であるが、求めるべき行列S_{\beta}は次式となる。

(18)   \begin{eqnarray*} S_{\beta} &=& 2|\psi\rangle\langle\psi|-I \\ &=& \left( \begin{array}{rr} \cos{2\theta} & e^{-i\phi}\sin{2\theta} \\ e^{i\phi}\sin{2\theta} & -\cos{2\theta} \end{array} \right) \end{eqnarray*}

Iは2\times 2の単位行列、|\psi\rangle\langle\psi|は列ベクトルと行ベクトルの積なので行列である。

　以上でS_{\alpha},S_{\beta}が求まったので青色のベクトルは

(19)   \begin{eqnarray*} S_{\beta}S_{\alpha}|\psi\rangle &=& \left( \begin{array}{rr} \cos{2\theta} & e^{-i\phi}\sin{2\theta} \\ e^{i\phi}\sin{2\theta} & -\cos{2\theta} \end{array} \right) \left( \begin{array}{rr} 1 & 0 \\ 0 & -1 \end{array} \right)|\psi\rangle\\ &=& Q|\psi\rangle \end{eqnarray*}

となる。ここで

(20)   \begin{equation*} Q=\left( \begin{array}{rr} \cos{2\theta} & -e^{-i\phi}\sin{2\theta} \\ e^{i\phi}\sin{2\theta} & \cos{2\theta} \end{array} \right) \end{equation*}

である。ここまでの手順を繰り返すことによりさらに振幅を増幅させる。m回繰り返した結果は

(21)   \begin{equation*} Q^m|\psi\rangle=\cos{(2m+1)\theta}\;|\psi_0\rangle+e^{i\phi}\sin{(2m+1)\theta}\;|\psi_1\rangle \end{equation*}

となる（計算は面倒ですが線形代数の基本問題です）。増幅前の状態は

(22)   \begin{equation*} |\psi\rangle=\cos{\theta}\;|\psi_0\rangle+e^{i\phi}\sin{\theta}\;|\psi_1\rangle \end{equation*}

であったから、|\psi_1\rangleの成分が\sin{\theta}から\sin{(2m+1)\theta}に増幅されたことが分かる。以上が量子振幅増幅のアルゴリズムである。

グローバーのアルゴリズム

　上で説明した量子振幅増幅を使い、グローバーのアルゴリズムを説明する。考える問題は以下である。

　n個の量子ビットからなる次の状態を考える。

(23)   \begin{equation*} |\psi_s\rangle=\dfrac{1}{\sqrt{N}}\sum_{k=0}^{N-1}|k\rangle \end{equation*}

ここで、N=2^nである。式(23)の右辺は、n桁の2進数|0\cdots0\rangleから|1\cdots1\rangleまでの状態の重ね合わせである。ある関数f(k)が定義されており、f(k)=1を満たすk=k^*がただ1つ存在する。ほかのkについてはf(k)=0である。状態k^*を見つけよ。

　式(23)の右辺を変形すると

(24)   \begin{equation*} |\psi_s\rangle=\dfrac{1}{\sqrt{N}}\sum_{k\neq k^*}|k\rangle+\dfrac{1}{\sqrt{N}}|k^*\rangle \end{equation*}

　
先と同じ置き換えを行うと

(25)   \begin{eqnarray*} |\psi_1\rangle&=&|k^*\rangle\\ \sin{\theta}&=&\dfrac{1}{\sqrt{N}} \end{eqnarray*}

　
である。\thetaが\pi/2になるまで増幅を行えば、式(24)の右辺の第1項の振幅は0(=\cos{\pi/2})、第2項の振幅は1(=\sin{\pi/2}=1)になる。増幅回数mは以下のように見積もることができる。式(21)より

(26)   \begin{equation*} (2m+1)\theta=\dfrac{\pi}{2} \end{equation*}

したがって

(27)   \begin{equation*} m=\dfrac{\pi}{4\theta}-\dfrac{1}{2} \end{equation*}

となる。いまビット数nが十分大きいとき、N(=2^n)も十分大きくなる。このとき、式(25)の2つ目の式より\sin{\theta}は十分小さくなり、\sin{\theta}\sim\thetaとしてよい。したがって、\theta\sim1/\sqrt{N}と置けるから、m\sim\mathcal{O}(\sqrt{N})となる。すなわち、\mathcal{O}(\sqrt{N})の手間で検索を行うことができる。以上がグローバーのアルゴリズムの内容である。

まとめ

　今回は量子振幅増幅と呼ばれる手法を解説し、その応用例としてグローバーのアルゴリズムを紹介した。グローバーのアルゴリズムは、ソートされていないデータベースから特定のデータを探索する手法であり、N個のデータに対し\mathcal{O}(\sqrt{N})回の問い合わせで目的とするデータを発見できる。古典コンピュータの場合、問い合わせ回数は\mathcal{O}(N)であるから、量子コンピュータを用いることで検索速度を加速させることができる。
　グローバーのアルゴリズムは、誤り耐性あり量子コンピュータ（FTQC）向けのアルゴリズムである。FTQCの実用化にはまだ多くの時間が必要であり、このアルゴリズムがすぐに実用化されることはないことを付記しておく。

参考文献

  • IBM Quantumで学ぶ量子コンピュータ
  • 量子コンピューティング　基本アルゴリズムから量子機械学習まで
  • みんなの量子コンピュータ

    • Kumada Seiya

    Kumada Seiya

    仕事であろうとなかろうと勉強し続ける、その結果”中身”を知ったエンジニアになれる

    最近の記事

    • 関連記事
    • おすすめ記事
    • 特集記事

    アーカイブ

    カテゴリー

    PAGE TOP