Proof of hiding conjecture in Gaussian boson sampling

技术摘要：高斯玻色采样中隐藏猜想的证明

1. 问题陈述

高斯玻色采样（GBS）是展示量子计算优势的主要候选方案。关于模拟 GBS 的经典硬度的论证依赖于两个主要组成部分：关于近似矩阵哈夫尼安（hafnian）在平均情况下的硬度猜想，以及隐藏猜想（hiding conjecture）。

隐藏猜想断言，一个复高斯矩阵（特别是具有独立分量的矩阵）可以被“隐藏”在哈尔随机（Haar-random）酉矩阵的对称积的一个子矩阵中，使得这两个分布在全变分（TV）距离下是不可区分的。这一特性至关重要，因为它允许将一个特定的难计算矩阵 $Z$ 嵌入到 GBS 输出分布中，而不会让对手（或经典模拟器）能够识别出 $Z$ 的位置从而破坏概率估计。

虽然标准（福克/Fock）玻色采样的隐藏性质已在稀疏机制下得到确立，但在与近期大规模 GBS 实验相关的机制——即所有 $M$ 个输入模式都被挤压（$K=M$）的情况下——仍未得到证明。在此机制下，相关的子矩阵是哈尔酉矩阵的一个 $N \times M$ 矩形块，已知该块在 TV 距离下并不看起来像高斯矩阵，这是由于行归一化约束所致。开放性问题在于，这个非高斯子矩阵的对称积（$U_{N,M}U_{N,M}^T$）是否仍然在 TV 距离下收敛于一个复对称高斯矩阵。

2. 方法论

作者为所有输入模式都被挤压（$K=M$）的情况提供了严格证明。其核心方法论包括：

• 随机矩阵理论表述：将问题映射为证明一个 $M \times M$ 圆周正交系（COE）随机矩阵（其分布为 $UU^T$，其中 $U$ 是哈尔随机的）的上左 $N \times N$ 子矩阵 $A$，在经由 $\sqrt{M}$ 缩放后，收敛于一个复对称高斯矩阵 $G \sim \mathcal{G}^{\text{sym}}_N$。
• 通过 KL 散度计算全变分距离：作者并非通过直接耦合，而是利用 Pinsker 不等式来限制 TV 距离，该不等式将 TV 距离与两个分布之间的库尔贝克-莱布勒（KL）散度联系起来。
• 密度分析：
  • COE 子矩阵的概率密度函数（PDF）是根据现有文献（Hua, 1963; Kieburg et al., 2013）推导出的，涉及行列式项 $\det(I - Z^\dagger Z/M)^{(M-2N-1)/2}$。
  • 目标高斯矩阵的 PDF 是标准的复对称高斯分布。
• 处理归一化常数：一项关键的技术创新是避免显式计算 COE 密度的复归一化常数。相反，作者引入了一个缩放因子 $\zeta$，并利用矩阵奇异值的界限证明了当 $M \to \infty$ 时 $\zeta \to 1$。这使得他们能够绕过 COE 密度中困难的渐近展开，同时保持收敛证明的有效性。
• 矩界限：证明利用 Weingarten 微积分来计算奇异值（$A^\dagger A$ 的特征值）的矩，并利用集中不等式（亚高斯集中性）来限制大特征值的概率，从而确保对数密度项的泰勒展开保持有效。

3. 关键贡献与结果

定理 1.1 / 定理 1.2（主要结果）：
作者证明了对于所有输入模式都被挤压（$K=M$）的 GBS 情况下的隐藏猜想。具体而言，他们证明了对于 $N = o(\sqrt{M})$，缩放后的 COE 子矩阵 $\sqrt{M}A$ 与复对称高斯矩阵 $G$ 之间的全变分距离在 $M \to \infty$ 时趋于零：
$$d_{\text{TV}}(\sqrt{M}A, G) \leq O\left(\frac{N}{\sqrt{M}}\right)$$
这确立了对称积 $U_{N,M}U_{N,M}^T$ 在实验相关机制下可以被复对称高斯矩阵良好近似。

推论 1.1：
作者证明了复对称高斯矩阵 $G$（具有独立分量）与矩形高斯矩阵的对称积 $GG^T$ 在条目最大范数（以及在足够小的 $N$ 下的 TV 距离）上是接近的。这意味着在相关机制下，近似 $\text{Haf}(G)$ 的硬度本质上等同于近似 $\text{Haf}(GG^T)$ 的硬度。

定理 1.3（乘性估计）：
论文提供了一个密度函数的乘性界限：$f(Z) \leq (1 + O(N^3/M))g(Z)$。这一结果对于硬度证明中使用的“实例生成”方法是必要的，它允许生成一个包含特定隐藏高斯矩阵的随机酉矩阵。

定理 1.5 & 1.6（稀疏机制扩展）：
论文将隐藏性质扩展到了稀疏机制（$NK = o(M)$），确认了在 $K < M$ 的此机制下隐藏猜想依然成立，并将已知对于福克（Fock）玻色采样的界限改进到了最大尺寸 $N = o(\sqrt{M})$。

4. 意义与主张

该论文声称为在输入模式数 $K$ 与总模式数 $M$ 成比例（具体为 $K=M$）的实验相关机制下，提供了 GBS 隐藏性质的首次严格证明。

• 硬度论证：通过证明隐藏猜想，作者将最大化挤压输入模式下 GBS 模拟的经典硬度论证，置于与传统福克玻色采样硬度论证（Aaronson and Arkhipov, 2013）“相当的水平”上。
• 实验相关性：该结果直接支持了近期大规模 GBS 实验（例如 Madsen et al., Nature 2022）的复杂性理论依据，这些实验使用了完全挤压的输入态。
• 理论细微差别：作者强调，证明依赖于子矩阵的对称积的分布，而非子矩阵本身。子矩阵 $U_{N,M}$ 在 TV 距离下远离高斯分布，但其对称积 $U_{N,M}U_{N,M}^T$ 收敛于高斯矩阵。这一区别至关重要，因为以往试图从福克玻色采样隐藏性质推导 GBS 硬度的尝试，在这一稠密机制下均告失败。

论文最后指出，虽然 $K=M$ 的情况已得到解决，但针对中间情况（$K=cM$ 且 $c<1$）的隐藏猜想在本研究中仍是一个开放问题（尽管作者提到该问题在随后的后续工作中 [47] 已得到解决）。本工作严格遵循无碰撞机制（$N \ll M$），并依赖于关于哈夫尼安近似平均情况硬度的标准复杂性理论假设。