ドイチュのアルゴリズムで量子計算のこころに触れる

【要旨】アルゴリズム、アルゴリズムとよく言いますが、コインの真偽判定に関するドイチュのアルゴリズムは、現在のPC上では考えられません。量子計算に特有の全く不思議なアルゴリズムですが、小生なりに理解した結果を、分かりやすく説明します。（なお、量子ビットの状態、重ね合わせ、もつれ、及び量子ゲートの基礎知識を前提としていますが、ご存じなくても、不思議さは感じていただけると思います。）

このアルゴリズムの拡張版であるドイチュ・ジョサのアルゴリズムについてはこちらに簡単な試行結果があります。

●コインの真偽判定の問題
　コインをトスして何かを決める場合がある。その際、コインが変造されていないかを検査したい。表裏が同一のデザインならば、それは偽物だ。表と裏をそれぞれ見るので、２回の検査を要する。これを２値（０, 1）関数f(x)の適用に置き換えてみる。変数xも0か1をとるとする。コインの最初の検査をf(0)、２回目の検査をf(1)とする。関数値0と1は、それぞれ、QueenエリザベスIIのデザインと裏地のデザインに対応する。そのような関数fとして、図１に示すように、 f1, f2, f3, f4の４種が考えられる。f1と f2は、平衡関数（裏表が異なる）と呼ばれ、f3, f4は定数関数（表裏が同一）と呼ばれる。

●ドイチュのアルゴリズム
　この問題を解く、ドイチュのアルゴリズム（1985年）は、ただ１回のコインの検査だけで済むという。そんなことできるのか？実に不思議だが、それを実現する量子回路が図２に示すものだ。詳細は後で述べるが、まずはそれがどんなものかを見てみよう。

　制御ビットと標的ビットという２つの量子ビットを用意し、それぞれ"|0>"と"|1>"に初期化する。それらにアダマールゲートHを通す。その状態にOracleと呼ばれる判定ゲート適用する。Oracleの中身は、図にあるように排他的論理和をとるだけの単純なものだが、Oracleに入ってくる状態①が、すでに量子特有の重ね合わせ状態となっていて、これが常識では考えにくい作用を起こす元になっている。
　それはともかく、Oracle適用後の制御ビットにさらにアダマールHを適用し、その結果を観測した結果が、"0"ならば定数関数（偽物）であり、"1"ならば平衡関数（本物）だという。繰り返しになるが、Oracleは１回しか通していない。だから、f(x)の計算も１回しかやっていない。それなのに、このような結論が得られるのだ！

●ドイチュのアルゴリズムの実行
　なぜこのアルゴリムでよいのかは後で述べるが、その前に、この回路をQni量子シミュレータで実行して結果を確認する。IBM Quantumの実機でも簡単に実行できるのだが、待ち時間が長すぎるので、今回は保留した。

　図２では、対象の関数として一般的にf(x)としたが、実際には具体的な関数に対応した量子回路をOracleとして設定する必要がある。図３に、上で述べた４種類の関数ごとのOracleを示した。各関数がなぜ、それぞれ図のようなOracle（量子ゲートで構成）になるのかは、青色の数式で示してある。例えば、関数f1は、制御NOTゲート（CNOT）だけでOracleを構成できる。

　それぞれの関数ごとに、図２に示した量子回路の実行結果（最終的な観測結果）は、上で述べたように、平衡関数（本物）、定数関数（偽物）を正しく識別したことが確認できた！

●ドイチュのアルゴリズムの証明
　ここからは、このアルゴリズムが思い通りに働くことを理論的に示す。ここで用いた計算は、渡邉靖志著[1]に従っているが、途中の計算過程もできるだけ省略せずに、独自の説明も加えた。その前に必要となる種々の量子ゲートの働きについては、こちらのブログ記事も参照されたい。また、アダマールゲートHについては、小生自作の図４のブロッホ球の模型もイメージするのに役立つだろう。

　では、図２の量子回路に戻り、アダマールゲート適用後の状態①がどうなるかを、以下の計算で示す。（ケットベクトルや直積の記号が頻出して入力しにくいので、万年筆で手書きした。クリックして拡大してご覧ください。）

　次に、Oracleを通過後の状態②の計算を示す。そして、この状態での制御ビットに再度アダマールゲートHを適用し、それを観測して、関数の均衡、定数を判定できることを明らかにしている。

これで完結した！

●IBM Quantum実機でも実行
　量子コンピュータ実機（IBM Quantum - ibm_nairobi)による結果も得られたので記録しておく。下図は、図３の関数f1に対するものであり、観測結果は93.5%(=958/1024)の確率で、"1"、すなわち、平衡関数だという正しい結果となった。

●感想など

　ここまでで計算上、ドイチュのアルゴリズムを理解できたことになる。しかし、実感としては、いまだに不思議さは拭い去れない。そこでは、量子ビットの重ね合わせ状態が巧みに使われていて、f(0)とf(1)が同時に計算されていることになる。これは、従来の並列処理を想起させるかも知れないが、その仕組みは本質的に異なる。量子コンピューティングのこころに触れることができるアルゴリズムなのである。

謝辞

　この記事を書くに当たって、以下の参考文献を大いに利用させていただいた。[1]からは、量子コンピューティング全般の基本を、理論と例題を通して学ぶことができた。また[2]からは、Qni量子シミュレータを活用したアルゴリズムの実装について学んだ。これらの著者に感謝申し上げたい。

参考文献

[1] 渡邉靖志：入門講義　量子コンピュータ、講談社サイエンティフィック、2021年11月24日初版

[2] 中山茂：量子アプリQni - 量子プログラミング初歩、Gaia教育シリーズ52、2022年8月8日初版