Ember: An Extensible Benchmark Suite for Quantum Annealing Embedding Algorithms

本文介绍了 Ember，这是一个开源且可复现的基准测试套件，用于标准化量子退火嵌入算法在不同图实例和硬件拓扑结构上的评估，结果表明没有任何单一算法具有普遍优势，且性能高度依赖于具体的图结构。

要点

想象一下，你有一个复杂的谜题想要解决，而你要使用一台名为量子退火器（Quantum Annealer，特指 D-Wave 公司制造的机器）的特殊高科技设备。这台机器就像一座由道路（量子比特）构成的巨大而错综复杂的城市，信息在其中穿梭。然而，这座城市存在一个问题：道路并非处处相连。有些街区是孤立的，如果两点之间没有道路，你就无法直接从 A 点驾车前往 B 点。

然而，你的谜题却假设你可以去往任何地方。为了让你的谜题在这台机器上运行，你必须执行一个称为**“小嵌入”（Minor Embedding）**的翻译步骤。这就像是将你的谜题碎片拉伸成由连接车辆组成的长链，以填补城市道路网络中的缺口。

问题所在：
多年来，科学家们一直在发明不同的“翻译策略”（算法），以找出如何最有效地拉伸这些谜题碎片。但存在一个主要问题：每个人都在不同的谜题上测试他们的策略，使用不同的规则，并以不同的方式衡量成功。这就像是用不同的烤箱和不同的品尝者，来比较一位厨师的汤食谱和一位面包师的蛋糕食谱。你无法判断谁才是真正的烹饪高手。

解决方案："Ember"
本文的作者构建了Ember（用于评估可重现性的嵌入基准，Embedding Minor Benchmark for Evaluative Reproducibility）。将 Ember 想象成一个通用的、标准化的烹饪比赛。

• 厨房：它提供了一个单一、公平的厨房（软件框架），所有策略都必须在完全相同的条件下进行烹饪。
• 食材：他们不仅仅使用随机食材，而是创建了一个拥有24,016 种不同类型谜题的巨大储藏室。这些谜题包括标准的随机谜题，也包括受物理学（如晶体和磁铁）启发的特殊谜题，以及现实世界问题实际呈现的结构性模式。
• 评委：他们测试了五位不同的“厨师”（算法），看看谁能最好地解决这些谜题。

他们的发现：
当他们运行比赛时，发现并没有单一的“最佳”厨师。获胜者完全取决于你给他们什么样的谜题：

• MinorMiner：这是“可靠的资深专家”。它在几乎所有情况下都表现良好，尤其是在受物理学启发的谜题和简单形状上。如果你不知道拥有什么类型的谜题，这是最稳妥的选择。
• OCT-fast：这是“速度专家”。当它起作用时，速度极快且能产生非常短的链（高效的解决方案），但它仅在特定的、高度结构化的谜题（如完美网格或对称形状）上表现良好。
• Clique：这是“蛮力”方法。它运行速度最快，但通常会生成非常长且笨拙的链。只有当你拥有一个完美的、密集的网状谜题（完全图）时，它才有效。
• ATOM 和 PSSA：这两者的结果喜忧参半。ATOM 速度很快，但经常无法找到解决方案或生成杂乱的链。PSSA 擅长解决“完美密集”的谜题，但在其他谜题上则表现挣扎。

硬件比厨师更重要：
本文还在三代不同的 D-Wave 机器（Chimera、Pegasus 和 Zephyr）上测试了这些策略。

• “城市”升级：他们发现，升级机器的硬件（道路网络）比改变翻译策略带来的影响更大。最新的机器（Zephyr）能够解决的谜题数量是最旧的机器（Chimera）的3 倍，仅仅因为它的道路连接得更好。
• 破损道路（故障）：真实机器中存在破损的道路（故障量子比特）。当他们模拟破损道路时，“可靠的资深专家”（MinorMiner）几乎像以前一样继续工作。然而，其他策略（如 PSSA 和 Clique）则严重崩溃，几乎立即失去了解决谜题的能力。

核心结论：
本文得出结论，如果你试图在量子计算机上解决问题：

1. 不要只选择最快的算法。最好的算法取决于你问题的形状。
2. 如果你不知道问题的形状，请使用 MinorMiner。它是最稳健的，适用于最广泛的谜题类型。
3. 硬件升级非常强大。一台更好的机器可以解决旧机器上任何算法都无法触及的问题。
4. 可靠性是关键。有些算法在纸面上看起来不错，但一旦硬件出现少量故障，它们就会失效。

Ember 现已向任何人开放使用，确保未来的“厨师”能够针对这个庞大的谜题库进行公平测试，从而让我们最终知道谁在将我们的问题翻译给量子机器方面真正最出色。

技术摘要

以下是论文《Ember：用于量子退火嵌入算法的可扩展基准套件》的详细技术总结。

1. 问题陈述

D-Wave 处理器上的量子退火（QA）需要小嵌入（minor embedding），这是一个将逻辑问题图映射到稀疏硬件拓扑（Chimera、Pegasus、Zephyr）上的编译步骤。这种嵌入的质量——特别是链长和成功率——直接决定了退火性能和解的保真度。

尽管嵌入至关重要，但该领域仍缺乏标准化的基准。现有的比较存在以下问题：

• 不兼容性：算法在不同的图库、硬件拓扑和实验设置上进行测试。
• 不可复现性：许多研究缺乏随机种子或详细的配置日志。
• 范围有限：先前的基准严重依赖随机图族（例如 Erdős-Rényi、Barabási-Albert），往往忽略了现实应用中常见的结构化或物理驱动的图。
• 缺失比较：新算法（如 ATOM、CHARME）尚未在与既定基线（如 MinorMiner、OCT）相同的条件下进行比较。

2. 方法论：Ember 框架

作者引入了Ember（用于可复现评估的嵌入小基准），这是一个开源的、可扩展的基准测试框架，旨在解决上述差距。

A. 架构与基础设施

• 标准化接口：为嵌入算法定义了严格的 Python 契约（输入/输出格式、超时处理、版本控制），以确保公平比较。
• 可复现性：每次运行均设置随机种子，解析后的配置保存为 YAML 文件。支持检查点保存和中断运行的恢复。
• 故障模拟：允许通过从目标硬件图中随机移除节点/边来模拟量子比特故障，以测试鲁棒性。
• 两部分设计：ember-qc（运行器）和 ember-qc-analysis（独立分析），允许在没有 D-Wave 软件栈的机器上进行分析。

B. 图库

Ember 引入了一个包含24,016 个不同问题图的多样化库，涵盖35 个类别和5 个结构族，显著扩展了以往的工作：

1. 随机图：包括 Watts–Strogatz、Erdős–Rényi、Barabási–Albert 和随机块模型。
2. 结构化图：代数图（Petersen、循环图、Turán 图、完全二分图、超立方体）。
3. 物理/晶格图：与量子模拟相关的 2D 和 3D 晶格（三角形、蜂窝、Kagome、受挫方格、Shastry–Sutherland）。
4. 拓扑图：极值图（路径、环、星形、树），用于测试树宽和直径极限。
5. 基准/应用图：植入解图、强弱簇、自旋玻璃实例和硬件原生子图。

C. 评估的算法

本研究评估了通过 Ember 契约实现的五种主要算法（及其变体）：

1. MinorMiner：标准的 D-Wave 启发式算法（贪婪搜索）。
2. Clique Embedding：针对完全图的精确多项式时间嵌入。
3. 基于 OCT 的算法（fast-OCT）：使用奇数环横截分解。
4. ATOM：自适应拓扑方法。
5. PSSA：概率交换移位退火（针对 D-Wave 拓扑重新实现）。
6. CHARME：一种强化学习（RL）方法（在特定子集上评估）。

3. 主要贡献

1. 可复现的基础设施：一个统一的开源平台，支持嵌入算法的直接、公平比较，并具有完整的可追溯性。
2. 多样化的图库：首个系统性地包含物理驱动晶格和结构化图的基准，揭示了算法性能高度依赖于图拓扑。
3. 跨拓扑分析：在所有三代 D-Wave 硬件（Chimera、Pegasus、Zephyr）上进行评估，量化了硬件容量的提升。
4. 容错性表征：系统地测试了算法针对模拟量子比特故障的鲁棒性。

4. 关键结果

A. 无通用主导者（排名反转）

• 总体与特定：虽然MinorMiner在总体上排名第一（成功率：61.3%，平均链长：4.23），但没有单一算法在所有图类型中都占主导地位。
• 结构依赖性：排名根据图结构发生系统性反转：
  • MinorMiner在物理/晶格和拓扑图上占主导地位。
  • OCT-fast在代数规则图（二分图、Turán 图、超立方体）和自旋玻璃实例上优于 MinorMiner，产生的链长缩短 7–15%，且运行时间约为其 1/8。
  • PSSA在完全图上领先。
  • Clique仅在硬件限制内的稠密完全图中是最优的，但在其他结构上迅速失效。
• 结论：总体排名掩盖了关键的性能差异；算法选择必须与特定的问题结构相匹配。

B. 硬件拓扑效应

• 容量提升：Zephyr将 Pegasus 的边容量扩展了 12%，并提供比 Chimera 多约 3.4 倍的容量。
• 链长：由于更高的连通性（度数为 15 对比度数为 6），Zephyr 在大图上产生的链长比 Chimera 短 2.7–3.0 倍。
• 可扩展性：MinorMiner 在 Zephyr 上对高达 200+ 节点的图保持了有意义的成功率（>40%），而 Chimera 在相同尺寸下的成功率降至<12%。

C. 容错性

• 优雅降级：MinorMiner在量子比特故障下表现优雅降级（在 25% 故障率下损失约 28% 的成功率）。
• 陡峭悬崖：PSSA和Clique在 1% 到 5% 的故障率之间表现出灾难性故障（“悬崖”），损失的成功率约为 MinorMiner 的两倍。
• 机制：MinorMiner 的增量路径查找能够绕过孤立的故障，而 Clique 的固定模板和 PSSA 的全局属性在连通性被破坏时会不连续地失效。

D. 强化学习（CHARME）

• 在与其训练分布匹配的图（$N=120$）上进行了评估。
• 性能：在 $N=120$ 时，CHARME 显著优于 ATOM（成功率 51% 对比 29%），但仍低于 MinorMiner（75–100%）。
• 权衡：CHARME 通过接受显著更长的链（平均链长增加 34%）和更高的运行时间（约为 ATOM 的 20 倍，MinorMiner 的 5 倍）来实现可行性提升。

5. 意义与实际影响

• 算法选择：本文提供了具体指导：对于结构化图上的时间敏感型工作负载，使用OCT-fast；对于通用/物理问题，将MinorMiner作为鲁棒的默认选择；仅针对特定的稠密图类使用PSSA/Clique。
• 硬件利用：对于大型问题，升级硬件（例如从 Chimera 到 Zephyr）带来的性能提升（成功率提升 3.8 倍）大于算法调优。
• 鲁棒性：MinorMiner 是现实世界部署中最具鲁棒性的选择，因为量子比特故障不可避免。
• 未来研究：Ember 为未来的工作奠定了基础，包括将 OCT/ATOM/CHARME 推广到 Pegasus/Zephyr，集成图结构元数据以进行动态算法选择，以及在实际 QPU 上进行端到端评估。

可用性：该框架是开源的，可通过 pip install ember-qc 安装。