Simulating Gaussian boson sampling on graphs in polynomial time

技术摘要：在多项式时间内模拟图上的高斯玻色采样

问题陈述
本文探讨了与玻色采样（Boson Sampling, BS）和高斯玻色采样（Gaussian Boson Sampling, GBS）相关的分布采样的计算复杂度。虽然 Aaronson 和 Arkhipov [1] 提出了 BS 作为展示量子优势的模型，并假设了永久值反集中性和永久值猜想，认为从精确输出分布中进行经典采样在计算上是难以实现的（会导致多项式层级坍缩）。类似地，GBS 作为一种利用挤压态（squeezed states）以避免特定光子源成本的变体，已被提议用于解决困难的图问题，如计算完美匹配、寻找最密子图和图同构问题。

本文解决的核心开放性问题是：是否存在高效的经典算法来对图上的 GBS 分布进行采样，即分布 $\mu_{GBS,G}$，该分布正比于 $c^{2|S|} \text{PM}(S)^2$（其中 $\text{PM}(S)$ 是诱导子图 $G[S]$ 中的完美匹配数量）。前人的工作 [12] 仅为非常稠密的图提供了快速算法，而 Oh 等人 [13] 则针对一个略有不同的分布（正比于 $\text{PM}(S)$ 而非 $\text{PM}(S)^2$）提出了经典算法，这使得非负 GBS 情况下的研究仍处于开放状态。

方法论
作者采用了一种归约策略，将目标采样分布映射到图的加权完美匹配问题上。他们利用了 Jerrum 和 Sinclair [14] 以及 Jerrum, Sinclair 和 Vigoda [17] 开发的马尔可夫链蒙特卡洛（MCMC）算法，这些算法允许在特定条件下对完美匹配进行高效的近似采样。

1. 对于非负玻色采样（定理 1.3）：
   作者从给定的非负实矩阵 $A$ 构建了一个二分图 $G$。该构建过程涉及创建顶点集 $L_1, L_2$ 和 $R_1, R_2$，并使用 $A$ 的条目作为边权重。通过在该构建图中对具有特定边权重的完美匹配进行采样，可以近似得到玻色采样分布 $\mu_{BS}$ 在匹配顶点在 $R_1$ 中的边缘分布。近似误差由参数 $k$（顶点的副本数）控制，该参数被选为足够大（$O(n^2/\varepsilon)$）。

2. 对于图上的高斯玻色采样（定理 1.1）：
   作者定义了 GBS 分布 $\mu_{GBS,G}(S) \propto c^{2|S|} \text{PM}(S)^2$。为了进行采样，他们构造了输入图 $G$ 与一条边 $K_2$ 的笛卡尔积，记作 $G \square K_2$。

   • 构建： $G \square K_2$ 由两个 $G$ 的副本（$G$ 和 $G'$）以及连接对应顶点的边组成。
   • 加权： $G$ 和 $G'$ 内部的边（集合 $E$ 和 $E'$）被分配权重 $c^2$，而连接两个副本的边（集合 $E_0$）被分配权重 $1$。
   • 归约： $G \square K_2$ 中的一个完美匹配会诱导出一个子集 $S \subseteq V$（在原图副本内匹配的顶点）。诱导特定集合 $S$ 的概率被证明正比于 $c^{2|S|} \text{Haf}(A_S)^2$，对于诱导子图而言，这等于 $c^{2|S|} \text{PM}(S)^2$。
   • 效率条件： Jerrum-Sinclair 算法要求近乎完美匹配（near-perfect matchings）与完美匹配的比率被限制在多项式范围内。为了确保这一点，作者定义了一个新的权重函数 $\lambda'$（由 $4n^2$ 缩放），并证明了在此新权重下，近乎完美匹配的总权重（$Z'_{n-1}$）与完美匹配的总权重（$Z'_n$）之比被限制为一个常数（具体为 $Z'_{n-1} \le Z'_n/2$）。这是通过 Lemma 4.2 得出的，该引理确立了在原始权重下 $Z_{n-1} < 2n^2 Z_n$，并结合了匹配多项式的对数凹性（Heilmann 和 Lieb [20]）以及 AM-GM 不等式。这确保了马尔可夫链可以在多项式时间内混合。

主要贡献与结果
论文提出了两个建立多项式时间经典算法的主定理：

• 定理 1.1 (图上的 GBS)： 存在一个算法，给定图 $G$ 和实参数 $c > 0$，能在全变差距离（total variation distance）下采样出一个与 $\mu_{GBS,G}$ $\varepsilon$-接近的分布。其运行时间为 $O(\bar{c}mn^4 \log^2(nc/\varepsilon))$，其中 $m=|E|$，$n=|V|$，且 $\bar{c} = \max\{1, c\}$。该结果适用于所有图，而不仅仅是稠密图，且适用于任何正实数 $c$。
• 定理 1.3 (非负玻色采样)： 存在一个算法，给定非负实矩阵 $A$（$A$ 不一定是非截断幺正矩阵），能在 $O(m^7 n^{14} \varepsilon^{-7} \log^4(mn/\varepsilon))$ 时间内采样出一个与玻色采样分布 $\mu_{BS}$ $\varepsilon$-接近的分布。

意义与主张
作者声称，他们的结果证明了量子算法在基于分布 $\mu_{GBS,G}$ 采样的应用中无法提供指数级的加速。由于许多提议的 GBS 应用（例如图同构、计数完美匹配）都依赖于从该特定分布中进行采样，因此存在多项式时间经典采样器的存在意味着这些特定任务在标准 GBS 模型下不具备量子优势。

论文指出，虽然 Jerrum-Sinclair-Vigoda 算法并不直接适用于一般的玻色采样（其中输入矩阵是具有复数条目的截断幺正矩阵），但作者的构建将采样问题归约为近似复权重矩阵的永久值。由于近似永久值通常是 NP-难的，因此一般玻色采样的经典模拟仍然是困难的。然而，对于特定的非负矩阵和基于图的 GBS 分布，作者已经证明了高效的经典模拟是可能的。

这项工作通过其适用于所有图（而非仅限稠密图）以及利用基于笛卡尔积构建的更简单、更快的算法，使自己脱颖而出。