過去・現在・未来

【  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年代、対話型証明と量子複雑性を中心に、大きく変貌することになります。  -------------------------------- 「複雑性の新しいクラスBQPの

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