sparse-dense by FoYo: 初級量子コンピューティングの旅の目的地Grover

【要旨】初級量子コンピューティングの旅を２ヶ月ほど続けてきたが、ようやくその目的地Grover（グローバーアルゴリズム）に達した。旅の魅力は尽きないが、次の出発に向けて、ここでひと息とする。グローバー探索アルゴリズムは、ショアの因数分解アルゴリズムと並んで、量子の性質を巧みに利用した傑作である。量子の概念と量子ビット/ゲート/回路の基礎を学んだ後に、このアルゴリズムをIBM Quautum実機で確かめることができた。（→ 一連の旅の日記はこの記事の末尾を参照されたい。）

■今回の記事で何をしたいのか

　グローバー探索アルゴリズムを簡単な例で実装するのだが、まず、その狙いを説明する。図１にあるように、整列されていない電話番号簿（小学校名-電話番号）がある。例えば、電話番号241-7312の小学校名を知りたい場合、普通は順番に一件一件、名簿を調べていくだろう。しかし、グローバーは、これと全く異なり、名簿の全ての項目を重ね合わせた状態にして、一度に問い合わせることができる。ただし、精度を上げるために、項目数をNとした場合、√N回の問い合わせを行う。従来の探索では平均N/2回の問い合わせが必要なので、Nが巨大になれば、グローバーの優位性は顕著になるだろう。

　本記事では、グローバーアルゴリズムを量子コンピュータ実機で動かして観察する都合上、扱う電話番号簿は図1右下のように、僅か４項目に縮小して、電話番号 "11" の小学校名を探すという、簡単な例題とした。

■グローバー探索アルゴリズムの概要

　ロブ・グローバーによって1996年に発表された探索アルゴリズは、「振幅増幅法」という量子特有の性質を利用したものである。図２にあるように、ステップ(1)として、N個（今回N=4）のデータに対応した量子状態ベクトルを用意し、全状態ベクトルの確率振幅が等しい重ね合わせ状態を作ることから始める。

　次に、ステップ(2)として、探索したい項目番号（今回は"11"）の状態ベクトルの確率振幅を位相反転させる。（マイナスの振幅となる。）これは、探したいものにマーキングすることになる。ここで誤解しやすいのだが、「マーキングしたらもう解は分かっているのじゃないのか」と言うかも知れないが、それは違う。解はこの時点で分かっていない。問い合わせたある小学校の電話番号が、マーキングされたものと一致するかを判定するために使うのだ。

　続いてステップ(3)はまさに、振幅増幅である。ステップ(2)でターゲットにマーキングはしたが、振幅の位相が反転しただけであり、依然として全状態ベクトルの確率振幅の大きさは揃っていて見分けがつかない。そこで、全確率振幅の平均値周りに、全確率振幅を反転させる。すると、ターゲットの確率振幅だけが大きくなる。すなわち、それが解に対応する。ただし、他の状態ベクトルの確率振幅もまだ相当大きいかも知れないので、ステップ(2)とステップ(3)を何度か繰り返すことによって、ターゲットの確率振幅の大きさを際立せるのである。

■グローバー探索アルゴリズムを実現する量子回路

　このアルゴリズムを実現する量子回路は種々考えられるが、図３はその一例である。それは、アダマールゲート（H）、パウリXゲート（丸の中に+）、CNOT（制御付きNOT）で構成されている。それらのゲートの働きは学んで来たので、この回路の動作を把握することはそれほど難しくない。また、IBM QuantumのComoserでこの回路を作る場合、Investigatorにより、各ゲートを通過した後の状態ベクトルの確率振幅と位相の状況がシミュレーションで表示されるので、理解の助けとなる。

■IBM Quantum実機による実行結果

　この量子回路をIBM Quantum実機（５量子ビット構成のmanila機）での実行結果は図４のとおりである。図２でのシミュレーションでは、"11"だけが観測されたが、現状の実機では、種々のノイズによる誤差がどうしても含まれるため、他の"01"、"10"なども若干出現しているが、"11"はダントツに出現頻度が高いので問題ではない。

　さて、念の為、この結果を見方を述べておく。この例では、"11"、すなわち、0番から初めて３番目（電話番号簿では上から４番目）の「香川小学校」が正解であるということである。

　そして、繰り返しになるが、この例では、４件の候補の小学校のうちの正解校をただ１回の問い合わせだけで得ることができたのである。

　今回の記事では、以下の参考資料[1][2][3][4]を参考にさせていただいた。特に、武田俊太郎著[2]から学んだ「量子の波の性質を使って複数のパタンを並列に計算し、波と波をうまく干渉させて正しいパターンだけに絞り込んでいく」という、量子コンピュータだからこそできる芸当を見ることができた。

■これまでの初級量子コンピュータの旅の日記

　量子アニーリング以外の量子コンピューテング（ゲート型）を学んできた際に記した日記（ブログ記事）を以下に列挙しておきたい。

(11) 初級量子コンピュータの旅の目的地Grover（この記事）

(10) 量子もつれをIBM Quantum実機で体験

(9) もう一つブロッホ球の模型-Hadamardゲート

(8) 光に関する理科実験の量子力学的解釈

(7) アートとしての量子状態ベクトル模型

(6) 量子ビットの重ね合わせ状態を表すマスコット(Version2)

(5) 夏休みにもう少し本格的に量子コンピュータを学ぶ

(4) 量子コンピューティング国際会議Q2B22 Tokyo参加レポート(続)

(3) 量子コンピューティング国際会議Q2B22 Tokyo参加レポート

(2) IBM Quantumで量子機械学習（MLBの5,000投球）を試す