多彩な独創的アイディアや美しい数式にもたくさん出会った。改めてここに、テンソル積とドイチェ・ジョサのアルゴリズムに関する２つの数式を掲載して、今年のお別れとしよう。
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
登録:
投稿 (Atom)