No Free Compression in Quantum Relaxations for Optimization

技术摘要：量子松弛优化中不存在“免费压缩”

问题陈述
量子优化算法（如量子近似优化算法 QAOA 和量子退火）经常面临问题规模与可用硬件之间的不匹配。传统的二进制编码为每个决策变量分配一个量子比特，这使得可求解的问题规模受限于可用量子比特数（$m \approx n$）。为了解决这一问题，研究者提出了“量子比特高效”的编码方案，旨在将 $m$ 个经典二进制变量压缩到 $n$ 个量子比特中，其中 $n \ll m$。这些方法通常依赖于将变量表示为指定可观测量（例如 Pauli 算符或 Majorana 算符）的期望值，而非直接进行比特到量子比特的映射。

虽然这些压缩编码显著降低了寄存器宽度，但这种压缩所带来的资源权衡——特别是关于可达期望值的几何结构、这些值的量级以及信息恢复的成本——目前仍未得到充分理解。本文研究是否存在“免费”的压缩，或者减少量子比特数量是否必然会将成本转移到其他物理或信息论资源上。

研究方法
作者通过三个不同的维度对该问题进行了分析，从特定的算符几何结构转向通用的信息论界限：

1. 精确 Majorana 几何结构： 本文聚焦于“完全二次项-Majorana 族”，其中 $m = \binom{2n}{2} \approx 2n^2$ 个二进制变量通过 $2n$ 个 Majorana 算符在 $n$ 个量子比特上的两体相关性进行编码。作者定义了“通用裕度”（universal margin）$\Delta$，即在给定预设符号（对于所有可能的目标符号分配/比特串）的情况下，能够保证的最小相关量级。作者利用谱图论，特别是通过将这些算符的协方差矩阵与竞赛图矩阵（tournament matrices）联系起来，推导出了一个精确的解析界限。
2. 高斯完备性： 作者研究了非高斯量子态（纠缠态或相互作用态）是否能扩展出超越费米子高斯态（自由费米子态）所能达到的两点相关性集合。作者利用了 Majorana 算符的协方差体（covariance body/spectrahedron）的性质。
3. 通用信息论界限： 为了建立独立于特定算符结构的基准，本文应用了量子随机存取码（QRAC）理论。作者推导了对于任何固定的二进制可观测量族，其通用裕度 $\delta$ 的界限，并利用 Nayak 界限将量子比特宽度（$n$）与可靠随机存取解码所需的态副本数（$N$）联系起来。

核心贡献与结果

• Majorana 编码的精确通用裕度：
  本文证明了对于 $n$ 个量子比特上的完全二次项-Majorana 族，其通用裕度精确为：
  $$\Delta_{\text{Maj}}(n) = \tan\left(\frac{\pi}{4n}\right) \sim \frac{\pi}{4n} = \Theta(1/n)$$
  该结果是通过识别出在切换和重标记（switching and relabeling）下等价于“传递竞赛图”（transitive tournament）的最坏情况符号模式而得出的。虽然典型的随机符号模式保留了 $\Theta(1/\sqrt{n})$ 的裕度，但最坏情况下的缩放严格遵循 $\Theta(1/n)$。这代表了一种比通用的信息论预期更强的参数化衰减。

• 两体松弛的高斯完备性：
  作者证明了任意密度算符和费米子高斯态生成的二次项-Majorana 协方差矩阵集合（即“协方差体”）是完全相同的。因此，非高斯资源（如纠缠或相互作用）无法扩大可达的两点相关性集合。这意味着对于关于这些相关项的线性目标函数，使用高斯态进行半正定规划足以找到最优松弛。若要访问非高斯信息，则需要更高阶的相关性。

• 通用信息论基准：
  对于任何固定的 $m$ 个二进制可观测量在 $n$ 个量子比特上的情形，其裕度 $\delta$ 满足：
  $$\delta \leq \sqrt{\frac{2 \ln 2 \cdot n}{m}}$$
  这证实了如果 $m$ 相对于 $n$ 超线性增长（即 $n = o(m)$），则没有任何固定的可观测量族能保持常数级的裕度。此外，对于从 $N$ 个态副本中进行成功概率 $p > 1/2$ 的任意随机存取解码，宽度-副本乘积必须满足 $nN = \Omega(m)$。

• 操作性后果（“没有免费的午餐”）：
  由于裕度的缩小，在非线性解码器（例如 $z_i = \tanh(\alpha \langle A_i \rangle)$）中必须引入一个缩放参数 $\alpha$ 来恢复二进制输出。对于 Majorana 情况，为了维持固定的解码量级，要求 $\alpha = \Omega(n)$。这导致在最坏情况下，单个坐标的符号恢复成本为 $N = \Theta(n^2)$ 次测量采样（或副本）。因此，量子比特的节省被对更高测量分辨率、更强非线性缩放或更高采样预算的需求所抵消。

意义与主张
本文声称提供了针对特定高度压缩量子编码（完全二次项-Majorana 族）的第一个精确特征描述，揭示了特定于算符几何结构的 $\Theta(1/n)$ 瓶颈。

作者强调，虽然压缩并未“失败”，但它不是“免费”的。量子比特寄存器宽度的减少重新体现为：

1. 受限的几何结构： 可达的期望值被限制在特定的协方差体内，且该集合无法通过非高斯态来扩大。
2. 量级减小： 最坏情况下的相关量级随量子比特数量增加而反比例缩小。
3. 增加的恢复成本： 解码这些微小值需要要么随 $n$ 线性增长的缩放参数，要么对于孤立坐标而言随 $n^2$ 增长的测量采样预算。

该研究结论指出，评估量子优化资源需要对量子比特数、可达裕度、解码规则和采样预算进行整体评估，而非仅仅关注寄存器宽度。研究结果区分了属于压缩共性的成本（信息论界限）与特定于 Majorana 几何结构的成本（精确裕度定理）。