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!

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

自作モバイル量子回路シミュレータのテスト

【要旨】本稿は、これまでに自作したモバイル量子回路シミュレータQsim_multiの適用性をテストするものである。例題として、最近発刊されたある書籍に載っている、逆量子フーリエ変換と位数発見問題を取り上げた。これらは、Shorの素因数分解アルゴリズムの根幹を成している。結論として、自作シミュレータQsim_multiがこれらを正常に処理できることを確認できた。

🔴 A new book on quantum computing

　最近、Nivio Dos Santos著の新刊（FIg.1）を購入した。タイトルは、"How to code for Quantum Computers"となっているが、いわゆるハウツー本ではなく、基本概念がコンパクトにまとめられている。本を開いたとたんに、何か楽しいことが書いてある、という雰囲気がある。後半には、量子フーリエ変換、量子位相推定、Shorのアルゴリズムの計算が詳細に説明されている。だから、初級から中級レベルの本だと言える。

　本文には、プログラムコードはほとんど出てこないが、Google Cirq環境用のPythonコード（Jupyter Notebook）がWeb上に公開されているので重宝する。

　この本に掲載されている以下の二つの例題を、私の自作モバイル量子シミュレータで稼働させるのである。だが、ここで重要なことに気づいた。それは、量子ビットの並べ順である。私のシミュレータは、IBM Qiskitなどと同じだが、Cirqでは、それが逆順になっているのである。したがって、それを逆転させる必要があった。しかし、そうしても、例えば、量子フーリエ変換の結果などは、各基底の確率は同一になっても、位相は異なるだろう。それを踏まえて扱えば問題ない。

🔴 Example1: Using Inverse-QFT

　まず、逆量子フーリエ変換を使う例である。Fig.2はこの書籍で説明されている回路図と16個の基底からなる量子状態である。逆量子フーリエ変換invQFTは展開形で示されている。それぞれの円内の塗り潰した小さな円は確率を示し、赤い直線の傾きは位相を示す。

　これを私のシミュレータ用に変換して実行した結果をFig.3に示す。このシミュレータには、逆量子フーリエ変換IQFTを内蔵しているので、それをそのまま使った。量子状態をFig.2と比較すると、確率は同じであり、位相は鏡像反転している。この結果から、私のシミュレータは、正常に稼働していることが分かる。

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

　次に、Shorのアルゴリズムで重要な位数発見問題である。ここでは、具体例「7^k mod 15 = 1」の位数、すなわち、この式を満たす最小の整数kを求める。

　量子回路と位数発見結果を以下に示す。Fig.4はCirq環境であり、Fig.5は私のシミュレータによる。「7^k mod 15 」とinvQFTの適用後の測定結果は、3-qubitシステムにおいて、両者で一致した。すなわち、８個の可能性のうち、010、100、000、110の四つだけが、それぞれ等しい確率で測定される。その結果を有理数近似して1/4が得られ、位数が４であることがわかった。なぜそう言えるのかの詳細と、Shorのアルゴリズムとの関係は以下に示されている：

　2024年7月9日火曜日

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

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

　Fig.4では、測定結果は、1000回試行おける出現頻度で示してあり、Fog.5では確率計算結果として示している。

　なお、Fig.5の私のシミュレータでは、測定した4ケース（3-qubit）の値が、それぞれ四つに分かれている。これは少し見にくいので、Fig4.のようにまとめた方が良い。次回のバージョンアップの際に対処したい。

🔴結論

　逆量子フーリエ変換と位数発見問題の簡単な場合について、私のモバイル量子回路シミュレータは、Google Cirq環境で実行されたのと同一の結果を与えた。一定の適用性を確認できたと考える。

量子位相推定(Quantum Phase Estimation)-計算例

【要旨】前回の記事では、量子位相推定の理論と計算法の詳細を示した。今回は、簡単な例でその計算を 確認する。すでに書いたかもしれないが、量子位相推定は、Shor's素因数分解アルゴリズムの中核でもある。

🔴量子位相推定回路の一般形
　前回記事で述べた量子位相推定のための回路の一般形をFig.1に再掲する。図の下部に、m-qubitのユニタリ行列Uの固有状態|v>を与えている。それに対して、上部では、前半でn-qubitを使って、制御付きUゲートの繰り返しを構成し、後半で逆量子フーリエ変換IQFTを適用する。最後にn-qubit全体を測定する。詳細は、前回記事をご覧いただきたい。

🔴位相シフトゲートP(2π/3)で試す
　具体例として、位相シフトゲートP(2π/3)の場合の量子回路をFig.2のように構成した。IBM QuantumのComposerを利用した。この位相ゲートに対する固有状態として、|1>を与えている。これは、Fig.1においては、m=1の場合となる。そして、量子ビット数n=3, 4, 5の３ケースの回路を用意した。制御付きPゲートを、2個、４個、８個、16個と繰り返す必要があるが、回路図を簡単にするため、Composerのカスタムゲート機能を使った。すなわち、冗長になるゲートの繰り返しを、p066p_2, p066p_4, ... , p066p16のような新たなゲートを作ることで簡単にしている。

🔴量子位相推定の実行結果
　上記の３ケースに対する実行（Composerシミュレーション）結果をFig.3に示す。結論から言うと、３ケースとも、確率約70%で、妥当な位相の値が得られた。当然ながら、量子ビット数を増やすに従って結果の精度が向上する。
　対象としたゲートP(2π/3)の固有状態|1>の固有位相は2π/3 = 120°である。n = 3, 4, 5の測定結果は、いずれも、古典ビット数nの範囲では最適値を与えている。なお、測定結果のビット列（２進整数）からどのように位相角度を求めるのかについては、すでに前報の後半で述べたのでここでは略している。

🔴量子コンピュータ実機ではどうなのか？（結論：negative）
　上記Fig.3に相当する、量子コンピュータ実機での結果も得た。しかし、.... ここではその詳細データの掲載はやめておく。現時点では、期待した結果ではなかったからである。この位相推定問題は、現在の量子コンピュータ（ハードウェア）にとって、大変苦手の部類に入るのかもしれない。たとえば、Fig.3のn = 5 qubitsの場合、測定結果01011（古典5ビットでの最適解）は確率70%で得られたが、量子コンピュータ実機では、その確率は10〜20%前後でしかなかった。つまり、解から遠い測定結果も同程度の確率で見られるのであった。（もしも私の誤りであることが判明したらお詫びするが....）

　ここで思い起こしたことがある。2024年２月頃に、IBM Quantumのアルゴリズム集からShorの素因数分解が削除された。当面、大規模な誤り耐性量子コンピュータの実現が難しいためとのことであった。私が実施した小規模な位相推定問題でも、上記の如く、現状の量子コンピュータでは困難のようなので、なるほどと納得するのである。引き続き、研究開発の進展を注視して行きたい。量子位相推定アルゴリズムは間違いなく非常に優れたアイディアだ！いずれ、100%に近い確率で正解が得られる日が来るだろう。

【私の質問】

　現時点の量子コンピュータにとって、位相推定アルゴリズムの実行は、他の量子アリゴリズムに比べて、かなり難易度が高いですか。つまり、測定しても、高い確率で正解が得られないという状況ですか？

【Gen AIの答え】

　現時点での量子コンピュータでは、量子位相推定アルゴリズムの実行は非常に難しいです。主な理由は、高いエラー率、限られた量子ビット数、測定の確率性、そして量子エラー訂正の複雑さによります。これらの問題が解決されるまでは、他の量子アルゴリズムよりも実行が困難です。

【書籍の表紙にも】

　最近購入した、T.G. Wongによるこの書籍の表紙は、Fig.1そのものだった！著者の意図はどこにあるのだろうか？これを実現することが一つの目標ということだろうか？

量子位相推定(Quantum Phase Estimation)-理論と計算

【要旨】量子コンピューティングの中級レベルでは、位相推定が重要事項の一つになる。それは、ユニタリ行列に対して、固有状態の固有位相を推定するものである。その前半部の計算結果は、ある正規直交基底ベクトルに対する量子フーリエ変換の結果と同一となる。従って、後半では、前半の結果に対して逆量子フーリエ変換を施し、全ての量子ビット（固有状態ベクトルを除く）を測定すれば固有位相を推定できる。このあたりの計算を明らかにできれば、理解が大いに進むであろう。そのポイントは、以下のような数式の意味を説明することかもしれない。

Q (Human): What is this?

A (Generative AI): The expression represents the superposition state after the application of the controlled-U operations, with the phase factor corresponding to the binary fraction of the phase ϕ. This is a crucial step in estimating the eigenvalue’s phase in the QPE algorithm.

🔴量子フーリエ変換QFTを復習

　量子位相推定アルゴリズムの前半の結果を、正規直交基底ベクトルに対するQFTの結果と比較する必要上、まず、QFTを復習する。これまでもQFTに関していくつか記事を書いてきたので、ここでは、今回必要な計算を中心に示したい。

　下図は、正規直交基底ベクトル|j>に対するn-qubitのQFTの詳細計算である。式(4)から式(5)への変形はわかりにくいかもしれないが、式(5)から逆に展開してみれば式(4)になることが分かる。

　ここで注目していただきたいのは、式(6)の赤字部分である。eの冪に、２進の少数がある。式(5)から式(6)への変形の詳細手順は、下図をご覧いただきたい。上記の整数jを２進表現し、さらにそれから２進の少数を導いている。また、eの(i2π・整数)乗は１であることを使っている。ここで、iは虚数単位である。

　とにかく、この後、式(6)を再び参照することになる。

🔴量子位相推定Quantum Phase Estimatonとは

　ここからが本題である。位相推定とは、ユニタリ行列Uに対して、その固有状態|v>の位相を求める（推定する）ことである。それは、下図のような式で表せる。

🔴量子位相推定を構成する量子回路

　いきなりだが、そのための量子回路図を以下に示す。上段のn-qubitが位相推定の計算用であり、下段に、|v>がユニタリ行列Uの固有状態として与えられる。固有状態から右へ引かれた直線は１本のように見えるが、実際は、行列Uへの入力量子ビット数がmだとするとm本存在する。Uの右肩に冪乗が書かれているが、その数だけ制御付き（黒点付き）Uの適用を右方向へ繰り返すことを意味する。後半のIQFTは（後述するが）、逆量子フーリエ変換である。最後にn-qubitを全て測定している。

　この量子回路で量子位相推定できるのか？それに答えるには、以下に述べる通り、回路を右に進める各ステップで、量子ビットシステム全体の状態がどのように変化するのかを明らかにすれば良い。

🔴量子位相推定の計算

　上記回路図の各ステップでの状態を計算した結果を下図に示す。ここで最も重要なのは位相キックバック（Phase Kickback）である。これに関してはこちらの記事をご覧いただきたい。下図の中の赤字で示したeの冪乗は位相キックバックの効果そのものである。制御付きUが繰り返される度に、|1>の位相にその効果が累積されることが分かる。

　さて、上記の計算を、上位n-qubitのそれぞれを使って明示するには下図のようにする。そのため、量子フーリエ変換のところで示したのと同様に、２進の少数を使っている。

　これら２つの図と、最初に述べた量子フーリエ変換の結果と比べて見ると、全く同一であることが分かる！すなわち、ここまでに述べた量子位相推定のための計算は、QFT計算と同じである。従って、次に、逆量子フーリエ変換IQFTを施せば、正規直交基底ベクトルが得られるはずである。実際には、n-qubitを全て測定して、高い確率で得られた量子ビットの組み合わせから、最終的に求める固有位相を推定（確率的に判断）できる。以下のとおりである。

　具体的な位相推定の計算例は、こちらの記事で示す。