2023年10月24日火曜日

Oracle and Amplitude Amplifier in Grover's Quantum Algorithm

[Summary] The Grover search algorithm, which is one of the famous quantum algorithms, has already been discussed in the articles below, so I will not explain its meaning or solution in detail here.
In this article, we will review flipping the sign of probability amplitude and inversion about the mean value. Also includes execution results on the latest IBM quantum computer (127 qubits). The following discussion is based on knowledge gained from reference [1].

●Grover's algorithm quantum circuit
Here we consider the case of 2 qubits (number of qubits n = 2). In addition, one more qubit is used for control. The quantum circuit is shown in Fig.1. For all qubits, we apply a Hadamard gate to create a uniform superposition state as an initial state. Next, configure Oracle F for the target function f. The bit string xy with f(xy)=1 is what is searched. Now, the target is set to xy=10. The function of this Oracle F is to flip the sign of the probability amplitude of the basis |10> corresponding to this target. The probability amplitude of other basis is not changed.

The next gate A inverts the four basis probability amplitudes of the top 2 qubits system about the mean of their values. As a result, only the probability amplitude whose sign was flipped in the preceding Oracle is amplified, and the others are attenuated. By repeating Gate F and Gate A as a set, a specific basis can be measured with a high probability (approximately close to 1.0). That's what you're looking for. This repetition needs to be performed only once when n=2.


●Amplitude Amplification Matrix
Now, if we multiply matrix A shown in the upper right corner of Fig. 1 (diagonal elements are -1 and other elements are 1) by the ket vector whose elements are probability amplitudes', the probability amplitudes will certainly be amplified. We can understand that. This is detailed in Chapter 9 of Reference [1]. But how did we derive this matrix? This is explained using Fig.2. Although we will deal with the case of n=2 here, it will be easier to understand if we consider the general case of n. In short, it takes advantage of the fact that the result of inverting the value p of an element around the average value m of all elements is 2m-p.

●Execution on the IBM Quantum 127 qubits real machine
After making the above preparations, execute the quantum circuit shown in Fig.3. The Oracle F circuit was configured for f(10)=1. Also, the amplitude amplification section (purple Amp gate) that inverts about the average value can be configured with Hadamard gates, X gates, and controlled X gates, but it is also possible to just give the unitary matrix A shown in Fig.2. The latter seems easier to think about.
The execution results are shown in Fig.4. These are the execution results of (a) ibm_lagos with a 7-qubits Falcon processor, (b) ibm_brisbane with a 127-qubits Eagle processor, and (c) ibmq_qsam simulator. First, by the simulator (c), the basis of the target was measured with a probability of 1.0, as in theory.

On the other hand, the error rate of the machine (a)lagos was relatively high, and the target basis was measured with a probability of 0.75, and other basis were also measured slightly. However, with the latest model (b) brisbane, the target basis probability has improved to 0.87. Enough information was obtained to find the desired solution.
●Impressions
Until last year, IBM provided general users with real machines with 5-qubits and 7-qubits for free, but recently they have also made the latest machine with 127-qubits available for free. In fact, in April 2023, there was news [2] that "The University of Tokyo will be the first university outside of North America to install an IBM Eagle 127 quantum bits computer.'' Only half a year later, anyone could use this (presumably) same quantum computer over the web, as mentioned above. Amazing progress in quantum computers!

In principle, 127 qubits have the potential to simultaneously process a huge number of states: 2 to the 127th power (= 10 to the 38th power). Such a machine can now be used from home via the web, so although there are still many challenges to overcome, the dream is growing.

●Words from Prof. Chris Bernhardt
==============================
Dear Fujio,
Another great post! Your site contains really useful information. 
I especially like the fact that you are showing how to do things on the IBM quantum computer.
Chris
==============================
Dear Chris
Thank you very much for reading my blog article.
My introductory quantum computing journey has come to an end.
I was able to achieve this by coming across your wonderful book and fully understanding its contents.
Based on this, I can move on to even higher levels of quantum computing.
Fujio
==============================

References
[1] Chris Bernhardt: Quantum Computing for Everyone, The MIT Press, 2020.
[2] News about the introduction of IBM's 127 qubit computer to the University of Tokyo

時刻: 0 件のコメント:

2023年10月23日月曜日

Groverの量子アルゴリズムにおけるOracleとAmplitude Amplifier

【要旨】著名な量子アルゴリズムの一つであるGrover search algorithmについては、すでに以下の記事で述べていますので、ここではその意味や解法の詳細説明は略します。
今回の記事では、確率振幅の反転と、平均値を中心とした折り返しに関して復習します。最新のIBM量子コンピュータ（127量子ビット）による実行結果も含みます。以下の考察は、参考文献[1]から得た知識に基づいています。

●Groverのアルゴリズムの量子回路
　ここでは2qubits（量子ビット数n=2）の場合を考える。そのほかに、制御用の1qubitを使う。その量子回路をFig.1に示した。全てのqubitsについて、初期状態として均等な重ね合わせ状態を作るため、Hadamardゲートを適用する。次に、対象とする関数fに対してOracle Fを構成する。f(xy)=1となるビット列xyが探索するものである。今はそのターゲットを、xy=10と設定した。このOracleFの機能は、このターゲットに対応するbasis |10>の確率振幅の符号を反転させること（flipping the sign）である。それ以外のbasisの確率振幅は変更しない。

　次のゲートAは、上位の２qubitsシステムの４つのbasisの確率振幅を、それらの値の平均値を中心に反転（inversion about the mean）させる。これによって、前段のOracleで符号反転された確率振幅だけが増幅され、他は減衰することになる。ゲートFとゲートAをセットで繰り返すことによって、（ほぼ1.0に近い）高い確率で特定のbasisが測定されるようになる。それが求めるものである。この繰り返しは、n=2の場合は１回で済む。
●Amplitude Amplification Matrix
　さて、Fig.1の右上に示した行列A（対角要素が-1で他の要素は１）を、「確率振幅を要素とするケットベクトル」に掛ければ、確かに上記の通り、確率振幅が増幅されることが分かる。そのことは、参考文献[1]の第9章に詳しく書かれている。だが、どのようにこの行列を導出したのであろうか？それをFig.2で説明する。ここではn=2の場合を扱うのだが、一般のnに対して考察した方が分かり易い。要は、要素の値aを要素全体の平均値mの周りに反転させた結果は、2m-aとなることを利用しているのである。
●Execution on the IBM Quantum 127 qubits real machine
　以上の準備をしてFig.3に示した量子回路を実行する。Oracle Fの回路は、f(10)=1に対して構成した。また、平均値で折り返す振幅増幅部（紫色のAmpというゲート）は、Hadamardゲート、Xゲート、制御付きXゲートで構成することもできるが、Fig.2で示したユニタリ行列Aをそのまま与えることもできる。後者の方が、考え易いように思われる。
　その実行結果をFig.4に示す。(a)7-qubits Falconプロセッサのibm_lagos、(b)127-qubits Eagleプロセッサのibm_brisbane、(c)ibmq_qsam simulatorの実行結果である。まず、(c)のシミュレータでは、ターゲットのbasisが理論通り、確率1.0で測定された。
　一方、実機(a)lagosのエラー発生率は比較的高く、ターゲットのbasisは確率0.75で測定され、他のbasisも若干測定された。だが、最新機(b)brisbaneでは、ターゲットのbasisの確率は0.87まで向上した。目的の解を求めるには十分な情報が得られた。
●感想
　昨年までは、IBMは一般ユーザに5-qubitsおよび7-qubitsのリアルマシンを無償提供していたが、最近、実に127-qubitsという最新マシンも、無料で使えるようにした。実は、2023年４月に、「北米以外で初めて、東大にIBM Eagle 127量子ビットコンピュータを導入」のニュース[2]があった。それから僅か半年で、これと（恐らく）同じ量子コンピュータを、上記の通り、誰でもwebから使えるようになったのである。驚くべき、量子コンピュータの進歩である！
　127量子ビットは、原理的には、2の127乗(=10の38乗)個の状態を同時に処理できる可能性を秘めている。アルゴリズムの発案次第である。そんなマシンを、今や、自宅からweb経由で利用できるのであるから、まだまだ課題は山積ではあるが、夢は膨らむ。

●Prof. Chris Bernhardtからのコメント
（英語版記事はこちら）
==============================
Dear Fujio,
Another great post! Your site contains really useful information. 
I especially like the fact that you are showing how to do things on the IBM quantum computer.
Chris
==============================
Dear Chris
Thank you very much for reading my blog article.
My introductory quantum computing journey has come to an end.
I was able to achieve this by coming across your wonderful book and fully understanding its contents.
Based on this, I can move on to even higher levels of quantum computing.
Fujio
==============================

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

[2] 東大にIBMの127量子ビットコンピュータ導入のニュース


時刻: 0 件のコメント:

2023年10月6日金曜日

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.

時刻: 0 件のコメント: