Optimal Average Success Probabilities of Binary $(n,n-1)$ and $(n,n-2)$ Quantum Random Access Codes

技術的要約：バイナリ $(n, n-1)$ および $(n, n-2)$ 量子ランダムアクセスコードの最適な平均成功確率

問題設定
本論文は、量子ランダムアクセスコード（QRAC）の根本的な限界について扱う。バイナリ $(n, m)$ QRACでは、$n$ ビットの古典的文字列が $m$ 量子ビットの状態へとエンコードされる。デコーダは、与えられた状態とランダムに選択されたインデックス $i \in \{1, \dots, n\}$ に基づき、$i$ 番目のビットを復元を試みる。主要な性能指標は、最適な平均成功確率 $P^{Q,avg,opt}_{n,m}$ である。

ホレヴォの定理は、取得可能な情報に関するグローバルな限界を確立しているが、個々のビットへのアクセスの信頼性を完全に特徴付けるものではない。数値的に推測された上界 $P^{Q,avg,opt}_{n,m} \leq \frac{1}{2} + \frac{1}{2}\sqrt{\frac{m}{n}}$ は、特定の小さなケース（例：$(2,1), (3,1), (3,2), (4,2), (6,2)$）においてタイトであることが観察されている。鈴木による最近の構成（$m=n-1$ の場合）および Akibue らによる構成（$m=n-2$ の場合）は、まさにこの境界を達成している。しかし、これらの構成の厳密な最適性、および高レート領域 $m \in \{n-1, n-2\}$ における推測された上界の妥当性は、未証明のままであった。

手法
著者らは、**フルストリング・プレッティ・グッド測定（Full-String Pretty Good Measurement: PGM）**の性質を分析することにより、$m \in \{n-1, n-2\}$ における推測された上界を証明する。証明の戦略は、以下のステップを通じて、問題をローカルなビット再構成からグローバルな文字列再構成へと翻訳することである：

1. フルストリング PGM の構成: 著者らは、$m$ 量子ビットのエンコーディングから $n$ ビットの全文字列 $X$ を再構成しようとする POVM ($Q^C_y$) を定義する。これは、遷移確率 $T^{C,PGM}_{xy}$ を持つ古典チャネルを誘導する。
2. ローカル・グローバル翻訳: Lin と de Wolf の研究に基づき、著者らは、フルストリング PGM の出力を $i$ 番目のビットを除くすべてのビットについて合計すると、正確に $i$ 番目のビットに対する 1 ビット PGM になるという性質を利用する。
3. ハミング距離の境界: 証明では、入力文字列と PGM 出力との間の期待ハミング距離 $\Delta_{C,PGM} = E[d_H(X, Y^{C,PGM})]$ に関する上限と下限を確立する：
   • 上界: Renes の洗練された PGM 境界を用いることで、平均成功確率が $P^C$ であるならば、$\Delta_{C,PGM} \leq \frac{n}{2}(1 - (2P^C - 1)^2)$ となることを示す。
   • 下界: 著者らは、次元制約と誘導チャネルの性質に基づいて $\Delta_{C,PGM}$ の下限を導出する。
     • 遷移行列 $T^{C,PGM}$ が**半正定値（PSD）**であることを証明する。
     • PSD 性を用いることで、ハミング距離が奇数である確率が最大でも $1/2$ であることを示す。
     • これらを、完全な文字列の復元確率に関する Nayak の境界（$P[Y=X] \leq 2^{m-n}$）と組み合わせることで、$m=n-1$ のとき $\Delta_{C,PGM} \geq 1/2$、$m=n-2$ のとき $\Delta_{C,PGM} \geq 1$ であることを確立する。一般に、$\Delta_{C,PGM} \geq \frac{n-m}{2}$ となる。
4. 統合: $\Delta_{C,PGM}$ に対する上界と下界を等置することにより、著者らは不等式 $P^C \leq \frac{1}{2} + \frac{1}{2}\sqrt{\frac{m}{n}}$ を導出する。

主な貢献と結果

• 最適性の証明: 本論文は、推測された上界 $P^{Q,avg,opt}_{n,m} \leq \frac{1}{2} + \frac{1}{2}\sqrt{\frac{m}{n}}$ が $m = n-1$ および $m = n-2$ のケースにおいて厳密に成立することを厳密に証明した。
• 正確な特徴付け: その結果、本論文はこれらのファミリにおける最適な平均成功確率を正確に決定した：
  $$P^{Q,avg,opt}_{n,n-1} = P^{Q,avg,opt}_{n,n-2} = \frac{1}{2} + \frac{1}{2}\sqrt{\frac{m}{n}}$$
• 構成の検証: この結果は、鈴木による QRAC 構成（$n, n-1$ 用）および Akibue らによる構成（$n, n-2$ 用）が厳密に最適であることを確認している。
• 技術的補題: 本研究は、フルストリング PGM に関する 3 つの主要な補題を導入している：
  1. 平均成功確率を用いた期待ハミング距離の上限。
  2. 誘導チャネルの遷移行列が半正定値であることの証明。
  3. ハミング距離が偶数よりも奇数である確率が高くないことを示す境界。

意義
本論文は、量子ビット数が古典的ビット数よりわずか 1 または 2 少ない高レートのバイナリ QRAC における厳密な最適性の問題を解決した。推測された上界を証明することにより、著者らはこれらの特定のレジームにおける圧縮性と取得性のトレードオフを正確に特徴付けている。ローカルな再構成から PGM を介したグローバルな再構成へと翻訳し、次元および PSD 制約を利用するという手法は、QRAC の限界を研究するための新しい解析的枠組みを提供している。本結果は、既知の構成で見られる平方根スケーリングが、これらのパラメータにおける理論的限界であることを裏付けている。