過去・現在・未来

【「チャイティンのΩとバエズのエントロピー」を公開しました】 https://youtu.be/ZjMfjlBxO5o?list=PLQIrJ0f9gMcPPgVvBB4BWA7-RuBmWLqqz スライドのpdfはこちらです。 https://drive.google.com/file/d/1E545s0CYATo5NlFHlgMr-87SRfpIjwng/view?usp=sharing 今回から、バエズのエントロピーの話を始めようと思います。といっても、今回は、バエズのエントロピーの式が、先日話したチャイティンが定義した不思議な数Ωの定義によく似ているという話で終わります。 以前、「チャイティンとゲーデル」という小咄をことが書いたあります。冗談が好きな人は、こちらを参照ください。 https://maruyama097.blogspot.com/2017/01/blog-post_25.html 今回は、シャノンのエントロピーとコルモゴロフの複雑性について、いくつか基本的なことを確認したいと思います。 シャノンの理論は、 複数のオブジェクトの集まりをどのようにエンコードし、そうしたオブジェクトのシークエンスを如何に効率的に送るかについて考えます。それに対して、コルモゴロフの複雑性は、一つのオブジェクトを、最も効率的にエンコードすることを考えます。 ただ、「情報圧縮」という点では、二つの理論は共通の関心があります。 シャノンの理論では、例えば、アルファベットの集まりXがある確率分布に従う時、そのエントロピーH(X)を用いて、N文字のメッセージを。NH(X)ビットに情報圧縮できることを示せます。 コルモゴロフの複雑性理論では、次のような形で情報圧縮に関心を持ちます。 「Berryのパラドックス」というのがあります。 　「30文字以下では定義されない最小の自然数B」 これはある意味、Bの定義ですが、Bは日本語では21文字で定義されています。 こうした「定義」「名前づけ」「記述」の曖昧さを避けるために、あるオブジェクトの「記述」はそれを出力するプログラムで与えられると考えます。コルモゴロフの複雑性𝐶_𝑈 (𝑥)は、万能チューリングマシンUにプログラムpが与えられた時、xを出力するプログラムpのうち、最小のプログラムの長さ（|p|）です。その時、pは、オブジェク

【 5/29マルレク基礎「情報とエントロピー入門」講演ビデオ全編公開しました】 MaruLaboでは、3ヶ月経過した丸山のセミナーを無料で公開しています。 今年の5月29日に開催したマルレク基礎「情報とエントロピー入門」講演ビデオを全編公開しました。エントロピーの勉強を始めようと考えている人、是非、ご利用ください。 YouTubeの新しい「チャプター」機能で、ビデオの途中からの視聴が可能になっています。お試しください。（PC/Mac をご利用の方は、ビデオの説明のなかの「もっとみる」をクリックください。） 講演資料は、こちらからダウンロードできます。合わせてご利用ください。 https://drive.google.com/file/d/1hoJMalvdnzg_m75a5KYvpGt0dTo96-6Z/view?usp=sharing 　------------------------------------------ 　　「情報とエントロピー入門」 　------------------------------------------ 　● Part 1 「エントロピーの理論を振り返る」 https://youtu.be/n1m0xFX6Dmc?list=PLQIrJ0f9gMcNUBuVzPZ2BXUB_vZp4e4Xq 　● Part 2 「統計力学とボルツマン・エントロピー」 https://youtu.be/3rJA7L2xHJA?list=PLQIrJ0f9gMcNUBuVzPZ2BXUB_vZp4e4Xq 　● Part 3 「情報理論とシャノン・エントロピー」 https://youtu.be/xLf69raZ5G4?list=PLQIrJ0f9gMcNUBuVzPZ2BXUB_vZp4e4Xq 　● Part 4 「シャノン・エントロピーの通信技術への応用」 https://youtu.be/Wj2nskUOfpk?list=PLQIrJ0f9gMcNUBuVzPZ2BXUB_vZp4e4Xq 講演ビデオ、講演資料は、次のまとめページからもアクセスできます。 https://www.marulabo.net/docs/info-entropy/

【「エントロピーは計算科学とも接点を持つ」を公開しました】 9/4マルレク第三部「複雑性とエントロピー」のショートムービー「エントロピーは計算科学とも接点を持つ」を公開しました。お楽しみください。 https://youtu.be/DIMaG5muL4Y?list=PLQIrJ0f9gMcOLx0Fm-G0wbNnIRr-GfP2z スライドのpdfは、次からダウンロードできます。 https://drive.google.com/file/d/1vddaC9-_8Tk_Mb6riA1KarZzwemMlQ0Y/view?usp=sharing 第三部では、John Baez, Mike Stayの論文 “Algorithmic Thermodynamics”の概要を紹介しようと思っています。 https://arxiv.org/pdf/1010.2067.pdf エントロピー概念には、歴史的には、熱力学と情報理論の二つの起源があります。 エントロピーという概念は熱力学の中で発見され、ボルツマン、ギブスらの研究の中で、熱力学的・統計力学的概念として理論的に定式化されました。　 こうした研究の系譜とは全く独立に、シャノンは、自ら作り上げた情報理論の中で、エントロピー概念を再発見します。（シャノンに「エントロピー」という言葉を使うように勧めたのは、フォン・ノイマンだと言われています。） バエズらの論文は、エントロピー概念に、熱力学・情報理論以外に、第三の起源がありうることを示唆するものです。 そして、その第三の起源は、計算科学であるといいます。バエズらの「アルゴリズム論的熱力学」では、エントロピーは計算理論のプログラムの複雑性に対応づけられます。ここでの複雑性は、「コルモゴロフの複雑性」と言われるものです。 もともとは、熱力学的概念であったエントロピーが、プログラムとどのような関連を持つのでしょう？　ここでは途中を省略して、この理論が明らかにする、両者の対応の例を紹介しましょう。 　● 熱力学での容器中のガスのエネルギー Eは、「プログラムの実行時間の対数の期待値」に対応する。 　● 熱力学での容器の体積 Vは、「プログラムの長さの期待値」に対応する。 　● 熱力学での容器中のガスの分子の数 Nは、「プログラムの出力の期待値」に対応する。 なんか、にわかには信じられない

【「たとえ話で理解する「量子暗号」 3  -- コインからqubitへ」公開しました】 「たとえ話で理解する量子暗号」の第三弾として「コインからqubitへ」を公開しました。お楽しみください。 https://youtu.be/VVkWXtT50GA?list=PLQIrJ0f9gMcOLx0Fm-G0wbNnIRr-GfP2z スライドのpdfは、次からダウンロードできます。https://drive.google.com/file/d/1QFSQM56NdpuW_z9jQTze30gRq5w6qMY5/view?usp=sharing 4種類のコインとコイントスを使って、量子暗号 BB84をシミレートしているのですが、この方式には大きな脆弱性があります。 AliceとBobの通信の途中に、こっそり攻撃者Eveが入り込んだとします。Aliceが送ったコインを見れば、Aliceが送ろうとしたビットの情報が分かります。また、情報を盗んだコインをそのままBobに送れば、Bobは異変が起きていることに気づきません。 量子暗号のエンコード・デコードのシミレーションは、物理的コインで可能でしたし、量子暗号の共有キーの構成のシミレーションも、物理的コインでも可能でした。ただ、AliceからBobに、物理的コインを渡すというスタイルでは、中間者攻撃により、共有キーの秘密は破られます。この点で、物理的コインによる量子暗号のシミレーションは失敗します。 量子暗号では、こうした攻撃を跳ね返すことができます。今回は、4つのコインを４つのqubit |0>,  |1>,  |+>,  |−> に置き換えて、量子暗号が、この問題に、とてもスマートに対応しているのを見ていきます。さすが量子！ 回り道をして、やはり量子暗号は量子でなければという結論に落ち着いたわけなのですが、コインによるシミレーションは、量子暗号の特質を知る上で、役に立つのではと考えています。 9/4 マルレクでは、情報とエントロピーにまつわる、様々なエピソードを紹介しようと思っています。ぜひ、お申し込みください。https://info-entropy3.peatix.com/ まとめページは、 https://www.marulabo.net/docs/info-entropy3/ です。スライドの

【 「たとえ話で理解する「量子暗号」 2 -- 共有キーの構成」公開しました】 昨日の「たとえ話で理解する量子暗号」の第二弾として「共有キーの構成」を公開しました。お楽しみください。 https://youtu.be/lsjSDYVGuD4?list=PLQIrJ0f9gMcOLx0Fm-G0wbNnIRr-GfP2z スライドのpdfは、次からダウンロードできます。 https://drive.google.com/file/d/19u6mU7HIDUuPQSpDktPuZ871hWANuKEe/view?usp=sharing 4種類のコインとコイントスを使って、量子暗号 BB84をシミレートしているのですが、今回は、AliceとBobが共有するキーの構成法を紹介します。 Aliceがランダムな入力ビットのそれぞれに対して、どのようなエンコードを行ってビットをコインにエンコードし、BobがAliceから送られるコインを、どのようなデコードを用いてビットを出力するのかの、エンコード・デコード情報をAliceとBobが公開しても、その公開情報だけからは、共有キーの情報は得られないことを説明します。 ここまでは、順調に進みました。 ただ、こうしたやり方には問題もあります。それについては、次回に説明します。是非、何が問題かお考えください。（ヒント：共有キー構成のプロトコルは「盗聴」されても安全か？） 9/4 マルレクでは、情報とエントロピーにまつわる、様々なエピソードを紹介しようと思っています。ぜひ、お申し込みください。 https://info-entropy3.peatix.com/ まとめページは、 https://www.marulabo.net/docs/info-entropy3/ です。スライドのpdfにアクセスできます。

【 たとえ話で理解する「量子暗号」】 9/3 マルレク「量子情報とエントロピー」にむけて、ショートムービー「たとえ話で理解する量子暗号」を公開しました。お楽しみください。 https://youtu.be/joTWZCO5uEE?list=PLQIrJ0f9gMcOLx0Fm-G0wbNnIRr-GfP2z 今回は、予定にはなかった番外編です。昨日、思いつきました。ベネットの量子暗号 BB84 の初等的な説明です。ケットもアダマールも出てきません。出てくるのは、四種類のコインとコイン投げだけです。この説明、すこし、自分でも気に入っています。 この「たとえ話」でのコイン投げは、もちろん、量子論の観測に対応しているのですが、ここでの四つのコインが、どのような量子状態に対応しているのか考えてもらうのがいいと思います。 実は、BB84の説明としては、まだ途中です。ただ、ここまでくれば、ランダムなビット列に対して、Aliceがランダムにエンコード方法を選び、Bobもランダムにデコード方法を選ぶことを通じて、公開キーが構成できることを、やはり初等的に説明できます。 スライドは、こちらからアクセスできます。BB84自体、物理的というより論理的なパズルみたいなものですので、動画を観るより、週末、ゆっくりpdf眺めてもらえればと思います。 https://drive.google.com/file/d/1rvcj5FCjmwZkJ8MfNXZfCIjSeqvMP3pC/view?usp=sharing 明日のショートムービーから、第二部の「様々なエントロピーの形式」に入ります。ご期待ください。

 【 「量子通信の世界」を公開しました 】 9/3 マルレク「量子情報とエントロピー」にむけて、ショートムービー「量子通信の世界」を公開しました。お楽しみください。 https://youtu.be/gT1-6b0d1lc?list=PLQIrJ0f9gMcOLx0Fm-G0wbNnIRr-GfP2z まとめページは、 https://www.marulabo.net/docs/info-entropy3/ です。スライドのpdfにアクセスできます。 9/4 マルレクでは、情報とエントロピーにまつわる、様々なエピソードを紹介しようと思っています。ぜひ、お申し込みください。https://info-entropy3.peatix.com/ 今回の登場人物は、Charles H. Bennett とPeter Shorです。 Shorは、有名な「ショアのアルゴリズム」のショアですが、今回紹介するのは、それとは別の彼の仕事についてです。 トピックスは、「量子暗号」と「量子テレポーテーション」と「量子エラー訂正」の三つです。前の二つはベネットの、最後の一つはショアの仕事です。 「量子暗号」について。 「RSA公開キー暗号の安全さは、公開キーが簡単には素因数分解されないことに依存している。強力な計算パワーを持つマシンが登場すれば、公開キーが破られる可能性はある。ただ、量子の性質を利用すれば、どんな計算パワーでも破れない、公開キーの構成が可能だ。 しかも、悪意のある第三者が、公開キーの構成を「盗聴」して、それを再構成しようとしても、それは現実的には不可能であることが保証される。」 「量子テレポーテーション」について。 「量子Aと量子Bがエンタングルメント状態にある時、量子Aの状態変化は、瞬時に量子Bに反映される。たとえAとBとが、どんなに離れていても。このことを利用して、量子Xの状態を、遠く離れた場所に転送することが可能となる。このことは、量子状態のコピーを禁じた量子情報論の「No Cloning定理」にも、光速を超えた情報伝達を禁じた相対論の原理とも矛盾しない。」 「量子エラー訂正」について。 「ハミング・コードは、冗長なbitを付加して転送されたbit の誤りを検出し訂正する。これは古典bitに対するものだが、同様なことが、量子bit=qubit に対しても可能である。すな