【要旨】量子コンピューティングでの重要な行列（ゲート機能）の一つに、アダマール行列があります。複数の量子ビットシステム（テンソル積）の各量子ビットにアダマール変換を施すための行列が、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を特定するのである。
この質問の回答を、以下で検討する。Fig.4は、Fig.1 case(a)でのψaのフェーズ（２回目のHadamard変換後で測定を行う直前）の4量子ビットシステムの状態ベクトルである。いくつかの計算を経ているが、ここに示されているのは、４qubitsのうちの上段の2qubitsに着目して式を整理した結果である。
Prof. Bernhardtは [1]の中で、このSimon's algorithmにダブルスター⭐️⭐️（かなり難しい）を付している。確かにその通りだが、何度か読み返して検討して、上記のように理解できた。確率振幅の増幅と減衰に関しては、Groverのアルゴリズムではその操作を明示的に行なってるが、Simonでは「知らぬ間にそうなっている」感がある。ともかく、以下の文言を言えれば、Simonアルゴリズムは一応理解できたことになるのではないか。Fig.7参照。
0 件のコメント:
コメントを投稿