過去・現在・未来

【 8/27 マルレク「暗号技術の現在」講演資料と講演ビデオ公開しました 】  MaruLaboでは、実施したセミナーの講演資料と講演ビデオを公開しています。 今回は、8月27日に行ったマルレク「暗号技術の現在」のセミナーの 講演資料と講演ビデオの公開です。ご利用ください。 講演資料： https://drive.google.com/file/d/172wp0DjNR1BehXyBejI4g_yXgxHT55fE/view?usp=sharing 講演ビデオ再生リスト： https://www.youtube.com/playlist?list=PLQIrJ0f9gMcNJxKzZgnbw09zYBVrwoCNz この「暗号技術の現在」の再生リストは、次の四つのビデオから構成されています。 　●  「暗号技術の現在」概説 https://youtu.be/LGkK28M1NPE?list=PLQIrJ0f9gMcNJxKzZgnbw09zYBVrwoCNz 　●  第1部 「現代暗号技術の成立」 https://youtu.be/Rpl4a7Whd7A?list=PLQIrJ0f9gMcNJxKzZgnbw09zYBVrwoCNz 　●  第2部 「ショアのアルゴリズムの発見」 https://youtu.be/itRvFSmIpgc?list=PLQIrJ0f9gMcNJxKzZgnbw09zYBVrwoCNz 　●  第3部 「ラティス暗号の時代の始まり」概説 https://youtu.be/K5-YWvcbfVw?list=PLQIrJ0f9gMcNJxKzZgnbw09zYBVrwoCNz このセミナー「暗号技術の現在」の参考資料・ショートムービーは、次のMaruLaboのサイト   https://www.marulabo.net/docs/cipher2/  からアクセスできます。 また、このセミナーは 内容的には、9月のマルゼミ「ラティス暗号入門」に続いています。こちらのページも参照ください。マルゼミ「ラティス暗号入門」： https://www.marulabo.net/docs/ciphe

 　「先生、肉牛と乳牛の違いわかりますか？」 昔、稚内に引っ越した頃、知り合いになった酪農家に聞かれたことがある。 　「食肉になる牛と、ミルクをだす牛の違いでしょ。（まんまだ）」 　「あ、乳牛はメスだけで、肉牛は、どっちもあり。（あたりまえだ）」 そんなことではなかった。 　「肉牛には名前がないけど、乳牛には名前があるんです。」 彼が言うには、肉牛は名前を持たず番号で管理されるが、乳牛は「メリー」とか「ベス」と名前をつけられて、酪農家に大事に育てられるのだという。 そうなんだ。知らなかった。 先日、近所のスーパーで「ホルスタイン」（これは乳牛）の肉が売っていた。珍しい。ローストビーフにして食べたが、新鮮で、ほとんどレアでもとても美味しかった。 宗谷では、人間より牛の数が多い。「宗谷黒牛」というブランドで肉牛も育てているが、それは宗谷岬一帯だけで、ほとんどは乳牛・ホルスタインだ。 大事に育てられていても、乳牛だって、僕ら人間と一緒で、いつか斃れる。ペットの葬式は普通にあるが、牛の葬式は見たことない。というかそんなこと、考えたこともなかったが。 美味しくいただいたお肉には、「個体識別番号」が明記されていた。乳牛にも番号あるじゃないか。 もしも、僕が誰かに食べられるなら、マイナンバーや戒名じゃなく、名前を使って欲しいな。

【 量子コンピュータであることを確認する方法 】 今回は、Mahadevの論文の紹介です。 2018年の論文全てではなく、彼女の仕事の一部である「Quantum Certification Protocol」の紹介です。これは、検証者が対話している相手のコンピュータが、本当に量子コンピュータであるのかをチェックするというプロトコルで、いわゆる「量子優越性」の実証に利用できるものです。 今回紹介するプロトコルとそのバリアントは、彼女のもっと大きな対話プロトコルの「1ラウンド」を形成することになります。「1ラウンド」というのは、今回見たプロトコルを一つのブロックとして、何度も何度も、何ラウンドも、対話を繰り返すのです。 今回見たプロトコルで、「標準基底で測定する」「Hadamard基底で測定する」という選択肢が含まれているのですが、それぞれの選択をSとHで表すと、SとHからなる長い並びで、大きな対話を特徴づけることができます。 彼女は、こうした対話を通じて、相手の量子デバイスを自分の忠実な「量子状態測定器」にかえます。こちらが本論なのですが、今回は、残念ながら触れることができませんでした。 また、いろいろ、説明が足りないところがあることに気づきました。 今日のセッションで、いきなりProver（証明者）とVerifier（検証者）という言葉が出てくるので、少し気になったのですが、Mahadevが対話型証明の手法を使ったということは触れていましたが、こうした数学的な「対話型証明」の設定と、彼女の「対話型証明」の設定には、違いがあります。 数学的な対話型証明の「証明者」は、能力に制限のない「全能者」でしたが、Mahadevの「証明者」は、そうではありません。能力に限界があります。Mahadevの「証明者」の能力は、量子複雑性の言葉で「BQP」と特徴づけられています。（ショアのアルゴリズムが属するクラスです）また、検証者の能力は「BPP」と定義されています。 それは、文脈上は明らかかもしれませんが、きちんと説明したほうがよかったと思っています。なぜなら、問題を明確に定義することが問題解決には不可欠ですから。 -------------------------------- 「 Quantum Certification Protocol 」 を公開しました...

【 LWE暗号の利用 】 Mahadevの論文を読む準備をしています。 Mahadevの量子計算の古典的検証では、古典コンピュータ上で実装可能で、しかし、量子コンピュータでも解読できない暗号、ポスト量子暗号のLWE暗号を利用します。今回のセッションでは、そのことを見ていきます。 基本的には、前回見た Trapdoor Claw-Free Functions (TCF) をLWEを使って定義します。こうして再定義された TCFを Noisy Trapdoor Claw-Free Functions (NTCF) といいます。それについては、セッションのスライドとビデオを参照ください。 ここでは、参考にした 2021年のMahadev達の論文の「はじめに」の部分が、よくまとまっていたので、それを紹介したいと思います。 「この論文では、純粋に古典的な検証者が、多項式時間に制限された一つの量子マシンと相互作用する新しいモデルを考察する。」 「量子デバイスの計算を多項式時間に制限することで、検証者は、ポスト量子暗号、すなわち、古典コンピュータ上で効率的に実装可能であるが、量子コンピュータでも解読できない暗号の基本技術を活用することができる。」 「このモデルでは、「信頼できない量子デバイスが “本当に ”量子的であることを効率的に検証する方法」と「信頼できない量子デバイスから検証可能な乱数文字列を生成する方法」という2つの基本的問題に対する解決策を提案する。」 「一つ目の課題は「量子優越性の証明問題」とも呼ばれ、既存のプロトコルでは、古典的スーパーコンピュータを用いて指数関数的な時間をかけて検証する必要がある。それに対し、本論文のqubit検証テストは、古典的検証者が多項式時間で検証可能な量子性の証明を提供する。」 「信頼できない量子デバイスを扱う難しさの中核には、デバイスの操作を通じて、量子デバイスの内部にあるqubitの構造を持たせることを強制することにある。すなわち、量子デバイスに実際にこの量子ビットを保持させ、また、検証者の要求に応えて、qubitの計測を実行することの難しさにある。」 この最後の部分をどう実現するかが、ポイントになります。 前回のセッションの最後の式、それは、今回のセッションの最後の式とも同じなのですが、claw (x0, x1) に対して、c...

【 clawとは何か 】 Mahadev の論文を読む上で必要な準備をしています。 今回は、Mahadevの暗号の利用で重要な役割を果たしている Trapdoor Claw-Free Functions の話をしようと思います。 Trapdoor というのは、現代の暗号の基本的な構成要素である「一方向関数」のことです。xからf(x)を求めるのは易しいのですが、逆に、f(x)からxを求めるのが難しい関数を、「一方向関数」といいます。 例えば、二つの素数p,qから、その積 N=pqを求めるのは簡単ですが、逆の、二つの素因数を持つ大きな数Nが与えられたとき、Nからその素因数p,qを求めるのは難しいです。そのギャップを利用しようと言うのが、RSA暗号の基本的なアイデアです。 「一方向関数」の上に見た説明に出てくる「易しい」とか「難しい」という言葉、感覚的にはわかると思うのですが、その定義を正確に述べるのは難しいことです。 「易しい」の定義は比較的簡単で、計算に要する時間が「多項式時間」であれば「易しい」と考えることができます。 ただ、「難しい」をその計算に要する時間が「多項式時間」ではなく「指数関数的時間」だとすればいいのでしょうか？ ある計算が、本当に「指数関数的時間」かかることを示すのは、難しいです。ある計算法では、「指数関数的時間」がかかるけど、素晴らしいアルゴリズムが発見されて、その計算が、「多項式時間」で終わる可能性があるからです。 （逆に、「多項式時間」で済む計算にも、「指数関数的時間」が必要な「おばかアルゴリズム」は存在します。おひまなら僕の「計算理論入門 -- 「やさしい計算」と「むずかしい計算」」をご覧ください。割り算を掛け算で計算できるのですが、とても手間がかかります。https://drive.google.com/file/d/1MNnGRkCJAsrR1GeKPyhVMk3VLYfnDhZH/view ） 「一方向関数」が存在すると言うことは、数学的にはキチンと証明されていません。 「易しい」とか「難しい」というけど、それは程度問題で、実際には、「一方向関数」といわれているものも、その逆関数も実は「多項式時間」で計算できる。ただ、そのやり方に気づいていないだけだ。と考えることもできるのですから。 実は、「一方向関数が存在する」という命題は、...

【 任意のf(x)を計算する量子回路を考える 】 Mahadev の論文を読む上で必要な準備をしています。 前回は、ポスト量子暗号のLWE (Learning with Errors)が、古典コンピュータで実装できるアルゴリズムだということを紹介しました。Mahadevの方法は、この古典的に実装可能なLWE暗号を量子コンピュータは破ることはできないということを前提にしています。 Mahadevは、古典コンピュータと量子コンピュータを「対話」させます。正確にいうと、古典コンピュータと人間が一緒にチームを作って、その混合チームを量子コンピュータと対話させます。この対話は「対戦」でもあります。対戦しているのは古典コンピュータと人間の混合チームと単独の量子コンピュータです。 なぜ、人間と古典コンピュータが、同じ仲間になるのかと言えば、量子コンピュータとの関係では、両者は共に同じような能力しか持っていないからなのですが、そこは、「いや、コンピュータ（古典）より、人間がエライ」「そんなことはない。AIをみろ。人間はコンピュータ（でも古典）にかなわない」という議論はあるでしょうが、それは等しく古典的なものの内輪揉めとして、先に進みます。納得いかない人も多いと思いますので、それについては、次回に説明します。 対話あるいは対戦は、古典チームが量子コンピュータにある計算の実行を指示することで始まります。量子コンピュータはそれを計算しその結果を古典チームに返します。古典チームは、その結果を見て新しい指示を量子コンピュータに出します。こうしたことを繰り返します。 量子コンピュータは、古典族と同様に計算を行う能力を持つのですが、その計算のスタイルは、ちょっと変わっています。今回のビデオのセッションは、そのことにフォーカスしています。 関数を計算する量子回路を考えます。量子回路は、量子ゲートから構成されているのですが、量子ゲートは、すべて「ユニタリ性」という性質を持ちます。その結果、量子回路自体も「ユニタリ性」を持つことになります。 量子回路のユニタリ性というのは、簡単に言えば、入力から出力を返す量子回路は、入力と出力を鏡に移したように回路ごと反転させれば、出力から入力を得ることができるという性質です。計算結果の出力から、時間を遡ったように入力を復元できると考えることもできます。これを...

【 Post量子暗号 】 「Post量子暗号」という名前は一般的に利用されているのですが、「量子の後の暗号」とか、「量子暗号の次のもの」と受け止められかねない、少しミスリーディングな名前のように、僕は感じています。かといって代わりの名前がすぐに思い浮かぶわけではないのですが。 この名前の中の「量子」という言葉でイメージしているのは、量子コンピュータが現在の暗号技術に対する脅威になりうるという認識なのではないかと思います。 「ショアのアルゴリズムの発見は、暗号技術にとって危機だったが、それを乗り越える暗号技術を我々は必要としている。」ということなら、気持ちはよくわかります。 ですから、「Post量子暗号」のコンセプトが含意していることは、まず、「量子コンピュータによる暗号破りの攻撃を跳ね返すことができること」です。これを「量子耐性をもつ暗号」といったりします。「Post量子暗号」を「量子耐性暗号」と言い換えてもいいのです。 ただ、現在の「Post量子暗号」のコンセプトには、もうひとつ大事な含意があります。残念ながら、そのことは、この名前にはあまり反映されていないように思えます。当たり前すぎるからでしょうか？それは、それが量子コンピュータの上ではなく、現在のコンピュータの技術の上に構築される技術だということです。 これも、ミスリーディングな言い方に聞こえるかもしれませんが、「現在のコンピュータ」を量子コンピュータとの対比で「古典コンピュータ」といいます。「古典コンピュータ」というのは、「そろばん」のことではありません。 「Post量子暗号」技術は、量子コンピュータによる暗号攻撃を跳ね返すことの出来る、古典コンピュータ上の技術です、これは、量子コンピュータとの対比で「古典コンピュータ」の能力を考えたとき、一般的には、ほとんどすべての点で、量子コンピュータが優っていることを考えれば、とても興味深い性質だと思います。決して、当たり前のことではありません。 Mahadevは、まさにこのことを、量子コンピュータのコントロールに利用しようとしたことは、前回述べました。 今回のビデオのセッションでは、「Post量子暗号」の中心的技術である、Learning with Error のアルゴリズムの実装を、ざっとみていきます。これなら、古典コンピュータで実装できることはわかると思います。...

【  Mahadevのアプローチ (2)  -- 暗号化 】 「量子計算の古典的検証」問題というのは、簡単に言えば、量子コンピュータを人間のコントロールのもとにおこうと思ってもなかなか思うようにはいかないという問題です。 それには理由があります。複雑な状態を理解する能力にしても、計算能力にしても、我々人間は、何一つ量子コンピュータにはかなわないのですから。 その上、彼らは秘密主義で、自分の手の内を人間には見せません。複雑な内部の状態をチェックしようとすると、別の姿に、簡単な見掛けに、姿を変えてしまいます。 　【 なぜ、暗号化技術が必要なのか？ 】 Mahadev の「量子計算の古典的検証」問題へのアプローチの特徴は、「対話型証明」の手法の利用とともに、「暗号化」の技術を積極的に利用することです。 なぜそこに「暗号化」技術が出てくるのでしょう？ それは、圧倒的な力の差がある量子コンピュータに対して、彼らを出し抜いて人間が少しでも優位に立つ手段として「暗号化」が利用できる可能性があるからです。 彼らが秘密主義なら、我々も、彼らに対して「秘密」を持つことができると、状況は少し変わります。 　【「ポスト量子暗号」技術の特徴 】 量子コンピュータは、既存の暗号技術への脅威として意識されてきました。ショアのアルゴリズムは、素因数分解や離散対数問題を解くことが難しいことに基礎を置く、RSA暗号や楕円曲線暗号を簡単に解きうるからです。 ただ、その中で追求されてきた「ポスト量子暗号」技術は、次のような特徴を持ちます。 　「普通のコンピュータで実現できて、量子コンピュータでも破られない暗号」 　【 「ポスト量子暗号」技術を優位性として利用する 】 量子コンピュータでも破れない暗号があり、かつ、その暗号の解き方を我々が知っているなら、それは、量子コンピュータに対する我々の数少ない優位性として利用できます。 例えば、ポスト量子暗号技術 LWE( Learning with Errors ) で暗号化したデータを、量子コンピュータに送り込みます。そしてそのデータの処理を量子コンピュータに実行させます。 量子コンピュータは、その暗号化されたデータが本当はどういうデータなのかはわからないまま、暗号化されたままのデータを処理した結果を人間に返します。 我々は、そのデー...

【 Mahadevのアプローチ (1)-- 対話型証明 】 前回、普通のコンピュータのデバッグや動作検証のようなやり方は、量子コンピュータの検証には使えそうもないという話をしました。 そのことは、現在の量子コンピュータが、普通のコンピュータと対比でいうと、ハードとソフトの分離もされていないし、OSとアプリケーションの区別もない状態にあることと、少し関係はあります。ただ、量子コンピュータには開発キットもデバッガーもないことを言いたかったわけではありません。 　【 原理が異なる二つのシステムの境界での相互作用 】 「量子計算の古典的検証」の問題は、原理が異なる二つシステムの境界での相互作用はいかにして可能なのか、あるいは、それにはどのような限界があるのかという、量子コンピュータと我々の関係にとって極めて本質的な問題です。 量子コンピュータの状態の遷移を正確には追えないだけではありません。我々は、現状では、量子計算の出発点となる、任意のqubitの状態を量子コンピュータ上にセットするというプリミティブな操作でも、その検証を含めれば、思い通りには量子コンピュータをコントロールできていないのです。 Mahadevの「量子計算の古典的検証」問題の肯定的解決は、こうした現状を変えて、量子コンピュータに対する人間のコントロール能力を大きく拡大する可能性を秘めているのです。 　【 Mahadevの二つのアプローチ】 Mahadevは、「古典的検証問題」に二つの方向からアプローチします。 第一のアプローチは、今回のセッションで紹介する「対話型証明 = Interactive Proof 」の手法を使います。「検証問題」の解決を可能にする、量子コンピュータと人間の「対話のプロトコル」を見つけようとします。 第二のアプローチは、量子コンピュータでも破れないと考えられている、「Post量子暗号」、先日セミナーを行ったLWE(Learning with Errors)を使います。量子コンピュータの中に、量子コンピュータも改変できない、我々は知っているが量子コンピュータには秘密の状態を作ります。これについては次回のセッションで。 　【 Interactive Proof 紹介 】 Interactive Proofの想定は、いささか奇妙なものです。Interactive Proof...

【 問題の難しさ 】 Mahadevは、量子コンピュータが行う計算についての最も基本的な問題である、「量子計算の古典的検証問題」を解きました。 我々人間が、量子コンピュータにある計算を実行させた時、量子コンピュータが我々の指示通りに計算を行ったのか、我々の予想もしなかった量子の奇妙な振る舞いで我々の意図とは違うデタラメな（我々にとって）計算をしたのかを、我々人間がチェックできるのかという問題は、ひとまず「大丈夫。人間がチェックできる」という形で解決されました。 ここでは、まず、この問題が難しい問題であることを確認してみたいと思います。 我々が、プログラムをデバッグしようとする時、 まず、プログラムの中の変数がどのような値を取っているかをチェックします。プログラム実行中のコンピュータの「状態」は、各変数へどのような値が割り当てられているかで決まります。 次に、プログラムのステップが進んだ時の、変数の値の変化をチェックします。変数の値の変化は、コンピュータの状態の変化をもたらすのですが、コンピュータの「ふるまい」というのは、この状態の変化の継起する系列に他なりません。 コンピュータの振る舞いが、正しいものかは、最終的には変数への値の割り当てに帰着する状態の変化を追いかければチェックできます。 n個のqubitからなる量子コンピュータの状態は、2^n 個の基底からなるベクトルで表現されます。それは、普通のコンピュータで言えば、 2^n個の変数があることに相当します。 我々は、この2^n個の変数の変化をトレースできるでしょうか？ 普通のコンピュータ・プログラムで変数の数nが 50を超えるのは珍しくないかもしれません。ただ、かつての Google IBMの論争は、2^53個の変数をどうやってトレースするかの論争と見ることができます。nが大きくなるにつれ、 2^n個の変数のトレースは、我々の手に余るようになるのは明らかです。 量子コンピュータの働きをチェックし検証することの難しさは、実は、もう一つあります。それは、我々は、量子コンピュータの状態を正確に知ることはできないという問題です。 量子コンピュータの状態は、先に見たように2^n個の状態の「重ね合わせ」になっているのですが、その状態を知ろうとして観測すると、その「重ね合わせ」の状態は失われてしまいます。 観測によって得られる...

 【 浅海ゼミ 第16回の講演ビデオと講演資料公開しました 】　 浅海ゼミ「クラウドアプリケーションのためのオブジェクト指向分析設計講座」第16回の講演ビデオと、講演資料を公開しました。 https://www.marulabo.net/docs/asami16/ 今回のテーマは 「分析」です。要求モデルから、分析モデルを作成する作業分野である分析について説明します。今回はユースケースからシステムの概観を抽出するシナリオ分析を取り上げます。　 次回にコンポーネントとシステム・アーキテクチャとして具体化したモデルを作成するコンポーネント分析を取り上げる予定です。　 講演ビデオ  https://youtu.be/GZQQCcDO4zg  は、次のような構成になっています。 　00:00:00 開始 　00:01:10 分析の位置づけ 　00:10:26 分析と設計 　00:17:37 シナリオ分析 　00:30:59 シナリオ分析の実践 　00:36:52 まとめ 資料は、次からアクセスできます。 MaruLabo:   https://www.marulabo.net/docs/asami15/ SlideShare:  https://www.slideshare.net/asami224/15-253173625 浅海ゼミの講座の全体構成はこちらを参照ください。 https://www.marulabo.net/docs/asami/

【「量子計算の古典的検証」問題とは何か？ 】 「量子計算」というのは、量子コンピュータが行なう計算のことです。「古典的検証」を行うのは人間です。人間が古典的手段を使って、量子コンピュータが行なった計算が正しいかどうかをチェックすることを、「量子計算の古典的検証」と言います。 「古典的手段」とは、主要には、古典的コンピュータのことを指します。これも、ピンとこない言い回しかもしれません。それは、量子コンピュータとの対比で古典的と言われているだけで、最新鋭のスーパーコンピュータを含む、普通のコンピュータのことです。 「量子計算の古典的検証」とは、量子コンピュータの行なった計算が正しいものであるかを、人間が普通のコンピュータを使って、確かめると言うことです。 　【 ショアのアルゴリズムの場合】 量子コンピュータのアルゴリズムとして有名な素因数分解を行う「ショアのアルゴリズム」の場合でしたら、「量子計算の古典的検証」は簡単です。 入力した数に対して量子コンピュータが出力した素因数を、コンピュータで実際に掛け算を行なって、それが入力したものと一致しているか確かめればいいわけですから。 ただ、量子コンピュータが行う計算の正しさが、コンピュータで簡単にチェックできるとは限りません。 　【 Google IBM論争の場合】 2019年のGoogleの量子優越性実証実験についての、GoogleとIBMの論争は、直接的には、50数個のqubitを持つ量子コンピュータの「古典的検証」の手法をめぐるものでした。 Googleは、検証にはスーパー・コンピュータを使っても「一万年」かかるとしたのに対して、IBMはやり方を工夫すれば、「二日半」で検証できると主張しました。 IBMは、現在、400 qubitの量子コンピュータを開発しているといいます。こうしたマシンでの「量子計算」の「古典的検証」は、かつて IBMがGoogleに対して主張したような手法で、高速化できるのでしょうか？　 それは、不可能です。  【 ファインマンの場合】 量子コンピュータのアイデアは、ファインマンの古典的なコンピュータ（スーパーコンピュータを含む普通のコンピュータのことです）では、量子の法則に従う自然をシミレートできないという問題意識から始まりました。 　「だから、量子の法則...

【 ショアのアルゴリズムと量子計算複雑性 】　 1990年代に入って、「対話型証明 = Interactive Proof」の導入によって、証明の概念が大きく変わったことは前回述べました。 1990年代、計算複雑性の世界では、対話型証明と並んでもう一つの大きな前進がありました。それは、1980年代にファインマンらによって始まった量子コンピュータ研究の流れの中で、計算複雑性の概念が、量子コンピュータの計算複雑性に拡大されたことです。 1993年、ベルンシュタインとヴァジラーニは、量子チューリング・マシンの上に、量子チューリング・マシンが多項式時間で計算可能な複雑性のクラス BQPを定義し、それがチューリング・マシンが多項式時間で計算可能な複雑性のクラスPを完全に包摂することを発見します。 古典的なコンピュータが多項式時間では計算できない問題が、量子コンピュータでは多項式時間で計算できる可能性があることが、複雑性理論の言葉で示されたのです。 1994年、ショアは驚くべき発表を行います。コンピュータでは多項式時間では解くことが難しいと考えられていた「素因数分解問題」を、量子コンピュータでは多項式時間で解くことができることを彼は見出したのです。「ショアのアルゴリズム」の発見です。 ショアのアルゴリズムの発見は、量子コンピュータの世界だけでなく、さまざまな分野の多くの人に強烈な影響を与えました。 量子コンピュータの研究に多くの人が加わるようになりました。素因数分解の困難さを、暗号の安全性の基礎に置いていた暗号技術も深刻な反省を迫られることになりました。その余波は、今も続いています。 理論的には、ショアのアルゴリズムは、ヴァジラーニたちが示した、複雑性クラスPの外側にあり（古典コンピュータでは多項式時間では計算できない）、かつ複雑性クラスBQPの内側にある（量子コンピュータでは多項式時間で計算できる）計算の実例を与えるものでした。 計算複雑性の研究も、ヴァジラーニのBQP、ショアのアルゴリズムの発見に大きな刺激を受けます。こうして、1970年代、クック、レビン、カープらによって始められた計算複雑性理論は、1990年代、対話型証明と量子複雑性を中心に、大きく変貌することになります。  -------------------------------- 「複雑性の新しいクラス...

【 証明と検証 -- 証明とは何か？ 】 ここまで、2019年のGoogleの「量子優越性」の実証実験、1982年のファインマンの自然をシミレートする量子コンピュータのアイデア、1964年の自然の非局所性を示す「ベルの定理」と、時間を遡ってきましたが、ここから、時間を普通の流れに戻します。 ファインマンの提唱で量子コンピュータの取り組みがはじまった1982年は、アスペたちが「ベルの定理」の実証実験に成功した年でもあります。この1982年をターニング・ポイントとして、現代科学を捉えるのは、面白いかもしれません。 前回、物理学の理論は、基本的には、実験によって検証されることが求められるということと、ただ、物理学の理論を実験で検証するのは、なかなか難しくなっているという話をしました。 確かに、実験による検証を、物理理論の正しさの要件にする必要はないという考えはあり得うるかもしれません。それは、「物理学の数学化」と言っていい考えなのですが、数学的な正しさ、体系性のある理論、「美しい理論」は多くの人を惹きつけるものです。 ただ、ここでは、逆の話をしたいと思います。数学の「正しさ」についての考え方も大きく変わってきていると言う話です。1990年代に入って、数学的証明についての考え方に大きな転換が起きます。"Interactive Proof" 「対話型証明」の登場です。 Interactive Proofの特徴は、「証明者」と「検証者」を分離し、証明を 「証明者」と「検証者」の両者の「対話」の過程として捉え返すことです。 証明は、もともとが正しい推論によって導かれているから正しいのだと考えることと、正しいと検証されるから正しい証明だと考えることは別のことです。Interactive Proofのアプローチでは、正しいと検証されたものが正しい証明であるとされます。 物理理論が実験による検証が必要であるように、数学もそれが正しいことを示すためには、検証というプロセスが必要だと言うことです。 さらに興味深いことは、こうしたアプローチでは、これまで決定論的に進行すると思われていた「数学的証明」は、非決定論的で確率的な性格を帯びることになります。非決定論的で確率的！　これは古典論的な物理学に対する量子論的な物理学の特徴と同じものです。 「物理の数学化」だけをみている...

【 証明と実験 】 物理では、有名な実験がたくさんあります。ノーベル物理学賞の多くは、そうした実験に与えられています。最近ですと、LIGOでの重力波の検出、CERNの加速器LHCでのヒッグス粒子の検出等が有名です。今回取り上げるベルの定理とアスペによる実験での検証も、その一つです。 物理学の理論は、「基本的には」実験によって検証されることが求められます。 理論と実験とは、二つの異なるプロセスです。物理学が、この二つのプロセスを要求していることは、実験を必要としない数学との大きな違いです。数学にとって必要なことは、実験ではなく証明です。 ただそのことは、実験で検証されていない理論が、物理学的には正しい理論とは認められないことを意味しません。 重力波やブラックホールの存在は、近年まで実験的には検証されたわけではありませんでした。そのことを理由に、それらの存在を予見したアインシュタインの重力理論は正しいとは認められないという科学者はいないと思います。 事実、現在多くの物理学者が正しいと信じている物理理論、たとえば超弦理論は、実験によって検証されているわけでは必ずしもありません。 理論と実験による検証との間に、こうしたズレが起きるのには、いくつかの理由があります。 一つには、正しい物理理論がすぐに実験によってその正しさが検証されるとは限らないからです。 今回の例でいえば、アインシュタインがエンタングルメントを発見したのは1935年。ベルが理論的にエンタングルメントの実在性を示したのは 1964年。30年近くかかっています。ただ、ベルが示したのは、それは理論的な証明でした。 アスペが実験でそれを検証したのは 1982年。ベルの定理から20年近く、アインシュタインらのEPR論文からは、50年近くかかっています。（一般に広く知られるようになったのは、多分、2022年のノーベル賞からです。） 理論と実験による検証にずれが生ずるもう一つの理由があります。それは、検証実験に膨大なエネルギーを必要として、既存の技術では実験装置自体、構築できない理論も存在するからです。 20世紀の量子論の集大成である素粒子の「標準モデル」の最後のピースであるヒッグス粒子が21世紀に検出されたのは、CERNの加速器の能力がこの粒子を検出できるまで拡大・増強されたからに他なりません。（あるいは、到達可能なエネ...

 【 ちょうど、40年前を振り返る 】 今回のセミナーの「量子計算の古典的検証」と言うテーマは、新しい、というか、歴史的に形成されたものです。 そのルーツは、「量子的に計算する機械 ＝ 量子コンピュータ」を人間が作り始めたことにあります。量子コンピュータが存在しなければ、その出力を検証しようと言う問題意識が生まれる訳ありませんからね。 今回のセッションは、前回のセッションが取り上げたGoogle-IBM論争の「3年前」より、すこし歴史を遡ります。量子コンピュータのルーツである、ちょうど「40年前」のファインマンの論文を取り上げます。 「40年前」というのは、時期的には、アスぺやクラウザーたちが、ベルの定理の実証実験で成果を上げた時期です。今回のノーベル賞受賞の対象になった研究です。 ファインマンとクラウザーには接点があるようです。「量子論の基礎を研究したい」という若いクラウザーに、ファインマンは、「そんなの時間の無駄だ。量子論はもう完成している。そんなことより、もっときちんと計算しろ。」と言ったそうです。多分、60年代か70年代のことだと思います。 （ノーベル賞受賞後のインタビューで、クラウザーはそんなことを語っていたのですが、今見に行ったら、そんな発言はきれいに削除されていました。魚拓とっとけばよかった。） とまれ、このファインマンの40年前の論文は、とても重要なものです。 彼の主張の力点は、古典的なコンピュータでは、量子の世界、ひいては自然のシミレーションなぞ出来はしないということに置かれています。 注意してほしいのは、彼のいう「古典的コンピュータ」の能力の理解は、正確なものだということです。それは、セル・オートマトンや「万能チューリングマシン」の能力に等しいことを、彼はよく理解していました。 そうだとしたら、量子コンピュータが可能にするものから、我々は何を学ぶことができるのでしょう？　それは、今回のセミナーの「量子計算の古典的検証」という問題に直結します。 この疑問に答えるために、もう少しだけ歴史を遡りたいと思います。次回のセッションは、ベルやアスぺやクラウザーの問題意識を取り上げます。 -------------------------- 「ファインマンの洞察」を公開しました。 https://youtu.be/KH0mm79fM...

【 3年前の10月に起きたことを振り返る 】 11月のセミナーでは、量子コンピュータの計算の正しさを、古典コンピュータ（現在の、普通のコンピュータのこと）で検証できるのかという、「量子計算の古典的検証」問題を取り上げます。 これがどういう問題かを示すために、今回は、ちょうど3年前の2019年の10月に起きた、「量子超越性」をめぐるGoogleとIBMの論争を、改めて紹介しようとおもいます。 2019年の10月、Googleは量子コンピュータの歴史のマイルストーンとも言うべき重要な論文を発表をします。それは、普通のコンピュータなら一万年かかる計算を量子コンピュータは3分で行うことができたとして、「量子超越性」を実証的に示すことが出来たと言うものでした。 それに対して、IBMは、現存のスーパーコンピュータを使えばその計算は一万年ではなく二日半で終わるとして、Googleの実験は「量子超越性」を実証したものとは言えないと反論しました。 この論争は、量子コンピュータの行う計算を古典的な手段で検証することの難しさを表しています。注意してほしいのは、この論争でGoogleもIBMも、「一万年」「二日半」というコンピュータでの計算を実際に行ったわけではないと言うことです。 「「量子超越性」をめぐる論争」を公開しました。 https://youtu.be/6C3ML6NoKC8?list=PLQIrJ0f9gMcOQHQ6KmWuUxuRZkHT-2gZ- スライドのpdf https://drive.google.com/file/d/1LhXVnbJXSGZU3cgTzTbxz2TDPRrVBUwR/view?usp=sharing blog：「3年前の10月に起きたことを振り返る 」　 https://maruyama097.blogspot.com/2022/11/310.html まとめページ「量子計算の古典的検証 」 https://www.marulabo.net/docs/cvqc/ 参考資料「量子コンピュータの現在 -- 量子優越性のマイルストーンの達成 --」 https://www.marulabo.net/docs/q-supremacy/