Simonの記念碑的量子アルゴリズム

【要旨】Simonの量子アルゴリズム（by Daniel R. Simon, 1994）は、従来アルゴリズムではデータサイズに対して指数関数的に計算量が増大するある問題を、量子計算によって線形 (+α)オーダーの計算量で解けることを示した記念碑的なものである。その詳細は参考文献[1]にあるが、著者Prof. Chris Bernhardtはこれに、難度☆☆（ダブルスター）を付け、非常に難しいとしている。しかしながら、彼は、難しい仕組みも巧みに整理して可能な限り簡単化し、かつ、数式を使った厳密性を維持し、高校数学レベルで分かるように叙述している。そのため、じっくり読むことで具体的に理解することができた。本記事では、アルゴリズムの詳細は略すが、その結果として何が出力され、それが何を意味するかを、小生の理解に立って纏めた。さらに、量子回路シミュレータ[2]でその働きを確認した。

●Simonのアルゴリズムが解く問題

　対象とする問題を示す。長さnのbinary string（0か1の羅列）を入力とし、出力も長さnのbinary stringである関数fがあるとする。ここで、あるsecret binary string（秘密のbinary string）b があり、(y=x or y=x⊕b) の時に限りf(x)=f(y) となる。ただし、bの全ての文字が0であることは無いとする。記号⊕は、bitwise addition of strings modulo 2の意味である。入力xに対する関数値f(x)を問い合わせることはできるが、関数fの定義内容と秘密のbが何かは与えられていない。このような関数fが与えられた場合に、解くべきことは、bを特定することである。

　秘密のbを知るには、x≠yでありf(x)=f(y)となるxとyを見つける必要がある。そこに至るまでに何回関数fを評価する必要があるのか、それが問題である。古典的方法で、2ⁿ個の入力について関数値を問い合わせた場合、連続して半分の関数値が全て異なるかも知れない。この場合は、さらに別の入力１個の関数値を知る必要がある。すなわち、最悪ケースでは、2^n-1+1回の関数評価が必要となる。

●Simonの量子アルゴリズムの説明

　この問題に対するSimonの量子アルゴリズムの詳細は参考文献[1]にあるが、難度☆☆（ダブルスター）が付されており非常に難しいように見える。しかしながら、この著者は、難しい仕組みも巧みに整理して可能な限り簡単化し、高校数学レベルで分かるように叙述している。その上で、数式を使った厳密性を維持している。特に、Hadamard(アダマール)行列のKronecker Productを利用した簡潔な説明は実に見事、というほかない。図２にその箇所を引用した。

●Simonの量子アルゴリズムを実現する量子回路

　上述の通りなので、ここにアルゴリズムの詳細を述べることは避ける。したがって、それを実現する量子回路がなぜ図２のようになるかは略すが、結論をまとめる。上段がOracleである。Oracleとは、問い合わせに答える機能一般に使われる呼称であり、１回の問い合わせにおいて、この中で着目関数fを１回評価する。

　Oracleには、量子状態 |0⟩と|1⟩からなる長さnの２つのstringsが入力される。上段の入力は変わらないが、下段の出力は、上段の入力に対して関数fを評価した値と下段の入力との⊕ (bitwise addition modulo 2)となる。このOracleを、図の下側のように利用するのだが、Oracleの左右で、上段の各入力に対してHadamard変換を施すのがポイントである。その後に上段を測定すると、いくつかのn次元の縦ベクトルが得られる。

　この測定結果の縦ベクトルをstringsと見做し、それと秘密のbとのdot product (・)を取るとその結果が、どの縦ベクトルに関しても 0（ゼロ）となる。そのように設計されているのである！素晴らしい発想に基づく結果なのである！これは、秘密stringの要素に関する一次方程式を与えることになる。測定結果がこのように与える各一次方程式を連立させて（古典的方法で）解くことで、最終的にbを決定できる。（dot productの意味は図3下部を参照願いたい。）

●量子/古典アルゴリズムの連携

　繰り返しになるが、重要な点なので再度記しておきたい。図２の量子回路は、秘密stringの要素に関する線形方程式を出力すると言える。解を得るために必要な線形独立な方程式が出揃うまで、この回路を繰り返し実行する必要がある。それが揃えば、ガウス消去法などの古典的解法を用いて解を求め、bを決定できる。すなわち、量子と古典のアルゴリズムの連携で成り立つ。これと似た状況が、古典通信と連携する量子テレポーションや超高密度符号化においても見られたのは興味深い。

●Simonの量子アルゴリズムをシミュレータで確認する

　具体例を量子回路シミュレータQniを利用して確認する。図３ではn=3で、秘密string b=110の関数fに対するOracle Fを作成した。もちろん、この量子回路を使用する側は、bの値は知らない。これをOracleとするシミュレーションを実行すると、右上示した４通りのパタンがそれぞれほぼ1/4の確率で出現することが確認できた。

　最初の実行で001が得られ、２回目で111が得られた場合の連立一次方程式とその解を図の下部に示した。（回路図での上方のビットが、stringにした場合は下位になっている。）この場合は、２回のOracleへの問い合わせで、秘密string b=110を特定できることが確認された。

●計算の複雑度（Complexity Analysis）

　このような量子回路を何度実行しても（確率の世界ゆえ）bに関する線形独立な方程式が揃わないことは皆無とは言えない。つまり、量子アルゴリズムが古典アルゴリズムよりも遅くなる状況も有り得る。しかしながら、そのようなケースは極めて稀と考えられる。そこで、BQP (for bounded-error Quantum polynomial time)という考え方がある。つまり、データサイズnに依らない定数Nを決め、うまく行かないケースの確率が(1/2)^N以下ならばそれを許容（除外）しようとするものである。

　詳細は略すが、Simonの量子アルゴリズムでは、適切に決めたNによるerror boundの元では、(n+N) 回のOracle呼び出しで必要な一次独立な線形方程式が揃う。Nはnによらないので、線形の回数での達成となる。それに加えて、古典的方法により、出揃った一次独立な線形方程式をn²のオーダーで解く。（なお、一般の連立一次方程式の解法はn³のオーダーだが、Simonの場合は、変数が全て0か１であり、さらに、秘密string bがオール0ではないことが効いている。）

●感想

　このSimonのアルゴリズムは、素因数分解で有名なショアのアルゴリズムに大きな影響を与えたとのことである。この書[1]の最後の章にはそれが説明されている。Simonのアルゴリズムの量子回路で説明した、秘密stringの要素に関する線形方程式の生成（出力）は、２つの波の干渉のように、確率振幅を増幅させたり、キャンセルで減衰させたりする制御を含んでいる。真に量子計算の真髄に触れることができるものだ感じる。

References

[1] Chris Bernhardt, “Quantum Computing for Everyone”, MIT Press, 2020 

      https://www.chrisbernhardt.info/

[2] Qni; https://github.com/qniapp/qni