Developing a mobilephone app to demonstrate Shor's prime factorization

[Abstract] I have written several articles about Shor's prime factorization, one of the pinnacles of quantum algorithms. The mobilephone app I developed this time is an all-in-one app that includes both classical processing and quantum algorithms. However, I did not create the quantum algorithm part myself, but used the quantum circuit simulator Quirk. Quirk does not provide an API, so the necessary parameters for linking the classical and quantum parts are passed manually. The significance of this app is that it allows you to complete the execution of the entire Shor's algorithm on a single screen (although it is limited to small integers). In practice, this method of manually passing the necessary parameters (not a fully automated process) while checking the results of the quantum circuit simulation is useful for deepening your understanding. I would like to demonstrate this in detail below.

🔴Details of Shor's Factoring Algorithm

The theory and calculation details of Shor's algorithm are written in this article. Also, the most important part, finding order, is an application of quantum phase estimation, and this is also explained in detail in this article. Therefore, this article only describes the overview and usage of the app developed this time.

🔴All-in-one app for Shor's algorithm

First, the overall image of the developed app is shown in Fig.1. This screen shows an example of decomposing 221, given as the product of two prime numbers 13 and 17, into the original two prime numbers. It consists of a classical calculation part and a quantum calculation part.

This app was created with MIT App Inventor. The classical part verifies the order (period) candidates obtained from the quantum part, and if they are valid, prime factorization is performed immediately. If they are not, a parameter (called A here) is changed appropriately and the process is retried. Meanwhile, the quantum part calls the quantum circuit simulator Quirk to obtain order candidates. The Quirk screen is crowded, but you can use your finger to zoom in on the parts you need.

🔴How to use the app

Please see Fig.2 below. Give two prime numbers p and q, and press the blue button "setup R" to obtain the desired integer R. Next, turn on the switch with red characters "Quirk Q Sim". Then, manually give this integer R as an input to the displayed Quirk simulator. Give another (randomly selected) integer A to Quirk in the same way. This Quirk quantum circuit is designed to find candidates for the order (i.e., period) of f(x) = A^x mod R. This simulation consists of a total of 14 qubits. (8 qubits for problem setting, 6 qubits for solution)

Next, as shown in Fig. 3, the results of the Quirk simulation (measurement results) show that out of 256 (=2⁸) bases, only four appeared with a probability of 25% each. If you enlarge the screen, you can see that one of the bases, |010000⟩, is a candidate for giving the order. Set this as the binary bit string "010000" in the window at the top of the screen.

Next, press the round "Shor" button as shown in Fig. 4. This binary bit string is then converted into a decimal, and then converted into a rational number (fraction s/r) using the continued fraction approximation method. The denominator r becomes a candidate for the order. In this example (N=221, A=18), s=1 and r=4. The validity of the order can be confirmed, and as mentioned earlier, we get GCD(A^r/2+1, R)=13 and GCD(A^r/2-1, R)=17, completing the prime factorization!

Although it is not a fully automated process, it is impressive that the entire Shor prime factorization can be demonstrated on a single screen in this app!

🔴Shor's Algorithm is Probabilistic

So far we have seen the whole picture of Shor's algorithm. It is a probabilistic algorithm. In fact, another result executed under the above conditions did not give a valid order, and the prime factorization ultimately failed. Such an example is shown in Fig. 5.

However, when executed using a fully quantum computer, the correct answer can be obtained with a sufficiently small number of attempts! The details are described in Nielsen & Chuang [1].

[Additional Notes]

MIT App Inventor was once again very useful. It was great to be able to call the external quantum circuit simulator Quirk easily using the WebViewer. On the other hand, if all the processing related to "f(x) = A^x mod R" was created in App Inventor, the number of blocks would increase, making it difficult to manage. Furthermore, it was necessary to use the Modular Exponentiation Method to prevent the calculation from overflowing. Therefore, this time, most of these were created in JavaScript and called from App Inventor. This kind of integration with JavaScript is also useful.

In creating this app, I referred to the chapter II-5 of Nielsen & Chuang [1], the chapter 7 of Wong [2] and the chapter 9 of Burd[3]. I would like to express my gratitude.

Reference

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

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

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

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

ショアの素因数分解をデモするためのスマホアプリの開発

【要旨】量子アルゴリズムの頂点の一つ、ショアの素因数分解については、何度か記事を書いてきた。今回開発したスマホアプリは、その古典的処理と量子アルゴリズムの両方を包含したall-in-oneとなっている。ただし、量子アルゴリズム部分は自作ではなく、量子回路シミュレータQuirkを利用した。QuirkではAPIが提供されていないため、古典的部分と量子部分の連携では、必要なパラメータは人手で授受した。このアプリにより、（対象は小さな整数に限定されるが）一つの画面でショアのアルゴリズム全体の実行を完結できることに意味がある。実際に行ってみると、量子回路シミュレーション結果を確認しながら、人手で必要なパラメータを渡す（完全自動処理ではない）この方法は、理解を深める上で有用な面がある。以下に、それを具体的に示したい。

🔴Shor's Factoring Algorithmの詳細

　ショアのアルゴリズムの理論と計算の詳細はこの記事に書いた。また、その最も重要な部分である位数発見（finding order）は、量子位相推定の応用であるが、これに関してもこちらの記事に詳細を示した。従って、本記事では、今回開発のアプリの概要と使い方についてのみ述べる。

🔴ショアのアルゴリズムのAll-in-oneアプリ

　まず、開発したアプリの全体像をFig.1に示す。この画面は、２つの素数13と17の積として与えた221を、元の２つの素数に分解した例である。古典的計算部分と量子計算部分から成る。

　このアプリはMIT App Inventorで作られた。古典的部分では、量子部分から得た位数（周期）の候補を検証し、妥当であれば、直ちに素因数分解を行うことができる。そうでなければパラメータ（ここではAという名称）を適宜変更して再試行する。

　一方、量子部分では、位数の候補を得るため、量子回路シミュレータQuirkが呼び出される。Quirkの画面は込み入っているが、必要な箇所を指で拡大して見ることができる。
　

🔴アプリの操作手順

　下図のFig.2をご覧いただきたい。２つの素数p,qを与えて、青いボタン「setup R」を押すと目的の整数Rが得られる。次に、赤字のスイッチ「Quirk Q Sim」をonにする。そして、この整数Rを、表示されたQuirkシミュレータへの入力として（手動で）与える。もう一つの（ランダムに選んだ）整数Aも同様にQuirkに与える。このQuirkの量子回路は、f(x) = A^x mod Rの位数（すなわち、周期）の候補を見つけるように作られている。全部で14-qubitの構成（問題設定用に8-qubit、解答用に6-qubit）である。

　次に、Fig.3に示すように、Quirkシミュレーションの結果（測定結果）として、2⁸= 256個の基底のうち、4個だけがそれぞれ25%の確率で出現した。画面を拡大して見ると、その一つの基底 |010000⟩が、位数を与える候補であることが分かる。それを２進ビット列"010000"として、画面上部の窓に設定する。

　続けて、Fig.4に示すように丸い「Shor」ボタンを押す。するとこの２進ビット列が10進小数に変換され、さらに、連分数近似法により有理数（分数s/r）に変換される。その分母rが位数の候補となる。この例（N=221, A=18）では、s=1、r=4であった。位数としての妥当性が確認できるので、すでに述べた通り、 GCD(A^r/2+1, R)=13とGCD(A^r/2-1, R)=17が得られて、素因数分解完了！

　完全自動処理ではないが、このアプリの一つの画面だけで、ショアの素因数分解の全体をデモできることは意味があるのではないか！

🔴Shor's Algorithmは確率的

　ここまでにショアのアルゴリズムの全貌を見た。これは確率的アルゴリズムである。実際、上記の条件で実行された別の結果は、妥当な位数を与えず、最終的に素因数分解が失敗した。そのような例をFig.5に示す。

　しかし、完全な量子コンピュータを使った実行においては、十分に少ない試行で正解が得られるという事実がある。その詳細は、Nielsen & Chuang [1]に叙述されている。

【補足】

　今回もMIT App Inventorをとても有効に利用できた。外部の量子回路シミュレータQuirkをWebViewerから簡単に呼び出せることは素晴らしい。一方、f(x) = A^x mod R に関係する処理を全てApp Inventorで作るとブロック数が増えて見通しが悪くなる。計算がオーバーフローしないように、Modular Exponentiation Methodを使う必要もある。そこで、今回は、これらの大部分をJavascripで作成し、それをApp Inventorから呼び出している。このような、Javascriptとの連携機能も有用である。

　このアプリの作成にあたっては、Wong[2]の第７章「Quantum Algorithms」とBurd[3]の第９章を参考にさせていただいた。感謝申し上げる。

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] Thomas G. Wong: Introduction to Classical and Quantum Computing, Rooted Grove, 2022.

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

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

関数電卓アプリでf(x) = a^x mod Nを計算

　前回のShor's Algorithmの記事で、f(x) = a^x mod Nが出てきた。その際、整数xの値を0, 1, 2, ...と増やした場合のf(x)をグラフにして、周期rを手軽に知りたいことがあった。もちろん、Pythonなどでそのようなアプリを作るのは難しくないが、電卓でパッとできたらいいなあ！

　そんな高機能な関数電卓アプリがありました！アプリ名は991EXという地味な名称（ではなく、カシオの関数電卓fx-991exを意識したもの）になっていて、プロ版でも約300円という安価なものでした。こんな素晴らしいアプリもあったのかと驚きました。もちろんノーコードで、例えば、下図の通り、f(x) = 7^x mod 15 のグラフがサッと描けました。f({0,1,2,3,4,5,6,7, ...}) = {1,7,4,13,1,7,4,13, ... }です。周期 r=4 がすぐに掴めます。素晴らしい！

　また、（実際には特に必要ありませんが）例えば下図のように、7¹⁰⁰⁰³ mod 15という巨大な冪乗でもオーバフローせずに答えが出ます。Modular Exponentiation Methodですね。さらに、数々の驚きのジュアルと、使いきれないほどの高機能が潜んでいるようです。Pythonのようなプログラミング言語も内蔵しているので、必要であればコーディングによってもっと高度な計算も行えます。（関数電卓だからこそ、という手軽さを保ちつつ...）

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