Mahadevのアプローチ (1) -- 対話型証明

11月 15, 2022

【 Mahadevのアプローチ (1)-- 対話型証明】

前回、普通のコンピュータのデバッグや動作検証のようなやり方は、量子コンピュータの検証には使えそうもないという話をしました。

そのことは、現在の量子コンピュータが、普通のコンピュータと対比でいうと、ハードとソフトの分離もされていないし、OSとアプリケーションの区別もない状態にあることと、少し関係はあります。ただ、量子コンピュータには開発キットもデバッガーもないことを言いたかったわけではありません。

　【原理が異なる二つのシステムの境界での相互作用】

「量子計算の古典的検証」の問題は、原理が異なる二つシステムの境界での相互作用はいかにして可能なのか、あるいは、それにはどのような限界があるのかという、量子コンピュータと我々の関係にとって極めて本質的な問題です。

量子コンピュータの状態の遷移を正確には追えないだけではありません。我々は、現状では、量子計算の出発点となる、任意のqubitの状態を量子コンピュータ上にセットするというプリミティブな操作でも、その検証を含めれば、思い通りには量子コンピュータをコントロールできていないのです。

Mahadevの「量子計算の古典的検証」問題の肯定的解決は、こうした現状を変えて、量子コンピュータに対する人間のコントロール能力を大きく拡大する可能性を秘めているのです。

　【 Mahadevの二つのアプローチ】

Mahadevは、「古典的検証問題」に二つの方向からアプローチします。

第一のアプローチは、今回のセッションで紹介する「対話型証明 = Interactive Proof 」の手法を使います。「検証問題」の解決を可能にする、量子コンピュータと人間の「対話のプロトコル」を見つけようとします。

第二のアプローチは、量子コンピュータでも破れないと考えられている、「Post量子暗号」、先日セミナーを行ったLWE(Learning with Errors)を使います。量子コンピュータの中に、量子コンピュータも改変できない、我々は知っているが量子コンピュータには秘密の状態を作ります。これについては次回のセッションで。

　【 Interactive Proof 紹介】

Interactive Proofの想定は、いささか奇妙なものです。Interactive Proofには、二人の人物が登場します。

一人は「証明者 Prover」です。彼は、全知全能で、どんな問題も瞬時に答えを返す能力をもっています。ただし、彼は誠実ではなく、時々、人を欺く嘘をつきます。

もう一人は、「検証者 Verifier」です。彼は、普通の人間です。理性をもっていて、証明者の主張を検証しようとします。彼は、証明者の言うことを、盲信はしません。

Interactive Proofは、この両者「不実な全能者」と能力は限られているが「理性的な人間」が対話を繰り返すことで、何かを証明しようというシステムです。

基本的には、検証者が証明者の主張を受け入れた時、すなわち、証明者が証明者の主張が正しいと検証者を納得させることができた時、証明は終わります。

ただし、ある場合には、証明者の検証者の説得は失敗し、検証者は証明者の主張を拒否して、証明が終わります。

　【「Bellの定理」とInteractive Proof 】

1990年代、Interactive Proofは、計算複雑性の世界で快進撃を始めます。Shamirの IP = PSPACEの証明、BabaiらのMIP = NEXPの証明はは、その代表的な成果です。

21世紀に入って、2004年、コンピュータ・サイエンティストのRichard Cleve, Peter Hoyer, Ben Toner, John Watrousらは、Bellの思考実験がInteractive Proofと極めて似ていることに気づきます。

--------------------------------

「Mahadevのアプローチ (1)-- 対話型証明」を公開しました。