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

量子位相推定(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ゲートが両方の量子ビットに適用されます。この結果、エンタングルメント状態が得られます。

量子ビットの位相の波の生成とその表示

【要旨】量子ビットの状態ベクトルの確率振幅は、確率と位相を含む。それぞれ独立したプロパティである。その両方をビジュアル化するにはいくつか方法がある。IBM QuantumのComposerでは、確率を棒グラフで、位相をカラーマップで示している。一方、小生が開発したモバイル量子回路シミュレータでは（他の多くのシミュレータに習って）確率は塗りつぶし円の面積で、位相は直線の傾きで表示している。どちらが使いやすいかは人それぞれだが、以下に比較のために図を載せた。（続編は→こちら）

🔴位相回転角の計算式

🔴位相の波のビジュアル化
 　Fig.1は、３-qubitの場合の、周波数=1の位相の波の生成である。全てのqubitにアダマール変換Hを施した後、上のqubitから順にそれぞれの位相（|0>に対する|1> の相対位相）を、45°、90°、180°に設定している。位相ゲートφを使っても良いのだが、ここでは、TゲートとSゲートを利用している。

　一方、Fig.2は、周波数=2の位相の波の生成である。アダマール変換後、今度は、上のqubitから順にそれぞれの位相を、90°、180°に設定している。最後のqubitの位相は360°なので何も設定していない。

　最初に見た時は、カラーマップにちょっと戸惑ったが、目が慣れてくると、位相の波の周期が識別しやすくなってきた。(a)、(b)どちらが使いやすいかは状況次第かもしれない。

🔴Composerのカスタムゲートを利用
 　もう少し量子ビットを増やした場合も見てみる。Fig.3は、６-qubitの場合であるが、ここでは、Custum gate機能を使ってみた。Composerのビジュアル操作と連動するQASMのコードも表示される。場合によっては、QASMコードを編集する方が効率的かも知れない。ただし、QASMではラムダ式（ラムダ関数）がサポートされていないので、ちょっと使いにくかもしれないが。FIg.4には、このカスタムゲートのパラメータ（引数）を変えることで、周波数を変更させた結果を示す。あまり意味はないかもしれないが、単純に美しい。

量子コンピューティングEXPO2024春に参加

【要旨】量子コンピューティングEXPO2024春に参加したので、感想などを簡単に述べる。このEXPOは、(1)AI・人工知能、(2)デジタル人材育成支援、(3)量子コンピューティング、(4)ブロックチェーンの４つの同時開催である。このなかでも、最近のAI・IT社会の情勢を反映して、AI・人工知能に圧倒的に多数の出展がみられた。また、デジタル人材育成への関心も非常に高いことを感じた。一方、量子コンピューティングは、出展数はあまり多くはなかったが、出展していた企業の技術者と直接対話したり、最新技術動向に関する講演も聴けたので、参加の意義は大いにあった。

　ここには、国内で参加できる量子コンピューティング関係のイベント等を列挙してある。今回は、そのうちの一つである量子コンピューティングEXPOに参加した。全体の極く一部に過ぎないが、思い出して書いた。場内は、撮影・録音禁止なので僅かな手書きメモを頼りに。

（１）出展企業の技術者との対話

　量子コンピューティングの出展は、約３０社（企業、団体、大学）のようである。そのなかでも、国内量子スタートアップとして著名な企業の技術者と、会場で10分ほど対話した。この企業は、量子コンピュータハードウェア方式の一つとして注目され始めたシリコン方式の試作も発表していた。実際にそのチップも展示されていた。それはともかく、対話の概要は以下のようなことであった。

　今年に入ってから、「中性原子方式」と「シリコン方式」への注目が高まったが、まだまだ実用化は先のようだ。国のムーンショット計画で官民学一体の協力のもとで、５つほどのハードウェア方式の研究開発が進められている。そこに参加している企業でも、もちろん、並行して独自に開発も進めており、現状はまさに群雄割拠である。

　現状の実稼働量子コンピュータは、数百qubit程度だが、NDIVIAでは、高性能GPUによる5,000 qubitのハードウェア量子シミュレータを発表しており、こちらはなかなか使えるのではないか。このシミュレータもエラーを起こす。例えば、理論計算ではある基底ベクトルの起こる確率が100%のはずがそうならない等である。だが、それは本物の量子が外部環境から受けるノイズによって生ずるエラーとは別物である。また、GPUによるマシンでは、真性の乱数を生成することは困難であるが、量子の元々の特性を利用した量子コンピュータならばそれが可能になるのではないか。例えば、Quantinuum社ではそれを表明しているようだ。

　そして、いくら高性能なシュミレータであっても、所詮、量子現象の模倣であるから、非常に複雑な現象の計算（分子分野等）では、本物の量子コンピュータにははるかに及ばない場面が考えられる。（→実は、この話は、次の阪大　北川勝浩氏の講演で明確になった。）

（2）阪大の北川勝浩氏の講演

　この講演「日本の量子研究開発 最前線」は、開始前から続々聴衆が集まり、約400席と見られる会場は満席となった。関心の高さが窺える。北川氏は、誤りの無い量子コンピュータがもたらす未来社会を展望した後、それに向けたムーンショット目標6を含む世界的な最新の研究開発動向を紹介した。

（以下の叙述は、この講演の小生独自の解釈や感想である。）

　国内では、最初に量子コンピュータなるものが開発されてから25年後の、2023年に超電導方式の32-qubitの初号機が出た。現在は、その３号機である64-qubitマシンが阪大にある。IBMやGoogleは、垂直開発（全ての工程を自社のみで完結）だが、日本は水平開発（各機関で分業協業）が特徴である。IBM製の実稼働マシンは127-qubitや400-qubitなので、国産64-qubit機は、規模としてはそれほど遜色のないレベルと見ている。現在は、NISQ(誤り含むNoisy Intermediate-Scale Quantum)だが、狙いはもちろん、FTQC(誤り耐性Fault-Tolerant Quantum Computer)である。

　大規模なFTQCはなぜ必要なのか？その答えは、地球規模の環境保全のための施策を支える計算性能にある。具体的には、人工光合成（CO2削減）や人工窒素合成（省エネ）である。人工窒素合成を見てみよう。現在、アンモニアを工業的に作る方法は確立されているが、高温高圧を要するので非常に多くのエネルギーを要する。一方、学校の理科の授業で出てくる、マメ科植物の窒素固定では極く僅かのエネルギーしか必要としない。だが、そのメカニズムの解明には、非常に精密な分子計算が必要であり、現在のスーパーコン用にその精密モデルを作り計算を行うことはかなり困難である。

　実際、マメ科植物と共生する根粒菌では、多数の電子のうち約50個の電子がもつれあっているので、2の50乗という膨大な状態の計算が必要となる。そこで、量子コンピュータであれば、そのような量子もつれを自然に利用して極めて高速計算することを期待できる。つまり、精密な分子計算は、無理に古典コンピュータを持ち出すのではなく、量子原理に基づく素直な計算に持ち込めるはずである。（元祖ファインマンが初期に述べていたことが実現されつつある。）

　後半は、誤り訂正方法の技術的内容であった。量子ビットが反転してしまうビットフリップと位相が反転する位相フリップの２つがある。例えば、2048ビットの素因数分解のためのShor'sアルゴリズムでは、6,000-qubit、8ギガgateを要する。時間も８時間〜22時間などと見積もられる。この間で誤りが起こらないことが求められるので、とても大変である。誤り訂正中に誤りが起こることもあるので、そのような誤りの増加を抑止することも不可欠である。

--------------------------------
(番外編) I asked ChatGPT-4o the following questions. The answer is omitted, but it was very similar to the content of Prof. Kitagawa's lecture above! I can't help but be surprised again. The momentum of using generative AI is unstoppable!

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

(番外編) Currently, in the general public, generative AI has much more momentum than quantum computing. But let's persevere and learn about quantum computing!

In the future, we will see a beautiful fusion of AI and quantum computing!

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

国内で参加できる量子コンピューティング関係イベント

 　今年（2024年）、日本に居ながらにして参加できる、量子コンピューティング関係のイベント、コンファレンス、オンラインコース、投稿などを列挙してみた。もちろん、小生が実際に参加するものは少ないのだが、Googleカレンダーには載せてある。条件が揃えば参加したいものも多い。これらはどちらかと言えば情報寄りの観点から収集したが、物理寄りのイベント等は他にも幾つかあるだろう。

(1)第1回 Quantum CAE研究会
URL：https://unit.aist.go.jp/g-quat/ja/events/2024/CAE_20240509-10.html
主催：G-QuAT（産総研：量子・AI融合技術ビジネス開発グローバル研究センター）
日時：2024-05-09, 10
場所：産総研　臨海副都心センター
対象：専門家

(2)量子コンピューティングExpo 2024(春)
URL：https://www.nextech-week.jp/hub/ja-jp/visit/qc.html
主催：RX Japan
日時：2024-05-22, 23, 24
場所：東京ビックサイト
対象：一般、技術者

(3)連続セミナー2024「情報技術の新たな地平：AIと量子が導く社会変革」
URL：https://www.ipsj.or.jp/event/seminar/2024/infomation.html
主催：情報処理学会
日時：量子関係は、2024-06-11, 19のみ。
場所：オンライン（有料）
対象：一般、技術者

(4)Q2B 2024 Tokyo
URL：https://q2b.qcware.com/2024-conferences/tokyo-english/
主催：QC Ware
日時：2024-07-24, 25
場所：東京（有料）
対象：専門家、技術者

(5)「社会を変える量子コンピュータ活用」論⽂募集
URL：https://www.ipsj.or.jp/dp/submit/tdp0602s.html
主催：情報処理学会　デジタルプラクティス
日時：2024-08-05（投稿〆切）
場所：オンライン投稿
対象：専門家、技術者

(6) QUANTUM COMPUTING FUNDAMENTALS
URL: https://learn-xpro.mit.edu/quantum-computing
主催：MIT xPro
日時：2024-10-07 (Start date)
場所：on-line course (price: $2,319)
対象：技術者、専門家

(7) Quantum Innovation 2024
URL：https://quantum-innovation.riken.jp/
主催：Quantum Technology Innovation Hubs
日時：2024-10-21, 22, 23（招待講演のみ）
場所：東京
対象：専門家、技術者

(8)量子コンピューティングExpo 2024(秋)
URL：https://www.jetro.go.jp/j-messe/tradefair/detail/131501
主催：RX Japan
日時：2024-11-20, 21, 22
場所：幕張メッセ
対象：一般、技術者

Congratulations Global AI Hackathon Winners!

MIT RAISE and the App Inventor Foundation have announced the winners of the Global AI Hackathon 2024. The Global AI Hackathon was a free virtual hackathon that encouraged people around the world to use MIT App Inventor to build AI apps for their purposes. The winners in each category will be invited to present their projects at the MIT AI & Education Summit in Boston from July 24-26.

For more information, see here and here.

IBM Quantum Labは廃止、だが新Composerがある

 【要旨】予告通り本日(現地時間 2024-5-15)、IBM Quantum Labのサービスが停止。これまでWeb上でQiskitコード(with Python)で量子回路を編集し、シミュレータや実機で実行できた環境がなくなってしまった！そのかわり、従来のComposerと呼ばれるビジュアル量子回路編集のサービスの質向上が図られた。そこから、実機で実行することもできるので、全体としては、ユーザサービスは向上したと言える。

🔴IBM Quantumからのアナウンス

　図１に示す通りだが、アナウンスはこのサイトの中にある。今後は、Qiskitコード編集、および実行環境はユーザ自身がローカルマシンに構築しなければならない。Webでのサービスは終了したのである。量子コンピュータハードウェア開発競争が激化し、IBMもハードウエア開発により注力するためらしい。
　Qiskitで作成した量子回路は、ユーザのローカル環境からもIBM Quantumマシン実機で実行できるので、中級以上のユーザには特に問題ないであろう。一方、初級ユーザ（および中級ユーザ）は、従来のビジュアル型のComposerが利用でき、今回はそのサービス内容もかなり向上したようである。

　ローカルにQiskit環境を構築後は、こちらのドキュメントが参考になる。

🔴新しいIBM Quantum Composerを使ってみる

　前向きに捉えて、新しくなったComposerを使ってみた。簡単な例題として、先のポストで示した「位相キックバックの量子回路」を使う。図２上部のように、量子回路の編集において、その各フェースで、確率振幅と位相を分かりやすく円盤で表示できる。また、図２下部に示すように、基底ベクトル毎の確率計算結果も表示される。

　このようにビジュアルに編集した量子回路に対して生成されるQiskitコードも見ることができる。図３にそれを示す。このコードをコピーして、自分のQiskit環境で使うこともできる。そして、注目すべきは、この画面から、IBM Quantumマシン実機で実行させることができることだ。特に嬉しいことに、利用可能なマシンそれぞれの混み具合（キューに何個のジョブが実行待ちか）を確認できるので、早く実行できそうなマシンを指定できる。性能（誤り発生率など）指標も表示されるので選択の参考にもなる。

　今回は、ibm_brisbaneという名称のマシンを指定したところ、まもなく実行された。実行結果として、1024ショット（デフォルト試行回数）のうちの、各基底ベクトルの出現頻度（Frequency）がヒストグラムで表示される。

　ここで良いことがある。この実行の結果、基底ベクトル|01>の頻度は図４の通り、94%であった。本来は、図２に示した通り、この頻度は理論計算上100%のはずだが、実際のマシンでは、このように数%程度の誤差が生ずる。

　もう一例示そう。図５は、３-qubitの強い量子もつれを起こすGHZと呼ばれる量子回路である。そのシミュレータ（小生自作のアプリ）とQuantumマシン実機(ibm_brisbane)の結果も図４の場合と同様に若干の差異が生じている。理論計算では、右側のシミュレータが示す通り、基底ベクトル|000>と|111>以外の基底ベクトルの頻度はゼロになるはずである。

　現状の本物の量子コンピュータとはこういうものである。それを実感することはとても重要なのではないか。現在の量子コンピュータ開発競争ではこのような誤差の低減を目指しているのだが、量子物理の世界はそういうものだ、として受け入れて利用したいという気にもなる。もちろん、幾つか分野の数理アルゴリズムでは、このような少しの誤差も許容できない場合があることも事実だ。

　IBMは、こういう状況ではあっても、ユーザには、「シミュレータよりも量子コンピュータ実機を使って欲しい」と言っているように思える。そこから得られる知見を今後の研究開発に生かしていくのであろう。