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

技术摘要：二元 $(n, n-1)$ 与 $(n, n-2)$ 量子随机访问码的最优平均成功概率

问题陈述
本文探讨了量子随机访问码（QRACs）的基本极限。在二元 $(n, m)$ QRAC 中，$n$ 位经典字符串被编码为一个 $m$ 量子比特的状态。解码器在给定该状态且随机选择一个索引 $i \in \{1, \dots, n\}$ 时，尝试恢复第 $i$ 位比特。主要的性能指标是平均最优成功概率，记作 $P^{Q,avg,opt}_{n,m}$。

虽然 Holevo 定理确立了一个全局信息量限制，但它并未完全刻画访问单个比特的可靠性。一个数值推测的上界 $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)$）被观察到是紧致的。近期由 Suzuki 提出的构造（针对 $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$ 位的单比特 PGM。
3. 汉明距离界限： 证明过程建立了期望汉明距离 $\Delta_{C,PGM} = E[d_H(X, Y^{C,PGM})]$（即输入字符串与 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}}$$
• 验证构造： 该结果证实了 Suzuki（针对 $n, n-1$）和 Akibue 等人（针对 $n, n-2$）所做的特定 QRAC 构造是严格最优的。
• 技术引理： 本研究引入了关于全字符串 PGM 的三个关键引理：
  1. 关于期望汉明距离与平均成功概率关系的上界。
  2. 证明诱导信道的转移矩阵是半正定的。
  3. 一个显示对于此类信道，汉明距离为奇数的概率不会高于偶数的界限。

意义
本文解决了高速率二元 QRAC（即量子比特数仅比经典比特数少一或两个时）的严格最优性问题。通过证明该推测界限，作者精确地刻画了这些特定参数下压缩率与可检索性之间的权衡。其方法论通过利用优良测量（PGM）实现从局部到全局重构的转化，并利用维度和 PSD 约束，为研究 QRAC 极限提供了一种全新的分析框架。研究结果证实，在已知构造中所观察到的平方根缩放规律，确实是这些参数下的理论极限。