Enjoy Shor's Prime Factorization with a Mobilephone App

This is the English translation of this article.
[Abstract] To fully execute the well-known Shor's Factoring Algorithm, a large-scale fault-tolerant quantum computer is required, and with current quantum computers, this is unlikely to happen. However, when an ideal quantum computer appears, it is believed that this algorithm will have a huge impact on cybersecurity. Here, we created an app to apply Shor's algorithm to small integers (products of two prime numbers). This will allow you to become familiar with Shor's algorithm and deepen your understanding.

🔴 Overview of Shor's Factoring
There are many explanations of Shor's algorithm, but I was drawn to the YouTube video by Elucyda shown in Fig. 1. It takes about 25 minutes, and he explains it clearly and step by step, using only a whiteboard and clearly handwritten. This is great!

Shor's algorithm is said to be difficult to understand, but the outline is on this one page (8 lines). It involves prime factorizing an integer N, which is the product of two prime numbers. If N is small, it is not difficult to create an original program on a classical computer by following the steps in this diagram. However, you should pay attention to the part surrounded by a red frame in Fig. 1, "Find MIN r>0 such that a^r=1 mod N". This finds the smallest integer r (order) such that a^r = 1 mod N when you bring in another integer a for the integer N you want to factorize. This is nothing more than finding the minimum period of the repeating wave of the value of a^r mod N.

For very large N, this order-finding is the core of Shor's algorithm, and this is where quantum computers come into play. (This article is only beginner level. Without a complete understanding of quantum algorithms for order finding, it cannot be called intermediate level or above. I would like to write about this in another article.) Since we are assuming a small N this time, we have realized the entire processing of Fig. 1 as a mobilephoe app. This will help you become familiar with Shor's algorithm, and will also serve as a preparation for creating quantum programs later.

🔴 Creating a mobile phone app

Originally, the search for the above order r would be performed as a quantum algorithm, but since we are creating a mobile phone app here, this part is also a primitive (naive) program that runs on a classical computer. Fig. 2 shows the order calculation function created with MIT App Inventor. It should be noted that there is a risk of overflow when calculating a^r, especially when the value of r becomes large. Therefore, in order to prevent this to a certain extent, we do not calculate a^r mod N directly, but instead use repeated calculations using a small r.

🔴 Review of execution results

Let's start by trying to prime factorize a small integer, for example N=247, with this app. (N is given as the product of two prime numbers p=19 and q=13.) Figure 3 shows two successful examples. In Figure (a), the integer a randomly set in Figure 1 happened to be GCD(q, a)>1, so factorization was completed immediately. This corresponds to Case 1 in Figure 1. On the other hand, Figure (b) corresponds to Case 2 in Figure 1, and factorization was successful as expected.

Figure 4 shows different cases of failure. In Figure 4(a), the order r for a random integer a could not be found within the preset range. Furthermore, in Figure 4(b), the random integer a and the order r were set successfully, but prime factorization failed. This corresponds to Case 3 in Figure 1. Shor's algorithm thus succeeds probabilistically (by heuristics). However, it is known that the success rate is quite high.

🔴Why can this algorithm be used for prime factorization?

This article focuses on how Shor's algorithm works, not on why it can be used for factorization. However, I would like to briefly explain the key points of why below. One of them, which may be surprising, is the following formula (junior high school math!):

      a² - 1 = (a + 1)(a - 1)

Using this, a^r-1 = 0 mod N in the explanation of Fig. 1 becomes (a^r/2 + 1)(a^r/2 - 1) = 0 mod N. In other words, the left side of = is divisible by N. Therefore, one of the prime numbers that make up N divides one of the factors on the left side. From this, GCD(N, a^r/2 + 1) and GCD(N, a^r/2 -1) should be prime factors of N. When we calculate the case of Fig.3(b) (a = 30, r = 6), we see that this is indeed the case, as shown below:

     GCD(30^6/2+1, 247) = GCD(27001, 247) = 13

     GCD(30^6/2 -1, 247) = GCD(26999, 247) = 19

Incidentally, the algorithm for finding the underlying order r turns out to be roughly equivalent to the (precise) quantum phase estimation already described here and here, which makes Shor's algorithm more familiar.

ショアの素因数分解に親しむためのスマホアプリ

 【要旨】著名なShor's Factoring Algorithmの本格的な実行には、大規模な誤り耐性量子コンピュータが必要であり、現時点の量子コンピュータでは、その実現がほとんど望めない。だが、理想的な量子コンピュータが出現した時には、このアルゴリズムが与えるインパクトは、サイバーセキュリティ上、非常に大きいと考えられている。ここでは、小さな整数（２つの素数の積）に対して、このショアのアルゴリズムを適用するためのスマホアプリを作成した。それによって、Shor'sに親しみを持ち、理解を深めることができた。

🔴Shor's Factoringの概要
　ショアのアルゴリズムの解説は多数存在するが、私は、Fig.1に示したElucyda氏によるYoutubeビデオに注目した。約25分で、白板１枚だけを使って、鮮明に手書きしながら、分かりやすくstep by stepで説明している。これは上手、素晴らしい！

　難解と言われるショアのアルゴリムだが、概要はこの１枚（８行）である。２つの素数の積である整数Nを逆に素因数分解するのである。小さなNであれば、この図の手順に従って、パソコンなどで独自にプログラムを作って確かめることは難しくない。ただし、注意すべきは、Fig.1の赤枠で囲った部分、"Find MIN r>0 such that a^r=1 mod N"である。これは、因数分解したい整数Nに対して、別のある整数aをもってきた時に、a^r = 1 mod Nとなる最小の整数r（位数）を求めるのである。これは、a^r mod Nの値の繰り返しの最小周期を求めることに他ならない。

　非常に大きなNに対しては、この位数探索がショアのアルゴリズムの根幹であり、量子コンピュータの出番となるところなのである。（この記事は初級レベルに過ぎない。位数探索のための量子アルゴリズムの完全理解無しでは、中級レベル以上と言えないのである。）今回は、小さなNを想定するので、Fig.1の処理全体をスマホのアプリとして実現した。ショアのアルゴリズムに親しむとともに、この後の量子プログラム作成の準備ともなる。

🔴スマホアプリの作成
　本来は、量子アルゴリズムとして上記の位数rの探索を行うのだが、ここではスマホアプリとして作るので、この部分も古典コンピュータで動く原始的な（ナイーブな）プログラムとした。Fig.2は、MIT App Inventorで作った位数計算関数である。

　注意点として、a^rの計算で、特にrの値が大きくなるとオーバーフローを起こす恐れがある。そこで、一定程度それを抑止するため、a^r mod Nの計算をダイレクトに行わずに、小さなrを使った繰り返し計算で実現している。

🔴実行結果の検討
　早速だが、このスマホアプリで、小さな整数、例えばN=247を素因数分解してみる。（このNは２つの素数p=19とq=13の積として与えた。）成功した２例をFig.3に示す。このうち、図(a)は、Fig.1においてランダムに設定した整数aが、たまたまGCD(q, a)>1となったので、因数分解はすぐに完了した。Fig.1のCase1に該当する。また、図(b)の方はFig.1のCase2に該当し、正常に因数分解ができた。

　一方、失敗した場合をFig.4に示す。このうち図(a)は、当方で適宜設定した、ランダムな整数aと求める位数rの値の制限範囲内においては、値rの探索に失敗した場合である。また、図(b)の方は、ランダムな整数aと位数rは設定できたものの、素因数分解に失敗したケースである。これは、Fig.1でのCase3に該当する。Shorのアルゴリズムは、このように、確率的（発見的）に成功するものである。ただし、その成功確率はかなり高いことが分かっている。

🔴なぜこのアルゴリズムで素因数分解できるのか
　本記事は、なぜショアのアルゴリズムで因数分解できるのか、ではなく、どのように働いているのかを中心に述べている。とはいえ、whyについても以下にポイントを簡単に述べてみたい。意外かもしれないが、その一つは、以下の計算式（中学校数学）にあった。

a² - 1 = (a + 1)(a - 1)

　これを使うと、Fig.1の説明にある、a^r-1 = 0 mod Nは、(a^r/2 + 1)(a^r/2 - 1) = 0 mod Nとなる。すなわち、=の左辺は、Nで割り切れる。だから、Nを構成する一つの素数は左辺のどちらかの因子を割り切る。このことから、GCD(N, a^r/2 + 1)とGCD(N, a^r/2 -1)がNの素因数となるはずである。Fig.3(b)の場合（a = 30, r = 6）を計算してみると、以下の通り

確かにそうなる。

     GCD(30^6/2+1, 247) = GCD(27001, 247) = 13

     GCD(30^6/2 -1, 247) = GCD(26999, 247) = 19

　ところで、根幹をなす位数rを見つけるアルゴリズム（finding the order）は、すでにこことここに述べた（精密な）量子位相推定とほぼ同等であることが分かっている。このことからも、Shor'sアルゴリズムへの親しみは増すのである。

量子位相推定(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を全て測定して、高い確率で得られた量子ビットの組み合わせから、最終的に求める固有位相を推定（確率的に判断）できる。以下のとおりである。

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

量子フーリエ変換(QFT)再訪

　前報では、正規直交基底ベクトルの組に対して、少しづつ位相を変化させることで位相の波を起こし、それをビジュアル化して楽しんだ。ここでは、もっと先を見据えて、それを量子フーリエ変換で行ってみた。

🔴過去の記事
　量子フーリエ変換に関しては、これまでに断片的であるが以下のような短い記事を書いてきた。今回はその復習にもなっている。

    ⚪︎スマホのアプリで量子フーリエ変換をデモする
    ⚪︎Running quantum Fourier transform on my mobile simulator
    ⚪︎量子フーリエ変換：QFT(|ψ⟩+|φ⟩)=QFT|ψ⟩+QFT|φ⟩

🔴量子フーリエ変換の回路とその実行
　一例として、４個の量子ビット（4-qubit）の場合を考える。それに対する量子フーリエ変換QFTの回路をFig.1の上段に示した。qft4q_coreとなっているが、このcoreとは、swapを含まないQFTのコア部分という意味である。それを3-qubitの場合のQFTコアqft3q_coreを使って作っている。このような、カスタムゲート機能をIBM Quantum Composerで使うことができる。この図からも推測される通り、1-qubit、すなわち２次元のQFTはアダマール変換Hそのものである。

　このqft4q_coreの前段に、全てのqubitの順序を逆転させるswapを施している。そして、入力状態として、|0010>、すなわち、|2>を与えてこの回路を実行させた結果をFig.1の下段に示した。（注：qubitの縦の並びの上位を２進ビット列の下位に対応させている。）このカラーの配置から、正規直交基底ベクトルの並び順に従って、π/4づつ位相が反時計回りに回転していることがわかる。すなわち、生成された位相の波の周波数は２である。
　なお、QFTは、Fig.2のように、量子ビット重ね合わせ状態に対しも働くのが特徴的である。

🔴量子フーリエ変換の計算式
　上図の回路は、Fig.3に示すQFTの計算式に基づいて作られている。確かに、その位相項を見ると位相の回転の様子がFig.1のようになることが推定できる。しかし、Fig.3の数式が正確にFig.1に反映されているのを確かめるには（特に、位相変換ゲートPが制御付きとなっている点など）、少し複雑な計算をしないといけないようである。だが、その計算の詳細は参考文献[1]の第5章に示されているので、必要であれば参照願いたい。

　ここで、|x>は、正規直交基底ベクトルであり、xは10進数である。例えば、3-qubitの場合、|5>は|101>を意味する。一般の状態ベクトル|ψ>は、正規直交基底ベクトルの重ね合わせなので、QFT(|ψ>)はQFTの線形性から、上図の計算式を使って計算できる。

🔴逆量子フーリエ変換IQFT
　この記事では詳細は略すが、QFTの逆変換となるIQFTもよく利用される。IQFTは、以下のように作ればよい。
（１）QFTを構成するゲートを逆順に配置する。
（２）各位相変換ゲートでの位相角の符号を反転させる。（QFTの場合に対して）
（３）最後に、全てのqubitの並び順を逆転させるためのswapを施す。

🔴まとめ
　量子フーリエ変換 (QFT) は、n-qubitからなる量子状態を周波数領域に変換する操作である。入力の量子状態が一つの整数に対応していると考えられる場合は、QFTの結果は、その整数値を周波数とする位相の波を出力すると言える。
　逆量子フーリエ変換 (IQFT) は QFT の逆変換であり、量子状態にエンコードされた位相情報を元の振幅情報に戻す。言い換えると、QFT によって位相の回転としてエンコードされた周波数情報を、IQFT によって元の振幅分布に変換する。

参考文献

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

ChatGPT-4oの「量子もつれ」に関する説明

　ChatGPT-4oに、以下の写真を与えて、その説明を求めた。

　２量子ビット間のもつれ（Entanglement）であるとの説明、見事ではないか！！！

　写真の中に書かれていた数式が決め手となったのか。

🔴私の問い（プロンプト）

これは何？特に、曲がった銅線は何？

🔴ChatGPT-4oからの答え

これは、量子ビットの状態を示すためのBloch球の物理モデルです。写真には、2つのBloch球があり、各Bloch球は量子ビットの状態を表しています。

曲がった銅線は、2つのBloch球の間のエンタングルメントを視覚的に示しているものです。エンタングルメントは、量子ビットが相互に依存する状態を表し、1つの量子ビットの状態がもう1つの量子ビットの状態に影響を与えることを意味します。

写真の下部にある数式 CNOT(H|0⟩|0⟩) = 1/√2 (|00⟩ + |11⟩) は、Hadamardゲート (H) と制御NOTゲート (CNOT) の操作を示しています。この操作により、2つの量子ビットがエンタングルされた状態になります。具体的には、Hadamardゲートが最初の量子ビットに適用され、その後に制御NOTゲートが両方の量子ビットに適用されます。この結果、エンタングルメント状態が得られます。