2024年2月21日水曜日

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. 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 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.

2024年2月14日水曜日

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
 
リスト処理において、図1に示すような関数型プログラミングのためのブロックが使える。すなわち、

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

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

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

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


2024年2月12日月曜日

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

 以前のこのブログ記事で、量子計算に基づく、偏光板のスマホアプリを作成した。
これと同等機能のアプリを、最近知ったDesmos(2D3D数学グラフ計算機)を用いて作成してみた。Desmosの素晴らしさに感嘆!

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

 さらにwebで作成したアプリは、ほとんどそのままスマホアプリのように使うこともできる。
これで、ビジュアライゼーションの強力なツールを身につけられる!

 以下の図1、図2をご覧いただきたい。説明はほとんど不要であろう。
 以下の短いビデオもご覧ください。
 さらに、国際数学アートコンテストもやっていて、楽しく、ためになる。

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

2024年2月9日金曜日

多様体の基礎

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

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

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


2024年2月2日金曜日

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

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

まず、表紙に凝ってみました。
positive、negativeありますが、新しいことへ挑戦するなら、positiveに!
量子コンピューティングのためのスマホアプリの開発経緯です。
Prof. Chris Bernhardtにご紹介いただいた、私のアプリ2つを取り上げます。
アプリの具体的な説明の前に、基本事項の確認をします。
異なる正規直交基底による測定、これがこの後必要になります。
アダマールゲートHなど、種々の量子ゲートを使う。
量子もつれ:これが全てではないが、こんな感じです。
 この後、Polarized filter experiment光子の偏光)とEkert protocol量子鍵配送)を詳しく述べるのですが、予告編なのでそこは省略します。本当は、Probability Amplitude Amplification(確率振幅の増幅を使うGroverアルゴリズム)もあるのですが、時間の関係で省略です。最後に、MIT App Inventorでこれらのアプリが効率的に開発できたことを述べます。

2024年1月26日金曜日

Ekert protocol revisited

Recently, I have been working on quantum algorithms that apply various quantum gates. There, the direction in which the quantum is measured is fixed, often by projecting it onto the Z axis. On the other hand, quantum algorithms that change the measurement method, that is, change the orthonormal basis and use it, are also important. For example, there is the Ekert protocol, which is the basis of quantum key distribution. I've already written about Ekert in this article, so I won't go into any further explanation, but I've revised the app that demos it this time. The situation is shown below.

The left side of the figure shows the case where there is no eavesdropping, and the right side shows the case where eavesdropping was detected. An important aspect of the Ekert protocol is the use of Bell's test, or quantum entanglement.

Animation added!
If there is no eavesdropping and Alice and Bob measure in the same orthonormal basis, the result will be 00 or 11. That is, the result is the same. Quantum entanglement is at work. On the other hand, if Eve eavesdrops first, the same thing happens between Eve and Alice. However, since quantum entanglement has already disappeared, there is no such relationship between Alice and Bob. This fact is tied to eavesdropping detection.

2024年1月23日火曜日

Development of scientific calculator-like quantum circuit simulator V2

(This is an English translation of a previous Japanese article)

I have been developing a quantum circuit simulator that is as easy to use as a scientific calculator. As a single smartphone app, you can try out various quantum algorithms and apps within the 3-qubit range. This time, version 2 has been completed. I also added a little bit of play.

If you shake your smartphone lightly, one of five icons will randomly appear. It's a little fun. Of the five images, one was created by me, while the other four were created by ChatGPT.
Of course, this is not the only thing. Added a playback function that applies quantum gates. That is, by recording the steps of an algorithm (which quantum gates were applied to which registers (qubits)) in sequence, and pressing one or two buttons, the algorithm can be played back. I found this to be very useful when showing a demo to someone or when running under different conditions myself. Although details are omitted, three algorithm playback examples recorded in this manner are shown below.

Superdense Coding
In Fig.1, Alice has the top two qubits (q0 and q1), and Bob has q2. Both qubits are in a state of quantum entanglement. Just like that, Bob went away. Alice wants to send any of the classical 3-bit information (000, 001, 010, ..., 111) to Bob. In other words, she wants to send "101" out of eight, for example, in (a). However, there are only two qubits that can be sent. This is not enough!
Nevertheless, with this wonderful Superdense Coding, Bob can always obtain any information from Alice simply by operating a predetermined quantum gate! Fig.1(b) shows this.
Grover's Algorithm
For example, assume that eight pieces of information (000, 001, ..., 111) are arranged randomly. The problem is finding specific information from among them. Fig.2 is an example of searching for "101". First, mark the information in (a). This is achieved by inverting the phase of the corresponding basis vector |101>. This is not a scam! It simply tells you what to look for. Without such information, the search itself is meaningless.
In (b), when the button Amp3step is pressed, the probability amplitude amplification is activated, and only the probability amplitude of the basis vector whose phase was inverted in (a) is amplified, and the desired information "101" is obtained. In this example, we only needed to perform the phase inversion and amplification pair once!
Quantum Fourier Transform
This is an application example of quantum Fourier transform QFT. One of the characteristics of QFT is that it can be applied to states of quantum superposition. In Fig.3(a), we created a superposition of two certain quantum states. Next, in (b), when the button QFT is pressed, the phase waves that are the results of each QFT in both states interfere and appear as separate phase waves. The wave swell can be seen from the phase angle and amplitude (area of the disk filled in red) in the lower part of (b).
Although omitted here, you can restore the original quantum superposition state by pressing the button next to it, IQFT. IQFT is the inverse quantum Fourier transform.

2024年1月21日日曜日

関数電卓型の量子回路シミュレータV2

 関数電卓のような使い勝手の量子回路シミュレータを目指し、独自に開発を進めてきた。1台のスマホのアプリとして、3-qubitの範囲で、種々の量子アルゴリズムやアプリをこれで試すことができる。今回、バージョン2を完成させた。遊びもちょっと入れてみた。
 スマホを軽く振れば、4つのアイコンのいずれかがランダムに現れる。ちょっと楽しい。4つのイメージのうち、1つは自作したが、他の3つはChatGPT氏によるものである。

 もちろん、これだけではない。目玉は、量子ゲート適用の再生機能を追加したことだ。すなわち、あるアルゴリズムの手順(どのレジスタ(量子ビット)にどの量子ゲート適用したか)を順に記録して、ボタン1つか2つを押すと、そのアルゴリズムが再生できる。これは、人にデモを見せたり、自分でも条件を変えて実行する場合に非常に便利であることが分かった。詳細は略すが、そのようにして記録した3つのアルゴリズム再生例を以下に示した。

Superdense Coding(超高密度符号化)
 Fig.1において、Aliceは上段の2つのqubit(q0とq1)を持ち、Bobは下段のq2を保有する。両者のqubitは量子もつれの状態にしてある。その後、Bobは遠方へ行ってしまった。もつれは保持されたままである。Aliceは古典3ビット情報(000, 001, 010, ... , 111)のどれかをBobに送りたい。つまり、8個のうちから、例えば、(a)では"101"を送たい。だが、送れるqubitは2つしかない。これでは足りない!
 それにも拘らず、この素晴らしいSuperdense Codingでは、Bobは常に予め決められた量子ゲートを操作するだけで、Aliceからのどの情報でも得られる!(b)はそれを示している。
Grover's Algorithm(グローバーの探索アルゴリズム)
 これは、例えば、8個の情報(000, 001, ... , 111)がランダムに並んでいるとする。その中から特定の情報を探し当てる問題である。Fig.2は、"101"を探す例である。まず、(a)で、その情報に印をつける。それは、対応するbasis vector |101>の位相を反転させることで実現させている。これはイカサマではない!単に、何を探すべきかの情報を与えているだけである。そもそも、そのような情報がなければ、探すこと自体が意味をなさない。
 (b)において、ボタンAmp3stepを押すと、確率振幅増幅が作動して、(a)で位相反転したbasis vectorの確率振幅だけが増幅されて、求める情報"101"が得られた。この例では、位相反転と増幅のペアをただ1回実行するだけで解決した!
Quantum Fourier Transform(量子フーリエ変換)
 これは、量子フーリエ変換QFTの適用例である。QFTの特徴の一つは、量子重ね合わせの状態に適用できることである。Fig.3(a)で、ある2つの量子状態の重ね合わせを作った。次に、(b)で、ボタンQFTを押すと、両方の状態のそれぞれのQFTの結果である位相の波が干渉して、別の位相波として現れる。(b)の下段の位相角度と振幅の大きさ(赤で塗り潰した円盤の面積)から、波のうねりが分かる。
 なお、ここでは省略したが、隣のボタンIQFTを押すと、元の量子重ね合わせ状態を復元できる。IQFTは、逆量子フーリエ変換である。

2024年1月15日月曜日

量子フーリエ変換:QFT(|ψ⟩+|φ⟩)=QFT|ψ⟩+QFT|φ⟩

 前報で、独自のモバイル量子回路シミュレータを用いて、3量子ビットシステムのbasis vector(|000⟩, |001⟩, |010⟩, ... ,|111⟩)それぞれに対して量子フーリエ変換QFTを行った。だが、QFTは、量子重ね合わせ(SuperPosition)に対して適用できる点に大きな特徴があるといえる。そこで、今回、私のシミュレータでのGUIを以下の図に見られるように若干変更して、これを実験してみた。以下の図から、実用上非常に重要なQFTの線形性を確認でき、位相の波の干渉による増幅/減衰(高め合い/弱め合い)の状況が分かる。

QFT(|000⟩+|001⟩)=QFT|000⟩+QFT|001⟩
 前回までにQFTを見てきたので、あまり説明は必要ないと思われる。Fig.1に、2
つの状態の重ね合わせ |000⟩+|001⟩ に対するQFTの結果を示した。
 (a)はQFT|000⟩、(b)はQFT|001⟩であり、(c)は両者の加算となっている。同じ位相の場合は確率(塗りつぶした赤い円の面積)が倍増しており、位相が180度逆転している場合は確率がゼロとなっていることが分かる。

QFT(|000⟩+|100⟩)=QFT|000⟩+QFT|100⟩
 もう一例見てみよう。Fig.2は、2つの状態の重ね合わせ |000⟩+|100⟩ に対するQFTの結果を示した。
 (d)はQFT|000⟩、(e)はQFT|100⟩であり、(c)は両者の加算となっている。今度は、|100⟩の位相が、(d)と(e)で完全に逆転しているので、(f)にてその確率はゼロとなる。赤い円の塗り潰しは無くなった。そして、その前後で、両者の位相が次第に近づくに従って、位相が揃ってきて増幅され、確率が増加する(赤い円の塗り潰しが大きくなる)ことが分かる。緩やかな波が見えてくる!

 最後に、逆量子フーリエ変換IQFTによって、この位相の波から、元の入力量子状態(すなわち、重ね合わせ状態)が復元される様子をFig.3に示す。

2024年1月13日土曜日

Running quantum Fourier transform on my mobile simulator

I have developed a 3-qubit quantum circuit simulator that runs on a mobile phone. As shown in the top row of Fig. 1, a large number of basic quantum gates can be used. This time, I was able to demonstrate quantum Fourier transform (QFT) and inverse quantum Fourier transform (IQFT) using these quantum gates. QFT and IQFT each consist of six quantum gates, which are registered to buttons.

In Fig1.(a), when the button QFT is pressed for the quantum bit state |101>, a wave with the phase shown at the bottom is generated. Next, in Fig2.(b), the original qubit state could be restored by pressing the button IQFT. This means that we were able to determine the periodicity of the waves, as shown in Fig.2.

As mentioned above, QFT and IQFT were constructed by combining individual quantum gates, but alternatively, a unitary matrix can be used as shown in Fig. 3. I won't go into details, but these unitary matrices are actually built into my simulator. Note that when using this method, it was necessary to perform swap processing according to the simulator's policy. Swap means reversing the direction in which three qubits are arranged.

2024年1月10日水曜日

スマホのアプリで量子フーリエ変換をデモする

要旨:スマホ1台で稼働する量子回路シミュレータを開発している。現在、3-Qubitまでのアプリを動かすことができる。今回、これを用いて、量子フーリエ変換(QFT)、及びその逆変換(IQFT)の簡単なデモを実現できた。

量子フーリエ変換(隠れた周期性の発見)
 ショアの因数分解アルゴリズムなどで重要な量子フーリエ変換(QFT)は、量子計算の代表例の一つである。QFTは、ある量子状態を入力すると、それに応じた周期性を有する量子状態(位相変化の波)を作り出す。また、逆量子フーリエ変換(IQFT)は、周期性を有する量子状態の隠れた周期を見つけることができる。

 ここでは、既存のシミュレータでQFTとIQFTを試すのではなく、量子回路シミュレータ自体をスマホ上に独自に構築した上で、QFTとIQFTを実験することに意義がある。そのため、以下の図にあるように、かなり多くの量子ゲートを実装することになった。

 IQFTでは、QFTを構成する量子ゲートを逆順に適用して行けば良いのであるが、実はその際、位相の回転方向を逆向き変更する必要があり、これが理由で実装量子ゲートが増えた面もある。

QFTとIQFTの実行例
 詳しいことは略すが、実行例をいくつか示す。図1は、3量子ビットの状態ベクトル|100>を量子フーリエ変換に入力した場合である。

(注)本質的なことではないが、回路図上の量子ビットは上から下へ、q0q1q2と並んでいるが、図の下方にある円盤に付した状態ベクトルでは、慣例上、量子ビットは左から右へ、q2q1q0の順になっている。これ以降、状態ベクトルはこの「慣例」で表現する。

 図1では、(a)に示した量子ビット状態|100>を入力としてQFTを実行すると、(b)に示すような位相の波が得られた。すなわち、基底ベクトル|000>、|001>、... |111>の順に、位相が反時計回りに45度づつ変化し、8個の基底ベクトルで1周期の位相の波となる。
 続けて、IQFTを適用した結果を図2に示す。結果として、確率100%(円盤が全面塗り潰し)で|100>が測定された。これは元の入力そのものであり、回路図に戻って考えると古典ビットで"001"を得たことになる。すなわち、"1"周期の波であることが分かる。
 同様にして、入力量子状態|010>をQFTに与えると、今度は、2周期の位相の波(半時計周りに90度づつ進む)となり、さらにIQFTを実行すると元の入力量子状態が復元された。
 さらにもう一例、入力量子状態|001>をQFTに与えると、今度は、4周期の位相の波(半時計周りに180度づつ進む)となり、さらにIQFTを実行すると元の入力量子状態が復元された。
 図5に、逆量子フーリエ変換で位相の周期が分かる様子を再度掲載した。
感想
 スマホで、電卓みたいな感覚で、簡単な量子回路シミュレータを作ろうとして始めたが、段々膨らんできて、3量子ビットの量子フーリエ変換ができるまでになった。まだまだ、初級レベルに留まるが、ちょっと嬉しくなる。ただ、スマホでは(性能上というよりも、画面設計やコード作成する上で)この位の規模が限界かもしれない。さらに高度なことは、QiskitやIBM Quantumで実行ということになろう。

 本記事内容を何かに生かすとしたら... 簡単なゲームが考えられる。3量子ビットで、何らかの周期性をもつビット列をプレイヤーに与えて、その周期を当ててもらう。あまり面白くないか。でも、量子アプリ作成の練習にはなるだろう。

 本記事内容を、整数の素因数分解に結びつけることは(たとえ15など小さな整数でも)非常に困難です。これを実現する量子回路を構成するには、より多くの知識と技術が必要です。私はまだその域に達していないようだ。特に、モジュラー指数関数を量子回路で実現する部分などです。

2024年1月7日日曜日

Yet another mobile quantum circuit simulator

In the previous article, I described the development of a quantum circuit simulator that allocates one qubit to one mobile phone. I also placed emphasis on graphical interfaces, including display on the Bloch sphere. This time, I have developed a new quantum circuit simulator that can run applications using three-qubit on a single mobile phone.

Simulate quantum circuits with a mobile phone that fits in the palm of your hand!
Without internet connection!
It's as fun as using a scientific calculator!

As shown in the figure below, I used this to implement Grover's algorithm. The same results were obtained with the IBM Quantum Computer, which had already been carried out.




Acknowledgment
In developing this quantum circuit simulator, the explanations and examples in the following reference [1] were very helpful to me.

References
[1]中山茂、"量子アプリQni量子プログラミング初歩",Gaia教育シリーズ52, 2022.