Redesigned Mobile Quantum Circuit Simulators (V2)

This article describes the revised version V2 of the mobile Quantum Circuit Simulator for n-qubit that I developed earlier.

▶️The new app name is nQsim_Aext.

🔴Addition of available quantum gates

The quantum gates shown in red below have been newly added.

[type1]

I, X, Y, Z, H, T, S, Td, Sd, √X , P(θ), RX(θ), RY(θ), RZ(θ)

 ("d" denotes "dagger", the angle(phase) θ should be given in radians, and π should be specified as "pi")

[type2]

Swap, QTF, QFTx, IQFT, IQFTx

 ("x" denotes Fourier transform without swap)

🔴Improvements to quantum circuit description format

・Comments (‘//’) can be placed anywhere on a line.

・Multiple quantum gates can be written on one line, separated by “;”.

・The name of the SWAP gate has been changed to Swap, and the argument “state” is no longer necessary.

・The newly added quantum Fourier transform has arguments given as follows:

[example] QFT, 0, 4 <- apply QFT to q0,q1,q2,q3

🔴Documentation screen setup

A separate screen with concise documentation. You can also jump to a blog with more detailed information.

🔴Phase Estimation built-in example

With the addition of QFT quantum gates, "Quantum Phase Estimation" has been added as a new built-in example. See the explanation below.

Here, a secret notation $$ is used that greatly reduces the amount of writing required. For example,

4$$P(2*pi/3),5,[2] -> P(2*pi/3),5,[2];P(2*pi/3),5,[2];P(2*pi/3),5,[2];P(2*pi/3),5,[2]

In this example, a phase shift gate P(2π/3) is used as an unitary operation. One of its eigenstates is |1>, so it is set to q5. Its phase 2π/3 = 120° is estimated by this quantum circuit. For this purpose, a phase kickback is applied to the five quantum bits q0, q1, q2, q3 and q4, which are the control bits. Finally, these quantum bits are measured after applying the inverse Fourier transform (IQFT).

As a result of the measurement, binary number "01011" (11 in decimal) was obtained with a probability of 68.4%. From this, the estimated phase = (360°/32)*11 = 123.75° is obtained. There is an error of about 3% from the correct answer of 120°. If the number of quantum bits used is increased, the accuracy should be further improved. 

🔴Two types of Bit-flip error correction

Bit-flip error correction incorporates two examples: "Bit-flip1" performs measurements to detect errors, then adds appropriate gates for error correction based on the results and runs again, whereas "Bit-flip2" automatically corrects errors without performing intermediate measurements.

[Note]

There is almost no syntax checking for quantum circuit descriptions. If you get abnormal results or the calculation does not proceed, please refer carefully to the built-in examples to resolve the issue.

Redesigned Mobile Quantum Circuit Simulators

Abstract: I have developed several quantum circuit simulator apps that run on mobile phones. Although my apps are not as good as well-known simulators such as Qiskit and Quirk, they are suitable for taking your mobile phone out of your pocket and learning the basics of quantum computing anytime, anywhere. No Internet connection is required. Until now, my simulators were for up to 3 qubits, but this time, I have made major design changes to enable it to handle any n qubits. (However, due to resource constraints on mobile phones, in reality, I am mainly assuming use of about 6 qubits.) These make it possible to run a large number of examples that are published in general quantum computing textbooks. These apps are currently unreleased, but I will provide them (.apk files for Android) immediately to anyone who is willing to try. Please contact me. (You can find my email address in the header of my blog.)

The app URL has changed, please contact me if you need it.

(▶️Please see the revised version V2 information here)

🔴Check out the introductory video for this simulator here!

🔴Two types of mobile phone apps developed

The following two quantum circuit simulators were developed.

(1) Simulator for n-qubit (app name: nQsim_9)

A new circuit description format similar to IBM's QASM was introduced. I also considered a GUI method in which qubits and quantum gates are set with buttons, but due to the limitations of mobile phone screen size and operability, I ultimately decided on a method in which quantum circuits are described in text. Fortunately, the description of quantum gates is very simple, and the number of qubits required for general learning is not very large, so I thought that there would be no major problems with this method. Rather, this method of creating a quantum circuit diagram by hand and writing (typing) quantum gates while looking at it would be more likely to deepen understanding.

(2) Simulator for one quantum bit (app name: sQ_b2)

This is an app specialized for one quantum bit, and the quantum state when various quantum gates are applied is graphically displayed on a disk-like image. The quantum bit state is also displayed on the Bloch sphere, which is useful for deepening understanding.

How to use the n-qubit simulator

(1) Overview of the simulator

See Fig.1 for an overview of this app. The user describes the quantum circuit in text format. For concrete examples, please refer to the built-in examples.

• Specify the number of qubits to be used and the quantum bits to be measured.
• Available quantum gates are I, X, Y, Z, H, T, S, √X , P, RX, RY, RZ, and SWAP.
  (CNOT should be represented by X with control.) 
• (The next version will also include the following gates: T_dagger, S_dagger, QFT, IQFT)
• The phase (angle) should be given in radians. The number π is specified as "pi".
• Any quantum gate can be equipped with necessary number of control bits. (However, SWAP is excluded because it has a different description format.)
  [example] X, 2, [0, 1]  <- apply X to q₂ controlled by q₀ and q₁
  [example] RY(pi/3), 2  <- apply RY with angle π/3 to q₂ 
  [example] SWAP, state, 2, 3  <- swap q₂ and q₃
• Only one quantum gate can be specified per line. (->In the next version, this restriction will likely be removed.)
• Lines containing "//" are considered comment lines.
• Blank lines are not allowed. (->In the next version, this restriction will likely be removed.)
• Measurements are automatically performed on the specified qubits at the end. (If you do not want to perform a measurement, set the list of qubits to be measured to a null list.)
• Newly added quantum gates based on measurement results, can also be executed.
• The described quantum circuits can be saved and retrieved. (However, the current version only supports two circuits.)
• Six simple quantum circuit examples are built in. Namely, Toffoli, GHZ, QFT, 7k%15, Grover's Algorithm, and Error correction (bit-flip).

(2) Example: Bit-Flip Error Correction

This example is an application of quantum teleportation and is considered important, so the details are shown in Fig. 2. First, click ① to import the example circuit. In this example, 5-qubit is used, and a bit-flip error occurs in quantum bit q₂. When the Go button is clicked in ②, a measurement result reflecting the error, that is, (q₄q₃=10) is obtained. Based on this result, in ③, a new quantum gate for error correction is provided. Next, when Go After Meas. button is clicked in ④, a new quantum state shown in ⑤ is obtained. Here, the error has certainly been corrected !

In this example, the following point is worth noting: namely, since the bottom two qubits (q₃ and q₄) are not entangled with the top three, measurements on the bottom two qubits make them collapsed, but will leave the top three unchanged. 

[Note]  When you use the "Go after meas" button, do not long-click the "clear" button. Doing so will cause the current quantum state to be completely lost. To clear the circuit description area, simply click the "clear" button.

(3) Other quantum circuit examples

Five examples other than the error correction above are shown in Fig. 3 to Fig. 5 for your reference. In the Fig.3, Grover's algorithm is demonstrated. The left hand side figure (a) shows flipping the phase of the target basis |01⟩ via the oracle. Then, amplitude amplification (b) is applied, and finally we can see the answer |01⟩.

In Fig.4(a), the GHZ circuit is illustrated which gives strong entanglement. A demonstration of applying QFT (Quantum Fourier Transform) is given in Fig.4(b).

Toffoli gate is applied in Fig.5(a) and SWAP gate is applied in Fig.5(b) to perform a modulo calculation.

[Notice 1] In the current version, error checking is not performed on the circuit description. If any strange results are obtained, please refer to the circuit description in the above example and review it. Also, the function to import handwritten circuit diagrams displayed to the right of the circuit is not supported.

[Notice 2] By using MIT App Inventor again, I was able to achieve significant efficiency in app development. The 1-qubit version of the simulator was developed using only App Inventor. The overall control and graphical parts of the n-qubit version were also developed using App Inventor, but most of the quantum state calculations (such as unitary matrix operations with complex coefficients) were created in Javascript (about 350 lines). The WebViewer function of App Inventor allowed us to call up the Javascript program smoothly.

How to use the single-qubit simulator

This is a graphical representation of operations on a single qubit using a disk and a Bloch sphere. In Fig. 6, a quantum state is set on the Bloch sphere using two sliders (θ and φ). In Fig. 7, the quantum state is changed using various quantum gates. Small disks on the right side of the Bloch sphere show the change in state before and after the application of the quantum gate. No detailed explanation might be necessary. Please try it out for yourself !

 

🔴 Other apps you might be interested in

# Developing a mobile phone app to demonstrate Shor's prime factorization

# A smartphone app reproducing the appearance through polarizers

# A mobile app that simulates the Ekert protocol for quantum key distribution

# Confirmation of quantum key distribution protocol BB84 with smartphone app (supplement)

量子コンピューティングの学びについて考える

　まだまだ猛暑続きだが、8月に入ってしまった。ここで、改めて量子コンピューティングの学びについて述べたい。そのきっかけは、米国のある有名高校（多分、日本の超難関高校に相当）の先生からいただいたメールである。それは、彼がある別の米国人からの紹介で、私の量子コンピューティングの学びに関するこのブログを知ったことによる。彼は次のように述べているのだが、大いに共感できる。

　彼は、この高校の数理系の教員だが、量子物理学で博士号を持つという素晴らしい人物である。物理学関係の研究所での勤務経験もある。この高校での来年度に向けて、「革新的テクノロジー」というパイロットクラスを編成し、高校低学年で、最初にAIと機械学習を教え、次に量子情報を教える予定とのこと。量子に関することをできるだけ早く教え始めることは可能であり、必要であると考えているようである。一般の大人は、ずっと古典物理学的な観点の世界で生きてきたので、量子の世界に入ることにはかなり抵抗があるが、若い生徒はそうではなく、量子の概念や論理に素直に入ることができると感じると述べている。

　彼は、教育におけるゲームに関する教師向けのSEPTプログラムに参加し、同僚と一緒に量子コンピューティングを教えるためのカードゲームを作成している。さらに関連アプリも作成したいとのこと。その際に私（山本）の作成したアプリを利用したり、参考にしたいとのことであった。一方、私の量子関係アプリは、振り返ってみると、造りがかなり複雑になったり、冗長であるところも多い。もっと、シンプルで扱いやすい構造にして、生徒にも親しめるアプリに改造したいと考えているところである。

　これまでに作ってきたブロッホ球模型と、量子関係アプリのいくつかの画面を、改めて以下に掲載する。これを眺めならが、どのように改善すべきかを考える。厳しい暑さが過ぎた頃には目処をつけたいのだが、保証はできない... だが、この分野で著名なMITの教授から頂いた以下のコメントが大いに励みになっている。

"I greatly enjoyed reading your blog post article. Your handmade plastic Bloch sphere is very appealing, and I appreciate how you are making such a kind effort to reach a new and young audience who may someday be important to the field.", by Prof. Isaac Chuang (MIT)

my Bloch sphere

my quantum apps logo

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

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そのものだった！著者の意図はどこにあるのだろうか？これを実現することが一つの目標ということだろうか？