アダマール変換のアニメーション

---------（その後、Bell回路についても同様の考察をここに書きました。）--------

🔴目 的

　量子ゲートは、一部の例外を除き、ユニタリ演算（行列演算）である。量子コンピュータでは、それはどのように実現されるのだろうか。詳細レベルでそれを示すことはできないが、シュレディンガー方程式 (Schrödinger Equation)を利用すれば、その動作の流れが分かる。ここでは、最も重要な量子ゲートの一つであるアダマール(Hadamard)ゲートを例として、その動作をアニメーションで確かめてみよう。

🔴アダマールゲート

　アダマールゲートHの適用効果は、量子シミュレータや実機で見ることができる。例えば、量子の初期状態が北極の状態 |0> であるとする。それに対するアダマールゲートの適用とは、Fig.1に示した行列Hを初期状態ベクトルに掛けることである。その結果 H|0> は、ブロッホ球の赤道とX軸の正方向の交点で表される、|0>と|1>の均等な重ね合わせ状態となる。その操作は一瞬の出来事のように見える。だが、そこへ至る経過を観察してみよう。

🔴ハミルトニアンの時間発展

　実は、時間依存シュレディンガー方程式に基づいて、以下のことが広く知られている。

「量子ゲートの機能は、量子状態をある規則に従って一定時間だけ変化させることで実現される。」

　この「状態の変化の規則」を決めるのがハミルトニアンHamiltonianである。量子ゲートの世界では、量子状態の変化は、量子をある回転軸で回転させることで生ずる。その回転軸と回転の強さ（回転速度）の情報をハミルトニアンに持たせている。そして、一定時間Tは、T= π/Ωという値で決まる。このΩは、システムの駆動強度に対応する角周波数（ラジアン毎秒）である。従って、Ωの値が非常に大きければ、量子ゲートの動作は一瞬にして終わることになる。それでは、次に、この時間Tに至るまでの動作アニメーションを見てみよう。

🔴ハミルトニアンの時間発展に伴う量子状態変化のアニメーション

　上記の時間Tまでの量子状態の変化を示そう。Fig.2は初期状態 |0> の場合であり、Fig.3は |+> の場合である。例えば、<σ_x>は、刻々変動する量子状態におけるパウリ演算子σ_xの期待値（測定される固有値の平均）を意味するが、実際には、ブロッホ球上のx座標値と考えて良い。<σ_y>, <σ_z>についても同様である。

　Hamiltonian(注1)の式の右辺にある(σ_x + σ_z)/√2は、パウリ演算子だが実はベクトルとみなすことができ（(注1), (注2)）、回転軸の方向を指している。Fig.2では、x座標は0→1へ、z座標は1→0へ変動している。σ_yはハミルトニアンの式には現れないが、y座標も変動している。

Fig.2 Changes in x, y, and z coordinates when applying the Hadamard gate to the initial state |0>

Fig.3 Changes in x, y, and z coordinates when applying the Hadamard gate to the initial state |+>

　Fig.4は、Fig.2とFig.3の結果をブロッホ球上に表示したものである。これにより、アダマールゲートとは、x軸とz軸の中間45度の傾き方向を軸として、反時計回りにπ（180度）だけ回転させる機能であることが確認できた。繰り返しになるが、それは、時間発展をT=π/Ω進めた時点での状態となる。なお、回転軸を示す、大文字のX, Yはそれぞれパウリ演算子σ_xとσ_zに対応する。

Fig. 4 Display of Fig. 2 and Fig. 3 on the Bloch sphere

--------------------------

（注1）少し紛らわしいが、ここでは、アダマールゲートをHとし、ハミルトニアンはHの上にハット記号を載せている。

（注2）期待値 <σ_x> = <ψ|σ_x|ψ>は、ブロッホ球上での量子状態 |ψ> のx軸方向の成分を表す。

（注3）パウリ演算子σ_x（行列）は、ブロッホ球のx軸方向の単位ベクトルでもある。これは少し紛らわしいが、量子力学では常用されていることである。

（注4）ここでは、換算プランク定数を1とする、自然単位系をつかうとする。

（注5) Fig.1は、MIT App Inventorで作られた量子回路シミュレータである。また、Fig.2〜Fig.4のアニメーションはChatGPTを利用して作成した。

Simonの量子アルゴリズムとHadamard行列のKronecker積

【要旨】量子コンピューティングでの重要な行列（ゲート機能）の一つに、アダマール行列があります。複数の量子ビットシステム（テンソル積）の各量子ビットにアダマール変換を施すための行列が、Kronecker Products of Hadamard Matrices（アダマール行列のクロネッカー積） です。記念碑的解法として有名なSimonの量子アルゴリズムにも有効に使われています。それは、参考文献[1]で丁寧に説明されているのですが、時間が経つと忘れてしまうので、私自身の理解をメモとして残して置きます。

■Simon's Algorithm
　まず、ここで解くべき問題については既に本ブログ（2022-12-11の記事）に書いたので、以下に極く簡単に記す：

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

　そのために、関数fを何回評価する必要があるかを問題とする。古典的アルゴリズムでは、最悪の場合、2のn乗のオーダーの関数呼び出し回数となるが、Simonの量子アルゴリズムではnの多項式オーダーとなる。しかし、この言い方はあまり正確ではない。計算量に関する、BQP（Bounded-error Quantum Polynomial-time）などの議論を、Prof. Bernhardtの書籍[1]のChapter 8 （pp.166-170）等でご覧いただく必要がある。

■Simon's Algorithmを実装する量子回路
　Simonの問題は、上記の関数fと秘密のsを知っている人が作成した問題を解く、いわばリバースエンジニアリングである。実用的な問題ではないにも拘らず、これに対するSimonの解法は、量子アルゴリズムの威力を示すものとして広く認められている。そのための量子回路を、n=2とn=3の場合について検討するが、その方法は一般のnについても自然に当てはめることができる。この量子回路の出力であるいくつかのbinary string（長さn）から、秘密のsを特定するための連立一次方程式を作ることができる。なぜかと言うと、出力されたbinary string bと秘密のsとのdot product（後述）が0になるからである。以下に、このようなdot productがなぜ0になるかを中心に、図を使って詳しく述べる。

　Fig.1は、n=2とn=3の場合のSimonのアルゴリズムを実装した量子回路である。上述の通り、関数fに対するOracleが設定されている。すなわち、関数fの定義と秘密のsがこのように決められているのだが、回答する人はそれを知らずにsを特定するのである。

　一般のnに対してのSimonの量子回路は、Fig.2のように描ける。

　さて、Fig.3は、Fig.1でのn=2とn=3の場合の量子回路の実行結果である。２段になっているレジスタの１段目を測定した結果をFig.3に示した。n=2の問題では測定結果としてbinary string 00と10がそれぞれ1/2の確率で得られた。これらのbinary stringと秘密のsとのdot productsは0となる。そうすれば、それらから連立一次方程式を作ってsを特定できのだが、この部分に関しては既に述べたので、ここでは省略する。以降では、なぜ、このdot productsが0になるのかを考察する。

■測定結果のbinary stringと秘密のsとのdot productsがなぜ0になるのか
　この質問の回答を、以下で検討する。Fig.4は、Fig.1 case(a)でのψaのフェーズ（２回目のHadamard変換後で測定を行う直前）の4量子ビットシステムの状態ベクトルである。いくつかの計算を経ているが、ここに示されているのは、４qubitsのうちの上段の2qubitsに着目して式を整理した結果である。

　テンソル積の左側が|10>（測定結果10に対応）である項の関数fの値に注目する。秘密sに関するペアのbit string（00と01、および10と11）に対する関数fの値は同一であるが、それらの符号（プラス、マイナス）も同一である。もう一つの測定結果|00>についても同様である。

　一方、測定結果に現れない|01>と|11>に関しては、これらのペアの間数値の符号が互いに反転している。そのため、最終的な計算結果として、|00>と|10>の確率振幅が増大され、|01>と|11>に関しては減衰（キャンセル）されて０となった。

　このような増幅と減衰が、「測定結果のbit stringと秘密のsとのdot podurct (・)」とどのように関係しているかを、Fig.5で明らかにしている。

　以上で説明を終わるのだが、最後に、Fig.6をご覧いただきたい。ここに、Hadamard行列のKronecker積がある。たとえば、n=2の場合の行列を見ると、その各要素の符号は、Fig.4で示した項の符号と完全に合致している。すなわち、Fig.4でのテンソル積の左側のqubitのペアを行ラベルとし、関数fの引数に与えるqubitの組みを列ラベルと考えれば、Hadamard行列の該当要素の符号が（マイナス１に対してのdot productの冪乗で）直ちに計算できるのである。むしろ、Fig.4でのテンソル積の右側に出現する項の符号は、このHadamard行列から決められるのである。ここに、Kronecker products of Hadamard matricesの重要性がある。

■まとめ
　Prof. Bernhardtは [1]の中で、このSimon's algorithmにダブルスター⭐️⭐️（かなり難しい）を付している。確かにその通りだが、何度か読み返して検討して、上記のように理解できた。確率振幅の増幅と減衰に関しては、Groverのアルゴリズムではその操作を明示的に行なってるが、Simonでは「知らぬ間にそうなっている」感がある。ともかく、以下の文言を言えれば、Simonアルゴリズムは一応理解できたことになるのではないか。Fig.7参照。

「Simonの量子回路での全ての測定結果（行ラベル）について、秘密sでペアとなるbinary string（列ラベル）が示すHadamard行列の要素の符号は互いに一致する」

　Simonのアルゴリズムは、有名なShorの因数分解アルゴリズムに影響を与えたことが[1]に具体的に説明されている。その叙述から、Shor's algorithmの"こころ"をつかむことができると思う。ただし、もちろん、その詳細を知るには、量子フーリエ変換などの進んだ数学が必要になるので、改めてじっくり取り組みたいと思う。

 Reference

 [1] Chris Bernhardt: Quantum Computing for Everyone, The MIT Press, 2020.

https://www.chrisbernhardt.info/

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