Illustrating Shor's algorithm with my quantum circuit simulator

Shor's algorithm is mathematically quite difficult, so many books on quantum computing often only briefly mention it. On the other hand, when an explanation is given, it is difficult to understand because it is a list of many mathematical formulas. In this context, the book by Prof. Barry Burd [1] is surprisingly easy to understand and explains the basics. Chapter 9 of this book takes 40 pages to thoroughly explain the essence of Shor's algorithm. Using a concrete example, he explains that if you can find the period (frequency) in a coprime powers sequence, you can factorize the public key number. He then demonstrated quantum Fourier transform (QFT) to find that frequency, expressed it in Qiskit code, and ran it on IBM Quantum Lab. This is fantastic! With this, I was able to grasp the heart of Shor's algorithm!

I have so far developed my own quantum circuit simulator for 3-qubit as a mobile phone app with MIT App Inventor. The outline is shown in Fig.1.

This time, I was able to use my simulator to identify frequencies using quantum Fourier transform, following the instructions in this book. The results matched those from IBM Quantum Lab. In other words, using just a mobile phone, they were able to perform a quantum Fourier transform and obtain the results, just like a scientific calculator. The situation is shown in Fig.2 and Fig.3.

(Notes)

As of 02/23/2024, the execution environment of Qiskit (IBM Quantum Lab) has changed, so it is necessary to modify the original Python code (for example, Chapter09.ipynb) to run it.

●Here is how to fix it:

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

(A)change libraries:

from qiskit import QuantumCircuit, Aer, execute

from qiskit.tools.visualization import plot_histogram

  ↓

from qiskit.primitives import Sampler

from qiskit.visualization import plot_histogram

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

(B)use 'Sampler' instead of 'Aer' as follows:

sampler = Sampler()

result = sampler.run(circ, shots=1000).result()

print("result: ", result)

quasi_dists = result.quasi_dists

print("quasi_dists: ", quasi_dists) 

display(plot_histogram(quasi_dists))

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

●More details here:

Migration examples

https://docs.quantum.ibm.com/api/migration-guides/qiskit-runtime-examples

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

Reference

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

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

Functional Programming in MIT App Inventor

Abstract: Functional programming blocks such as map, filter, reduce, and sort can be used in list operations in MIT App Inventor. These will allow you to create clean and easy-to-understand programs without using for loops or if-then-else. (This article has also been posted to the MIT App Inventor community. Have a look at this.)

要旨：MIT App Inventorのリスト操作において、map、filter、reduce、sortなどの関数型プログラミングブロックが使える。これにより、forループやif-then-elseを使わず、すっきりとした分かりやすいプログラムが作れるであろう。（この記事は MIT App Inventor コミュニティにも投稿されています。 こちらをご覧下さい。）

●MIT App InventorのFunctional List Operators
　リスト処理において、図１に示すような関数型プログラミングのためのブロックが使える。すなわち、

• map：要素に何らかの変換を施して新たなリストを作る。
• filter：条件を満たす要素だけのリストを作る。
• reduce：要素の最大値、最小値などを得るなど、縮約する。
• sort：要素を条件に従ってソートし、新たなリストを作る。

　このような関数型プログラミングは、多くのプログラミング言語でサポートされている。しかし、MIT App Inventorのようなブロック型プログラミング環境にこれを取り入れるには多くの課題があったようである。この機能は、参考文献[1]で説明されているが、その元になる論文が[2]である。

　この論文[2]は、米国Wellesley大学（最難関の女子大らしい）の学生が2015年に発表したものであり、全98ページに及ぶ。表紙には、"Thesis advisor : Prof. Franklyn Turbak"と書かれているので（修士）学位論文のようだ。それだけ奥が深いものである。MIT App Inventorは、生徒学生を主な対象とした使いやすいプログラミング環境を提供しているが、関数型のような、高度なソフトウェア技術もしっかり取り入れて、強固なバックグラウンドを築いていることを改めて感じる。

●例題1： 指定された年の"13日の金曜日"を全て求める

　よくある例題かも知れないが、"指定年の13日の金曜日"を全て求めるアプリを、上記の機能を使った書いてみた。図２はその全ブロックである。大きなブロック"get_13Fri_list"が主要部であるが、ここには、forループもif-then-elseも全く出てこない。これが典型的な関数型プログラミングの簡単な例である。

　このブロックには、関数型ブロックが３つ使われている。(a)では、mapにより、月のリストをその月の13日の日にちリストに変換している。(b)では、そのリストをfilterにより、"金曜日=曜日番号6"だけのリストに変換している。このリストの要素は日にちオブジェクトなので、それを(c)でのmapにより、通常の書式の日付に変換している。つまり、map - filter - mapを連続して適用して、一気に流れるように、答えの日付のリストを得ている。爽快感がある！

●例題2： reduce(combining)も使ってみる

　上記のmapとfilterの他に、reduce(combining)も有用です。図3に、リスト要素をユークリッドノルムで正規化して新たなリストを作る例を示します。

参考文献

[1] MIT App Inventor Functional List Operators
https://ai2.appinventor.mit.edu/reference/concepts/pholo.html#map

[2] Soojin Kim, "Developing and Assessing New List Operators in App Inventor", 2015.
https://repository.wellesley.edu/object/ir558

数学グラフ計算機Desmosで偏光板アプリを作る

　以前のこのブログ記事で、量子計算に基づく、偏光板のスマホアプリを作成した。

これと同等機能のアプリを、最近知ったDesmos（2D3D数学グラフ計算機）を用いて作成してみた。Desmosの素晴らしさに感嘆！

　ノーコードで（というよりも、宣言的記述だけで）、インタラクティブに動作するアプリが簡単に作れてしまう。例えば、関数の計算式に未定義のパラメータ名が出てくると、そのパラメータを設定するスライダーが自動的に出てくる。それを動かすとパラメータを変化させたアニメーションも簡単に作れる。プログラミングにとらわれず、やりたいことを数学的に記述すれば良い、という感があって嬉しい。

　さらにwebで作成したアプリは、ほとんどそのままスマホアプリのように使うこともできる。

これで、ビジュアライゼーションの強力なツールを身につけられる！

　以下の図１、図２をご覧いただきたい。説明はほとんど不要であろう。

　以下の短いビデオもご覧ください。

　さらに、国際数学アートコンテストもやっていて、楽しく、ためになる。

https://www.desmos.com/art?lang=ja

　なお、上記はDemosの「幾何ツール」と呼ばれるものを使った。この中で、角度θに偏光した光子が軸角度αの偏光板を通過する確率p(θ, α)を使ったいるのだが、その3Dグラフを見たい場合は、別途「3Dgraph」で描いたものを参照できる。以下の例をご覧いただきたく。

多様体の基礎

　突然だが、私は何十年も前に、理学部数学科を卒業した。その後はコンピュータメーカの研究所でのソフトウェアの研究開発、さらに大学での教育に従事して、現在は退職している。かっての数学科での学びのうち、多様体はごく入口のところしかやっていなかった。当時は（私にとっての）適当な参考書がなく、先生の板書を追うしかなかった。もちろん、よく理解できたとは言えなかった。それでも購入した書籍は、松島与三著「多様体入門（旧版）」であったが、これが、とてつもなく難しい。だから、その後は放ってあった。

　退職後は、趣味として、量子コンピューティングという、かなり現実的なことに日々取り組んでいる。量子コンピューティングは量子物理を抽象化したものであろう。しかし、多様体論は（他の高度な数学もそうだが）、これとは比べられないほど抽象度の高い世界である。精神の世界である。なぜ、今更多様体を持ち出すのか、自分でもよく分からないが、そういう世界に入りたいという思いが強くなってきただけである。かって、ポントリャーギン著「連続群論」のほんの入口だけだが、それを読んで、そういう、精神の世界があることを知り感動した。ポントリャーギンは14歳で視力を失っていたロシアの大数学者であった。目の見えない人が、ここまで頭の中で、こんな数学の世界を作り上げられるのかという驚きであった。

　最近のことである。依然として難しいことには違いないが、それでも懇切丁寧で、読者への配慮が十分に行き届いているとの評判の、松本幸夫著「多様体の基礎」があることを知った。出版は1988年であるから、36年ほど経過しているのだが、名著と言われる。これを購入した。どう進めるのか、分からないが時間は十分あるので、一歩一歩取り組むのが楽しみである。その際は、一時的にパソコンもスマホも片付けてしまい、別世界へ行きたい。ただ、そういう世界であっても、人間は具体的イメージを求めるのが常である。そうなると、やはり、パソコンやスマホの支援アプリの出番があるかも知れない。そういう域に達するならば、それはまた嬉しい。

量子コンピューティングのための自作アプリについて

　これまで何度も、このブログに登場した「量子コンピューティング関係スマホアプリ自作」に関して、短い講演をすることにしました。15分しかないので、スライド枚数は少ないですが、その前半部を以下に示します。予告編です。１時間もあれば、量子コンピューティングをご存じない方にもご理解いただけるように作れると思いますが、短時間ではそれは無理っぽいです。それでも、なんとか、解説的な説明も含めました。

 

Qubit

Ekert protocol (when eavesdropping)

●まず、表紙に凝ってみました。

●positive、negativeありますが、新しいことへ挑戦するなら、positiveに！

●量子コンピューティングのためのスマホアプリの開発経緯です。

●Prof. Chris Bernhardtにご紹介いただいた、私のアプリ２つを取り上げます。

●アプリの具体的な説明の前に、基本事項の確認をします。

●異なる正規直交基底による測定、これがこの後必要になります。

●アダマールゲートHなど、種々の量子ゲートを使う。

●量子もつれ：これが全てではないが、こんな感じです。

　この後、Polarized filter experiment（光子の偏光）とEkert protocol（量子鍵配送）を詳しく述べるのですが、予告編なのでそこは省略します。本当は、Probability Amplitude Amplification（確率振幅の増幅を使うGroverアルゴリズム）もあるのですが、時間の関係で省略です。最後に、MIT App Inventorでこれらのアプリが効率的に開発できたことを述べます。