Nat. Commun. | 无权图上高斯玻色采样分布的有效经典采样算法

关键词：MCMC 方法，高斯玻色采样

导读

本文是发表在 Nature Communications 上的论文 Efficient Classcial Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs^[1]的详细解读。该项研究由北京大学李彤阳课题组独立完成，北京大学博士生张业鑫、周烁、王昕兆为共同第一作者，王紫若、杨子熠、杨睿、薛烨诚均对该工作有所贡献。

论文提出了基于马尔可夫链蒙特卡洛（MCMC）的双循环 Glauber 动力学（double-loop Glauber dynamics）经典采样算法。论文论证了该算法在无权图上的的平稳分布（stationary distribution）能够匹配高斯玻色采样（GBS）的分布，并在稠密图情形下利用改进的正则路径（canonical path）方法严格证明了该算法能够在多项式时间内混合收敛。此外，论文还开展了数值实验佐证理论，数值实验显示算法在 256 节点规模上显著提升了若干图问题的求解质量（最高可达 10 倍改善）。

↑扫码跳转论文

论文链接：

https://www.nature.com/articles/s41467-025-64442-7

背景与动机

在矩阵中有一个重要的数学量 hafnian（Haf）与图的完美匹配密切相关：对一个实对称矩阵 $A\in \mathbb{R}^{2n\times 2n}$ ，其 hafnian 定义为 $\mathrm{Haf}(A)=\sum_{\rho \in P_{2 n}^{2}} \prod_{\{i, j\} \in \rho} A_{i, j},$ 其中 $P_{2 n}^{2}$ 是所有将 $\{1,…,2n\}$ 分为 $n$ 个二元子集的划分。当 $A$ 是一个无权简单无向图（顶点数为偶数）的邻接矩阵时， $\mathrm{Haf}(A)$ 恰好等于该图的完美匹配个数；若顶点数为奇数则 $\mathrm{Haf}(A)=0$ 。

这一定义与高斯玻色采样紧密联系。高斯玻色采样是验证量子计算优越性的重要途径之一，当把图的邻接矩阵嵌入到高斯量子态后，某一模式子集对应子矩阵的出现概率与 $\mathrm{Haf}(\cdot)^{2}$ 成正比，因此围绕 Hafnian 的图优化任务（如最密 $k$ -子图^[2]、max-Hafnian^[3]）天然可由高斯玻色采样的方法来刻画与求解。

但现有的对 GBS 的经典模拟法要么空间/时间开销巨大，要么缺少普适的性能保证。论文聚焦无权图这一在应用与理论上都重要的场景，追问：能否构建在一般图上同样可证有效、开销可与量子方案比肩的经典采样算法？

理论贡献

1. 方法亮点：从单循环到双循环

高斯玻色采样在图论应用中的核心结果是：将无权图的邻接矩阵编码到高斯量子态后，某一顶点子集 $S$ （对应子矩阵）的观测概率，与该子矩阵 hafnian（简记为 $\mathrm{Haf}(S)$ ）的平方成正比。具体地说，对于一个给定常数 $c$ ，我们希望采样概率满足 $\Pr[S] \propto c^{|S|}·\mathrm{Haf}(S)^2$ （二次方）。

为了实现这一目标，论文以 Glauber 动力学为起点设计了新的算法。

传统单循环版本的 Glauber 动力学作为一种特殊的 MCMC（Markov Chain Monte Carlo）策略，通过在匹配（matching）空间上迭代加边/删边更新状态，可以实现采样的匹配 $E$ 的分布权重正比于 $c^{2|E|}$ 。若考虑该匹配的所有顶点组成的子集 $S$ ，那么采样的平稳分布满足 $\Pr[S] \propto c^{|S|}·\mathrm{Haf}(S)$ （一次方）。为了得到与 $\mathrm{Haf}(S)^2$ 成正比的平稳概率，一个简单的思路是拒绝采样（rejection sampling）：独立运行两个马尔可夫链，当且仅当采样出相同的；两个匹配时接受。然而，对于一般图而言，由于可能的顶点子集数量呈指数级增长，若无顶点子集能主导权重分布，每次拒绝采样尝试的接受概率可能趋近于指数小。为避免这种情况，论文提出了“双循环”关键创新，尝试直接通过调整转移概率来实现期望的分布。具体而言，对于马尔可夫链中两个相邻的状态 $E$ 和 $E'$ ，假设 $E’=E\cup\{e\}$ ，那么我们希望转移概率满足 $\frac{\Pr[E’\to E]}{\Pr[E\to E’]} = c^2 \cdot \frac{\mathrm{Haf}(E)}{\mathrm{Haf}(E’)}$ 其中 $\mathrm{Haf}(E)$ 表示 $E$ 的所有顶点导出子图的 Hafnian。问题的关键在于考虑删除边 $e$ 时，我们需要在原本的 Glauber 动力学中加入一个概率 $\frac{\mathrm{Haf}(E)}{\mathrm{Haf}(E’)}$ 。论文巧妙地利用了以下性质：

一个邻接矩阵的子矩阵的 Hafnian，恰好对应于二部图中这些点的导出子图的完美匹配个数。

当马尔可夫链中采样的边 $e$ 恰好在当前匹配 $E'$ 中，决定是否删除该边时，论文引入一个内层马尔可夫链，在 $E'$ 的所有顶点的导出子图上近似均匀地采样一个完美匹配：若该边 $e$ 在新采到的完美匹配中出现，则继续按 Glauber 动力学设定规则删边；若未出现，则该步骤不转移状态。

这一“以完美匹配作二次抽样”的结构，使得每一步对删边的判断都隐含了“再乘一次匹配数量”的权重，由此，平稳分布权重变为与 $c^{2|S|}·\text{Haf}(S)^2$ （二次方）成正比，与高斯玻色采样得到的分布结果完全对齐。这一通过双循环实现平方化的权重结构是对齐高斯玻色采样的理论枢纽。

不难注意到这样的双循环 MCMC 采样方法也可以很自然地推广到带权图中。

2. 内层链的实现：完美匹配的近似均匀采样

双循环机制要求内层链在当前子图上均匀采样完美匹配。论文调研并纳入了二部/非二部两类图上近似均匀采样完美匹配的高效算法：

二部图：存在时间复杂度 $O\left(n^{11}(\log n)^{2}\left(\log n+\log \eta^{-1}\right)\right)$ 的算法，可在失败概率 $\eta$ 下近似均匀地采样完美匹配^[4]。
非二部稠密图：当最小度 $\delta (V)\ge n$ 时，存在 $\tilde{O}\left(n^{14}\left(\ln\eta^{-1}\right)^{2}\right)$ 的近似均匀采样算法^[5]。

论文在之后分析混合时间的过程中，进行了严谨的误差分析，分析了内层链的近似误差对总变差距离的影响。

3. 分析混合时间（mixing time)：将正则路径方法应用于稠密图上

为证明双循环链在稠密图上多项式时间混合，论文采用并改造了经典的正则路径方法导电度（conductance）分析框架。核心做法有两点：

(a) 完全图/完全二部图的对称性算路

若图具有足够对称性（如完全图、完全二部图），可以直接逐条转移计算导电度，避免繁琐的一一映射；
构造“只在匹配大小从 $k$ 向更小/更大变动时经过某转移”的特殊路径族，使同类转移的导电度可成批求和；
进一步设计具有对称性的多路径族（允许每对起止状态存在多条正则路径），从而把流量在对称转移间均匀摊开，便于对单条转移的最大导电度做精确上界。

(b) 从完全图到一般稠密图的延拓

对于足够稠密的图，只要每个子图的 hafnian 与完全图对应子图的 hafnian 之比至多多项式因子，即可继承完全图情形的导电度上界，从而得到多项式混合时间。这一推广以严格定理形式给出，并将二部图与非二部图分开表述与证明（详见论文）。

数值实验

为验证算法的实际效果，论文开展了大规模数值实验，在 256 顶点的图上求解最大 Hafnian 和最密 $k$ -子图问题，其规模超越了此前的 GBS 实验^[6]及相关经典模拟研究^[7]。实验结果充分验证了理论的有效性，并展现了算法的实际优势。

1. 算法有效性验证：显著增强经典算法性能

为验证 Glauber 动力学算法的有效性，我们首先在两类具有明确最优解的 256 顶点图上进行了实验。实验通过采样随机搜索（Random Search）和模拟退火（Simulated Annealing）这两种经典算法作为基准，将其中的均匀随机更新步骤分别替换为本文所提出的双循环 Glauber 动力学算法，以进行性能比较。实验数据显示，Glauber 动力学算法的增强策略效果显著：在求解最大 Hafnian 问题时，经 Glauber 动力学增强的随机搜索算法，所找到的解的 Hafnian 值比原始算法平均高出 240-300%，增强后的模拟退火算法也比原始算法平均提高 20-50%；在求解最密 $k$ -子图问题时，增强后的随机搜索算法和模拟退火算法所找到子图的密度分别平均高出 30-35% 和 10-15%。这些结果有力地证明，将 Glauber 动力学算法作为采样策略嵌入现有经典算法框架，能够显著提升其在最大 Hafnian 和最密 $k$ -子图这两类图优化问题上的求解质量。

2. 得分优势分析：在前沿问题中提供强大经典基准

近年来，利用光量子计算系统的高斯玻色采样计算已在图论问题求解中展现出潜力。例如，九章团队的研究[6]利用“九章”光量子计算机，在 144 顶点带随机复数权重的完全图上展示了其在两类图优化问题上的强大求解能力。为将本文提出的经典算法置于同一评估体系，我们在更具一般性的 256 顶点 Erdös-Rényi 随机图上进行了比较分析。采用该研究中定义的“得分优势”，即在有限迭代次数下增强算法与原始随机搜索所获最优解的比值，作为核心评价指标。实验结果显示，本文提出的经典算法在最大 Hafnian 问题上取得了最高 4 倍的得分优势，在最密 $k$ -子图问题上也与该研究的实验表现相当。这一成果表明，本文提出的高效经典采样算法，能够为评估高斯玻色采样这一量子算法在相关问题上的计算优势提供一个强有力的经典基准。

3. 双循环算法验证：在二部图上实现数量级提升

本文从理论上严格证明了双循环 Glauber 动力学算法在稠密二部图上具有多项式混合时间的快速收敛性。为在实践中验证该理论，研究团队在 256 顶点的随机二部图上进行了综合性能测试。实验结果有力支持了理论分析：在求解最大 Hafnian 问题时，搭载了双循环 Glauber 动力学的算法所求解的质量，最高可达原始经典算法的 10 倍。该结果不仅体现了双循环算法在处理特定结构图问题时的卓越性能，也再次确认了本文理论分析与算法设计的正确性和有效性。

我们的代码开源在：

https://github.com/Qubit-Fernand/GBS-MCMC.

参考文献

[1] Y.-X. Zhang, S. Zhou, X.-Z. Wang, Z.-R. Wang, Z.-Y. Yang, R. Yang, Y.-C. Xue, T.-Y. Li. "Efficient Classcial Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs". Nature Communications (2025). arXiv:2505.02445.

[2] J. M. Arrazola and T. R. Bromley, Using Gaussian boson sampling to find dense subgraphs, Physical Review Letters 121, 030503 (2018).

[3] J. M. Arrazola and T. R. Bromley, Using Gaussian boson sampling to find dense subgraphs, Physical Review Letters 121, 030503 (2018).

[4] M. Jerrum, A. Sinclair, and E. Vigoda, A polynomialtime approximation algorithm for the permanent of a matrix with nonnegative entries, Journal of the ACM(JACM) 51, 671 (2004).

[5] M. Jerrum and A. Sinclair, Approximating the permanent, SIAM journal on computing 18, 1149 (1989).

[6] Y.-H. Deng, S.-Q. Gong, Y.-C. Gu, Z.-J. Zhang, H.-L. Liu, H. Su, H.-Y. Tang, J.-M. Xu, M.-H. Jia, M.-C. Chen, H.-S. Zhong, H. Wang, J. Yan, Y. Hu, J. Huang, W.-J. Zhang, H. Li, X. Jiang, L. You, Z. Wang, L. Li, N.-L. Liu, C.-Y. Lu, and J.-W. Pan, Solving graph problems using Gaussian boson sampling, Physical Review Letters 130, 190601 (2023).

[7] C. Oh, M. Liu, Y. Alexeev, B. Fefferman, and L. Jiang, Classical algorithm for simulating experimental Gaussian boson sampling, Nature Physics 20, 1461 (2024).

图文 | 杨子熠、薛烨诚、杨睿、王紫若

PKU QUARK Lab

关于量子算法实验室

量子算法实验室 QUARK Lab (Laboratory for Quantum Algorithms: Theory and Practice) 由李彤阳博士于2021年创立。该实验室专注于研究量子计算机上的算法，主要探讨机器学习、优化、统计学、数论、图论等方向的量子算法及其相对于经典计算的量子加速；也包括近期 NISQ (Noisy, Intermediate-Scale Quantum Computers) 量子计算机上的量子算法。

实验室新闻：#PKU QUARK

实验室公众号：

课题组近期动态

CMP | 随机分层图上的指数级量子游走加速

Physical Review Research | 低围长图上的最大割量子近似优化算法

ICLR 2025 | 量子算法求解非凸优化问题的鲁棒性

CMP | 基于朗之万动力学的量子优化算法

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点击“阅读原文”转论文链接

内容中包含的图片若涉及版权问题，请及时与我们联系删除

Nat. Commun. | 无权图上高斯玻色采样分布的有效经典采样算法

评论列表

评论