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