多彩な独創的アイディアや美しい数式にもたくさん出会った。改めてここに、テンソル積とドイチェ・ジョサのアルゴリズムに関する２つの数式を掲載して、今年のお別れとしよう。
The Kronecker Product of Hadamard Matrices:
Thank you all.
I am a professor emeritus of CS at Kanagawa Institute of Technology, Japan. Originally my specialty was parallel and distributed systems. My current interests include machine learning, natural language processing, creating mobile apps with MIT App Inventor, and quantum computing. In the web version of this blog, clicking the icon on the right (a plastic sphere) will take you to the "List of Quantum Computing Articles". - Fujio Yamamoto (for e-mail, add "@ieee.org" after "yamamotof")
2022年12月31日土曜日
量子コンピューティングの入り口に到達したこの半年
とうとう大晦日を迎えた。この半年は、量子コンピューティングを学ぶことに大半を費やした。まだ序の口だが、この世界の入り口に立つことができた。驚きの量子アルゴリズムに触れ、それを計算によって、さらに、量子回路シミュレータや量子コンピュータ実機で確かめる手順も体験してきた。さらに前へ進めそうな気がしている。
Qubits state (superposition) after the Oracle for the Deutsch-Jozsa:
2022年12月29日木曜日
切り干し大根づくりと推敲
令和４年（2022年）が暮れようとしている。この時期、例年、ベランダで切り干し大根を作る。さっと洗って、皮を剥き、7mmくらいの厚さに輪切りにする。経験上、5mmでは薄すぎで1cmでは厚すぎるのだ。あとは、干物専用の吊り下げ網かごに入れて、天日をあて寒風にさらせば良い。一週間前後で完全に硬く乾燥して出来上がり。太陽で乾燥させると、うま味成分のグルタミン酸とGABAの含有量が増えるとのこと。水で戻して調理すれば、とても美味しく、栄養価も高い。
こじつけではないが、日数をかけた天日干しは、ブログ記事等の推敲と似たところがあるかも知れない。生のままではあまり美味しくない。何度か見直し、余分な水分を飛ばし、不足要素を加味し、エッセンスを凝縮させることで、簡潔で味わいのある文章になって行く気がする。読者にも美味しさが伝わるであろう。
全くの偶然なのだが、本日12月29日、私のブログへのアクセス回数（ページビュー）が、記念すべきジャスト10万回に達した！ブログ開設は2016年11月なので、ほぼ６年経過ということになる。大変ありがたいことだ。読んでいただくために書いているのだから。
アクセス回数10万回に到達（2023-12-29 13:00）
英語記事も少しはあるのだが、ほとんどは当然ながら日本語である。だが、Googleの分析ツールで見ると、米国や欧州、アジア諸国など海外からのアクセスも意外に多いこと分かった。日本語が分からなくても、ブラウザからGoogle翻訳で簡単に（かなり精度良く）自動翻訳できることが効いているのだと思われる。世の中、進化したものだ！
過去1ヶ月間の統計データ
今後も心構えは変わらない。切り干し大根のように、内容を凝縮する推敲を重ねる。不完全ながらも、それに近づけて行きたい。
2022年12月21日水曜日
Groverの探索（量子アルゴリズム）でコンビニ出店案
【要旨】Groverの探索は、典型的な量子アルゴリズムの一つである。これは、可能性のある全ての探索問合せを量子重ね合わせの原理で一度に行い、量子状態の確率振幅を波の干渉のように増幅/減衰させる。この繰り返しによって、解を浮き上がらせ、確定させる。そのような驚異のアルゴリズムである。その概要は、すでに本ブログ記事[1]でも述べた。ここでは、IBM Quantum Challenge 2019[2]で出題された課題「コンビニ出店案作成」に対するGrover探索による解答例を追試行し、その威力と魅力を確認した。
[量子アニーリングによる結果も、末尾に追加した。]
●Grover探索アルゴリズムの概要
すでに、別の記事[1]で述べたので、ここでは極く簡単に復習する。簡単な例として、00、01、10、11を入力とする関数fがあり、fはある一つの入力に対してのみ１であり、その他の入力に対しては0を出力する。関数値f(xx)=1となる入力xxを求める問題である。古典的探索では、最悪の場合、関数fの評価を３回行う必要があるが、Groverによれば、それは１回で済む。図１はこのアルゴリズムを実現する量子回路とその説明である。
まず、Oracleと呼ばれる量子回路を作る。それは、４個の全ての入力を纏めた量子重ね合わせを受け取り、f(xx)=1となる|xx⟩の確率振幅の符号を反転させる。その際、 解xxに応じたOracleを構成するのである。だが、これは解をすでに与えているわけではなく、課題そのものの記述に相当する。Oracleの中で、関数fは１回評価される。
次に、Grover反復と呼ばれる確率振幅の増幅/減衰により、解を他から分離することができるのである。すなわち、解を与える入力のみが多数回測定されるように作られている。そこが核心部分である。この例では反復１回で明確に解が得られた。一般には、入力サイズNに対して、√N回のオーダーの反復で解が得られることが知られている。
●課題：コンビニ出店案の作成
少し現実的な「コンビニ出店案の作成」にGrover探索を適用する。これは、IBMのQuantum Challenge 2019での出題[2]を若干変更したものである。図２にその仕様を示した。合計11地区に４社のいずれかのコンビニを一つだけ出店する案を全て列挙せよという問題である。
これはグラフの彩色問題の一つであり、各辺の両端のノードの色が同色になることを禁止することに相当する。すでにA社、B社、C社、D社が図１のようにそれぞれ１店を出店済みなので、残り７地区にどのように出店させるかである。
●「コンビニ出店案」をGrover探索で解く
この解法は、最初に挙げた00、01、10、11を入力とする探索と基本的に同じ仕組みである。だが、解がいくつ存在するかわからないので、それに対応するOracleの作成に工夫が必要である。具体的な実装方法とプログラムは参考資料[2]を利用させていただいた。解の候補として考えるべき、７量子による入力は16,384（4の7乗）とおりである。Oracleが構成した後は、上に述べたGrover反復を行えばよい。図３に、Qiskitを用いた量子シミュレーション結果を示した。
この量子シミュレーションでは同じことを500回（500 shots）行ない、その測定値の統計を示してある。図3(a)は、Grover反復１回の状態である。ほとんどの入力は１回だけ測定され、いくつかの入力に対しては２回〜７回程度測定された。さらに反復を続けると、解を与える入力の測定回数が順次増加し、解でないものの出現が減少する。
Grover反復を７回実行した結果が図4(b)である。出現頻度が40〜50と際立つものが９個観測された。それが解だと判定される。実に見事な解法ではないか！
（なお、(a)よりも(b)での縦棒の幅が太くなっているのは、出現回数0回の入力が激増したため、図からそれらが取り除かれたためである。）
●得られた解を確認する
以上の結果を図４の通り確認した。（解が９個しかないことは証明されていないが）恐らくこれが全ての解であろう。確かに、どの解においても、辺の両端のノードは異なる彩色となっており、全ての条件を満たしている。
●感想
驚嘆すべき量子アルゴリズムの一つであるGrover探索を、ある程度現実的な問題にも適用できることが分かった。IBM Quantum Challengeでは、現実的な課題を順次増やして量子コンピューティングコミュニティを活性化させようとしている。いずれ、そこで出題される課題にも挑戦してみたい。また、冒頭に述べたように、この課題は、量子アニーリングの利用にも適していると思われるので、そちらも試す価値はあるだろう。
[追加]2022-12-22
その後、量子アニーリングによる解法もやってみた。参考資料[3]のデモアプリ（グラフ彩色）を参考にした。縦軸にノード番号、横軸に色番号のマス目を作り、そこに０（該当せず）か１（該当する）が入るようにする。初期設定済み（出店済み）に対応するマス目は１とする。各行についてone-hot制約を、各色について隣接ノード同士の値の積が０となるように制約を設定する。それに対して量子アニーリングを実行すれば良い。その結果、上記と同一の９個の解が得られたので、以下に掲載する。
参考資料
[1] 初級量子コンピューティングの旅の目的地Grover:
[2] IBM Quantum Challenge 2019:
[3] Fixstars Amplify,
2022年12月13日火曜日
量子コンピューティングの基礎を学べる書籍を読み終えて
【要旨】量子コンピューティングの基礎を学ぶための情報は色々あるが、Prof. Chris Bernhardtの著書”Quantum Computing for Everyone”はその中でも特別に優れたものだった。本日までにその全ページを読み終わり、そのほぼ全てを十分に理解できたと思っている。それを振り返り、自分自身の今後の前進に役立たせたい。また、他の読者にも参考にしていただける点があるかも知れないので記事とした。[English version is here]
●どんな書籍なのか
量子コンピューティングとは何かを、一般常識としての読み物ではなく、厳密に解説している。他書と違うのは、高校レベルの数学で、量子コンピューティングの本質を見事に説明している点である。冒頭に、”The goal is not to give some vague idea of these concepts but to make them crystal clear.”と記されているのだが、まさにその通り、最後まで「水晶の如く明瞭」は本当であった。
基礎レベルとはいうものの、量子ビット、量子重ね合わせ、量子もつれ、はもちろんだが、2022年度ノーベル物理学賞で話題になった”Bellの不等式”までも、一定の厳密さを保って扱っている。難しい仕組みも巧みに整理して、可能な限り簡単化し、数式を使った厳密性を維持しつつ、高校数学レベルで分かるように叙述しているのである。例えば、終盤に出てくるSimonのアルゴリズムは、（難度☆☆）が付与されており、とても難しいのだが、そこでの、Hadamard(アダマール)行列のKronecker Productを利用した簡潔な説明は、実に見事である。また、秘密stringの要素に関する線形方程式の生成（出力）は、２つの波の干渉のように、確率振幅を増幅させたり、キャンセルで減衰させたりする制御を含んでいる。これも量子計算の真髄に触れることができるものだ感じる。
さらに本書の特徴を述べるならば、非常に広い観点から書かれていると言える。本著者は、”Turing’s Vision – the birth of computer science –“という本の著者でもあり、計算科学に深い造詣を持つことが伺われる。実際、本書は単なる技術書ではなく、計算の複雑度、可逆性などの計算基礎理論からの観点を随所に示している。また、量子物理学の根本に関わるEinstein、Schrödinger、Bohr、Bellらの議論も適切に解説し、読者のバックグラウンドを広げるのに役立っている。教育的観点から、理論を説明した後に、読者が計算を追えるように、具体例が必ず付随している。それは理解を確認するのに大いに役立つ。
ここまで述べると、本書は非常に堅い印象を与えるかも知れないが、以下のような日常社会の生活との関わりも書かれており、明るい気持ちにさせてくれる。例えば、次のようなエピソードを書いている。(1)光の偏光の説明部：友人の物理学者からもらった偏光板をポケットに入れてその不思議さを楽しんでいる。(2)「Bellの定理」という名の付いたBelfastの通りがあり、Google mapsでそれを確認できる。(3)量子の測定装置が回転しているのか、移動する量子ビットが回転するのか、そのどちらかが分からないのは、通勤で乗っている自分の電車が動き出したのか、すぐ向かいの別の列車が動き出したのかが分からなくなるのと似ている。(4)量子ビット誤り訂正のセクション：学生時代、聴いていたレコードに傷が付いた場合、毎分33回のプチプチ音に悩まされた。しかし、CD出現後はエラー訂正機能によりそれが解消した。
●どのように本書を学んだのか
本書に出会う前は、量子アニーリングを学んで、組み合わせ最適化問題のアプリケーションをいくつか作った。ゲート型量子コンピューティングについても、Webに載っている情報などから、断片的に知識を得ていた。だが、本書によって初めて系統的に量子コンピューティングを学ぶことになった。
毎日数時間をかけて読み進めた。全てのページを読み終わるまでに約２.５ヶ月を要した。現時点では、本書の全ての内容をほぼ十分に理解できたと考えている。この間に、理解し難い箇所は、２回、３回、あるいはそれ以上繰り返して読むことで理解に至った。その過程で、著者に幾つかの質問を電子メールで行い、丁寧に回答いただいたことによって前進できたところもある。また、重要な区切りごとに立ち止まり、自分の理解を確実にするため、その内容をブログ記事として公開した。その記事リストは本記事の末尾に記す。
本書は叙述で徹底的に理解する方針がとられており、現在では利用可能な量子回路シミュレータや量子コンピュータを使っていない。私もそれに従い、紙と鉛筆で理解できるまでは量子回路シミュレータを使わないようにした。そして、理解が十分になった後に、シミュレータでそれを確認した。そういう手順の方が理解が深まると感じた。つまり、最初からシミュレータを動かし、結果を見てしまうと、アルゴリズム自体へ深く入り込むのが阻害される気がしたからである。先駆者であるBellやDeutsch、Simon、Groverなどの時代には、量子回路シミュテータは存在していなかったであろう。
●まとめ
本書には驚くべき量子の性質と、それを利用した多数の量子アルゴリズムが記されている。その中で特に私が強い印象を受けたものを３つリストアップするとすれば、Bellの不等式、量子テレポーテーション、そしてSimonのアルゴリズムである。今や、本書をほぼ全て理解できたことで、私は一段高い位置に立つことができた。今後、さらに高度な量子アルゴリズムにも立ち向かうことができるだろう。最終章では、IBMやGoogleの量子コンピュータ開発状況とそのインパクトについても考察している。著者の以下の言葉を引用して終わりとしたい。
“Computation is really quantum computation. Classical computations are just special cases of quantum ones.”
“The greatest years for quantum computation are ahead of us.”
●Blog posts written to confirm understanding of the book (mostly in Japanese)
・Simon's Monumental Quantum Algorithm（2022-12-11）
・Qubit error correction using quantum teleportation（2022-12-04）
・Fredkin's Universal Logic Gate with Billiard Balls（2022-11-16）
・A street in Northern Ireland named "Bell's Theorem"（2022-10-24）
2022年12月12日月曜日
Impressions after reading “Quantum Computing for Everyone”
Abstract
Prof. Chris Bernhardt's book "Quantum Computing for Everyone" on the fundamentals of quantum computing stands out among the many. By today, I had read all the pages of it and understood almost all of its content. I want to look back on it and use it to help me move forward in the future. I also wrote this article because it might be useful for other readers.
●What kind of book is it
This book is a rigorous explanation of what quantum computing is, rather than just general knowledge. It differs from many other books in that it does a great job of explaining the essence of quantum computing in high school mathematics. At the beginning, it says, "The goal is not to give some vague idea of these concepts but to make them crystal clear." Exactly so, until the very end, "crystal clarity" was true.
Although it is at a basic level, qubits, quantum superposition, quantum entanglement, and even "Bell's inequality", which became a hot topic at the 2022 Nobel Prize in Physics, are explained with a certain degree of rigor. He skillfully organizes a difficult system and makes it as simple as possible. And while maintaining the rigor of using mathematical formulas, it is described so that it can be understood at the high school mathematics level.
For example, Simon's algorithm at the end looks very difficult. But the concise explanation using the Kronecker Product of the Hadamard matrices is really nice and makes it understandable. Also, the generation (output) of the linear equations for the elements of the secret string includes control to amplify or cancel the probability amplitude, such as the interference of two waves. This is also a way to get in touch with the essence of quantum computing.
Moreover, the book is written from a very broad perspective. The author is also the author of the book "Turing's Vision - the birth of computer science -" and has a deep knowledge of computational science. In fact, this book is not just a technical book, but shows everywhere the viewpoint of basic theory of computation such as computational complexity and reversibility. It also appropriately explains the discussions of Einstein, Schrödinger, Bohr, Bell, and others, which are related to the fundamentals of quantum physics, to broaden the reader's background. From an educational point of view, the theory is always followed by a concrete example so that the reader can follow the calculations. It helps a lot in checking understanding.
So far, this book may give you a solid impression, but it also writes about the relationship with the daily life of society as follows, and it makes me feel bright. For example, the following episodes are written. (1) In the explanation of the polarization of light: he puts in his pocket polarizers given to him by a physicist friend of his and enjoys its wonder. (2) There is a street in Belfast named "Bell's Theorem" which can be found on Google maps. (3) We may not know whether the quantum measuring device is rotating or whether the moving qubit is rotating. It's like when I'm commuting to work, I don't know if my train has started or the train across from me has started. (4) In the qubit error correction section: when he was a student, he suffered from 33 popping sounds per minute when the vinyl record was scratched. However, the error correction function of the CD eliminated it.
●How did I read this book
Before I came across this book, I was learning quantum annealing and made some applications for combinatorial optimization problems. I also got fragmentary knowledge about gate-type quantum computing from information on the web. But this book is the first time I've systematically learned about quantum computing.
I spent several hours reading each day. It took about 2.5 months to finish reading all the pages. At this point, I was able to understand almost everything in this book. During this time, I understood the difficult parts by reading them twice, three times, or more. In the process, I asked him several questions about the book by e-mail, and he kindly answered them. In some ways, this has allowed me to move forward. I also stopped at key milestones and published them as blog posts to ensure my understanding. A list of such articles is included at the end of this article.
This book aims to provide a thorough understanding of theory. It does not use currently available quantum circuit simulators or quantum computers. I followed suit and avoided using quantum circuit simulators until I could understand them on paper and pencil. After fully understanding it, I confirmed it with a simulator. I felt that such a procedure would deepen my understanding. In other words, I thought that running the simulator from the beginning and looking at the results would prevent me from delving deeper into the algorithm itself. Quantum circuit simulators would not have existed in the days of pioneers such as Bell, Deutsch, Simon and Grover.
●closing
This book describes the amazing properties of quantum and the numerous quantum algorithms that make use of them. Among them, if I were to list three that impressed me the most, they would be (1) Bell's inequality, (2) quantum teleportation, and (3) Simon's algorithm. Now that I understand almost everything in this book, I'm on a higher tier. In the future, I will be able to tackle even more advanced quantum algorithms. In the final chapter, he also considers IBM and Google's quantum computer development status and its impact. I would like to end by quoting the author's words:
“Computation is really quantum computation. Classical computations are just special cases of quantum ones.”
“The greatest years for quantum computation are ahead of us.”
●Blog posts written to confirm understanding of the book (mostly in Japanese)
・Simon's Monumental Quantum Algorithm（2022-12-11）
・Qubit error correction using quantum teleportation（2022-12-04）
・Fredkin's Universal Logic Gate with Billiard Balls（2022-11-16）
・A street in Northern Ireland named "Bell's Theorem"（2022-10-24）
2022年12月11日日曜日
Simonの記念碑的量子アルゴリズム
【要旨】Simonの量子アルゴリズム（by Daniel R. Simon, 1994）は、従来アルゴリズムではデータサイズに対して指数関数的に計算量が増大するある問題を、量子計算によって線形 (+α)オーダーの計算量で解けることを示した記念碑的なものである。その詳細は参考文献[1]にあるが、著者Prof. Chris Bernhardtはこれに、難度☆☆（ダブルスター）を付け、非常に難しいとしている。しかしながら、彼は、難しい仕組みも巧みに整理して可能な限り簡単化し、かつ、数式を使った厳密性を維持し、高校数学レベルで分かるように叙述している。そのため、じっくり読むことで具体的に理解することができた。本記事では、アルゴリズムの詳細は略すが、その結果として何が出力され、それが何を意味するかを、小生の理解に立って纏めた。さらに、量子回路シミュレータ[2]でその働きを確認した。
●Simonの量子アルゴリズムを実現する量子回路
References
●Simonのアルゴリズムが解く問題
対象とする問題を示す。長さnのbinary string（0か1の羅列）を入力とし、出力も長さnのbinary stringである関数fがあるとする。ここで、あるsecret binary string（秘密のbinary string）b があり、(y=x or y=x⊕b) の時に限りf(x)=f(y) となる。ただし、bの全ての文字が0であることは無いとする。記号⊕は、bitwise addition of strings modulo 2の意味である。入力xに対する関数値f(x)を問い合わせることはできるが、関数fの定義内容と秘密のbが何かは与えられていない。このような関数fが与えられた場合に、解くべきことは、bを特定することである。
秘密のbを知るには、x≠yでありf(x)=f(y)となるxとyを見つける必要がある。そこに至るまでに何回関数fを評価する必要があるのか、それが問題である。古典的方法で、2n個の入力について関数値を問い合わせた場合、連続して半分の関数値が全て異なるかも知れない。この場合は、さらに別の入力１個の関数値を知る必要がある。すなわち、最悪ケースでは、2n-1+1回の関数評価が必要となる。
●Simonの量子アルゴリズムの説明
この問題に対するSimonの量子アルゴリズムの詳細は参考文献[1]にあるが、難度☆☆（ダブルスター）が付されており非常に難しいように見える。しかしながら、この著者は、難しい仕組みも巧みに整理して可能な限り簡単化し、高校数学レベルで分かるように叙述している。その上で、数式を使った厳密性を維持している。特に、Hadamard(アダマール)行列のKronecker Productを利用した簡潔な説明は実に見事、というほかない。図２にその箇所を引用した。
●Simonの量子アルゴリズムを実現する量子回路
上述の通りなので、ここにアルゴリズムの詳細を述べることは避ける。したがって、それを実現する量子回路がなぜ図２のようになるかは略すが、結論をまとめる。上段がOracleである。Oracleとは、問い合わせに答える機能一般に使われる呼称であり、１回の問い合わせにおいて、この中で着目関数fを１回評価する。
Oracleには、量子状態 |0⟩と|1⟩からなる長さnの２つのstringsが入力される。上段の入力は変わらないが、下段の出力は、上段の入力に対して関数fを評価した値と下段の入力との⊕ (bitwise addition modulo 2)となる。このOracleを、図の下側のように利用するのだが、Oracleの左右で、上段の各入力に対してHadamard変換を施すのがポイントである。その後に上段を測定すると、いくつかのn次元の縦ベクトルが得られる。
この測定結果の縦ベクトルをstringsと見做し、それと秘密のbとのdot product (・)を取るとその結果が、どの縦ベクトルに関しても 0（ゼロ）となる。そのように設計されているのである！素晴らしい発想に基づく結果なのである！これは、秘密stringの要素に関する一次方程式を与えることになる。測定結果がこのように与える各一次方程式を連立させて（古典的方法で）解くことで、最終的にbを決定できる。（dot productの意味は図3下部を参照願いたい。）
●量子/古典アルゴリズムの連携
繰り返しになるが、重要な点なので再度記しておきたい。図２の量子回路は、秘密stringの要素に関する線形方程式を出力すると言える。解を得るために必要な線形独立な方程式が出揃うまで、この回路を繰り返し実行する必要がある。それが揃えば、ガウス消去法などの古典的解法を用いて解を求め、bを決定できる。すなわち、量子と古典のアルゴリズムの連携で成り立つ。これと似た状況が、古典通信と連携する量子テレポーションや超高密度符号化においても見られたのは興味深い。
●Simonの量子アルゴリズムをシミュレータで確認する
具体例を量子回路シミュレータQniを利用して確認する。図３ではn=3で、秘密string b=110の関数fに対するOracle Fを作成した。もちろん、この量子回路を使用する側は、bの値は知らない。これをOracleとするシミュレーションを実行すると、右上示した４通りのパタンがそれぞれほぼ1/4の確率で出現することが確認できた。
最初の実行で001が得られ、２回目で111が得られた場合の連立一次方程式とその解を図の下部に示した。（回路図での上方のビットが、stringにした場合は下位になっている。）この場合は、２回のOracleへの問い合わせで、秘密string b=110を特定できることが確認された。
●計算の複雑度（Complexity Analysis）
このような量子回路を何度実行しても（確率の世界ゆえ）bに関する線形独立な方程式が揃わないことは皆無とは言えない。つまり、量子アルゴリズムが古典アルゴリズムよりも遅くなる状況も有り得る。しかしながら、そのようなケースは極めて稀と考えられる。そこで、BQP (for bounded-error Quantum polynomial time)という考え方がある。つまり、データサイズnに依らない定数Nを決め、うまく行かないケースの確率が(1/2)N以下ならばそれを許容（除外）しようとするものである。
詳細は略すが、Simonの量子アルゴリズムでは、適切に決めたNによるerror boundの元では、(n+N) 回のOracle呼び出しで必要な一次独立な線形方程式が揃う。Nはnによらないので、線形の回数での達成となる。それに加えて、古典的方法により、出揃った一次独立な線形方程式をn2のオーダーで解く。（なお、一般の連立一次方程式の解法はn3のオーダーだが、Simonの場合は、変数が全て0か１であり、さらに、秘密string bがオール0ではないことが効いている。）
●感想
このSimonのアルゴリズムは、素因数分解で有名なショアのアルゴリズムに大きな影響を与えたとのことである。この書[1]の最後の章にはそれが説明されている。Simonのアルゴリズムの量子回路で説明した、秘密stringの要素に関する線形方程式の生成（出力）は、２つの波の干渉のように、確率振幅を増幅させたり、キャンセルで減衰させたりする制御を含んでいる。真に量子計算の真髄に触れることができるものだ感じる。
References
[1] Chris Bernhardt, “Quantum Computing for Everyone”, MIT Press, 2020
https://www.chrisbernhardt.info/
[2] Qni; https://github.com/qniapp/qni
2022年12月4日日曜日
量子テレポーテーションを利用した量子ビットのエラー訂正
【要旨】量子ビットは環境とのインタラクションによって壊れやすい性質があるので、量子コンピューティングおいてエラー訂正は非常に重要である。エラーの種類は様々だが、ここでは、量子ビットの誤反転の訂正（Quantum Bit-Flip Correction）を考える。その方法は、古典ビットにおいて広く利用されているパリティチェックに基づく。だが、それを量子ビットへ拡張するには、量子ビットの複製を作成できないことや、量子ビットの測定によりその状態は消滅するなどの問題がある。参考文献[1]には、量子テレポーテーションを利用してそれらを解決する素晴らしい発想が示されている。
次に、受信するBob側の量子回路である。詳細は図２をご覧いただきたいが、新たに２個のqubitsを下部に追加した。送信されてきた３個のqubitsの１番目と２番目のパリティと、１番目と３番目のパリティを計算するためである。これらの結果を見れば、前節「古典ビットのエラー訂正」の説明通りに、どのqubitにエラーがあるか、そしてどう訂正すれば良いかが分かるのである。ここで注目すべきは、これらの２個のパリティ用qubitはいずれも、本来の３個の量子ビットとは「もつれた状態にはない」ことである。つまり、これらのパリティ用qubitsを測定して結果を見ても、上部の３個の量子ビットのもつれ状態には何ら影響を与えない。
References
●従来の古典ビットのエラー訂正（パリティチェック）
まず、古典ビットのエラー訂正の簡単だが有効な方法を復習する。例えば、１ビット情報(0 or 1)を送信する場合、それらの複製を作って合計３ビットを送る。つまり、000か111が送られる。エラーの発生は稀であり、発生したとしても３ビットのうち高々１ビットだけと仮定する。これは現実的な想定である。そうすると、受信側で受け取った３ビットb0b1b2が、例えば、101の場合は111に、001の場合は000に訂正されることになる。一般的には以下のようにすればよい。
b0⊕b1とb0⊕b2が、
00ならば、訂正なし。
01ならば、b2を反転させる。
10ならば、b1を反転させる。
11ならば、b0を反転させる。
●量子ビットのエラー訂正（パリティチェックの拡張）
ここで扱うエラーは、量子ビットの誤反転である。すなわち、量子の本来の状態 a|0⟩+b|1⟩が何らかの理由でa|1⟩+b|0⟩に変化したエラーを検出し、それを訂正したい。そのために、上記の考え方を量子ビットに拡張するのだが課題がある。第一に、量子ビット（qubit）の複製は一般に不可能（量子複製不可能定理）である。第二に、量子の測定（情報の確認）を行えばその時点で量子状態は失われてしまう。しかし、それらを回避して量子テレポーテーションを利用する（qubitを載せる量子を実際には送信せずにその状態を瞬時に転送する）素晴らしい解法がある！
まず図１に示すように、Aliceは送信したいqubit a|0⟩+b|1⟩とそのコピー２個に相当するものを作成する。実際には、複写するのではなく、2個のancilla用のqubitを用意し、それらにCNOTを作用させる。その結果として、３qubitsの量子もつれ状態a|000⟩+b|111⟩が作られる。実質的に送信したいqubitのfan-outを作ったことになる。ここでは、送信するqubitの状態を、一例として、量子ゲートRY[π/3]を用いて設定した。
●量子シミュレータによる現象の確認
以上のエラー訂正の動作を完全に実現することは難しいが、本質的な動きは量子回路シミュレータQni[2]で確認できる。送信された３個のqubitsにエラーが無かった場合を図3(1)に、３番目のqubitにエラーを発生させた場合と、それを検知して訂正した様子をそれぞれ、図3(2)と図3(3)に示した。「古典ビットのエラー訂正」のところで述べたとおり、ここでのパリティ計算結果の01は、上から３番目のqubitにエラーがあることを示している。従って、そのqubitの置かれているwireにPauli Xゲートを作用させればその状態が反転して、エラーが訂正できたことを示している。
●感想
参考文献[1]の著者Prof. Chris Bernhardtは、その第７章の最後で、"We have seen some surprising things we can do with just a few quantum gates."と述べている。まさにその通りであった。古典ビットの世界にはない驚異の発想の存在を知り、それを理解することができ、実際に量子回路シミュレータで（そしてQuantum Computer実機でも）確かめることができたのである。まだまだ氷山の一角というものしか学んでいないが、今後さらにその奥深さを知ることになるだろう。
References
[1] Chris Bernhardt, “Quantum Computing for Everyone”, MIT Press, 2020
https://www.chrisbernhardt.info/
[2] Qni; https://github.com/qniapp/qni
2022年12月2日金曜日
超高密度符号化と量子テレポーテーション（その３）
【要旨】前報（その１）と（その２）に引き続き、本報では量子テレポーテーションについて纏めた。"量子テレポーテーション"という言葉は、宇宙SF映画Star Trekなどで有名になった"瞬間移動"を想起させるが、真の意味はどうなのか？数年前には、実際に数十キロ離れた量子（光子）間でこれが実験で確認されたとの報道もあった。ここでは、Prof. Chris Bernhardt著[1]に書かれている量子の数学モデルを当方が理解し、それを量子シミュレータで確認した結果を説明したい。
●量子テレポーテーションとは何か
これを図１の例で説明する。AliceとBobはそれぞれ１量子ビットを持っており、それらは量子もつれ状態（entangled）にある。さらにAliceは別のもう一つの量子を持っている。その量子状態はAliceもBob知らない。Bobは量子もつれ状態を保ったまま、遠方へ行ってしまった。その状況で、Aliceはこの別の量子の状態を、遠く離れたBobの量子の状態として設定したい。それは、量子もつれの効果により（あたかも光速を超えるかのように）瞬時に実現される。これが量子テレポーテーションである。
ここで、注目すべき点がいくつかある。まず、この実現は、Aliceの量子をコピーして送信したのではない。実際、量子（の状態）の複製は、量子複製不可能定理(No Cloning Theorem)によりで不可能である。この定理は数学的には簡単に証明できる。つまり、複製ではなく、状態の即時転送であり、元のAliceの量子は破壊され、もはや存在しない。だが、実はBobはその転送結果を知るには、Aliceからの古典的通信による情報を別途受ける必要がある。従って、量子テレポーテーションは、実質的には古典的通信の速度で抑えられてしまうのである。以下において、それを詳しく述べる。
●量子テレポーテーションの仕組み
上記例に基づく量子テレポーションの仕組みを図2(a)に示した。図の長い縦青線の左側で初期設定を行う。Aliceの量子ビット（上から２番目）とBobの量子ビット（上から３番目）は、Bell回路によって量子もつれ状態に設定されている。Aliceの「別の量子（上から１番目）」は任意の状態で良いのだが、ここでは、「RY(π/3)」ゲートを通して設定した。
次に、Aliceは自分の２つの量子に逆Bell回路を作用させる。その結果、３つの量子の状態は、（計算過程は略すが）図の右下枠内のような計算式になる。４項の加算になっているが、Bobの持つ量子については、（テンソル積⊗の右側に示すとおり）以下の状態がそれぞれ等しく1/4の確率で発生することが分かる：
aǀ0⟩+bǀ1⟩, aǀ1⟩+bǀ0⟩, aǀ0⟩-bǀ1⟩, aǀ1⟩-bǀ0⟩
従って、このままでは、Bobは自分の量子の状態がこのうちのどれなのかを判断できない。そこで、Aliceが自身の２量子ビットを測定した結果（古典２ビット情報：00, 01, 10, 11）を古典的通信で送ってもらう必要がある。その受信結果に従って、Bobはある量子ゲート[？]を選定し、その作用の結果を測定することになる。●量子テレポーテーションにおいて必要な古典通信
上記に示した、Bobが選定すべき量子ゲート[？]は何かを示したのが図2(b)である。Aliceから受信した結果の"00", "01", "10", "11"に対応して、それぞれ、I, +(X), Z, Yゲートを選定する。それを作用させると、素晴らしい結果が得られる！どのケースでも、Bobは、自分の量子状態が、Aliceが元々持っていた量子の状態そのもになることが分かる！これが量子テレポーテーションの結果なのである！
●超高密度符号化(Superdense Coding)との関係
本報の前に（その２）で、超高密度符号化を取り上げた。以下のように、これと量子テレポーテーションとの関係は興味深い。
すなわち、超高密度符号化では、Aliceは古典２ビット情報をBobへ伝えるために、１つの量子ビットを送った。一方、今回の量子テレポーテーションでは、Aliceは１つの量子ビットをBobへテレポートするために古典２ビット情報を送信した。
さらに、超高密度符号化では、Aliceは４つのPauliゲートを用いてエンコードを行い、Bobは逆Bell回路を持ちいてそれをデコードした。量子テレポーテーションでは、逆に、Aliceが逆Bell回路でエンコードを行い、BobはPauliゲートを用いてそれをデコードしたのである！
今回の記事も、参考文献[1]第７章後半の内容を当方の理解に基づいて纏めたものである。また、量子シミュレータ[2]を利用して量子回路動作を確認できた。
References
[1] Chris Bernhardt, “Quantum Computing for Everyone”, MIT Press, 2020
https://www.chrisbernhardt.info/
[2] Qni; https://github.com/qniapp/qni
2022年12月1日木曜日
超高密度符号化と量子テレポーテーション（その２）
【要旨】前回の（その１）での準備をもとに、本報では超高密度符号化（Superdense Coding）について述べる。極く簡単に言うならば、量子コンピューティングの世界において、Aliceが古典２ビットの情報（00, 01, 10, 11のどれでも）をBobへ送りたい場合、Aliceの持っている一つの量子ビット（電子など）を送るだけで済むという仕組みである。一見、話は簡単そうに見えるかもしれないが、そこには基本量子ゲートとBell回路と逆ベル回路が美しく簡潔に組み合わされている。だが、その仕組みの要点は、前回（その１）で述べた内容に尽きるのである。
続編の量子テレポーテーション（その３）はこちら。
●超高密度符号化の問題設定
この問題設定の例を図１に示す。AliceとBobはそれぞれ１量子ビットを持っている。それら２つは、図に示したような「量子もつれ状態（entangled）」にあるとする。Bobは、この量子もつれ状態を保持したまま、自分の量子を持って遠くへ出掛けてしまった。（現実には遠隔の量子もつれは破壊されやすいのだが、量子の測定を行なわない限り理論的に保持されると仮定する。）ここで、Aliceは、古典２ビットの情報（00, 01, 10, 11のどれでも）をBobへ送りたい。
●何が問題なのか？
AliceがBobへ送ることができるのは、自分の持つ１つの量子ビットだけである。それをBobが受け取った場合、Bobがその情報を得るには測定するしかないが、そうすると量子もつれは無くなり、測定結果は |0⟩か|1⟩のどちらかになる。いずれの場合も、Aliceが送る前の量子状態は壊れてしまうので、Aliceは何を送ったのかをBobは判定できない。さらに問題なのは、この方法では、Aliceは１個の古典ビット（0 or 1）しか送れない。
●Bell基底ベクトルと逆ベル回路を利用する発想
これを解決する素晴らしい発想がある!!!
Aliceは、初期設定後の自分の量子ビットをそのまま送信せずに、まず、ある量子ゲートを作用させる。その際、測定は行わないので、もつれ状態は保持され、Bobの持つ量子ビットに影響はない。図2の上部に示すその量子ゲート「？」を以下のように決める。
すなわち、送りたい古典ビット列が "00"ならば「I」ゲート（何もしない）、"10"ならば「+」(Pauli X）ゲート、"01"ならば「Z」ゲート、"11"ならば「Y」ゲートとする。これらのゲートを、初期設定後のもつれ状態に作用させると、それぞれの結果はBell基底の各ベクトルになる！これをBobへ送る。そこがポイントである。Bell基底とは、Bell( |00⟩), Bell( |01⟩), Bell( |10⟩), Bell( |11⟩)の作用結果として得られるentangledな状態ベクトルのセットである。
ここまでくると、あとは（その１）の記事に書いた通り、Bobは、逆Bell回路を作用させればよい。それによって、Bobは、Aliceが送ったのと同じ古典２ビット情報を得る。図２に示す通りである。ここで注目すべきは、Aliceが送る古典２ビット情報が何であれ、Bobは決まったやり方、すなわち、逆Bell回路を適応するだけでよいのである。なんと美しい解法ではないか！
今回の記事も、参考文献[1]第７章後半の内容を当方の理解に基づいて纏めたものである。また、量子シミュレータ[2]を利用して量子回路動作を確認できた。
References
[1] Chris Bernhardt, “Quantum Computing for Everyone”, MIT Press, 2020
https://www.chrisbernhardt.info/
[2] Qni; https://github.com/qniapp/qni
2022年11月28日月曜日
超高密度符号化と量子テレポーテーション（その１）
【要旨】超高密度符号化と量子テレポーションに関して、Prof. Chris Bernhardt著[1]第７章をどのように学んだかをメモしておきたい。安易にツールや可視化に頼らずに、紙と鉛筆だけを用いて考えながら取り組むことに徹してきた。そして、今や機は熟した。ツール等で知識を確認する段階に達した。こういう手順を踏む方が「分かった喜び」が大きいことを実感した。本報（その１）では、幾つかの基本量子回路の作用を量子シミュレータQni[2]を利用しながら確認した。
●２つの量子ビットの状態における量子ゲートの作用
●Bell回路とReverse Bell回路
この状態にさらにReverse Bell回路を作用させたのが図４である。Bell回路は自分自身が可逆回路である。従って、入力される２量子が４つの状態のいずれであっても、最終的に最初の状態に戻っている。図４には、Bell回路を作用させた後（Entangledの状態）と、さらにReverse Bell回路を作用させた後の状態（Unentangledの状態）を示しているので、このことが確認できるであろう。（なお、回路の適用結果では、量子ビットの並び順が最初の量子状態での量子ビット並びと逆順になっている。）
●単一量子ビットに対するXゲートとHゲートの適用
量子ゲートのうち、単一量子ビットに作用させるPauli X(NOT)ゲートとHadamard（アダマール）ゲートは特に重要だ。図１に示すとおり、これらの作用を量子シミュレータQniで確認した。Xゲートは、量子状態ベクトルをX軸を回転中心としてπだけ回転させる。また、Hゲートは、X軸とZ軸間のπ/4の傾きの軸を中心としてπだけ回転させる。これらによる量子状態ベクトルの確率振幅θと位相φの変化を確認できる。Hゲートの作用として、|0〉と|1〉との重ね合わせ状態（superposition）が作られることが極めて重要である。
図中に、自作の透明ブロッホ球を示しているが、これを手に取りながら、シミュレータの結果を確認できたのはとても良かったと思う。
●２つの量子ビットの状態における量子ゲートの作用
２つの量子ビットの場合、それがなす状態（２つの状態ベクトルのテンソル積）は、４つのケットベクトル |00〉、|01〉、|10〉、|11〉 の線形結合で表わされる。図２に、２番目の量子ビットq1にのみHゲートを作用させた結果を示した。この場合は、共に (1/√2 = 0.707) の２乗の確率（0.5）で |00〉、または |10〉 となることが確認できた。
●Bell回路とReverse Bell回路
次に、本報の続編で述べる「超高密度符号化」と「量子テレポーション」で必要となるBell回路とその逆作用となるReverse Bell回路を示す。図３に示すとおり、Bell回路は２つの量子ビットのち最初の量子ビットにまずHゲートを作用させ、続けて２番目の量子ビットにCNOT（制御付きNOT）を作用させるものだ。結果として、両量子ビットは「もつれた状態（Entangled）」となることが重要な点である。そして、両量子ビットの状態は、それぞれ50%の確率で |00〉 または |11〉 となる。これ以外の状態にはならない。すなわち、両量子ビットに相関関係が生じていることが分かる。
References
[1] Chris Bernhardt, “Quantum Computing for Everyone”, MIT Press, 2020
https://www.chrisbernhardt.info/
[2] Qni; https://github.com/qniapp/qni
2022年11月24日木曜日
量子アニーリングによる渋滞解消のための信号制御
【要旨】数日前に、日立製作所のCMOSアニーリングマシン利用に関するwebサイト[1]に、「渋滞解消のための信号制御最適化」という解説が公開されました。テスト用のPythonソースコードも提供されていますので、早速試してみました。
今回のこの解説は、今後、種々のアイディアを独自に試す場合の非常に重要な拠り所になりそうです。
●渋滞解消のための信号制御最適化
この課題は、古くから取り組まれています。車の自動運転技術も注目されていますが、今のところ、交通渋滞解消を目指すものではないでしょう。しかし、交通渋滞解消の技術は注目されるべきものです。それによる現代社会での経済的、社会的効果は計り知れません。
従来は、車の台数や速度、車間距離、青信号の点灯時間と切り替えタイミング、交差点での進行方向等々を時間変化で捉えて微分方程式モデルを作り解くこともあるようです。しかし、今回の手法は、そういう要素を明示的に使わずに、「交差点をつなぐ道の上にいる車の量」を「青信号の点灯」と関連付けた画期的なモデルだと思われます。参考文献[2]の豊田中央研究所と東大による論文に基づいているとのことです。
●量子アニーリングによる信号制御最適化
詳細は参考文献[1] [2]をご覧いただきたい。非常に丁寧な解説が[1]にあります。「各交差点で待機している垂直方向や水平方向の車の台数を信号制御によって均一化する」という観点から、イジングモデルを組み立てる考え方と具体的な手順が説明されています。もちろん、交差点に入る車の直進、右折、左折の割合や時間変化も考慮されています。そして最終的に、各交差点を量子のスピンに対応させて、スピン間の相互作用係数と外部磁場係数を使ったエネルギー関数（コスト関数）を導いています。
私が気にしていたのは、いくつかの制約条件をどのようにコスト関数に組み入れるのか、でしたが、例えば、隣り合う信号が相反する場合にペナルティを与えることなどをうまく取り入れています。
●実際に動かして試してみよう
原理的なことを一通り理解した上で、日立のCMOSアニーリングマシンを動かして、動きを確かめます。Pythonソースコードが公開されていますので、誰でもできます。ただし、日立から、無料のAnnealing Cloud Web用のAPIキーを取得する必要があります。
動かしてみると、なかなか素晴らしい！解説も分かりやすいのでとても勉強になります。各信号は量子スピンに対応するので、アニーリングの結果として、エネルギー関数を最小化するスピンの向き（北極、南極）のセットが返ってきます。すなわち、その時点では、北極ならその信号器の水平方向を青色に、南極なら垂直方向を青色にするのが最適だ、ということです。
ただ、最適化の結果を見やすくしたい。とうことで、信号の青点灯と交差点での渋滞の度合いを可視化するアニメーションアプリを作成しました。図１にそれを示します。
●感想
色々なことが思い浮かぶのですが、この結果をみると、初期状態でかなり渋滞していても、この最適化で、青信号の点灯方向が変わり、急速に渋滞が解消に向かうことがわかります。その後は、信号の切り替えは穏やかになり、渋滞は徐々に減少します。もちろん、初期状態での車の量や、交差点での直進、右折、左折の割合などで状況は変わるでしよう。また、どこかのスピンが故障して、ある確率で方向が反転してしまう場合に、最適性はどのように失われるのでしょうか。（パリティチェックみたいな機構が付いているのかもしれませんが。）今回のこの解説は、今後、種々のアイディアを独自に試す場合の非常に重要な拠り所になりそうです。
参考文献
[1] CMOS Annealing Cloud Web News
[2] Daisuke Inoue, Akihisa Okada, Tadayoshi Matsumori, Kazuyuki Aihara, Hiroaki Yoshida: "Traffic Signal Optimization on a Square Lattice with Quantum Annealing"
[Submitted on 17 Mar 2020 (v1), last revised 1 Feb 2021 (this version, v2)]
2022年11月19日土曜日
深まる秋、落ち葉とどんぐりを拾う
すっかり秋が深まった。読書の季節とも言われる。だが籠りがちになったら、散歩に出掛けて気分転換するのが良い。落ち葉が増えてきた小径をカサカサしばらく進むと、どんぐりを落とす木の下にきていた。種類は色々あるようだが、この近辺はコナラとマテバシイのようだ。落ちているどんぐりを布で軽く擦るとすぐに艶が出る。不思議な生命がまだ宿っているかのようだ。持ち帰って、落ち葉と共に台紙に貼り付けて眺める。今歩いてきた自然の情景を切り取り、机上に小さく再現したかのような感覚になる。
この他に、もっと丸っこい、イガの付いたどんぐりも見つけていた。クヌギらしい。少し前に、量子ビットの模型（ブロッホ球）を作るために購入した透明アクリル球体が余分に残っているのを思い出した。それに残りのどんぐりを詰めて、机上に転がしてまた楽しむ。
落ち葉やどんぐりの種類は、例えば以下のデジタル植物写真集で手軽に調べることができる。今回は、コナラ、マテバシイ、クヌギのどんぐりを確認することができた。
2022年11月16日水曜日
ビリヤードボールを使ったFredkinの万能論理ゲート
【要旨】量子コンピューティングに関するProf. Chris Bernhardtの著書[1]第６章は、"Classical Logic, Gates, and Circuits"だが、一般の論理回路の教科書には多分載っていない「Fredkinゲート」の説明がある。それは、著名な物理学者ファインマンも感銘を受けたと言われる、「ビリヤードボールによる万能ゲートの作成」である。その独創的なアイディアは量子（原子、分子）の衝突を連想させ、ファインマンの量子コンピュータ観に影響を与えたと言われる。この書籍で学んだことを纏めてみたい。（→改訂英語版はこちらをご覧ください。）
●Fredkinのゲートとは
これは、Edward Fredkinが1982年に発表した３入力（x, y, z）３出力の論理ゲートで、論理関数で表せば以下のように簡単なものである：
F(0, y, z )=(0, y, z), F(1, y, z) = (1, z, y)
最初のxは制御ビットなので、出力の１番目にそのまま出る。x = 0 の場合は、yとzとはそのまま出力され、x = 1 の場合は、yとzが交換されて出力される。簡単な計算で示すことができるのだが、以下の特徴を持つ：
- 可逆論理ゲートになっている。すなわち、出力から入力へ到達できる。
- 万能論理ゲートである。すなわち、NOTとANDとfan-out（入力の複製機能）をこのFredkinゲートのみで作成できる。
- 入力と出力の1（True）の個数は常に等しい。これは後述するが、ビリヤードボールの個数が入力側と出力側で常に等しいことに対応する。
Fredkinは、ビリヤードボールを使ってこのゲートを作成する方法を示した。ボール同士の衝突と、ボールと台の淵に置かれた鏡（入射角と反射角が等しい場合を想定した反射板）による反射を使う。ただし、完全な弾性衝突（エネルギーロスなし）や、複数のボールのサイズ、質量、速度、投入タイミングの完全な一致を想定するので、現実的に製造することは明らかに困難であり、概念的、論理的な論理モデルである。しかしながら、この方法は、驚くべき独創性に富んでおり、著名な物理学者ファインマンも感銘を受けた言われる。ボールの衝突が原子の衝突を連想させ、ファインマンの量子コンピュータへの考えにも影響を与えたとされる。
●ビリヤードボールでスイッチゲートを作る
まず、Fredkinゲートを構成するためのスイッチゲートを上記のビリヤードボールで作る。図１に示すように、２入力３出力である。ボールはIn1とIn2から投入される。それらのボールは弾性衝突と右上隅と左下隅に設置された鏡での反射を経て、Out1, Out2a, Out2bへ出力される。入力が２つとも与えられない場合は何も出力がない。In1にだけボールが入ると明らかにOut1にだけボールが出てくる。また、In2にのみボールが入るとOut2aにだけ出力がある。入力出力共に、ボール出現有りを１に、無しを０とすると、論理値表は右側のようになる。
ここで注目すべきは、このゲートは可逆ゲートであることだ。実際、図の下段に示すように、入出力のラベル（論理式）はそのままで矢印だけを逆向き（３入力２出力）にすることで、その事実がわかる。
さて、少し複雑なのが、In1とIn2に共にボールが投入された場合である。その動きを図２に示した。ここでは、見やすくするため、青と赤のボールを使っているが、本来はその区別は必要がない。入力側、出力側共に、とにかくボールが出現していれば１であり、出現しなければ０だということだけで十分なのである。
なお、動作の簡単なアニメーション（衝突と反射を反映したスマホアプリ）を自作したので、以下にそのgif画像を示す。
●Fredkinゲートをビリヤードボールのスイッチゲートで作る
上記のスイッチゲート４個を用いて、最初に示したFredkinゲート（図３）を作ることができる。４個のうち２個は、上で述べた可逆性を使って逆向きにしたものが接続されている。結論から言うと、仮にスイッチゲート自体は作成できたとしても、それを組み合わせて、Fredkinゲートを構成するには超絶技巧が必要だ。すなわち、スイッチゲート間を流れるボールを反射させる鏡を適切に設置する必要がある上、衝突すべき時に衝突し、そうでない時には衝突しないように、経路上に適切に遅延を与える必要があるからである。もしも、それが実現できれば、Fredkinゲートは、図３に示すような、３入力３出力の論理ゲートとして使うことができる。
上記のスイッチゲート４個を用いて、最初に示したFredkinゲート（図３）を作ることができる。４個のうち２個は、上で述べた可逆性を使って逆向きにしたものが接続されている。結論から言うと、仮にスイッチゲート自体は作成できたとしても、それを組み合わせて、Fredkinゲートを構成するには超絶技巧が必要だ。すなわち、スイッチゲート間を流れるボールを反射させる鏡を適切に設置する必要がある上、衝突すべき時に衝突し、そうでない時には衝突しないように、経路上に適切に遅延を与える必要があるからである。もしも、それが実現できれば、Fredkinゲートは、図３に示すような、３入力３出力の論理ゲートとして使うことができる。
本書第６章は、量子コンピューティングの基本原理（量子のsuperpositionやentanglement,
Bell's theoremなど）が終わり、次に量子ゲート、量子回路に入る直前の章である。著者は、
「このFredkinゲートはこの後の量子回路に直接必要なものではないが、類稀なる独創性に感銘を受けて本章に含めた」と述べている。小生にもそれが分かった気がするのである。
References
[1] Chris Bernhardt, “Quantum Computing for Everyone”, MIT Press, 2020
2022年11月10日木曜日
My understanding of the Quantum Key Distribution Protocol Ekert (E91)
Japanese abstract
前報は、単一量子ビットを利用する量子鍵配送プロトコルBB84の説明であったが、今回は、「もつれた状態」の２つの量子ビット対のストリームを利用した安全な鍵配送プロトコルEkertを説明する。これは、すでに本ブログで紹介した「Bellのテスト（Bellの不等式）」に基づいている。このような量子ビットを受け取った２者が、それぞれランダムに選択した正規直交基底を使ってそれを測定する。その結果の両者の古典ビット列の一致度が盗聴の有無を明らかにする。この記事は、Prof. Chris Bernhardtの著書[1]に基づいているが、小生が理解した内容を独自の観点からまとめたものである。
English Abstract
In my previous article, I described the quantum key distribution protocol BB84, which uses a single qubit. Here I describe the Ekert, a secure key distribution protocol that uses a stream of two qubit pairs in an entangled state. This is based on Bell's test (Bell's inequality) which was already introduced in this blog. Two parties that receive such qubits each measure them using randomly chosen orthonormal bases. The degree of matching between the two resulting classical bit strings reveals the presence or absence of eavesdropping. This article is based on Prof. Chris Bernhardt's book [1] and explains the Ekert from my own point of view.
●Measure qubits in different orthonormal bases
First, let's see what happens when we measure the received qubits in a different orthonormal basis than the one from the sender. In the following, for simplicity, the orthonormal bases will simply be referred to as bases. Here, one is randomly selected from the three types of bases shown in Fig 1. Bases D000, D120, and D240 correspond to setting the orientation of measurement apparatus to due north, southeast, and southwest, respectively.
Next, Fig. 2 summarizes how each ket vector (vertical vector) of the basis used for measurement on the transmitting side is expressed in a different basis. In general, the state of a qubit will be a linear combination of the ket vectors of the chosen basis. The probability that a measurement result falls to a ket vector is the square of the coefficient of that ket vector.
As already shown in Bell's test, Fig. 2 reveals an important point. If the measurement result in the original basis is 0 (falling to the first ket vector), it will be 0 with a probability of 1/4 when measured in another different basis. Also, if the measurement in the original basis is 1 (falling to the second ket vector), it will be 1 again with a probability of 1/4 when measured in a different basis.
That is, there is a 1/4 probability that a measurement on the original basis agrees with another measurement on a different basis. This is a theoretical value, but if you send enough qubits and measure them, it should approach this probability infinitely.
●How the quantum key distribution protocol Ekert works
With the above preparation, we can describe the Ekert protocol. Suppose we send a stream of two qubit pairs to Alice and Bob. Importantly, paired qubits are always in the entangled state
(1/√2) |↑〉|↑〉+(1/√2) |↓〉|↓〉.
Both will each receive one of the pair. My description will be made below with reference to Fig.3.
Note that the entangled states
(1/√2) |↑〉|↑〉+(1/√2) |↓〉|↓〉
and
(1/√2) |↘︎〉|↘︎〉+(1/√2) |↖︎〉|↖︎〉
are exactly the same. This fact is proven in reference [1], but is omitted here.
Suppose that Alice performs measurements on the selected basis D120 (see Figure 1) before Bob does. For example, if the result is 0 (ie, |↘︎〉|↘︎〉), Bob's qubit will also be |↘︎〉 because of the entangled state. Bob measures it on a randomly chosen basis. If the basis is different from Alice's, he gets 0 with probability 1/4, from the fact already revealed in Fig2. Similarly, if Alice's measurement result is 1, Bob's measurement result will be 1 with probability 1/4.
Now, after all qubits have been processed, Alice and Bob exchange their lists of bases (not measurement results) of their choice. In that case, secure communication is not particularly required. Since there are three types of bases that can be selected by both, the two bases match in 1/3 of the total cases. Qubits always give the same result when measured on the same basis. Therefore, If no eavesdropping has occurred, the measurements with their agreed bases can be the common key.
●Why can eavesdropping be detected?
Now consider the case where Eve eavesdrops on an entangled qubit. As I mentioned in the previous BB84 protocol explanation, Eve always needs to set a certain base and use it to make measurements. If measured in such a way, the entanglement will disappear immediately. As a result, the probability that Alice's and Bob's classical bits match will change. For example, if Eve eavesdrops before Alice's measurements, we find that the entanglement disappears and the probability that Alice and Bob's classical bits match increases to 3/8. In other words, when the bases of Alice and Bob are different, if the probability that the classical bits of both match is 1/4, it can be said that there was no eavesdropping.
Acknowledgments
Thanks to Prof. Chris Bernhardt, author of reference [1], for kindly answering some of my questions about entanglement and Bell's inequality.
I used the illustration (icon) of the Qni quantum circuit simulator[2] to show the qubit vectors..
References
[1] Chris Bernhardt, “Quantum Computing for Everyone”, MIT Press, 2020
[2] Qni; https://github.com/qniapp/qni
2022年11月6日日曜日
Amazon AlexaとMIT App Inventorのコラボ
【要旨】自然言語による応答システムとして、SiriやGoogleアシスタントなどを多くの人が利用しています。しかし、それらを組み込んで自分に必要な応答システムを自作するのは敷居が高いと言えるでしょう。今回、Amazonが10年間に渡って培ったAIによる自然言語処理AlexaとMIT App Inventorがコラボして、素晴らしいシステムをユーザに提供し始めました。まだ、全くの入り口に過ぎませんが、試用してみました。
■Amazon AlexaとMIT App Inventorのコラボ
下図のようなアナウンスがあり、いくつかのYoutube動画などでも紹介されています。これは初心者向けのチュートリアルですが、ビデオや資料を見ていると色々な魅力、可能性が感じられます。MITでは、自然言語でアプリの仕様を喋ることによって、現在のようなアプリ（処理ブロック）を自動生成するプロジェクトAptlyを進めています。今回のコラボは、Amazonの強力な自然言語処理を利用することで、Aptlyを推し進めることに繋がるのだと思います。（Aptlyについてはこちらで簡単に紹介しました。）
■自然言語による自分なりの応答システムを作る道が拓けそう
上記の情報をもとにして、簡単な自然言語による応答をテストしてみました。スマホ（AndroidまたはiPhone）とAlexaをCloud DBで連携させるものです。Alexaのデバイスを持っていれば良いのですが、それがなくても、PC上のエミュレータを使うことができます。また、Amazonの通常のアカウントの元で、「Developer ID」を取得しておく必要があります。上記URLの説明には、"no Amazon device or account required."と書いてあるのですが、"no account"は、教室の場合は先生だけがaccountを持っていれば良い、ということのようです。
この簡単な例では、スマホからメッセージをCloudDBへ格納し、それをAlexa側から"get my message"や"what is my message"のように発話をすることで取り出しています。また、逆に"send the message"や"post the message"などと発話してCloudDBへ送り、スマホ側でそれを取り出します。ユーザは、"get ..."や"what is ..."などをIntentに登録できますが、必ずしもそのように発話しなくても、それらに近い言葉を使っても、AI自然言語処理が適宜判断できます。
これは簡単な例に過ぎませんが、それでも、自分なりの特色ある応答システムを作れそうな気になりませんか？しかもそれを、これまで通り、MIT App Inventorの環境のままで実現できそうなところが素晴らしいです。今までは作れそうもないと思っていた人にとっても、新しい世界が拓けるように思います。
（追記）
AmazonのAlexaは本来、日本語もできるのですが、
2022年11月4日金曜日
量子鍵配送プロトコルBB84をスマホアプリで確認
abstract: 理論上（計算上）は明確になっている事項でも、実際に一歩づつトレースして理解することは意味があると考えました。AliceからBobへ、長い古典ビット列を送信することを想定します。問題は、それをEveに盗聴される可能性です。しかし、量子コンピューティングの世界では、Eveが盗聴すれば必ず露呈するという、量子鍵配送プロトコルBB84があります。そのエッセンスを、自作したスマホアプリを使って説明を試みました。
それにより、Bobの測定結果は本来のものと異なるであろう。Bobの測定結果として得られる古典ビット列は、Aliceが元々設定した古典ビット列と比較される。盗聴されていない場合は、上に述べた手順から、AliceとBobがそれぞれ選択した基底（H, V）は0.5の確率で一致するので、古典ビット列の少なくとも1/2が一致する。さらに、すでに述べた通り、異なる基底で測定したケースでは（量子ビットの重ね合わせにより）、確率0.5で両者の古典ビットが合致する。結局、(1/2)+(1/2)*(1/2) = 3/4 = 0.75の確率で両者の古典ビットは合致する。
【改訂】2023-05-28、後半に「実際にBB84を構成するには」を追加し補足した。
Check the quantum key distribution protocol BB84 with a smartphone app
Even if the conclusion is known in theory, it is useful to deepen understanding by actually proceeding step by step. Now imagine sending a long string of classical bits from Alice to Bob. The problem is that it can be eavesdropped on by Eve. However, in the world of quantum computing, there is a quantum key distribution protocol (BB84) that if Eve eavesdrops, it will always be revealed. This time, I will explain the essence using a self-made smartphone app.
●量子鍵配送プロトコルBB84の概要
このプロトコルは1984年に発表されたもので、量子ビットの重ね合わせ（Quantum Superposition）を利用している。ここでは、単一量子ビットをひとつづゝ連続して送信するので、量子もつれ（Quantum Entanglement）は無い。（量子もつれ状態の量子ビット対の送信用には、Ekertプロトコルがあるが、それは別記事とする。）
図１は、BB84の原理を確認するためのアプリである。量子シミュレータではない。Aliceは、例えば古典ビット2048個（これを暗号鍵にするつもり）の４倍の8192個を用意するが、これをそのままBobへ送信はしない。代わりに、２種類の２次元正規直交基底（以後、単に基底と呼ぶ）HかVを各ビット毎にランダムに選択して、ビット値に対応する、基底のケットベクトル（縦ベクトル）を送信する。古典ビット0と1は、それぞれ、基底の１番目と２番目のケットベクトルに対応させている。つまり、量子ビット（の状態ベクトル）を送信するのである。具体例は後で示す。
Bobは、受信した量子ビット毎に、ランダムに（Aliceとは無関係に）同様にHかVを選択して、それによって量子ビットを「測定」する。その結果として、全部の受信が完了後には、Aliceと同じ長さの古典ビット列（8192個で構成）を得る。AliceとBobの持つこの古典ビット列の合致度によって、盗聴の有無を判定できるのである。
Eveが盗聴する場合、受信量子ビットをそのままBobへ転送して自分はそのコピーを盗聴する、ということは量子原理から不可能である。盗聴するには、受信した量子ビットを必ず「測定」し、その結果としての量子ビットをBobへ転送するしかない。測定前の量子ビットは、（日常思考からは不思議なことだが）量子基本原理として、0に対応するか１に対応するかは決まらない。また、測定するには、どの基底を用いるかを決める必要がある。基底の選択によって0か1かに決まる確率は変化するが、Eveにとっては、ランダムに基底を選択する以外に方策がない。
●正規直交基底と量子ビットの重ね合わせと測定
上で述べた基底とその測定について、具体例で説明する。ここで選択できる基底VとHは以下のようなものである。
一般に量子ビットは、基底(|u>, |v>)を用いる場合、以下のような状態にある。これは量子重ね合わせ状態（Quantum Superposition）と呼ばれる。そして測定を行うと|u>か|v>のどちらかに確定する。つまり、0か１かになる。その確率は、それぞれの係数の２乗で決まる。
ある量子ビットに対して同一基底を適用するのならば、何度測定しても必ず同一の結果になる。しかし、異なる基底で計測した場合は、0と１のどちらに倒れるかの確率は、基底のケットベクトルの係数（振幅確率）の平方となる。振幅確率の求め方は、参考文献[1]にあるので、それを使って、基底H, Vの場合を計算すると以下のようになる。
このことから、HとVを使う限り、元の計測と今回の計測で異なる基底が使われる場合は、ちょうど確率0.5（= (±1/√2）の平方）で元の計測結果と同一となることが分かる。そこがポイントである。
●盗聴があったとすれば何が変化するのか
以上の準備をした上で、盗聴の有無で何が異なるのかを図２で見てみよう。すでに述べた通り、Eveが盗聴するとすれば、Eveは盗聴した量子ビット毎に、ランダムに基底HかVをに選択し、測定しなければならない。その結果として②に示された量子ビット列をBobへ送る。すなわち、Bobは本来の①の量子ビットとは異なる②を受信することになる。
一方、盗聴があった場合は、Eveによる基底選択が加わるので、AliceとBobの基底の一致確率は(1/2)*(1/2)に低下する。そして、基底が一致しない場合のAliceとBobの古典ビットの一致確率は3/8となる。結局、確率(1/4)+(3/8)=5/8 = 0.625でAliceとBobの古典ビットが一致する。従って、最終的にAliceとBobの古典ビットの一致確率が0.75であれば盗聴は無く、0.625であれば盗聴されたと結論付けられる。
●実際にBB84を構成するには
これで理論は説明された。上の説明から、AliceとBobの選択した基底が一致する回数は2nとなる。その合致した基底でBobが測定した結果のビット列は、Aliceが持っているビット列と一致する。従って、盗聴がないと仮定すれば、Aliceはその2n長のビット列をBobに送らずに、両者がキーとしてそのビット列を共有できる。
だが、実際には、Aliceは基底の量子状態ベクトルをBobに送信しているのでその盗聴の有無を確認しなければならない。そこで、両者はこの2n長のビット列の半分のn長のビット列を「暗号化しない通常通信」で送り合って、その一致度を確認する。もしも完全に一致すれば盗聴はないと言える。一方、その1/4が一致しなければ盗聴があったと言える。（そこでは、盗聴するにはその量子ビット（量子状態ベクトル）を測定する必要があり、そうすれば、Bobに送られるべき量子の状態は変化することを巧みに利用している。）
盗聴がないと分かった場合には、合致した2n長のビット列の残りの半分であるn長のビット列をキーとして安全に使える。（実際には2n長が合致しているのだが、上記通常通信により、そのうちの半分は他人に知られている可能性があるためである。）
だが、実際には、Aliceは基底の量子状態ベクトルをBobに送信しているのでその盗聴の有無を確認しなければならない。そこで、両者はこの2n長のビット列の半分のn長のビット列を「暗号化しない通常通信」で送り合って、その一致度を確認する。もしも完全に一致すれば盗聴はないと言える。一方、その1/4が一致しなければ盗聴があったと言える。（そこでは、盗聴するにはその量子ビット（量子状態ベクトル）を測定する必要があり、そうすれば、Bobに送られるべき量子の状態は変化することを巧みに利用している。）
盗聴がないと分かった場合には、合致した2n長のビット列の残りの半分であるn長のビット列をキーとして安全に使える。（実際には2n長が合致しているのだが、上記通常通信により、そのうちの半分は他人に知られている可能性があるためである。）
●AliceとBobの持つ情報の一致度をスマホで計算
ここでようやく前述のスマホアプリが登場する。今回は、両者の選択基底が異なる場合の振幅確率の平方はいずれの場合も0.5であった。このため、重ね合わせ状態にある量子ビットの測定結果は単にコイントス乱数で決めることができる。ただし、本当は、その乱数が「真の乱数」であることが求められる。スマホの数学ライブラリの乱数でも、非常に多く発生させれば問題は生じないだろう。図３には、Aliceが8192個の古典ビットを乱数で一つづゝ発生させた場合の結果を示している。
盗聴なしとありの場合の両方とも、AliceとBobの最終的な古典ビットの一致度は、上に述べた数値とほぼ同一（小数点以下３桁まで一致）となった。このことから、BB84の理論通りの結果が得られたと言える。
参考文献
[1] Chris Bernhardt: Quantum Computing for Everyone, The MIT Press, 2020.
2022年10月27日木曜日
「量子コンピューティングExpo2022秋」に参加
２日前まで量子物理の基本に関わるBellの定理に取り組んでいた。その発祥の地Belfast（北アイルランド）への旅行は当面無理だが、お馴染みの幕張メッセなら行ける。ということで、本日は一転して、そこで開催の実用指向「量子コンピューティングExpo」に参加した。でも、量子コンピューティングは実用レベルにあるのか？答えは大体分かっているだが、こんなに盛り上がっている状況を肌で感じ取りたい。
■量子コンピューティングExpo 2022秋（10/26-28、幕張メッセ）
まず、会場の雰囲気をご覧いただきたい。下図のように、他のいくつかのExpoとの同時開催なのでかなりの盛況。私は、今回は「量子コンピューティング」に絞って参加した。
量子関係の出展の数はあまり多くはないが、有力な機関が目につく。下図には、東北大学とBlueqat等のスペースが大きく見える。東北大学は実際にはシグマアイという量子ベンチャである。Blueqatも、湊雄一郎氏をトップとする国内で著名な量子ベンチャ。後述するが、「量子ICTフォーラム」という産学官の量子プロジェクトもあった。凸版印刷は、いくつかの量子応用を展示していた。カナダは、D-Waveやxanaduなどで量子の先進技術国と見做されているので、カナダ大使館も応援で出展したのだと思われる。
■量子アニーリングマシンと量子コンピュータ
色々と議論はあるのだが、量子アニーリングマシンは、量子コンピュータとは区別するのが一般的になってきた。量子コンピュータの方は、実用的にはまだまだだが、量子アニーリングの方はかなり実用が進んでいる面がある。例えば、前出のシグマアイ（東北大学)＋凸版印刷は、下図のような物流業務の改善を量子アニーリングで推進しているとの展示を行い、注目されたようだ。
■量子コンピュータ（ゲート型）のシミュレータ
量子物理に基づく量子コンピュータの物理的、数学的定式化ほぼ完成しているのだが、実用的な量子コンピュータ（NISQではなく、誤り耐性の実機）を作り上げるにはまだまだ課題が山積している。だが、継続的に研究開発が進められていることも強く感じられた。一方、そのような実用化には時間がかかるので、それまでに、使いやすい、高性能な量子回路シミュレータを利用する動きも見られる。
量子回路シミュレータとしては、IBMのQiskitなどがあるが、今回展示されていたIQM Quantum ComputersのQniも独自の特徴を持つ。その最大のメリットは、一切の登録手続き無しに、いきなりWebブラウザを使って、量子回路（量子ゲートの組み合わせ）をビジュアルに構成して、シミュレーション結果をすぐに得られることだ。以下の図は、配布されていた「量子コンピューティング チートシート」である。恐らく誰でも、少し勉強すれば、これを頼りに基本的な量子回路を作り実行させることができる！
また、これとは別の方向として、nvidiaが開発している量子回路シミュレータA100がある。cuQuantumやQsimというシミュレータをもち、自社の強力なGPU技術で大規模な量子ビット数を扱う量子回路のシミュレーションを大幅に高速化させるとしている。
■誤り耐性の量子コンピュータの実現はいつなのか
Googleなどから、これに関するロードマップは発表されていて、2029年にそれを実現させるとのことである。ただし、その確実性については懐疑的な見方もある。国内では、例えば日立製作所では、すでに独自のCMOS Annealingマシンを世に出しているのだが、今回は、誤り耐性量子ゲート型も開発中であり、その実現は2050年付近とする旨の展示を出していた。この展示は、「量子ICTフォーラム」のブース内で行われていた。
これらの開発見通しについては、次に述べる中村泰信氏へのインタビュー記事が大変参考になるであろう。
■理化学研究所の中村泰信氏へのインタビュー記事
中村泰信氏は、世界で初めて「超伝導量子ビット」を開発し、その制御を実現したことで知られる。現在、理化学研究所量子コンピュータ研究センター長である。中村氏へのインタビューが載った「量子ICTフォーラム通信」が配布された。８ページに渡る詳細な記事だが、その内容が実に素晴らしい。今回、小生がこの量子コンピューティングExpoに参加して得た最大の成果は、この冊子を入手したこと、とさえ言えるのである。誤解などがあるかも知れないが、小生が特に感銘を受けた部分を、独断で以下にまとめた。
Q1:Googleは量子コンピュータの実用化を2029年と発表したが、国産機の実用化は2050年とされている点についてお考えは？
A1（中村氏）：「2050年まで絶対にできない」のではない。だが、よその情報に安易に引きづられる形で前倒しするのではなく能動的に判断すべきだ。研究全体の動向を見ながら、ブレークスルーを起こすことを目標として、自分たちでできることを粛々とやっていく。
Q2:国産初の挑戦として、2022年度中に64量子ビット、次の段階で144量子ビットのものを出す計画だが、なぜ、自前で作っていく必要があるのですか？
A2（中村氏）：他に先んじられたら「やらない」では、逸するものが多い。日本にも非常に優れた研究者技術者が大勢いる。自分たちで取り組むからこそ、現段階では想定されていないスピンオフや新しいブレークスルーが生まれ得る。
Q3:日本は基礎研究は先行しても社会実装では他国に負けるイメージがあるのですが...
A3（中村氏）：「日本は駄目」「アメリカは良い」などと単純な結論に帰結したり、弱点ばかりに目を向けて悲観する必要はない。悲観的に考えてばかりだと何も解決しない。明るい側面を見ながら地道な努力を続けたい。目先に囚われずに、きちんと分野の基礎体力をつけることだ。
Q4:量子技術に関心を持つ企業の人々、研究したいと考えている学生へ向けたメッセージをお願いしたい。
A5（中村氏）：特に学生にとって、社会的インパクトが莫大かつ未知の事柄に溢れている量子技術領域は、研究対象として非常に魅力的に映ると思う。一歩をぜひ踏み出して欲しい。企業の方々は、「もうしばらくしてから考えよう」と思うかも知れない。しかし、早いうちから勉強した者勝ちと言える。わずか１年でも景色が大きく変わる可能性がある。ぜひ、目を離さないでいただきたい。
■感想
この出張の帰り際に、久しぶりに厚木有隣堂書店に立ち寄った。２階のIT関連書棚には、AI、機械学習、Web、プログラミング関係の書籍がびっしり数千冊は陳列されている。しかし、その中に、「量子コンピュータ」関係はわずか十数冊しかなかった。だからと言って、大学の情報技術関係者が、「まだいいだろう。もしばらく放っておこう」では寂しい。上記の中村氏の言葉通りである。大学であれば、行き先不透明であろうとも、未だ底知れぬ可能性を秘めた量子情報の分野へ踏み込む人が増えることを期待したい。
登録:
投稿 (Atom)