Sample efficient graph classification using binary Gaussian boson sampling

想象你有一个装满不同乐高结构的大箱子。有些像城堡，有些像宇宙飞船，还有些像抽象雕塑。你的目标是用计算机将它们分类为“城堡”和“宇宙飞船”。这是一个经典的机器学习问题，称为图分类，其中“乐高”是数据点（节点），它们之间的连接是边。

问题在于，计算机非常不擅长观察整个乐高结构并说出“那是一个城堡”。它们更喜欢数字列表。因此，科学家必须将这些复杂的形状翻译成计算机能理解的数字列表（“特征向量”）。

本文介绍了一种新的、更简单的方法来实现这种翻译，它使用一种特殊的量子计算机实验，称为高斯玻色取样（GBS）。

以下是他们想法的分解，使用简单的类比：

1. 旧方法：高分辨率相机

以前，为了将量子计算机用于此任务，研究人员使用了一种需要光子数分辨（PNR）探测器的装置。

类比：想象试图在暴风雨中精确计算有多少雨滴击中了特定的窗玻璃。你需要一台超级敏感的高科技相机，能够数出 1 滴、2 滴、100 滴等。
问题：这些“相机”极其昂贵，难以制造，并且需要保持在比外太空还冷的温度（低温）下才能工作。它们也非常复杂。

2. 新方法：“开/关”开关

作者提出了一种称为二值 GBS的变体。他们不再精确计算有多少雨滴击中，而是只问：“这个位置有雨滴击中吗？”

类比：你用简单的电灯开关替换了高科技相机。如果有雨滴击中，开关就会跳到“开”（1）。如果没有东西击中，它就保持“关”（0）。你不知道是击中了 1 滴还是 100 滴；你只知道开关是开着的。
优势：这些“开关”（二值探测器）要便宜得多，更容易制造，甚至可以在室温下工作。与超级计算机相比，它们就像简单的门铃。

3. 工作原理：图的“阴影”

本文解释了如何将乐高结构（图）转化为明暗斑点图案（二值探测器结果）。

设置：你编程量子机器，使乐高结构的“形状”决定光线如何在镜子迷宫（干涉仪）中传播。
结果：当你运行实验时，光线会以特定的模式击中“开关”。
神奇数学：作者表明，获得特定“开/关”模式的概率与一种称为**托伦特尼安（Torontonian）的复杂计算在数学上是关联的。这是另一个数学函数哈夫尼安（Hafnian）**的表亲，后者已知极难被普通计算机计算，但很容易被这台量子机器“取样”（生成）。

本质上，量子机器将复杂的形状送入量子迷宫，然后吐出一个“闪烁”模式，作为该形状的独特指纹。

4. 理解数据：“桶”策略

如果你只是查看每一个可能的“闪烁”模式，它们的数量太多，无法计数（可能性数量呈爆炸式增长）。为了解决这个问题，作者使用了一种称为粗粒度化（或“分桶”）的策略。

类比：与其试图数清海滩上的每一粒沙子，你只需数有多少桶沙子。
策略 A（“点击”计数）：你将所有具有相同数量“开”开关的模式归为一组。（例如：“有多少模式恰好有 3 盏灯亮着？”）。
策略 B（“前 5 个”模式）：你只查看前 5 个开关，并根据这 5 个特定开关的样子对模式进行分组，忽略其余部分。

这将数据减少到标准计算机可以快速学习的 manageable 大小。

5. 结果：它有效吗？

作者将他们的“二值开关”方法与以下方法进行了测试：

旧量子方法：（那些昂贵、低温的方法）。
经典方法：（标准计算机算法，如“随机游走”或“最短路径”分析）。

发现：

性能：他们简单的室温方法与昂贵的量子方法以及最佳经典计算机方法表现一样好，有时甚至更好。
效率：获取做出决策所需的数据要快得多（取样效率高）。
特定胜利：在一个名为"ENZYMES"（用于分类生物分子）的数据集上，他们的方法明显胜出，击败了其他所有方法。

底线

该论文声称，你不需要价值数十亿美元、极寒的量子计算机来进行有用的图分类。通过将探测器简化为简单的“开/关”开关，并使用智能数学对结果进行分组，你可以利用更接近当今实用和负担得起的技术获得出色的结果。

该论文未声称的内容：

它不声称这将直接治愈疾病或诊断患者（尽管数据来自生物分子，但论文严格关注分类算法）。
它不声称这解决了所有图问题，仅表明它是分类任务的高效工具。
它不承诺这将取代所有经典计算机，而是表明它是特定任务的具有竞争力的、取样效率高的替代方案。

技术摘要：基于二元高斯玻色采样的样本高效图分类

问题陈述
图分类是机器学习中的一项关键任务，在生物信息学、网络科学和计算机视觉中具有广泛应用。然而，为标准机器学习分类器表示图结构数据颇具挑战性，因为图通常表示为邻接矩阵，而分类器需要向量输入。这要求定义一个特征映射 $\phi$ ，将图投影到希尔伯特空间中，通常利用核方法来衡量相似性。

最近的提议建议使用高斯玻色采样（GBS）构建图核。虽然 GBS 通过采样由矩阵 Hafnian（一个 #P 完全问题）支配的概率分布，提供了潜在的“量子优势”，但现有的基于 GBS 的图分类算法面临重大障碍。具体而言，它们依赖于光子数分辨（PNR）探测器。近似 PNR 探测事件概率分布所需的样本复杂度随模式数量呈超指数级增长，使得该方法对于较大规模的图变得不可行。此外，PNR 探测器在技术上非常复杂，通常需要在低温环境下运行。

方法论
作者提出了一种 GBS 图核算法的变体，该变体利用二元探测器（单光子敏感但不分辨光子数）替代 PNR 探测器。在此设置中，探测事件被记录为二元字符串 $n_{bin} = (n_1, ..., n_M)$ ，其中 $n_i \in \{0, 1\}$ ，表示模式 $i$ 中是否探测到至少一个光子。

理论基础：二元探测事件的概率由Torontonian矩阵函数刻画，该函数在经典计算中同样不可行。作者建立了二元 GBS 与图论之间的联系，表明二元事件的概率与输入图中所有对应特定探测模式的子图的 Hafnian 平方和成正比。
特征提取策略：为了解决原始探测概率中固有的样本复杂度问题，作者引入了两种粗粒化策略来构建特征向量：
- $\mu$ -粗粒化：根据探测器“点击”（即 1）的总数对探测事件进行分组。这产生了一个大小为 $N+1$ 的特征向量（其中 $N$ 是最大点击数），其规模随模式数量线性增长。
- $\nu$ -粗粒化：根据前 $k$ 个模式（例如前 5 个模式）的探测事件模式进行分组。这产生了一个大小为常数（ $2^k$ ）的特征向量，独立于图的总大小。
算法实现：图通过其邻接矩阵利用 Takagi 分解确定压缩参数和干涉仪设置，被编码到 GBS 设备中。生成样本，将其粗粒化为特征向量，并输入到带有 RBF 核的支持向量机（SVM）中进行分类。

主要贡献

技术简化：该算法用二元探测器（如 SPADs）替代了 PNR 探测器，后者在技术上更简单，且可在接近室温的环境下运行，显著降低了实现复杂度和成本。
样本效率：通过采用粗粒化策略（ $\mu$ 和 $\nu$ ），作者证明样本复杂度从 PNR 情况下的超指数级降低为关于模式数量的线性（ $O(M)$ ）或常数（ $O(1)$ ），使得该算法能够处理更大规模的问题。
理论联系：本文阐明了二元 GBS 与 Torontonian 函数之间的关系，将经典不可行性的论证扩展到了该探测器体制。

结果
作者在十个标准图数据集（如 AIDS、MUTAG、ENZYMES）上评估了其二元 GBS 核，并将其与四种经典图核（子图匹配、图元采样、随机游走、最短路径）以及原始的基于 PNR 的 GBS 核进行了比较。

性能：在大多数数据集上，二元 GBS 核取得了与经典核相当或更优的准确率。值得注意的是，在ENZYMES数据集上， $\nu$ -粗粒化的二元 GBS 核达到了**48.10%**的准确率，显著优于随机游走（19.50%）、最短路径（22.15%）和子图匹配（37.38%）核。它也优于基于 PNR 的核（后者需要位移才能在数据集上达到约 40% 的准确率）。
鲁棒性：该核在类别间存在显著规模不平衡的数据集（如 AIDS、MUTAG）上表现良好，表明基于 GBS 的特征对图的大小属性敏感。
特征分析：主成分分析（PCA）揭示，对应于在前几个模式中探测到真空（无光子）的特征对分类贡献最大，将性能与移除特定顶点后的子图 Hafnian 联系起来。

意义与主张
本文声称，仅利用二元探测器的 GBS 核能够在样本高效且技术可行的同时实现高分类准确率。作者强调，这种方法消除了对低温 PNR 探测器及其相关的禁止性样本量的需求。

其意义在于证明，机器学习任务的“量子优势”并不一定需要最先进、最难实现的量子硬件（PNR 探测器）。相反，使用二元探测器的更简单的近期设备，结合适当的粗粒化策略，可以提供有用且具有竞争力的图核。作者总结道，虽然这些分布的精确采样在经典计算中仍然困难，但此处使用的特定粗粒化版本为将量子启发式方法应用于图结构数据提供了一条实用途径。他们还指出，需要进一步研究从这些特定粗粒化分布中采样的经典难度。