Grover Algorithm

近年，量子情報理論と機械学習の融合領域として量子機械学習という分野が形成されつつある．従来量子情報理論で親しまれてきたアダマール変換や量子フーリエ変換，Deutsch-Josza，Groverといった基本量子アルゴリズムが実際の量子コンピュータで動作させられる量子BLASという基本パッケージでfunction化され，今後異分野の研究者や企業の技術者が参入しやすいよう環境整備が整いつつある．
そこで，この機会に筆者の過去の仕事ともゆかりが深いGroverの量子アルゴリズムについて振り返ってみたい．
　Groverの量子アルゴリズムは振幅の等しいN個の量子状態から出発する．ある波動関数の量子状態の基底を記号|j>(j=1,2,...,N)で表し，一つの量子状態をファイルとみなし，N個の量子状態をN個のファイルとみる．波動関数は異なる異なる基底の重ねあわせで任意の状態を表現できる．N個のファイルが重ね合わさった状態は次のようになる．
　$$|s>=\frac{1}{\sqrt{N}}|1>+\frac{1}{\sqrt{N}}|2>+...+\frac{1}{\sqrt{N}}|N>$$
　以下は話を簡単にするために4個のファイルで以下の議論を進めてみよう．始状態|s>はとなるこれを行列表示で書くと次のようになる．

$$|s>=\frac{1}{\sqrt{4}}\left[\begin{array}{c}1\\ 0\\ 0\\ 0\end{array}\right]+\frac{1}{\sqrt{4}}\left[\begin{array}{c}0\\ 1\\ 0\\ 0\end{array}\right]+\frac{1}{\sqrt{4}}\left[\begin{array}{c}0\\ 0\\ 1\\ 0\end{array}\right]+\frac{1}{\sqrt{4}}\left[\begin{array}{c}0\\ 0\\ 0\\ 1\end{array}\right]$$
　Groverのアルゴリズムはこの4つのファイルのうちの1つのファイルの位相を反転させる．波動関数の位相という点が，古典計算機にはない概念である．ここでは二つ目のファイル|2>の位相を反転してみよう．位相反転を施す演算子はUtとかかれる．
$$Ut=\begin{array}{r}\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& -1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\end{array}\right)\end{array}$$
　位相反転演算子を始状態に作用させると次のようになる．
$$|t>=Ut|s>=\frac{1}{\sqrt{4}}\left[\begin{array}{c}1\\ -1\\ 1\\ 1\end{array}\right]$$
　次に始状態の平均に対する反転演算を考える．平均に対する反転演算は次のようになる．
$$Us=I-2|s><かけない$$
　したがって，4ファイル問題の場合次のようになる．
$$Us=\frac{1}{2}\begin{array}{r}\left(\begin{array}{cccc}1& -1& -1& -1\\ -1& 1& -1& -1\\ -1& -1& 1& -1\\ -1& -1& -1& 1\end{array}\right)\end{array}$$
　この平均反転演算を状態|t>に作用させると次のようになる．
$$|g>=Us|t>=$$
$$|t>=Ut|s>=\frac{1}{\sqrt{4}}\left[\begin{array}{c}0\\ -4\\ 0\\ 0\end{array}\right]=\left[\begin{array}{c}0\\ -1\\ 0\\ 0\end{array}\right]$$
　以上となり，位相反転したファイル以外の振幅が0となる．あとは量子計算機のファイル読込み観測操作をおこなえば振幅が1となるファイルが探し出せる．
　Groverの量子アルゴリズムはファイル探索問題に使えるといわれている．通常の線形探索ではファイル数に対し計算量がO(n)かかる．Groverのアルゴリズムは先の計算例でみるように$$O(\sqrt{n})$$で　よい(先の例ではn=4なのでUt,Usの2ステップでおわる)．したがって，様々なアルゴリズムで必須の探索が容易になることが期待されている．また量子状態の振幅変化をもたらすアルゴリズムであるので，その特性を活かして量子機械学習の基礎アルゴリズムとして活躍が期待されている．