Testing my mobile quantum circuit simulator

[Abstract] This article tests the applicability of the mobile quantum circuit simulator Qsim_multi that I have developed so far with MIT App Inventor. As examples, I have taken the inverse Quantum Fourier transform and the order finding problems that appear in a recently published book. These form the basis of Shor's prime factorization algorithm. In conclusion, I have confirmed that my simulator Qsim_multi can handle these problems successfully.

🔴 A new book on quantum computing

Recently, I bought a new book (FIg.1) by Nivio Dos Santos. The title is "How to code for Quantum Computers", but it is not a so-called how-to book, but a compact summary of basic concepts. As soon as you open the book, you get the feeling that something fun is written in it. In the second half, the quantum Fourier transform, quantum phase estimation, and Shor's algorithm calculations are explained in detail. Therefore, I would say that this is a book for beginners to intermediate level.

Although the main text does not include any program code, the Python code (Jupyter Notebook) for the Google Cirq environment is publicly available on the Web, which is useful.

I ran the following two examples from the book on my mobile quantum simulator. However, I noticed something important here. That is the order of the quantum bits. My simulator is the same as IBM Qiskit, but in Cirq, the order is reversed. Therefore, it was necessary to reverse it. However, even if I did that, for example, the results of the quantum Fourier transform would have different phases even if the probabilities of each basis were the same. If you keep that in mind, there is no problem.

🔴 Example1: Using Inverse-QFT

First, here is an example using the inverse quantum Fourier transform. Fig.2 shows the circuit diagram and quantum state consisting of 16 bases explained in this book. The inverse quantum Fourier transform invQFT is shown in its expanded form. The small filled circles in each circle indicate the probability, and the slope of the red line indicates the phase.

The result of converting this to my simulator and running it is shown in Fig. 3. This simulator has a built-in inverse quantum Fourier transform (IQFT), so I used it as is. Comparing the quantum state with Fig. 2, the probability is the same, and the phase is a mirror image. This result shows that my simulator is operating normally.

🔴 Example2: Finding the order of [g^k mod N = 1]

Next, we will look at the order-finding problem, which is important in Shor's algorithm. Here, we find the order of the specific example "7^k mod 15 = 1", that is, the smallest integer k that satisfies this equation.

The quantum circuit and the order discovery results are shown below. Fig. 4 is from the Cirq environment, and Fig. 5 is from my simulator. The measurement results after applying "7^k mod 15 " and invQFT were consistent for both in a 3-qubit system. That is, out of the eight possibilities, only 010, 100, 000, and 110 were measured with equal probability. By approximating the result to a rational number, we obtained 1/4, and found that the order was 4. The details of why we can say this and its relationship to Shor's algorithm are shown below:

　2024年7月9日火曜日

　Shor's Algorithm：量子コンピューティングの学びの最高峰

　https://sparse-dense.blogspot.com/2024/07/shors-algorithm.html

In Fig. 4, the measurement results are shown as the frequency of occurrence in 1000 trials, and in Fog.5 they are shown as probability calculation results.

In addition, in my simulator in Fig. 5, the measured values ​​for the four cases (3-qubit) are divided into four. This is a little difficult to see, so it would be better to summarize it as shown in Fig. 4. I would like to address this in the next version update.

🔴Conclusions
For simple cases of the inverse quantum Fourier transform and the order finding problem, my mobile quantum circuit simulator gave identical results to those run in the Google Cirq environment, confirming the applicability of the simulator to a certain extent.

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

Thank you Nivio for your great response!

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

Shor's Algorithm：量子コンピューティングの学びの最高峰

【要旨】前回、ショアの素因数分解アルゴリズムに親しむための記事をここに書いた。そこでは、概要をつかむのが主目的であったので、最も肝心な位数計算（order-finding）と呼ばれる処理を、ナイーブな古典的計算で済ませた。だが、この位数計算の量子版の理解無しには、ショアを理解したことにはならない。逆に、これを完全に理解できれば、量子コンピューティングの学びの最高峰に達すると言える。なぜなら、そこには、量子計算の重要な要素（量子状態重ね合わせ、量子もつれ、量子位相キックバック、量子フーリエ変換、量子位相推定、測定による波束の収縮、等々）が凝縮されているからである。本記事は、そこへの到達を目指す。

🔴Shor's Algorithmを理解するための参考資料
　まず、知識の源泉がある。解説書は多数あるが、私の場合は、Fig.1に示した６点である。このうち、Nielsen & Chuang[1]は、精緻な叙述で世界的に著名な大作（全676頁）である。Shor's algorithmの発表は1994年だが、本書の第１版は2000年（10周年記念版は2010年）である。その第5章「量子フーリエ変換とその応用」で、位相推定や位数計算が丁寧に説明されている。他にも、随所に計算基礎論に基づく知見が散りばめられている。まさにバイブルである。
　宮野&古澤[2]でも、第５章「ショアのアルゴリズム」の説明が丁寧であり、複雑そうに見える理論計算と具体例の計算をフォローしやすい。厳密に計算を追求したい読者には最適である。
　Bernhardt[3]は、私が量子コンピューティングの基礎を掴むのに徹底して読んだ最初の本である。そこには、ショアのアルゴリズムの詳細は無いのだが、それに大きな影響を与えたと言われるSimon'sアルゴリズムが、厳密かつ簡潔に叙述されていて、感銘を受けたのでここに含めた。

　Wong [4]は、量子アルゴリズムの基礎を幅広く優しく、かなり綿密に解説している。随所に、Niesen & Chuang[1]を参照しながらも、独特の平易な解説に徹している。量子回路シミュレータとして、主に、ビジュアルに優れるQuirkを利用している。
　Barry [5]は、独特の図解で、"why"よりも"how"に重きをおいて説明している。最初に、量子フーリエ変換から入って、coprime power sequenceの周期を求めている。その後、位相推定（および位数計算）を使う方法も説明している。主要な例題の量子回路は、Qiskitコードで示されており、シミュレーションを実行できる。
　最後のFrankharkins [6]は、Shor's factoring（全過程）に特化したQiskitコードの解説である。Jupyter notebook形式になっているので、一歩ずつ理解しながら、シミュレーションを進めることができる。（ただし、これらのコードは、Qiskit 0.x版に準拠している。現在のQiskit 1.x版ではいくつかのエラーが発生して動かなかったが、移行ドキュメントに従い、Qiskit 1.0版用に変換することができた。）

🔴Order finding (Period finding)の実際
　次に位数計算（Order finding）を具体的に検討する。【要旨】に述べた通り、Shor'sアルゴリズムの全体の流れはすでに分かったので、ここでは、Order findingのための量子コンピューティングに焦点を当てる。位数の候補が見つかれば、古典的アルゴリズムによって、目的の整数の素因数が（高い確率で）見つかるのである。

（１）量子位相推定（こちらとこちら）の応用として
　位数rの計算は、量子位相推定の応用であり、量子回路の構成もほぼ同じである。だが、入力とするユニタリ行列の固有状態の設定に注意する必要がある。ここで用いるユニタリ行列Uは以下の式(a)である。これは何なのか？例えば、a=3, N=35の場合、状態 |1⟩に対しては、Uの連続適用結果は、式(b)のようにrを周期として繰り返すことが分かる。ここでは、r=12である。実は式(c)が成り立つ。（証明は略）

　次に、式(d)に示すように、U^k|1⟩の重ね合わせ（superposition）である状態|u₀⟩を考えると、それはUの固有状態であり、その固有値は１であることが分かる。（証明は略すが、上記と同様に、具体的に展開すれば分かる。）
　同様に、式(e)に示す重ね合わせ |u₁⟩は、Uの固有状態であり、その固有値は、e^2πi/rである。さらに一般化した、式(f)に示す重ね合わせ |u_s⟩（sは整数）は、Uの固有状態であり、その固有値は、e^2πis/rである。

（２）量子位相推定回路へ入力する固有状態
　上記を理解できれば、すでに見た位相推定アルゴリズムQPE（Quantum Phase Estimation）によって、あるsについて位相s/rを測定によって得られそうである。しかしながら、それを実現する量子回路への入力となる |u_s⟩は、実はこの時点では作れないので困る。それを解消する方法がある。それは、sについて |u_s⟩の総和（すなわち、重ね合わせ）を取ると途中の位相がキャンセルされ、結果として式(g)の通り、状態が |1⟩になるという事実である！証明は略すが、これが重要！

　QPEへの入力として、この固有状態 |1⟩を与えると、QPEの前段の回路は、（位相）φ = s/rを量子フーリエ変換することになる。したがって、QPEの後段の逆量子フーリエ変換IQFTの結果を測定することで、s/rの近似値が得られる。具体的には、測定結果の古典ビット列（２進小数と見做される）を連分数アルゴリズム（continued fraction algorithm）によって有理数近似（分数表現）する。その分母として、rの候補が得られる。そのrが妥当な位数であれば採用し、そうでなければ、QPEの実行をやり直す。

🔴Order finding (Period finding)の量子回路と実行結果
　以上の検討に基づき、位数計算の量子回路を作り、その実行結果から、最終的に目的の整数を素因数分解することができる。ここでは、（多くの解説書で取り上げられている）極く小さな整数15の素因数分解（15 = 3 x 5）のデモを行う。そのための量子回路がFig.2である。

　この回路は確かに、既に示した位相推定回路とほとんど同じである。ただし、問題設定用のレジスタq₃q₄q₅q₆への入力が、上記式(g)の通り、 |1⟩となっていること、すなわち、量子ビットq₃に対してパウリXゲートが適用されていることに注目されたい。また、q₃q₄q₅q₆へ接続される３つの大きな回路は、以下の回路（7k mod 15）の繰り返しになっている。これは、上記式(a)(b)(c)のユニタリ操作Uに当てはめると考えやすい。

　そして、この回路の実行結果（1,000ショットの測定結果）をFig.3に示した。N=15は、素因数分解したい整数が15であることを意味する。整数a=7に設定しているが、このaはN以下でNと素な整数として選んだ。（最終的にうまく行かなければ、aの値を変更する。）

　この測定結果は、解答レジスタq₂q₁q₀が、４つの値000、010、100、110をほぼ等しい確率で取り、それ以外の値は取らないことを意味する。これらの値を2進小数にして、位相Phaseを計算することができる。（位相推定の場合と同じ方法による。）さらに、その位相を表す小数を、連分数アルゴリズムによって、有理数近似（分数で近似）する。その結果の分母が位数rの候補となる。その値rが妥当な位数であることが確認できれば、（こちらの記事で述べた通り）目的の整数15の素因数を得ることができる。以上の流れをFig.4に示した。

　この測定では、位数rの候補は1、4、２の３つであったが、r=1は妥当な位数ではなく失敗し、r=4の場合は成功している。

🔴感想
　以上の内容を示したことで、Shor'sアルゴリズムの全貌を（ほぼほぼ）把握できたと考える。今回の実行結果は、Qiskitのシミュレータによるものだが、極く小さな整数15の素因数分解に成功した。その要因は、位数計算に成功したことによる。
　しかし、現時点の量子コンピュータ実機では（ここにも示した様に）小規模な回路構成であっても、誤り発生のために、位相推定が、従って、位数計算がうまくできない。すなわち、大きな整数（semi prime）に対しては、現時点の実機ではShor'sをまともに動かせない。
　それにもかかわらず、Shor'sアルゴリズムは量子アルゴリズムの最高峰の一つであることに異論はないはずである。近い将来、完全な量子コンピュータが完成し、Shor'sアルゴリズムが真価を発揮することを期待したい。

🔴追加情報
　MITでは、量子コンピューティング基礎講座「QUANTUM COMPUTING FUNDAMENTALS」という4週間のオンラインコース（＄2,419)を定期的に開催している。その講師に、Prof. Peter Shorが入っている。彼が上記のShor's algorithmを発表したのは1994年（35才）だが、現在もMIT教授として活躍されているようだ。また、参考文献[1]の著者の一人、MITのProf. Isaac Chuangも同じくこのコースの講師となっている。私も受講を考えてはいるが...今回このブログ記事を書いたので、多分、講義内容には何とかついて行けそうな気はする。

References

[1] Michael A. Nielsen and Isaac L. Chuang: Quantum Computation and Quantum Information - 10th Anniversary Edition, Cambridge University Press, 2010 (First published 2000).

[2] 宮野健次郎、古澤明：量子コンピュータ入門第２版、日本評論社、2019(第2版第3刷)

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

https://www.chrisbernhardt.info/

[4] Thomas G. Wong: Introduction to Classical and Quantum Computing, Rooted Grove, 2022.

[5] Barry Burd: Quantum Computing Algorithms -Discover how a little math goes a long way, Packt Publishing, 2023.

https://users.drew.edu/bburd/quantum/

[6] Frank Harkins: Shor's Algorithm

https://github.com/Qiskit/textbook/blob/main/notebooks/ch-algorithms/shor.ipynb