技術要約：量子メモリの証明（Proofs of Quantum Memory）

1. 問題提起

量子コンピューティング・アーキテクチャの急速な進展と、大規模な量子メモリへの展望に伴い、極めて重要な検証上の課題が生じている。それは、「古典的な検証者が、遠隔の量子デバイスが実際に指定された数の量子ビットを特定の期間にわたって保持していることを、どのようにして確認できるか？」という問いである。

既存の量子性の証明（Proofs of Quantumness: PoQ） [BCM+21] は、古典的な検証者が、プローバー（証明者）が非古典的な計算を実行していることを確認することを可能にする。しかし、PoQは量子メモリの「容量」や「保持」を検証するには不十分である。プローバーは、少数の量子ビットと古典的な後処理を用いることで、理論上PoQをパスできてしまう可能性があり、それによって大規模な量子メモリ（例：1億量子ビット）を保有していることを示すことはできない。本論文は、初期化フェーズと実行フェーズの間の時間間隔 $\Delta$ において、プローバーが特定の量子メモリサイズ ($m_1$) を維持していたことを、古典的な検証者が証明できるプロトコルの必要性に対処するものである。

2. 手法および定義

2.1 量子メモリの証明（Proofs of Quantum Memory: PoQM）

著者らは、**量子メモリの証明（PoQM）**を新しい暗号プリミティブとして導入する。PoQMは、古典的な通信路を介した、古典的な確率的多項式時間（PPT）検証者と量子多項式時間（QPT）プローバーとの間の対話型プロクションである。プロトコルは以下の2つのフェーズで構成される：

1. 初期化フェーズ（Initialization Phase）： 検証者 ($V_1$) とプローバー ($P_1$) が相互作用する。$P_1$ は古典的な文字列 state と、$m_1$ 量子ビットの量子状態 $\sigma_{state}$ を出力する。
2. 実行フェーズ（Execution Phase）： 時間遅延 $\Delta$ の後、検証者 ($V_2$) とプローバー ($P_2$) が相互作用する。$P_2$ は state と $\sigma_{state}$ を入力として受け取る。

セキュリティ特性：

• 完全性（Completeness）： $m_1$ 量子ビットのメモリを持つ正直なプローバーは、高い確率で受理される。
• 健全性（Soundness）： 間隔 $\Delta$ の間に最大 $m_2$ 個の量子ビットしか保持できないプローバー（ここで $m_2 < m_1$）は、高い確率で拒絶される。検証者は、プローバーが少なくとも $(m_2 + 1)$ 個の量子ビットを保有していたことを実質的に証明する。

また、本論文では、検証者の最終的な決定計算が効率的である必要はない（非限定的である）**非効率検証者PoQM（Inefficient-Verifier PoQM: IV-PoQM）**についても定義している。ただし、相互作用自体は古典的である。

2.2 技術的ツール

構成には、以下の暗号プリミティブおよび補題が用いられている：

• LWEの困難性： Learning With Errors (LWE) 仮定、およびその劣指数関数的な困難性のバリアントの両方が、構成の中心となっている。
• 1-of-$2^k$ パズル： 否定的な健全性誤差を持つ2ラウンドPoQMを構築するために使用される。
• 検証可能なリモート状態準備（Verifiable Remote State Preparation: RSP）： 量子通信路を古典的通信路に置き換えるために使用され、量子状態の古典的な検証を可能にする。
• BB84状態に対するLOCCリーク特性： 限定的な量子メモリと古典的なリークを持つアドバーサリに対するBB84状態の安全性に関する[ÇG24]の補題。
• 測定補題（Measurement Lemma）： 中間測定の有無による、量子アルゴリズムによる文字列出力確率に関する[BZ13]の結果。

3. 主な貢献と結果

3.1 PoQMの構成

本論文では、LWEの困難性に基づいた2つの異なるPoQMの構成を示している。

1. 2ラウンド構成（劣指数関数的LWEに基づく）：

   • 基盤： 1-of-$2^k$ パズル [LLQ22] に基づく。
   • 仮定： 劣指数関数的なLWEの困難性。
   • 特性： 2ラウンド（4メッセージ）プロトコル。無視可能な健全性誤差を達成する。
   • メカニズム： プローバーは「Obligate」アルゴリズムを通じて状態を生成する。検証者はランダムな文字列でプローバーに挑戦する。健全性は、限定されたメモリを持つアドバーサリが、分割された状態の両方の半分に対してパズルを解くことができないことに依存している。

2. 多項式ラウンド構成（多項式関数的LWEに基づく）：

   • 基止： 検証可能なリモート状態準備（RSP） [Zha25] に基づく。
   • 仮定： 多項式関数的なLWEの困難性。
   • 特性： 多項式ラウンドのプロトコル。逆多項式的な健全性誤差を達成する。
   • メカニズム： 検証者はRSPを用いて、古典的通信路を介してBB84状態を生成する。プローバーはこれらの状態を保持し、チャレンジに応じて正しく測定しなければならない。健全性は、LOCCリーク特性を用いて増幅され、アドバーサリが $m_2$ 量子ビットしか持たない場合、$\lceil 9.1 m_2 \rceil$ 個の量子ビットの測定結果を高確率で予測できないことを示す。

3.2 下限値と示唆

本論文は、PoQMを構成するために必要な暗号プリミティブの理論的な下限値を確立している：

• IV-PoQM $\implies$ One-Way Puzzles (OWPuzzs)： 著者らは、IV-PoQMが、一方向関数（OWF）の量子版であるOWPuzzs [KT24] の存在を内含することを示している。これは、OWFのみから（ブラックボックス的に）PoQMを構築することが困難であることを示唆している。
• Predictable PoQM $\implies$ QCCC Key Exchange： 「予測可能なPoQM」（実行フェーズがシングルラウンドであり、検証者のチェックが決定論的である制限されたバージョン）について、著者らは、それが量子計算古典通信（QCCC）鍵交換を内含することを示す。QCCC鍵交換はOWFからブラックボックス的に構築できないという証拠があるため、これはPoQMについても同様の困難さがあることを示唆している。

3.3 Proofs of Quantumness (PoQ) との関係

本論文は、PoQMと既存のPoQとの関係を調査している：

• 一般化： PoQMはPoQを一般化する。もしPoQMが存在するならば、PoQも存在する。
• 「真にインタラクティブな」PoQの捕捉： 著者らは、定数ラウンドのPoQは、以下のいずれかであることを証明している：
  1. 定数ラウンドのPoQM（$m_2=0$ の場合）。
  2. シングルラウンドの量子検証者PoQ（QV-PoQ）。
     シングルラウンドのQV-PoQは、「自明な」もの（古典的に困難だが量子的に容易な問題を解いているもの）と見なされる。したがって、PoQMは、非自明なPoQの「真にインタラクティブな」性質を捉えていることが示されている。
• ブラックボックス簡約： もし量子的に安全な偽造不可能な仮定からブラックボックス的に構築された定数ラウンドのIV-PoQが存在するならば、定数ラウンドのIV-PoQMが存在する。これは、IV-PoQMが、量子的に安全な定数ラウンドの統計的隠蔽コミットメント（したがって衝突耐性ハッシュ関数）から構築可能であるという結論を導く。

4. 重要性と主張

本論文は、量子メモリの保持を古典的に検証するための理論的基礎を確立したと主張しており、これは量子性の検証とは明確に区別される、より強力な能力である。

• 実現可能性： 本論文は、PoQMが標準的な暗号仮定（LWE）の下で構築可能であることを示しており、将来の量子ネットワークにおける検証への具体的な道筋を提供している。
• 理論的限界： PoQMをOWPuzzsやQCCC鍵交換と結びつけることで、より弱い仮定（OWFなど）で達成できることの境界を明確にし、PoQMにはより強い仮定が必要であることを示唆している。
• 概念的明晰さ： 本研究は、量子検証プロトコルの階層構造を明確にし、「自明な」シングルラウンドの証明と、メモリ保持を必要とする「真にインタラクティブな」証明を区別しており、PoQMが後者の形式化として機能することを示している。

著者らは、応用に関しては控えめなトーンを維持しており、量子暗号学および計算複雑理論の文脈における、厳密な暗号学的定義、構成、および理論的示唆にのみ焦点を当てている。具体的な実験的実装や即時の商業的応用を提案しているのではなく、将来の検証システムに必要な理論的ツールを提供している。