量子計算の古典的検証

11/26 マルゼミ 「量子計算の古典的検証」について
「量子計算の古典的検証」とは、量子コンピュータが人間の指示通りに働いているか、量子コンピュータの行なった計算が正しいものであるかを、人間がキチンと確かめると言うことです。こうしたことは、普通のコンピュータではごく普通に行われていることですが、量子コンピュータでは、それがとても難しいのです。
この10年以上、研究者たちは、実践的にも大きな意味のあるこの問題に取り組んできたのですが、なかなか答えが見つかりませんでした。それが、最近になって、この難問が肯定的に解かれました。解いたのは、若い大学院生 Urmila Mahadev でした。
今回のセミナーは、彼女の「量子計算の古典的検証」を取り上げます。
まず、こちらを。わかりやすい解説です。
- 「量子計算の古典的検証」とは何か?
- 問題の難しさ
- Mahadevのアプローチ (1)-- 対話型証明
- 量子コンピュータとの「対話」
- Mahadevのアプローチ (2)-- 暗号化
- Post量子暗号の力
「量子計算の古典的検証」問題とは何か?
「量子計算の古典的検証」とは何か?
( スライドのpdf blog:「「量子計算の古典的検証」とは何か?」)
量子コンピュータの働きをチェックし検証する-- 問題の難しさ
Mahadevのアプローチ (1)-- 対話型証明
( スライドのpdf blog:「Mahadevのアプローチ (1)-- 対話型証明」)
Mahadevのアプローチ (2)-- 暗号化 --
( スライドのpdf blog:「Mahadevのアプローチ (2)-- 暗号化」)
背景
「量子超越性」をめぐる論争
( スライドのpdf blog:「3年前の10月に起きたこと」)
ファインマンの洞察
( スライドのpdf blog:「ちょうど、40年前を振り返る」)
ベルの定理とその実験での検証
Interactive Proofと証明概念の転換
( スライドのpdf blog:「証明と検証 -- 証明とは何か?」)
複雑性の新しいクラスBQPの発見
( スライドのpdf blog:「ショアのアルゴリズムと量子計算複雑性」)
準備
Learning with Errors
Universal Quantum Circuit
( スライドのpdf blog:「任意のf(x)を計算する量子回路を考える」)
Trapdoor Claw-Free Functions
Noisy Trapdoor Claw-Free Functions using LWE
Mahadev
Quantum Certification Protocol
( スライドのpdf blog:「量子コンピュータであることを確認する方法」)