量子計算の古典的検証

全体概要

本セミナーは「量子計算の古典的検証（Classical Verification of Quantum Computation）」という、量子コンピュータ時代の根幹を問う知的挑戦を主題としています。量子コンピュータが実用化されつつある現在、私たちは根本的な問いに直面しています——「量子コンピュータが正しく計算したかどうかを、普通のコンピュータを使う人間がどうやって確かめられるのか？」という問いです。

この問いが難しい理由は本質的です。n個のqubitからなる量子コンピュータの状態は2ⁿ個の振幅によって決まりますが、それを観測しようとすれば重ね合わせ状態は崩壊し、得られるのはn個の古典bitに過ぎません [p.23], [p.24]。量子コンピュータは圧倒的な計算能力を持ちながらも、その内部状態は人間には直接アクセスできない「秘密主義的」な存在なのです [p.46]。

この問題を2004年にGottesmanが定式化してから長らく未解決でしたが、若き大学院生Urmila Mahadevが「量子計算の古典的検証は可能である」という肯定的な解決を提示しました [p.15]。彼女のアプローチは二つの柱から成ります。第一は「Interactive Proof（対話型証明）」の手法であり、証明者と検証者の対話プロトコルを設計することで量子性を検証します [p.29]。第二は、量子コンピュータでも破れない「ポスト量子暗号」、特にLWE（Learning with Errors）を活用した暗号化技術であり、検証者が量子コンピュータに対して秘密の優位性を持つ構造を作り上げます [p.47], [p.48]。

セミナーはこの主題を多角的な背景から照らします。2019年のGoogleとIBMの「量子超越性」をめぐる論争 [p.58], [p.70]、ファインマンが1982年に提示した「古典コンピュータは量子をシミュレートできない」という洞察 [p.77]、ベルの定理とその実験的検証 [p.87], [p.115]、Interactive Proofが証明概念そのものを転換した歴史 [p.117], [p.131]、さらに量子複雑性クラスBQPの発見 [p.137] まで、豊かな知的背景が丁寧に描かれます。

そして準備として、LWE暗号 [p.152], [p.168]、Universal Quantum Circuit [p.169], [p.187]、Trapdoor Claw-Free Functions [p.188], [p.216] が解説され、最終的にMahadevの量子性検証プロトコルの具体的な構造が明かされます [p.218], [p.237]。本セミナーは、量子コンピュータと人間の関係における「信頼の根拠」を問う、計算理論・暗号理論・量子情報の三つが交差する知的冒険の記録です。

---

講義のロードマップ

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

• この部の核心:

「量子計算の古典的検証」という問題の意味と難しさを直観的に把握させることがゴールです。量子コンピュータは普通のコンピュータにはない能力に期待が寄せられる一方で、その正しさを人間がチェックできないという根本的な非対称性が存在します。Mahadevはこの問題を「対話型証明」と「暗号化」という二つのアプローチで解決し、「量子計算の古典的検証は可能」と証明しました [p.15]。

• 論理展開:
• 「古典的検証」とは、量子コンピュータの計算結果を普通のコンピュータで確かめること。素因数分解のように逆検証が容易な問題は簡単だが、一般には困難 [p.9], [p.10]。
• 量子コンピュータの状態は2ⁿ個の振幅で決まるが、観測するとn bitに崩壊し、内部状態のトレースが原理的にできない [p.21], [p.23]。
• MahadevはInteractive Proofと後量子暗号LWEを組み合わせ、量子コンピュータに対して人間が秘密の優位を持つ構造を実現した [p.29]。
• Hadamard基底での測定成功は量子デバイスにしか不可能であり、これが古典・量子を区別する鍵となる [p.236]。

---

■ Part II: 背景

• この部の核心:

Mahadevの成果が生まれた歴史的・理論的文脈を丁寧に描きます。GoogleとIBMの論争、ファインマンの量子シミュレーション構想、ベルの定理、Interactive Proofによる証明概念の革命、BQPの発見という五つのエピソードが、問題の深さと意義を際立たせます。

• 論理展開:
• Google vs IBM論争（2019年）は、53 qubitの量子計算の古典的シミュレーションの計算コストをめぐるものだったが、qubit数が増えると古典シミュレーションは指数的に困難になることが明確化された [p.57], [p.70]。
• ファインマン（1982年）は「量子系は古典コンピュータではシミュレートできない、変数が多すぎる」と喝破し、量子コンピュータの発想を先取りした [p.73], [p.83], [p.84]。
• ベルの定理（1964年）は「隠れた変数を仮定した古典論の相関は量子論の相関に違反する」ことを示し、CHSH不等式の違反（Tsirelson bound 2√2）として実験的に確かめられた [p.95], [p.115]。
• Goldwasser・Micali・BabaiらによるInteractive Proofは「証明を検証者側から捉え直す」革命をもたらし、IP=PSPACE、MIP=NEXPを証明、さらに量子版MIP*=REが2020年に確立された [p.117], [p.38], [p.44]。
• Bernstein・Vazirani（1993年）によるBQPクラスの発見と、ショアのアルゴリズムによる素因数分解がBQPに属することが証明され、量子計算の理論的位置づけが確立された [p.137], [p.138], [p.140]。

---

■ Part III: 準備

• この部の核心:

Mahadevのプロトコルを理解するための三つの技術的基盤——LWE暗号、Universal Quantum Circuit、Trapdoor Claw-Free Functions——を段階的に構築します。特に、LWEから構成されるNoisy Trapdoor Claw-Free Functions（NTCF）が、プロトコルの暗号論的安全性の核心をなします。

• 論理展開:
• LWE（Learning with Errors）: 行列A、秘密ベクトルs、小さなエラーeから公開鍵B=Aᵀs+eを生成。(A,t=As+e)の分布は一様ランダム分布と計算上区別できないため、sは隠蔽される。これがポスト量子暗号の根拠 [p.152], [p.168]。
• Universal Quantum Circuit: 任意の関数f(x)を計算しユニタリ性を保つ量子回路Ufの一般形。重ね合わせ入力に対してUfは線形性から全入力の同時評価Σ|x>|f(x)>を実現する [p.176], [p.187]。
• Trapdoor Claw-Free Functions: 公開鍵kに対して単射関数ペア{f_{k,0}, f_{k,1}: X→Y}を定義。f_{k,0}(x₀)=f_{k,1}(x₁)=yとなるclaw (x₀,x₁)を見つけることは計算上困難（claw-free）。トラップドアt_kを知れば逆関数が容易に計算できる [p.195], [p.196]。
• NTCFのLWEによる実装: f₀(x)=Ax+e₀、f₁(x)=Ax+e₀+tとして定義。e=0ならf₁(x)=f₀(x+s)が成立し、clawのペアは必ずx₁=x₀-sを満たす。clawの両方を知ることはLWEの秘密鍵を知ることに等しい [p.213], [p.215]。
• Hardcore bit properties: すべてのclaw (x₀,x₁)に対してd≠0でd·(x₀⊕x₁)=c_kとなるdとc_kが存在するが、量子コンピュータでもそれを見つけることはできない [p.198]。

---

■ Part IV: Mahadev — Quantum Certification Protocol

• この部の核心:

Mahadevの量子性検証プロトコルの全貌を具体的に展開します。VerifierがTrapdoor Claw-Free Function（TCF）ペアを生成してProverに渡し、標準基底またはHadamard基底での測定結果を要求・検証するという4ステップのプロトコルが中心です。Hadamard基底での正答は量子デバイスにのみ可能であり、これが量子性の証明となります。

• 論理展開:
• Proverは任意のqubit|ψ>=α₀|0>+α₁|1>を用意し、TCFペアを評価して重ね合わせΣα_b|b>|x>|f_b(x)>を生成。第三レジスターを測定してy=f₀(x₀)=f₁(x₁)を得ると、内部状態はα₀|0>|x₀>+α₁|1>|x₁>という「qubitとclawの重ね合わせ」になる [p.223], [p.225], [p.226]。
• Verifierは1（標準基底）または0（Hadamard基底）をランダムに送信。標準基底ではProverは(b, x_b)を返す（yの原像をランダムに返す）。Hadamard基底ではd·(x₀⊕x₁)=0を満たすdを返す [p.228], [p.229], [p.231]。
• VerifierはトラップドアでyのClaw (x₀,x₁)を既知としているため、両測定の正否を多項式時間で確認できる。一方、claw-free性質により古典デバイスはHadamard応答を生成できない——これが量子性の証明になる [p.236]。
• プロトコルの4ステップ: ①TCFペア送信 → ②y返送 → ③基底選択送信 → ④測定結果の検証 [p.237]。