⚛️ quantum physics

Bipartite Gaussian Boson Sampling for Hamiltonian Cycles in Directed Graphs

本文提出了一种二分高斯玻色采样框架，该框架利用永久偏置光子采样来增强用于解决有向哈密顿回路问题的遗传算法，并证明了与标准经典方法相比，该框架在随机有向图上具有更高的成功率和路径质量。

原作者： Miaomiao Yu, Jingyi Lv, Yan Wang, Kun Wang, Ping Xu

发布于 2026-06-30

📖 1 分钟阅读🧠 深度阅读

原作者： Miaomiao Yu, Jingyi Lv, Yan Wang, Kun Wang, Ping Xu

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

大局观：在单行道城市中寻找路线

想象你是一名在巨大且混乱的城市中工作的快递司机，这里的每一条街道都是单行道。你的目标是找到一条路径，能够恰好访问每一栋建筑一次，并最后回到起点。在数学术语中，这被称为**有向哈密顿回路（Directed Hamiltonian Cycle）**问题。

这是一个极其困难的谜题。如果你尝试随机猜测路径，你可能会在原地兜圈子，转了一辈子也找不到那条完美的环路。

这篇论文的作者提出了一个问题：一种特殊的量子计算机能否帮助我们更好地“猜”出这些路线？

工具：针对单行道的“量子骰子”

以往利用量子计算机解决图论问题的尝试，大多依赖于一种叫做高斯玻色采样（Gaussian Boson Sampling, GBS）的工具。你可以把标准 GBS 想象成一个神奇的骰子投掷器，它非常擅长发现双向街道（即如果可以从 A 到 B，也可以从 B 到 A）中的模式。

然而，现实世界中的问题（如交通流、社交媒体影响力或生物信号）通常是单向的。标准 GBS 的“神奇骰子”在这里并不好用，因为它预设了一种在现实中并不存在的对称性。

作者使用了另一种工具，叫做二分高斯玻色采样（Bipartite Gaussian Boson Sampling, BipartiteGBS）。

类比： 如果说标准 GBS 是一个只能掷出偶数的骰子，那么 BipartiteGBS 就是一个可以掷出任何数字的骰子。它是专门为处理单行道这种混乱、不对称的特性而设计的。
工作原理： 它通过一个由镜子组成的复杂迷宫发射光子（光粒子）。这些粒子落下的方式，在数学上与城市地图的“永恒式（permanents）”紧密相关。简单来说，这台量子机器会自然而然地“偏好”落在那些看起来连接性较强的路径上，即使这些路径目前还不完美。

策略：量子教练与人类跑者

这篇论文并不声称量子计算机可以独自解决这个谜题。相反，它扮演的是一个聪明教练的角色，为一名人类跑者（一种名为遗传算法的经典计算机算法）提供指导。

以下是他们如何协作的：

教练（量子机器）： BipartiteGBS 机器快速观察城市地图，并生成一系列“有潜力的”起始点。它会说：“嘿，这些特定的建筑似乎聚集在一起，那里可能存在一条很好的路径。”
跑者（遗传算法）： 经典计算机接收这些建议并开始奔跑。它尝试构建完整的路径，测试不同的组合，交换路径的部分片段，并保留表现最好的部分。
结果： 由于跑者不是从随机猜测开始，而是从教练提供的“智能建议”开始，它找到完美环路的速度更快，成功率也更高。

令人惊讶的发现：少即是多

研究人员测试了将“量子教练”与“人类跑者”结合的不同方式。他们发现了一个违反直觉的结果：

“全权控制”法： 他们尝试让量子教练指挥跑者做所有的事情——包括从哪里开始、如何判断路径优劣以及如何修复错误。这反而让跑者变得更慢、效率更低。这就像是一个事无巨细、过度管理的教练，反而让跑者感到困惑。
“智能开局”法： 最成功的方法仅仅是让量子教练挑选初始阵容（初始猜测），然后让人类跑者按照自己的标准规则完成剩下的工作。

核心启示： 量子计算机最适合作为开局的引导者，而不是全程的掌控者。它提供了一个“领先优势”，帮助经典计算机更快地找到答案。

实际的研究成果

团队在包含 15 到 40 栋建筑的随机城市地图上进行了测试。

成功率： 使用“量子教练”辅助的方法比不使用辅助的方法能更频繁地找到完美路径。
失败时的情况： 即使无法找到完美的环路，使用“量子辅助”的方法找到的有效路径长度（即在卡住之前能走多远）也比标准方法更长。
结论： 这证明了量子采样可以为困难的单向谜题提供有用的“提示”，但它是一种**启发式（heuristic）**工具（即聪明的猜测），而不是一个能瞬间解决问题的魔杖。

总结

这篇论文介绍了一种利用特定基于光的量子计算机来帮助解决单向网络中复杂路由问题的新方法。通过利用量子机器生成智能的初始猜测，来辅助经典计算机，我们可以更高效地解决这些难题。关键的教训是：量子工具在“搭建舞台”方面效果最好，而不是试图“导演整场戏”。

问题陈述

本文研究了解决有向哈密顿回路问题（Directed Hamiltonian Cycle Problem）的挑战。这是一个经典的 NP 完全问题，目标是确定一个有向图中是否存在一条访问每个顶点且仅访问一次的回路。虽然标准的高斯玻色采样（Gaussian Boson Sampling, GBS）通过利用编码对称矩阵的 Hafnian 函数，已成功应用于无向图问题，但它并不适用于有向图。有向图具有本质的非对称结构（非对称邻接矩阵），而标准 GBS 无法在不通过对称嵌入掩盖其原生结构的情况下自然地对其进行编码。此外，现有的针对有向图的启发式方法往往难以应对搜索空间的指数级缩放问题。

方法论

作者提出了一种利用**二分高斯玻色采样（Bipartite Gaussian Boson Sampling, BipartiteGBS）**为经典遗传算法（GA）生成启发式信息的框架。

理论基础 (BipartiteGBS)：
- 与使用单模压缩态并产生概率与对称矩阵的 Hafnian 平方成正比的标准 GBS 不同，BipartiteGBS 利用双模压缩态和两个干涉仪。
- 这种架构使得输出概率与任意（非对称）复矩阵的子矩阵的**平方永久值（Squared Permanents）**成正比。这使得 BipartiteGBS 成为编码有向图邻接矩阵的天然候选方案。
- 作者定义了 Max-Perm 问题：寻找使平方永久值最大化的 $k \times k$ 子矩阵。他们推导出了采样增强因子（ $R_{Per}$ ）的闭式表达式，证明了与均匀经典采样相比，BipartiteGBS 对具有大永久值的子矩阵提供了显著的偏置。
启发式映射：
- 论文建立了有向图邻接矩阵的永久值与其边密度之间的联系。虽然大永久值并不能保证存在哈密顿回路，但它暗示了存在稠密局部子结构（回路覆盖）的可能性，这些结构可能包含回路中的边。
- 作者将 BipartiteGBS 样本视为“具有信息量”的局部证据。具体而言，他们提取：
  - 顶点子集： 在无碰撞、平衡的样本中频繁共同出现的顶点集合 ( $S \cup T$ )。
  - 边共现频率： 有向边的端点在这些被采样的顶点池中共同出现的经验频率。
算法集成 (BipartiteGBS-GA)：
- 通过使用来自 BipartiteGBS 的数据来增强遗传算法 (GA)。
- 引导初始化： 初始种群不是由纯随机排列组成，而是利用从 BipartiteGBS 采样的子图和高频边构建的排列进行种子填充。
- 增强适应度： 适应度函数结合了标准度量（路径中有效边的比例）与基于 BipartiteGBS 派生的边共现频率的加权项。
- 引导变异： 变异算子偶尔会针对低频边进行修复，并受量子采样数据的引导。
- 多阶段变体 (MS-BipartiteGBS-GA)： 提出了一个两阶段方法，首先运行快速的经典 GA 以找到一条较好的路径；随后强化该路径的边，并运行 BipartiteGBS 引导的 GA 进行精细化搜索。

核心贡献

BipartiteGBS 的新颖应用： 本文首次提出了专门用于有向图问题的 BipartiteGBS 算法，超越了标准 GBS 的对称性限制。
Max-Perm 问题公式化： 引入了 Max-Perm 问题作为 BipartiteGBS 的典型优化任务，并推导出了相对于均匀经典采样的理论采样增强因子。
混合量子-经典框架： 展示了一个实用的流水线，其中量子采样提供结构先验（子图和边频率）以引导经典随机优化器。
消融分析： 通过严格的分量级测试，论文指出 BipartiteGBS 引导的初始化是性能提升的主要贡献者，而持续对适应度和变异算子进行偏置则产生的收益递减或中性。

结果

数值模拟在规模从 $n=15$ 到 $n=40$ 、边概率 $p=0.3$ 的 Erdős–Rényi 随机有向图上进行。

成功率： 与标准 GA 和基于度中心性的 GA (Degree-GA) 相比，BipartiteGBS 增强型算法（BipartiteGBS-GA 和 MS-BipartiteGBS-GA）始终实现了更高的哈密顿回路寻找成功率。例如，在 $n=40$ 时，MS-BipartiteGBS-GA 实现了约 71.3% 的成功率，而标准 GA 约为 60.0%。
路径长度： 在未能找到完整哈密顿回路的情况下，BipartiteGBS 增强型方法生成的有效路径明显更长，表明其具有提取和利用局部结构信息的高超能力。
消融发现： “InitOnly”变体（仅将 BipartiteGBS 数据用于初始化）的表现通常优于完整的 BipartiteGBS-GA（后者同时也修改了适应度和变异），这表明量子采样作为提议机制（用于初始种群）最为有效，而标准的进化算子更适合后续的精细化过程。
基准对比： 使用简单顶点度统计信息的 Degree-GA 表现逊于标准 GA，这证实了改进源于 BipartiteGBS 提供的结构信息（子图和共现性），而非仅仅是简单的顶点中心性。

意义与主张

论文声称基于永久值的光子采样可以为非对称组合搜索问题提供有用的算法引导。

启发式性质： 作者明确指出，其结果代表一种启发式增强，并不构成解决哈密顿回路问题具有复杂性理论意义上的量子优势的声明。该方法是通过提供更好的起点和结构先验来提高经典搜索的效率。
可扩展性： 该方法旨在具备可扩展性，因为量子采样步骤是针对每个图实例的一次性预处理成本，而繁重的计算工作由经典 GA 完成。
未来方向： 作者建议该框架可以自然地扩展到其他有向图问题，如旅行商问题 (TSP)，并指出在光子芯片上进行实验实现是评估现实世界噪声和损耗影响的必要下一步。