A Quantum-Inspired Algorithm for Graph Isomorphism

大局观：图同构（Graph Isomorphism）谜题

想象你有两张看起来不同的城市地图。一张地图上的街道标记为“A, B, C”，另一张则标记为“X, Y, Z”。尽管名字不同，但这些地图可能实际上展示的是完全相同的城市布局。

在计算机科学中，这被称为图同构问题。“图”仅仅是一个由点（顶点）和连接这些点的线（边）组成的网络。问题在于：这两个网络是否本质上是同一种形状，只是标签不同而已？

虽然检查两个小型地图是否相同很容易，但要检查两个规模巨大、复杂的网络对常规计算机来说却极其困难。这就像是在一座如山般巨大的干草堆中寻找特定的图案。

背景：处于“噪声”时代的量子时代

我们目前正处于被称为 NISQ 时代（含噪声的中等规模量子时代）的时期。你可以把它看作是量子计算机的“原型阶段”。它们功能强大，但带有“噪声”（容易出错），且尚无法运行解决最难问题所需的那些庞大且完美的算法。

科学家们正在尝试寻找这些不完美机器的用途。其中一个想法是使用一种特定类型的量子机器，称为高斯玻色采样器（Gaussian Boson Sampler, GBS）。

类比： 想象一台巨大的、复杂的弹珠机（量子设备）。你从顶部射入小球（光子），它们在迷宫般的镜子（图）中弹跳，最后落在底部的不同洞口中。小球落下的位置模式会告诉你关于这个迷路形状的信息。

量子方法的缺陷

之前的研究曾建议使用这种弹珠机来解决图谜题。其思路是：

将图 A 编码进机器。
射入小球并记录落点模式。
对图 B 进行同样的操作。
对比这些模式。

症结所在： 为了 100% 确定两个图是否相同，你需要收集如此之多的球落点模式，以至于所需的时间会超过宇宙的年龄。这就像是通过等待每一滴水滴落下，来试图猜出云朵的确切形状；你永远也无法完成。

作者的解决方案：一位“量子启发式”侦探

本文的作者意识到，虽然我们无法等待所有的球落点模式，但我们可以使用常规计算机来计算小球“将会”落下的统计平均值。

他们创建了一种新的经典算法（适用于普通计算机的程序），它模仿了量子机器的逻辑，而无需实际使用该机器。

他们的算法是如何工作的（“指纹”类比）

想象你想知道两个人是否是双胞胎。

第一级（简单检查）： 你观察他们的身高和体重。如果一个 6 英尺，另一个 5 英尺，那他们就不是双胞胎。（在论文中，这对应于检查“一阶相关性”）。
第二级（更深层的检查）： 如果身高相同，你就观察他们的指纹。如果指纹模式不匹配，他们就不是双胞胎。（这是“二阶相关性”）。
第三级（深度挖掘）： 如果指纹匹配，你就观察他们的 DNA。

作者的算法对图也是如此：

它根据量子机器的行为方式，计算图的特定统计“指纹”。
它从简单的指纹开始。如果图不匹配，算法会停止并判定：“这些图肯定不同。”
如果匹配，它会转向更复杂、更详细的指纹。
它会不断深入细节，直到发现不匹配（证明它们不同）或者耗尽时间为止。

他们实际声称的内容

论文提出了几个具体的声明，我们可以将其简单总结如下：

我们找到了一个“必要条件”： 他们证明了如果两个图确实是相同的（同构的），它们的统计指纹必须匹配。如果指纹不匹配，那么这两个图肯定不同。
我们构建了一个经典侦探： 他们编写了一个在普通计算机上计算这些指纹的程序。它不需要量子机器。
它与量子设想一样好（但更快）： 他们的经典程序在识别差异方面与提出的量子方法一样出色，但它不会受到“噪声”的影响，也不需要等待数十亿次球的落下。
它不是万能灵药：
- 它并不比现有的最佳经典方法（如“Babai 算法”）更快。
- 它也不是一个完整的解决方案。对于非常棘手、具有对称性的图，该算法可能会陷入困境，并表示：“我无法判断它们是相同还是不同”，即使它已经检查到了非常深的层级。
- 然而，它是一种全新的、截然不同的方法。它观察图的方式与其他经典方法（如“颜色细化法/Color Refinement”，即通过给邻居涂上不同的颜色来观察模式是否匹配）不同。

核心结论

作者并没有发明一种比现有方法更快的解决图谜题的方法。相反，他们借鉴了一个来自嘈杂量子世界的酷炫想法，弄清楚了如何在普通计算机上进行这些数学运算，并创造了一个有助于排除“伪匹配”的新工具。

可以这样理解：量子机器是一台昂贵且华丽的相机，通过拍摄数百万张照片来证明两幅画作是完全一致的。而作者构建了一个智能 App，通过观察笔触和调色板来证明两幅画作是不同的，而且速度更快，无需使用相机。这是一个有用的工具，但它并不会取代那些顶尖的艺术史学家（Babai 算法）。

技术摘要：一种受量子启发解决图同构问题的算法

问题陈述
本文探讨了图同构（Graph Isomorphism, GI）问题：即判定两个离散图在顶点标签置换下是否具有结构上的同一性。虽然该问题尚未被证实为 NP 完全，但寻找一种多项式时间内的通用算法仍是理论计算机科学领域的一项重大挑战。目前最先进的经典方法是 Babai 的算法（2015年），其运行时间为拟多项式时间（ $2^{O(\log V)^3}$ ）。作者研究了噪声中规模量子（NISQ）时代，特别是高斯玻色采样（Gaussian Boson Sampling, GBS），是否能为更高效的解决方案提供路径。他们批判性地评估了 Brádler 等人 [13] 提出的一种量子算法，并基于其底层原理提出了一个经典替代方案。

方法论
作者开发了一种经典算法，利用 GBS 系统的统计特性来测试图同构，从而避免了对物理量子设备的依赖。

编码： 使用 Autonne-Takagi 分解（ $A = UDU^T$ ）将图的邻接矩阵 $A$ 编码进 GBS 系统。酉矩阵 $U$ 定义了干涉仪，而对角矩阵 $D$ （包含特征值）决定了输入挤压参数。这种编码确保了采样器的概率分布能够反映图的结构。
统计不变性： 为了避免直接收集物理样本（这在近似精确分布时效率极低），该算法计算采样器输出分布的模式相关性（cumulants/累积量）。
- GBS 中输出模式的概率由子矩阵的 Hafnian（哈夫尼安）控制，这是一个在经典计算上难以求解的函数。
- 然而，低阶累积量（相关性）是可以高效计算的。作者使用 Ursell 函数定义了 $k$ 阶相关性 $C^{(k)}$ ，用于描述 $k$ 个输出模式之间的相关性。
- 至关重要的是，作者并未假设均匀挤压；他们利用图的具体特征值来确定非均匀输入挤压，从而允许进行前置的同谱性（isospectrality）检查（这是同构的必要条件）。
算法流程：
- 分解： 将两个图的邻接矩阵分别分解为 $U$ 和 $D$ 。
- 迭代相关性计算： 算法计算逐级递增的阶数 $k$ （从 1 到顶点数 $M$ ）的相关值。
- 置换过滤： 对于每个阶数 $k$ ，算法比较两个图之间的相关值集合。算法维护一个候选置换矩阵 $\sigma$ （初始全为 1）。如果某个相关值存在于图 1 的顶点中但在图 2 中不存在，则在 $\sigma$ 中对应的映射关系会被消除（设为零）。
- 终止条件：
  - 如果 $\sigma$ 变得无效（出现空行或空列），则宣布两图不同构。
  - 如果 $\sigma$ 缩减为一个唯一的置换矩阵，则验证两图同构。
  - 如果 $\sigma$ 仍处于不确定状态（存在多种可能的映射），则进入下一个更高阶 $k+1$ 的计算。
- 截断： 如果计算成本变得过高，过程可能会在最大阶数 $k_{max}$ 处截断。

核心贡献

必要条件公式化： 作者提出了一个基于采样编码图的 $k$ 阶模式相关性等价性的图同构必要条件。他们证明了如果两个图同构，它们的关联集在所有 $k$ 阶下必须是置换等价的。
经典算法： 他们引入了一种经典算法来测试这一必要条件。该算法利用从图邻接矩阵导出的高效可计算统计特性（相关性）来区分非同构图。
复杂度分析： 本文证明，所提出的经典算法在计算复杂度和区分图的能力方面，与 Brádler 等人 [13] 的量子启发采样算法以及经典的颜色细化（Weisfeiler-Leman）算法 [23] 相当。
与现有方法的区别： 作者澄清，尽管其方法在复杂度特征上与颜色细化算法（具体为 Weisfeiler-Leman 测试）相似，但两者评估的信息不同（采样器模式相关性 vs. 邻域颜色计数）。他们指出，目前尚不清楚该方法是否会面临 Weisfeiler-Leman 测试在特定图族（如 Cai-Fürer-Immerman 图）中所遭遇的局限性。

结果与局限性

效率： 相关值的计算相对于顶点数 $M$ 是多项式级的，但随相关阶数 $k$ 的增加呈指数级增长。
区分能力： 该算法通过展示对必要条件的违反，成功识别出非同构图。然而，与颜色细化算法类似，它在处理高度对称的图（例如正则图）时表现挣扎，因为这些图的低阶相关性是相同的。
完备性： 作者指出，在最大阶数（ $k=M$ ）时，该方法可以恢复相关的概率分布，并且在理论上足以测试同构性。然而，由于计算成本变得极其昂贵，这在实践中并不高效。
与最先进技术的对比： 本文明确声称，其方法在类别上显著逊色于 Babai 的最先进拟多项式算法。它并未为一般的图同构问题提供多项式时间解法。

意义与主张
本文对 NISQ 时代量子优势的说法进行了批判性评估。其主要意义在于：

揭示量子主张的本质： 它表明 Brádler 等人算法所提出的“量子优势”可以通过计算相同的统计特性在经典层面实现，而无需物理量子设备。
界定极限： 它强化了目前的观点，即使用线性光学量子计算机目前无法为图同构问题提供通用的高效量子算法。
方法论区分： 它建立了一种基于 GBS 统计的新型、独特的非同构测试启发式方法，该方法在最大阶数下理论上能够恢复充分条件，这与标准的颜色细化不同。

作者总结道，虽然该方法是区分非同构图的一种有用启发式手段，但目前尚未展现出相对于现有最佳经典方法的实质性量子优势。