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）

・Ultra-High Density Coding and Quantum Teleportation (Part 3)（2022-12-02）

・Ultra-High Density Coding and Quantum Teleportation (Part 2)（2022-12-01）

・Ultra-High Density Coding and Quantum Teleportation (Part 1)（2022-11-28）

・Fredkin's Universal Logic Gate with Billiard Balls（2022-11-16）

・My understanding of the Quantum Key Distribution Protocol Ekert (E91)（2022-11-10）

・Check the quantum key distribution protocol BB84 with a smartphone app（2022-11-04）

・A street in Northern Ireland named "Bell's Theorem"（2022-10-24）

・Ask the Author - Fundamental Theory of Quantum Computing（2022-10-21）

・Learn Nobel Prize in Physics 2022 Quantum Theory in High School Mathematics（2022-10-05）

Simonの記念碑的量子アルゴリズム

【要旨】Simonの量子アルゴリズム（by Daniel R. Simon, 1994）は、従来アルゴリズムではデータサイズに対して指数関数的に計算量が増大するある問題を、量子計算によって線形 (+α)オーダーの計算量で解けることを示した記念碑的なものである。その詳細は参考文献[1]にあるが、著者Prof. Chris Bernhardtはこれに、難度☆☆（ダブルスター）を付け、非常に難しいとしている。しかしながら、彼は、難しい仕組みも巧みに整理して可能な限り簡単化し、かつ、数式を使った厳密性を維持し、高校数学レベルで分かるように叙述している。そのため、じっくり読むことで具体的に理解することができた。本記事では、アルゴリズムの詳細は略すが、その結果として何が出力され、それが何を意味するかを、小生の理解に立って纏めた。さらに、量子回路シミュレータ[2]でその働きを確認した。

●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を評価する必要があるのか、それが問題である。古典的方法で、2ⁿ個の入力について関数値を問い合わせた場合、連続して半分の関数値が全て異なるかも知れない。この場合は、さらに別の入力１個の関数値を知る必要がある。すなわち、最悪ケースでは、2^n-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によらないので、線形の回数での達成となる。それに加えて、古典的方法により、出揃った一次独立な線形方程式をn²のオーダーで解く。（なお、一般の連立一次方程式の解法はn³のオーダーだが、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

量子テレポーテーションを利用した量子ビットのエラー訂正

【要旨】量子ビットは環境とのインタラクションによって壊れやすい性質があるので、量子コンピューティングおいてエラー訂正は非常に重要である。エラーの種類は様々だが、ここでは、量子ビットの誤反転の訂正（Quantum Bit-Flip Correction）を考える。その方法は、古典ビットにおいて広く利用されているパリティチェックに基づく。だが、それを量子ビットへ拡張するには、量子ビットの複製を作成できないことや、量子ビットの測定によりその状態は消滅するなどの問題がある。参考文献[1]には、量子テレポーテーションを利用してそれらを解決する素晴らしい発想が示されている。

●従来の古典ビットのエラー訂正（パリティチェック）

　まず、古典ビットのエラー訂正の簡単だが有効な方法を復習する。例えば、１ビット情報(0 or 1)を送信する場合、それらの複製を作って合計３ビットを送る。つまり、000か111が送られる。エラーの発生は稀であり、発生したとしても３ビットのうち高々１ビットだけと仮定する。これは現実的な想定である。そうすると、受信側で受け取った３ビットb₀b₁b₂が、例えば、101の場合は111に、001の場合は000に訂正されることになる。一般的には以下のようにすればよい。

    b₀⊕b₁とb₀⊕b₂が、

    00ならば、訂正なし。

    01ならば、b₂を反転させる。

    10ならば、b₁を反転させる。

    11ならば、b₀を反転させる。

●量子ビットのエラー訂正（パリティチェックの拡張）

　ここで扱うエラーは、量子ビットの誤反転である。すなわち、量子の本来の状態 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]を用いて設定した。

　次に、受信するBob側の量子回路である。詳細は図２をご覧いただきたいが、新たに２個のqubitsを下部に追加した。送信されてきた３個のqubitsの１番目と２番目のパリティと、１番目と３番目のパリティを計算するためである。これらの結果を見れば、前節「古典ビットのエラー訂正」の説明通りに、どのqubitにエラーがあるか、そしてどう訂正すれば良いかが分かるのである。ここで注目すべきは、これらの２個のパリティ用qubitはいずれも、本来の３個の量子ビットとは「もつれた状態にはない」ことである。つまり、これらのパリティ用qubitsを測定して結果を見ても、上部の３個の量子ビットのもつれ状態には何ら影響を与えない。

●量子シミュレータによる現象の確認

　以上のエラー訂正の動作を完全に実現することは難しいが、本質的な動きは量子回路シミュレータ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

超高密度符号化と量子テレポーテーション（その３）

【要旨】前報（その１）と（その２）に引き続き、本報では量子テレポーテーションについて纏めた。"量子テレポーテーション"という言葉は、宇宙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

超高密度符号化と量子テレポーテーション（その２）

【要旨】前回の（その１）での準備をもとに、本報では超高密度符号化（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

超高密度符号化と量子テレポーテーション（その１）

【要旨】超高密度符号化と量子テレポーションに関して、Prof. Chris Bernhardt著[1]第７章をどのように学んだかをメモしておきたい。安易にツールや可視化に頼らずに、紙と鉛筆だけを用いて考えながら取り組むことに徹してきた。そして、今や機は熟した。ツール等で知識を確認する段階に達した。こういう手順を踏む方が「分かった喜び」が大きいことを実感した。本報（その１）では、幾つかの基本量子回路の作用を量子シミュレータQni[2]を利用しながら確認した。

●単一量子ビットに対する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〉 となる。これ以外の状態にはならない。すなわち、両量子ビットに相関関係が生じていることが分かる。

　この状態にさらにReverse Bell回路を作用させたのが図４である。Bell回路は自分自身が可逆回路である。従って、入力される２量子が４つの状態のいずれであっても、最終的に最初の状態に戻っている。図４には、Bell回路を作用させた後（Entangledの状態）と、さらにReverse Bell回路を作用させた後の状態（Unentangledの状態）を示しているので、このことが確認できるであろう。（なお、回路の適用結果では、量子ビットの並び順が最初の量子状態での量子ビット並びと逆順になっている。）

References

[1] Chris Bernhardt, “Quantum Computing for Everyone”, MIT Press, 2020 

https://www.chrisbernhardt.info/

[2] Qni; https://github.com/qniapp/qni

量子アニーリングによる渋滞解消のための信号制御

【要旨】数日前に、日立製作所のCMOSアニーリングマシン利用に関するwebサイト[1]に、「渋滞解消のための信号制御最適化」という解説が公開されました。テスト用のPythonソースコードも提供されていますので、早速試してみました。

●渋滞解消のための信号制御最適化

　この課題は、古くから取り組まれています。車の自動運転技術も注目されていますが、今のところ、交通渋滞解消を目指すものではないでしょう。しかし、交通渋滞解消の技術は注目されるべきものです。それによる現代社会での経済的、社会的効果は計り知れません。

　従来は、車の台数や速度、車間距離、青信号の点灯時間と切り替えタイミング、交差点での進行方向等々を時間変化で捉えて微分方程式モデルを作り解くこともあるようです。しかし、今回の手法は、そういう要素を明示的に使わずに、「交差点をつなぐ道の上にいる車の量」を「青信号の点灯」と関連付けた画期的なモデルだと思われます。参考文献[2]の豊田中央研究所と東大による論文に基づいているとのことです。

●量子アニーリングによる信号制御最適化

　詳細は参考文献[1] [2]をご覧いただきたい。非常に丁寧な解説が[1]にあります。「各交差点で待機している垂直方向や水平方向の車の台数を信号制御によって均一化する」という観点から、イジングモデルを組み立てる考え方と具体的な手順が説明されています。もちろん、交差点に入る車の直進、右折、左折の割合や時間変化も考慮されています。そして最終的に、各交差点を量子のスピンに対応させて、スピン間の相互作用係数と外部磁場係数を使ったエネルギー関数（コスト関数）を導いています。

　私が気にしていたのは、いくつかの制約条件をどのようにコスト関数に組み入れるのか、でしたが、例えば、隣り合う信号が相反する場合にペナルティを与えることなどをうまく取り入れています。

●実際に動かして試してみよう

　原理的なことを一通り理解した上で、日立のCMOSアニーリングマシンを動かして、動きを確かめます。Pythonソースコードが公開されていますので、誰でもできます。ただし、日立から、無料のAnnealing Cloud Web用のAPIキーを取得する必要があります。

　動かしてみると、なかなか素晴らしい！解説も分かりやすいのでとても勉強になります。各信号は量子スピンに対応するので、アニーリングの結果として、エネルギー関数を最小化するスピンの向き（北極、南極）のセットが返ってきます。すなわち、その時点では、北極ならその信号器の水平方向を青色に、南極なら垂直方向を青色にするのが最適だ、ということです。

　ただ、最適化の結果を見やすくしたい。とうことで、信号の青点灯と交差点での渋滞の度合いを可視化するアニメーションアプリを作成しました。図１にそれを示します。

●感想

　色々なことが思い浮かぶのですが、この結果をみると、初期状態でかなり渋滞していても、この最適化で、青信号の点灯方向が変わり、急速に渋滞が解消に向かうことがわかります。その後は、信号の切り替えは穏やかになり、渋滞は徐々に減少します。もちろん、初期状態での車の量や、交差点での直進、右折、左折の割合などで状況は変わるでしよう。また、どこかのスピンが故障して、ある確率で方向が反転してしまう場合に、最適性はどのように失われるのでしょうか。（パリティチェックみたいな機構が付いているのかもしれませんが。）
　今回のこの解説は、今後、種々のアイディアを独自に試す場合の非常に重要な拠り所になりそうです。

参考文献

[1] CMOS Annealing Cloud Web News

https://annealing-cloud.com/ja/index.html

[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)]

https://arxiv.org/abs/2003.07527

深まる秋、落ち葉とどんぐりを拾う

　すっかり秋が深まった。読書の季節とも言われる。だが籠りがちになったら、散歩に出掛けて気分転換するのが良い。落ち葉が増えてきた小径をカサカサしばらく進むと、どんぐりを落とす木の下にきていた。種類は色々あるようだが、この近辺はコナラとマテバシイのようだ。落ちているどんぐりを布で軽く擦るとすぐに艶が出る。不思議な生命がまだ宿っているかのようだ。持ち帰って、落ち葉と共に台紙に貼り付けて眺める。今歩いてきた自然の情景を切り取り、机上に小さく再現したかのような感覚になる。

　この他に、もっと丸っこい、イガの付いたどんぐりも見つけていた。クヌギらしい。少し前に、量子ビットの模型（ブロッホ球）を作るために購入した透明アクリル球体が余分に残っているのを思い出した。それに残りのどんぐりを詰めて、机上に転がしてまた楽しむ。

　落ち葉やどんぐりの種類は、例えば以下のデジタル植物写真集で手軽に調べることができる。今回は、コナラ、マテバシイ、クヌギのどんぐりを確認することができた。

●植物の名前を探しやすい デジタル植物写真集

http://plantidentifier.ec-net.jp/

ビリヤードボールを使った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は、ビリヤードボールを使ってこのゲートを作成する方法を示した。ボール同士の衝突と、ボールと台の淵に置かれた鏡（入射角と反射角が等しい場合を想定した反射板）による反射を使う。ただし、完全な弾性衝突（エネルギーロスなし）や、複数のボールのサイズ、質量、速度、投入タイミングの完全な一致を想定するので、現実的に製造することは明らかに困難であり、概念的、論理的な論理モデルである。しかしながら、この方法は、驚くべき独創性に富んでおり、著名な物理学者ファインマンも感銘を受けた言われる。ボールの衝突が原子の衝突を連想させ、ファインマンの量子コンピュータへの考えにも影響を与えたとされる。

●ビリヤードボールでスイッチゲートを作る
　まず、Fredkinゲートを構成するためのスイッチゲートを上記のビリヤードボールで作る。図１に示すように、２入力３出力である。ボールはIn1とIn2から投入される。それらのボールは弾性衝突と右上隅と左下隅に設置された鏡での反射を経て、Out1, Out2a, Out2bへ出力される。入力が２つとも与えられない場合は何も出力がない。In1にだけボールが入ると明らかにOut1にだけボールが出てくる。また、In2にのみボールが入るとOut2aにだけ出力がある。入力出力共に、ボール出現有りを１に、無しを０とすると、論理値表は右側のようになる。

　ここで注目すべきは、このゲートは可逆ゲートであることだ。実際、図の下段に示すように、入出力のラベル（論理式）はそのままで矢印だけを逆向き（３入力２出力）にすることで、その事実がわかる。

　さて、少し複雑なのが、In1とIn2に共にボールが投入された場合である。その動きを図２に示した。ここでは、見やすくするため、青と赤のボールを使っているが、本来はその区別は必要がない。入力側、出力側共に、とにかくボールが出現していれば１であり、出現しなければ０だということだけで十分なのである。

　なお、動作の簡単なアニメーション（衝突と反射を反映したスマホアプリ）を自作したので、以下にそのgif画像を示す。

●Fredkinゲートをビリヤードボールのスイッチゲートで作る
　上記のスイッチゲート４個を用いて、最初に示したFredkinゲート（図３）を作ることができる。４個のうち２個は、上で述べた可逆性を使って逆向きにしたものが接続されている。結論から言うと、仮にスイッチゲート自体は作成できたとしても、それを組み合わせて、Fredkinゲートを構成するには超絶技巧が必要だ。すなわち、スイッチゲート間を流れるボールを反射させる鏡を適切に設置する必要がある上、衝突すべき時に衝突し、そうでない時には衝突しないように、経路上に適切に遅延を与える必要があるからである。もしも、それが実現できれば、Fredkinゲートは、図３に示すような、３入力３出力の論理ゲートとして使うことができる。

●感想

　本書第６章は、量子コンピューティングの基本原理（量子のsuperpositionやentanglement,

Bell's theoremなど）が終わり、次に量子ゲート、量子回路に入る直前の章である。著者は、

「このFredkinゲートはこの後の量子回路に直接必要なものではないが、類稀なる独創性に感銘を受けて本章に含めた」と述べている。小生にもそれが分かった気がするのである。

References

[1] Chris Bernhardt, “Quantum Computing for Everyone”, MIT Press, 2020 

https://www.chrisbernhardt.info/

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 

https://www.chrisbernhardt.info/

[2] Qni; https://github.com/qniapp/qni