2022年10月24日月曜日

"Bellの定理"という名前の北アイルランドの通り

 今回は、Entanglement(量子もつれ)に関する著名なBell's Inequality(1964年発表のベルの不等式)について簡単に書きたいと思います。まず、この物理学者John Stewart Bellの偉大な功績を示すGoogle Mapsのスクリーンショットをご覧ください。
 人名に由来する、街の通りは幾つかあると思いますが、数学や物理の定理の名前がついているのはこれくらいしかないでしょう。すでにご紹介済みのProf. Chris Bernhardtの著書[1]に、そういう通りがあると書かれていたので、Google Mapsで検索したところ、上図のとおり発見。北アイルランドBelfastにある大学前の三日月形道路 "Bell's Theorem Crescent" がそれです。素晴らしい!多分無理ですが、Belfastへ旅行できればいいのですが。

■ノーベル物理学賞2022とBellの不等式
 今年のノーベル物理学賞は、1982年に "violation of Bell inequalities"(Bell不等式の破れ)を確立したAlain Aspect等に贈られました。ここで誤解のないように書きたいのですが、「Bell不等式の破れ、すなわち不成立」と言うと、Bellが誤っていたかのように聞こえますが、全くその逆なのです。Bellは、ある問題に関する(Local Realism, Hidden Variablesを仮定した)古典物理観点の答えと量子物理の答えが異なること(すなわち、等しくない=inequality)を示しました。そして、量子物理の方が正しいだろうと唱えていたのです。それが、発表から20年近く後に、Alain Aspectによって実証されたのです。このことは、量子物理にとって(従って量子コンピューティングにも)極めて重要なこととされています。

■Bellの不等式を古典物理と量子物理の観点から高校数学で理解する
 Bellの不等式の真髄を理解することは難しいかも知れません。しかしながら、Prof. Chris Bernhardtの著書[1]は、ある例題を用いて、高校数学の範囲の数式で、この理論を厳密かつ明快に説明しています。一貫性、厳密性、分かりやすさにおいて、卓越した名著だと感じ入ります。
 それでもなお生ずる疑問や理解が難しい点を、私は、著者にメールで2回質問(EntanglementとBell's Inequalityに関する確認)をしました。すぐに丁寧な回答を送ってくれました。それによって、私の理解は一段と深まったのです。そのメールでの応答はこちらにありますので、ご参考にして下さい。

■Bellの理論が量子物理の正しさを示すことの実用的利用
 上のBell's Inequalityは、アカデミックな世界の理論ですが、実は応用上も注目されています。その一つは、現在主流の公開鍵暗号RSAなどにとって替わるとも言われる量子暗号での量子暗号鍵の配送の安全性保証です。これに関しても、[1]に簡潔に説明されていますが、2者間で配送している量子暗号鍵を第三者が盗聴すれば、Bellの理論におけるEntanglementによって必ず露呈してしまう、というものです。Eckert Protocol for Quantum Key Distributionと呼ばれています。

参考文献
[1] Chris Bernhardt: Quantum Computing for Everyone, The MIT Press, 2020.


2022年10月21日金曜日

著者に質問してみよう - 量子計算の基礎理論

 私は、量子コンピュータの基礎理論を下記に示した英語の本で勉強しています。単なる教養としてではなく、高校数学の範囲で、厳密に式を使ってクリアに説明しているところが非常に気に入っています。易しい英語で貫かれています。

●ノーベル物理学賞2022の量子理論を高校数学で学ぶ
https://sparse-dense.blogspot.com/2022/10/2022.html

 読み進めているうちに、ヤマ場となるEntanglement(量子もつれ)とBell's Inequality(Bellの不等式(の不成立))のところで、どうしても確認したい点が出てきました。著者のChris Bernhardt(米国Fairfield大学の数学の名誉教授)に質問したところ、直ちに回答してくれました。この世界、そういう文化になっているので、思いついたら質問するのがいいですね。

もしかすると、この本で勉強する人にとって、以下の応答は役立つかも知れないと考え掲載します。Prof. Chrisからは、メール応答文のブログ掲載に同意していただいています。
(あなたのブログはとても役立ちそうだ、と言っていただいたのも嬉しい。)

----------------
【山本より】
Hello Chris,
I am a Japanese reader of "Quantum Computing for Everyone".
This book is wonderful because it tries to explain difficult things clearly in high school mathematics.

I have a few questions regarding the Entangled Quantum Clocks on Page 68.
I think this is one of the most important parts of the book.
Thank you for your reply in advance.

Q1
I understand as follows, is it correct?
"There are two humans here (me and you), each with 100 clocks.
In other words, it is not the assumption that 100 people each have a watch."

Q2
Is the First scenario or the second scenario a fact that can be derived from the entangled state shown in the center of this page?
Or rather, if such a scenario were to hold, would it be considered as explained on page 69 below?
----------------

【Chrisより】
Hello Fujio,
You are correct that entanglement is one of the most important parts. 

Q1. You are correct. There are 100 pairs of clocks. Each pair of clocks is entangled. For each pair, you have one and I have the other.

Q2. The entangled state shown corresponds to one pair of entangled clocks. As soon as one of us looks at a clock, the state immediately jumps to either 

 or .

 Both states are unentangled. We either both get YES or both get NO.

 Our clocks are correlated, they always agree, but they don’t “decide” what the answer will be until one of us looks at (measures) our clock.


Hope this helps,
Chris 
----------------

【山本より】
Dear Chris,
Thank you very much for your reply.
Your answer cleared my mind.
I totally understand!
This takes me to Chapter 5, "Bell's Inequality".

I have already featured this book of yours in my blog post.
It's in Japanese so you may not be able to read it, but here it is:
https://sparse-dense.blogspot.com/2022/10/2022.html

I hope my question and your answer will be useful to other readers.
May I publish this response as-is on my blog?

Add the following information:
A Japanese version of this book was already published by Yuichiro Minato et. al.
In the middle of p.68 of the English version, "and I have the hundred partners." was mistranslated as follows:
"suppose there are 100 people to be paired with me"
I quickly realized that it was a weird translation, but your answer made it clear.
----------------

【Chrisより】
Of course! The translation sounds a little strange. Your blog looks as though it could be very helpful.
----------------

【山本より】

Dear Chris,

With your answers to my previous questions, I was able to read and understand Chapter 5 Bell's Inequality. Just in case, I would like to confirm. I understood as below, is it correct?

In the classical model, the results of Alice's and Bob's agree at least 5/9 (=0.55) in the case of P.82. The existence of such a lower bound is called Bell's inequality.

On the other hand, in the Quantum theory model, both results agree exactly by half (=0.50). The difference between the classical model and the quantum model, that is, 0.55 not equal 0.50, is called Bell's inequality violation.

Best regards,
Fujio Yamamoto

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

【Chrisより】

Dear Fujio,

The classical model predicts the proportion of times the measurements agree to be at least 5/9. Quantum theory predicts 1/2. These two numbers are not equal — that’s Bell’s inequality. It means that we can perform experiments to determine which theory is incorrect. 

All experiments performed so far, have agreed with quantum theory.

Chris

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

【山本より】

Dear Chris,

Thank you very much again for your reply.

The word "inequality" reminded me of ">" or "<", so I focused on the "lower limit" or "upper limit". Anyway, now I have a clear understanding.

I think your book can be divided into chapters 1 to 5 (Bell' Inequality) and chapters 6 onwards. The first half is basic theory and the second half is applied. I understand the first half almost perfectly, so I can work on the second half smoothly.

Incidentally, I was able to find a street in Belfast on Google Maps named "Bell's Theorem Crescent". Great!
----------------

【山本より】

Dear Chris

I really like your book on Quantum Computing and am studying.
I wrote a blog post to remind myself of what I've learned about Entanglement and the Ekert protocol.

#My understanding of the Quantum Key Distribution Protocol Ekerthttps://sparse-dense.blogspot.com/2022/11/my-understanding-of-quantum-key.html

Thanks for your wonderful book.

Regards,
Fujio

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

【Chrisより】

Dear Fuji,

Great post — and in English!
Thanks for sending me this,

Chris 
----------------

2022年10月10日月曜日

MIT App Inventor of the Month受賞5回の記録

 前報で、過去6年間のブログ記事の分析を行いました。この中で、ダントツに"MIT App Inventor"の出現頻度が高いことが確認できました。確かにかなり入れ込んできました。しかしながら、「MIT App Inventorがあるからそれで何かを作ろう」としたことはありません。いつも、「こういうものを設計して作りたい」という発想が湧き、その実現にはMIT App Inventorが適している、という思いで取り組みました。

 その中で、幸い、”MIT App Inventor of the Month”という賞をこれまで5回受賞することができました。守りに入る姿勢は取りたくないのですが、以下に、それらを纏めて記録しておくことは意味があると考えました。下図にあるような、出来上がったアプリのロゴをデザインするのも楽しいことでした。
Age doesn't matter, do what you believe in.

 ●先方からの講評とアプリの内容説明Webページ(英文)

(1)June 2019:Enjoy Reinforcement Learning in Tic-Tac-Toe
Retired Computer Science professor Fujio decided to make use of the new generic blocks in App Inventor to make this app where you can train the mobile device to play tic-tac-toe using reinforcement learning.
https://sparse-dense.blogspot.com/2019/05/enjoy-reinforcement-learning-in-tic-tac.html

(2)Dec 2019:My Live Camera
Retired computer science professor Fujio from Japan, created this fascinating app to access some of his favorite live cameras from across the world. You can enjoy real-time views of some amazing places such as Mount Fuji. We hope you will enjoy it as much as we did.
https://sparse-dense.blogspot.com/2019/11/enjoy-live-cameras-from-around-world-on.html

(3)March 2021:Enjoy finding out Hamiltonian cycles
Fujio Yamamoto is an emeritus professor from Japan who made this complex app that solves the Hamiltonian cycle problem for a given graph. It's complex yet comprehensive, and if you've ever wanted to learn about Hamiltonian cycles, this is a great place to start!
https://sparse-dense.blogspot.com/2021/02/enjoy-finding-out-hamiltonian-cycles.html

(4)Oct 2021:Running Q-Learning On Your Palm
Retired emeritus professor of Computer Science Fujio, from Japan, created this amazing app to explain the basic idea and mechanism of reinforcement learning (especially Q-Learning), which is a field of artificial intelligence. We needed some MIT students to help us understand the advanced ideas behind this app, and we are glad to see such deep ideas realized in App Inventor.
https://sparse-dense.blogspot.com/2021/08/enjoy-q-learning-with-simple-example.html

(5)Sept 2022:Noise Reduction QA
Professor Yamamoto from Japan has created this app that uses quantum annealing, a type of quantum computing, to reduce noise in images. The app, which runs on most mobile devices, lets you experience the processing of a quantum annealing machine that is different from existing computers. Dr. Yamamoto would like to thank Dr. Masanao Yamaoka of Hitachi, Ltd., who developed the CMOS annealing machine, for answering various technical questions.
https://sparse-dense.blogspot.com/2022/09/image-noise-reduction-based-on-quantum.html

 ●補足:もう一つ受賞していました-Thunkable Top Developer 2016 

(0)Jan 2017:Elevator Fun
Elevator Fun / Make Your Own Version Elevator Fun was developed by Professor Fujio Yamamoto of Kanagawa Institute of Technology, Japan to encourage his students to develop their own Android apps rapidly. The app estimates the next arrival floor of an elevator using the acceleration sensor, aka accelerometer, equipped on each phone. The app detects the velocity profile, in particular, the length of a constant velocity section, which corresponds to the number of floors the elevator passes through during a trip. Since elevators have different speeds, you can calibrate the app with the actual performance of your elevator. Great for those living and working in tall buildings!
https://sparse-dense.blogspot.com/2017/01/android.html

2022年10月9日日曜日

6年間のブログ記事380件のタイトルに出現した単語の分析

 これまでの6年間、ブログ記事を毎年60件以上書いてきました。合計で約380件となりましたので、少し振り返ってみます。

●6年間のブログ記事タイトルに出現した単語の分析
 毎年のブログ記事それぞれ約60件強のタイトルを形態素解析して、単語の出現頻度を調べました。これには、userlocal.jpの自然言語解析ツール[1]を利用しました。極く短くまとめると以下のようであることが確認できました。

2017年:人工知能、Deep Learning、Tensorflowが全盛。(2016年分も含む)
2018年:MIT App Inventor、及びJavaによる拡張、micro:bitとの連携など。
2019年:MIT App Inventorと画像処理、AIとの連携など。
2020年:自然言語処理、特に、植物の自由記述からJsonの自動生成。
2021年:強化学習の基本とその応用に移行。
2022年:量子コンピュータ関係に傾倒。
 この単語出現頻度の分析結果は、単に個人の興味の推移を表しているに過ぎないかも知れません。ですから、他の人にはほとんど何も意味をなさないとも言えます。

 しかし、見方によっては、世の中の動向や技術の潮流をある程度反映しているとも言えます。私の個人的な見方では、Deep Learningはもはや誰でも使いやすいソフトで利用できるので、必要に応じて使えばよいという思いです。その後、自然言語処理に興味が移り、さらに、強化学習へまた移りました。そして、現在は、完全に、量子コンピューティングということになってしまいました。目移りばかりせずに、温故知新も真実と思いながら。

【付録】
 少し違う観点の解析もできます。下図は、「量子コンピューティング」に関するブログ記事12篇の本文全体を纏めたテキストにおける、共起語解析結果です。「量子アニーリング」はかなり多数出現しているのですが、「量子コンピュータ」に比べると様子が異なります。「量子アニーリングは量子コンピュータではない」という説を裏付ける?かのようにも見えますが、本当のところはよくわかりません!

●利用したソフト
[1] ユーザーローカル テキストマイニングツール( https://textmining.userlocal.jp/ )

2022年10月8日土曜日

量子アニーリングアプリで「MIT App Inventor of the Month」を受賞

 当方が開発したスマホアプリ「Noise Reduction QA」が、米国MIT CSAIL(マサチューセッツ工科大学 計算機科学・人工知能研究所)より、「2022 September's MIT App Inventor of the Month(Adult Inventor部門)」に選定されました。以下の講評をいただきました。

Professor Yamamoto from Japan has created this app that uses quantum annealing, a type of quantum computing, to reduce noise in images. The app, which runs on most mobile devices, lets you experience the processing of a quantum annealing machine that is different from existing computers. Dr. Yamamoto would like to thank Dr. Masanao Yamaoka of Hitachi, Ltd., who developed the CMOS annealing machine, for answering various technical questions.

The MIT App Inventor Team
Massachusetts Institute of Technology 
Computer Science and Artificial Intelligence Lab

 このアプリは、量子アニーリングと呼ばれる方式のCMOSアニーリングマシン(日立製)を利用して、白黒画像に重畳されたノイズを低減させるデモプログラムです。アニーリングマシンは、従来のコンピュータとは全く異なる仕組みで動き、複雑な「組合せ最適化」と呼ばれる問題を高速に解くことが期待されています。今回のアプリは、身近なスマホから、このような量子アニーリングに親しむことを目的として開発されました。

●MIT App Inventor of the Monthのページ:
Congratulations to September's Adult Inventors!の区分

●本アプリの説明ページ:

以下、受賞デジタルバッチと受賞アプリの画面です。

 MIT App Inventor公式Twitterにも紹介されています。(2022-10-08現在)

2022年10月5日水曜日

ノーベル物理学賞2022の量子理論を高校数学で学ぶ

 今年のノーベル物理学賞は、昨日(2022-10-04)ノーベル財団から発表されました:

 The Nobel Prize in Physics 2022 was awarded jointly to Alain Aspect, John F. Clauser and Anton Zeilinger "for experiments with entangled photons, establishing the violation of Bell inequalities and pioneering quantum information science"
(2022年のノーベル物理学賞は、アラン・アスペクト、ジョン・F・クラウザー、アントン・ザイリンガーの3人が共同で受賞した。"もつれた光子の実験、ベル不等式の違反の確立、量子情報科学の先駆的な業績" - DeepL翻訳による- )

●量子情報科学のpioneering
 と書かれていますので、情報工学に関わる人であれば、その知識を得たいと考えるでしょう。私もその一人です。

●高校数学で量子コンピューティングを学べる本
 Fairfield大学の数学者 Prof. Chris Bernhardtが書いた「Quantum Computing for Everyone」という書籍で勉強中でした。彼は、数学者として、高校数学の範囲でできるだけ明快に量子コンピューティングを解説する、それには、数式は欠かせない、という方針を貫いています。
The goal is not to give some vague idea of these concepts but to make them crystal clear.
(目標は、これらの概念について漠然とした考えを与えることではなく、非常に明確にすることです。)

 この書籍の主要部は、下図にある通り、ノーベル賞説明にある「 entangled」と「Bell inequalities」などです。第4章 Entanglement(量子もつれ)や第5章 Bell's Inequality(ベルの不等式)が目次にあります。実際、上記の方針どうり、高校数学で分かる数式を用いて、厳密に、簡潔に、丁寧に書かれていて、感心するばかりです。
 量子コンピューティングに関する教科書は他にも優れたものがいくつか出版されていますが、Chris によるこの書籍は、それらの中でも、簡潔さ、一貫性、数式による明快さにおいて、非常に優れていると感じます。また、平易な英文に徹しているところも嬉しいです。ということでご紹介しました。

●高校数学で説明できるのですか?
 ごもっともな質問です。YesでもありNoでもあると思います。
 Yesとは、実際にEntanglement(量子もつれ)とBell不等式については、本質的なところ基本的なところは高校数学の範囲の数式で明快に説明していると思います。

 Noとは、それでも限界があるようです。というのも、著者はこの本では実数の世界で話を展開しています。普通に考えれば、量子力学の世界は複素数の世界ですね。彼は数学者ですから、そこは十分に考慮した上で独自の説明をしていると思います。実際、例えば、ショアの因数分解アルゴリズムもこの本の最後の方に出てきますが、そこも実数の世界で、"taste"を解説するに留めています。そして、これより深くは、複素数を扱うさらに上位のテキストで学んでほしいとしています。

 しかしながら、量子コンピューティングに携わる一般的なソフトウェア技術者に必要な量子力学の基礎知識は、実数の世界で十分身に付けられる。その実数世界において、きちんと数式を使ってクリアに説明を尽くすという考えだと思います。その通りになっているので大いに感心します。

●このChris Bernhardt著に関する情報
彼のwebサイトに本書に関する幾つかの有用な情報が載っています。

(1)  Quantum computing in 10 minutes
 10分で分かってもらえるかわからないが、ともかく書いてみました。という本書全194ページをまとめた資料。

(2) Short intro to IBM quantum computer
 本書は数式で概念を明確にすることに徹しているのだが、この資料は、それらをIBM Quantumマシンで確かめるための短い手引き。これも有用だ!

(3) そして、執筆意図などについて、著者がインタビューに答えるpodcastもある!

2022年10月4日火曜日

極細0.2mmのシャープペンシルの使い心地

 筆記用具の話です。電子書籍を読むことがあるのですが、これはじっくり読みたいとなった場合は、どうしても紙の書籍を注文してしまいます。赤や青で線を引いたり、余白や行間にメモを書かないと気がすまないからです。そんな時、普通の0.5mm芯のシャープペンでは太過ぎます。最近、0.2mm芯のものがあることを知り、使い始めました。素晴らしい使い心地です!

 きっかけは、量子コンピュータ初歩実験「光子の干渉」をやったことです。ここにその記事があります。レーザーポインタの光線を当てる極細軸として、0.2mmの芯が必要でした。その後、この芯を使うシャープペン「ぺんてるOrenz」を購入して使い始めたところ、予想以上の素晴らしい使い心地でした!
 狭いところに小さな文字を鮮明に書くことができます。そして、0.2mmという極細なのに折れません。素晴らしい芯出しメカニズムになっているようです。芯の出口付近をうんと拡大してみると、シリンダ先端の切り口は丸味を帯びています。そのため、シリンダが紙に触れる前に、わずかに顔を出している芯の方が先に紙に当たる。そこがポイントらしい。

 図にある通り、芯はほとんど見えません。この状態で書き続けられます。芯は細いシリンダに囲まれているので折れないのです。そして、芯が減って行くと、自動的にシリンダも少しづつ縮んで行きます。だいぶ短くなったら、再度クリックすれば良いのです。

 私にとっては、筆記の革命のようです。これまで、0.5mmを使っていた場面でも、代わりにこの0.2mmを使えそうです。以上、ご参考までにご紹介。
 Pentel Orenz 0.2mmのシャープペンの価格は500円〜2000円程度。機構は同じだと思いますが、軸(ケース)の材質やデザインにバラエティがあります。また、同じ0.2mmでも、濃さ(硬さ)はHBや2B等があるので、好みで選ぶことになります。

2022年9月27日火曜日

MIT App Inventorの新設Chart機能の利用例

 MIT App Inventorに新設されたChart機能[1]について、前報で述べました。ここでは、簡単な例で具体的にその使用例を示します。簡単にグラフを描きたい場合の参考にしていただければ幸いです。

■CSVファイルのデータからグラフを素早く描く
 x, yの組みのデータが格納されたcsvファイルからグラフを描きます。図1の左上に示したような.csvファイルです。このファイルから、その右側にあるようなグラフ描画は、下段にある2つのブロックだけで実現できます!最初のブロックでは、このファイルを読み込みます。読み込みが完了すると下のブロックが起動されます。その中では、.csvデータをリスト(リストのリスト)に変換して、それをChart.ImportFromListに与えるだけです。
■グラフを拡大して描画したい
 こんなに素早くグラフを描けたのですが、x軸, y軸とも自動で設定されており、この例では、158点のデータが一つの画面に圧縮して表示されています。そのため、グラフが太くなっています。データ全体の状況はこれでよくわかるのですが、拡大して詳しくみたい場合は、自分で工夫する必要があります。例えば、画面にはいつも15点づつのデータを表示し、グラフは自動的に左にシフトさせるようにしたのが、図2です。この実現にあたっては、[2]を参考にさせていただきました。
■Y軸のmin, maxを指定してグラフをシフトしたい
 図2では、グラフがシフトされるたびに、Y軸方向が自動的に拡大・縮小してしまい、みていると目がチラチラする場合があります。Y軸のmin, maxを指定してY軸範囲を固定できれば良いのですが、現状のChartにそれは無いようです。そこでその機能をなんとか実現させたのが図3です。図2では、グラフ描画のためのChartオプジェクトを1つ使っていましたが、ここでは、別にもう一つのChartオブジェクトを使い、そこには、右端の方に、最小値と最大値にしたい値を設定したのがミソです!
 この場合のグラフのシフトの様子は、下記のビデオをご覧ください。
 この利用例のアプリ(ソースコード)は、以下に公開していますので、詳細が必要な方はそれをご覧ください。

参考資料
[1] Data Science with Charts and GoogleSheets
https://community.appinventor.mit.edu/t/data-science-with-charts-and-googlesheets/66116
[2] Charts component. Graphic shift left
https://community.appinventor.mit.edu/t/charts-component-graphic-shift-left/66169

2022年9月24日土曜日

Data Science work in MIT AppInventor with new Data Charts components

MIT App Inventor is continuously being upgraded in a wide range of ways, from new features incorporating cutting-edge AI technology to convenient features for daily application development. The members of the development team also seem to have grown even more recently. This time, I tried the newly added Data Chart function. Very convenient!

Until now, there was no built-in function for drawing graphs, so if necessary, we used extension functions developed by volunteers, or drew them offline with Excel. Now, anyone can use Data Chart as a standard feature right away. It facilitates visualization of various data. Chart types include standard line charts, bar charts, pie charts, scatter charts, and more. It also has support for many types of data sources.

You can easily draw a graph from a list as shown in Figure 1. The function to convert CSV format and JSON format data to a list is already built in, so this is easy to use. Also, we can use Spreadsheet, CloudDB, and TinyDB as data sources, so they are very convenient when large data files already exist. In addition, adding single point to a  graph is available, so it can be used to display data from various sensors in real time.
Here is one application that uses this Data Chart. This is a recording app of atmospheric pressure fluctuations. Figure 2(a) shows real-time air pressure ​​obtained in a short term from the barometer built into the smartphone.

On the other hand, Fig. 2(b) shows the atmospheric pressure fluctuation when Typhoon No. 19 passed nearby in 2019. The data acquired at intervals of about 5 minutes over 12 hours was stored in CSV file, and it is displayed. You can see that the air pressure dropped sharply at the time of closest approach, and immediately turned to rise.

As the graph shows, the atmospheric pressure of the typhoon at that time dropped by about 40hPa in a few hours, so it was a fairly strong typhoon. Even with a personal smartphone, you can feel the approach of a typhoon like this. If many people do this kind of thing in various places and aggregate those data, it seems to make some big thing.

2022年9月18日日曜日

ドイチュのアルゴリズムで量子計算のこころに触れる(続)

 前回の記事で、ドイチュの量子アルゴリズムを述べた。今回は、その拡張版であるドイチュ・ジョサのアルゴリズムを試した。

■ドイチュ・ジョサのアルゴリズム
 この場合も、値として0か1をとる2値関数f(x)が定数関数か平衡関数かを、ただ1回の関数の評価で判定できるという不思議なアルゴリズムである。今回は、変数xは、0,1,2, ... , 2n-1を取るように値域が拡大されている。この場合の定数関数とは、どのxに対してもf(x)の値は同一であり、平衡関数とは、半分のxに対してはf(x)=0であり、残り半分のxに対してはf(x)=1ということである。
 従来のコンピュータで平衡関数/定数関数を判定するには、f(x)を最大2n-1+1回調べる必要があるが、ドイチュ・ジョサの量子アルゴリズムでは、ただ1回で済む、という素晴らしさがある。

■ドイチュ・ジョサのアルゴリズムの量子回路
 前回同様、渡邉靖志著[1]のドイチュ・ジョサのアルゴリズムとその量子回路の説明を参考にさせていただいた。この著書には、簡潔にその真髄が書かれている。図1に示す通り、特に難しい数式を含むわけではないが巧妙に組み立てられているので、じっくりと腰を据えて理解する必要がある。ここには詳細説明は書けないが、ともかく、この量子回路によって最終的に測定した結果、n個の0の列 "000...0" が観測される可能性が0%であれば、平衡関数であるということだ。
■IBM Quantum実機での実行
 理解を確認するため、n=3の場合の量子回路図を作り、それをIBM Quantum実機で動かしてみた。その際、Qiskitの解説[2]を参考にさせていただいた。図2に定数関数の場合の、図3に平衡関数の場合の判定結果をそれぞれ示した。いずれも納得できる結果だが、現状の実機ではノイズのために幾らかの誤差が生ずる。すなわち、理論的には観測されないはずのビット列も若干観測されたが、結果の判断に影響はない。
 なお、誤差のない理論通りの実行結果を得て、理解を進めたいのであれば、実機ではなくシミュレータを使えば良い。IBM Quantumの環境では、実機の場合と全く同じインタフェースでこのようなシミュレータを使うことができる。また、図4に示す通り、Qni量子シミュレータを使うのも良いだろう。
参考文献
[1] 渡邉靖志:入門講義 量子コンピュータ、講談社サイエンティフィック、2021年11月24日初版
[2] Open-Source Quantum Development Qiskit,
https://qiskit.org/textbook/ja/ch-states/introduction.html