量子計算の古典的検証

11/26 マルゼミ 「量子計算の古典的検証」について

「量子計算の古典的検証」とは、量子コンピュータが人間の指示通りに働いているか、量子コンピュータの行なった計算が正しいものであるかを、人間がキチンと確かめると言うことです。こうしたことは、普通のコンピュータではごく普通に行われていることですが、量子コンピュータでは、それがとても難しいのです。

この10年以上、研究者たちは、実践的にも大きな意味のあるこの問題に取り組んできたのですが、なかなか答えが見つかりませんでした。それが、最近になって、この難問が肯定的に解かれました。解いたのは、若い大学院生 Urmila Mahadev でした。

今回のセミナーは、彼女の「量子計算の古典的検証」を取り上げます。

まず、こちらを。わかりやすい解説です。

• 「量子計算の古典的検証」とは何か？
• 問題の難しさ
• Mahadevのアプローチ (1)-- 対話型証明
• 量子コンピュータとの「対話」
• Mahadevのアプローチ (2)-- 暗号化
• Post量子暗号の力

「量子計算の古典的検証」問題とは何か？

「量子計算の古典的検証」とは何か？

( スライドのpdf blog:「「量子計算の古典的検証」とは何か？」)

量子コンピュータの働きをチェックし検証する-- 問題の難しさ

( スライドのpdf 　blog:「問題の難しさ」)

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

( スライドのpdf 　blog:「Mahadevのアプローチ (1)-- 対話型証明」)

Mahadevのアプローチ (2)-- 暗号化 --

( スライドのpdf 　blog:「Mahadevのアプローチ (2)-- 暗号化」)

背景

「量子超越性」をめぐる論争

( スライドのpdf blog:「3年前の10月に起きたこと」)

ファインマンの洞察

( スライドのpdf blog:「ちょうど、40年前を振り返る」)

ベルの定理とその実験での検証

( スライドのpdf blog:「証明と実験」)

Interactive Proofと証明概念の転換

( スライドのpdf blog:「証明と検証 -- 証明とは何か？」)

複雑性の新しいクラスBQPの発見

( スライドのpdf blog:「ショアのアルゴリズムと量子計算複雑性」)

準備

Learning with Errors

( スライドのpdf blog:「Post量子暗号」)

Universal Quantum Circuit

( スライドのpdf blog:「任意のf(x)を計算する量子回路を考える」)

Trapdoor Claw-Free Functions

( スライドのpdf blog:「Clawとは何か」)

Noisy Trapdoor Claw-Free Functions using LWE

( スライドのpdf blog:「LWE暗号の利用」)

Mahadev

Quantum Certification Protocol

( スライドのpdf blog:「量子コンピュータであることを確認する方法」)

講演ビデオ

Part 1 「『量子計算の古典的検証』問題とは何か？」

Part 2 「量子計算の古典的検証 (2) 背景」

Part 3「量子計算の古典的検証 (3) 準備」

講演資料

関連ページ

量子コンピュータの現在 -- 量子優越性のマイルストーンの達成 --

ラティス暗号入門

チューリングマシンの拡大と複雑性