⚛️ quantum physics

Quantum WalkScore: Benchmarking Quantum Computers on the Graph Nodefinding Problem

本文介绍了 Quantum WalkScore (QWS)，这是一个可扩展的、面向应用的基准测试，通过衡量量子计算机利用离散时间量子行走和振幅放大解决图节点查找问题的能力，通过模拟以及在 IBM 量子处理器上的实验进行验证，从而评估 NISQ 及未来容错量子计算机的性能。

原作者： Noé Olivier, Michel Nowak

发布于 2026-09-18

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Noé Olivier, Michel Nowak

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

在构建能够解决超越当今超级计算机能力的难题之机器的探索过程中，科学家们正致力于开发量子计算机。这些设备并不依赖于经典比特简单的开/关开关，而是使用量子比特（qubits），量子比特可以同时存在于多种状态之中。这种独特的属性使它们能够同时探索极其广阔的可能性。然而，构建一台能够可靠保持这些脆弱量子态的机器是极其困难的。目前的设备经常受到噪声和误差的影响，这导致研究人员提出了一个关键问题：我们如何知道一台量子计算机是否真的在工作，以及它在解决现实世界任务时的表现究竟如何？为了回答这个问题，科学界需要的不仅仅是一份误差率清单；他们需要一种实用的测试，来衡量一台机器是否能成功地应对复杂的难题。

法国 CortAIx 实验室的一个研究小组提出了一种衡量这种能力的新方法，称为“量子行走评分”（Quantum WalkScore）。该基准测试并非测试抽象的数学属性，而是要求计算机执行一项特定的、有用的任务：在网络中寻找一个隐藏的目标。想象一位旅行者试图在一张由连接道路组成的庞大地图中找到一座特定的城市。经典计算机会逐一检查道路，但量子计算机可以同时探索许多路径。研究人员专注于量子计算机用于此类搜索的两项强大工具：一种被称为“离散时间量子行走”的方法，它就像一种在网络中移动的高级方式；以及一种被称为“振幅放大”的技术，它能提高找到正确答案的概率。通过结合这些工具，该团队创建了一个测试，用以衡量一台量子计算机在噪声导致其失效之前，能够搜索多大规模的网络。

该基准测试旨在具备可扩展性，这意味着它可以从一个非常小的网络开始，并随着硬件的改进而变得更大、更复杂。研究人员在两种类型的网络形状上测试了这一协议：一种是简单的环形结构，其中每个点都与两个邻居相连；另一种是更复杂的网格结构，它像甜甜圈的表面一样在自身周围环绕。他们定义了一个明确的目标：计算机必须以高于纯粹靠运气所能达到的成功率找到隐藏目标。如果计算机成功了，测试就会转向一个稍微更大或更难的问题版本。最终得分仅仅是计算机在无法可靠找到目标之前所能解决的最大网络规模。这种方法提供了一个任何人都能理解的具体数值，代表了该机器当前能力的实际极限。

为了观察这在实践中是如何运作的，研究人员在包括名为 Heron 和 Nighthawk 的型号在内的几代 IBM 提供的真实量子处理器上运行了他们的测试。他们还在完美的、无噪声的计算机上进行了模拟，以观察在理想世界中结果应该是怎样的。模拟显示，在正确的设置下，量子算法理论上可以解决非常大的问题，并以很高的置信度找到目标。然而，当团队在实际的物理机器上运行相同的测试时，结果却要平庸得多。由于现有硬件中固有的噪声和误差，这些计算机只能成功解决非常小的网络。对于环形网络，表现最好的机器能在特定的小规模网络中找到目标，但随着网络规模的增长，成功率下降到了随机猜测的水平。

这项研究凸显了量子算法在理论上能做什么与当前硬件实际能实现什么之间的显著差距。研究人员发现，运行搜索所需的电路复杂度随着问题的增大而迅速增长。在他们测试的机器上，过于深或过于复杂的电路会被误差淹没，导致量子信息在找到答案之前就发生退化。即使是使用当时最先进的处理器，该团队也只能展示出一个概念验证性的得分，这证明了该方法是有效的，但也揭示了硬件还需要多么大的提升。结果表明，虽然数学工具已经准备就绪，但物理机器仍处于处理诸如物流或数据库搜索等现实应用所需的高难度任务的早期阶段。

这种新的基准测试——量子行走评分，提供了一种清晰且诚实的追踪进步的方法。它不依赖于理论潜力或理想化的模拟，而是通过一种受控且可重复的方式来衡量机器的实际性能。通过建立一个要求计算机在特定图论问题上击败随机概率的标准，研究人员为整个领域提供了一个标尺。随着量子硬件不断进化，变得更加稳定且不易受误差影响，这个分数自然会随之提高。这项工作提醒人们，通往强大量子计算的道路是一个渐进的过程，每一次性能的提升都必须通过成功解决一个此前无法触及的问题来得到验证。研究人员已经为这段旅程绘制了一张地图，清晰地展示了机器目前的现状以及它们必须克服的障碍，以迈向未来。

技术摘要：量子行走评分 (Quantum WalkScore, QWS)

问题定义
本文针对评估噪声中等规模量子 (NISQ) 及未来容错量子计算机成熟度时，对面向应用基准测试的需求进行了研究。现有的基准测试多侧重于物理门保真度或随机电路采样，而缺乏利用具有前景的量子程序（特别是离散时间量子行走 (DTQW) 和 量子振幅放大 (AA)）来解决实际图论问题的基准测试。作者关注的是图节点查找问题：即在给定无向图中，从源节点 $v_0$ 开始识别特定的“标记”目标节点 $v_t$ 。该问题是电信路由、数据库搜索和复杂网络分析等现实世界应用的基础构建模块。

方法论：量子行走评分 (QWS) 协议
作者提出了 量子行走评分 (QWS)，这是一种可扩展的基准测试协议，旨在衡量量子计算机能够成功解决的最大问题规模。

图族 (Graph Families)： 基准测试利用了两种特定的图拓扑结构，以平衡简单性、可扩展性和硬件适用性：
1. 循环图 (Cycle Graphs)： 具有 $2^n$ 个节点的 1D 结构，每个节点连接两个相邻节点。
2. 2D-环面图 (2D-Torus Graphs)： 具有 $2^n \times 2^n$ 个节点的 2D 结构，每个节点连接四个相邻节点（周期性边界条件）。
问题实例： 由 $(n, d)$ 定义，其中 $n$ 是量子比特数， $d$ 是源节点与目标节点之间的距离（最短路径边数）。
算法程序：
1. 初始化： 系统初始化在状态 $|v_0\rangle$ 。
2. 离散时间量子行走 (DTQW)： 行走者进行 $num\_w$ 步演化。协议要求 $num\_w \ge d$ 且 $num\_w \equiv d \pmod 2$ 以确保可达性。使用哈达玛硬币 (Hadamard coin) 进行无偏行走。
3. 振幅放大 (AA)： 将 DTQW 程序嵌入到 AA 框架（Brassard 等人）中，以提升测量目标态的概率。这涉及关于目标态和初始态的 $num\_aa$ 次反射迭代。
4. 测量： 实验成功概率 $p_{exp}$ 被测量为观测到目标节点状态的概率。
评分标准：
- 阈值概率 ( $p^*$ )： 定义了一个动态阈值，以确保成功率显著高于随机猜测。对于距离 $d \le 2$ ， $p^* = 1/3$ 。对于 $d > 2$ ， $p^* = 1/5 + 1/2^d$ 。
- 指标： 成功概率在多个批次（4 个批次，每个批次 1000 次采样/shots）和多个目标节点实例（循环图为 2 个，环面图为 4 个）上取平均值。
- QWS 分数： 分数是在第一次失败前，测量成功概率超过 $p^*$ 的最大问题规模。计算方式为 $QWS_{cycle} = 2^{e_n-1} + e_d$ 以及 $QWS_{torus} = 2^{e_n} + e_d$ ，其中 $(e_n, e_d)$ 是最后一次成功的实例。

核心贡献

协议设计： 引入了一个完整的、面向应用的基准测试协议，该协议集成了 DTQW 和 AA，这两者是未来量子算法的关键程序。
可扩展性与可复现性： 该协议旨在适用于任何基于门的量子计算机，具有标准化的实验参数（采样次数、分批处理）以及灵活的算法参数（ $num\_w$ 、 $num\_aa$ ），后者留给最终用户进行优化。
理论与实证分析： 文中提供了关于存在能够理论上解决任何问题规模的参数的理论保证，并对两种实现方式（算法层面和原生硬件层面）进行了详细的资源估算（电路深度缩放）。
实验验证： 该协议在三代 IBM 量子处理器（Heron r2, Heron r3, 和 Nighthawk r1）上执行，为当前硬件能力提供了概念验证性评估。

结果

无噪声模拟： 在理想量子计算机上的模拟表明，该基准测试对于较大的问题规模是可解的。在“充分性能 (suff-perf)”场景下（最小化 AA 迭代次数），成功概率保持接近阈值。在“最佳性能 (best-perf)”场景下，成功概率趋近于 1，但这也需要更高的电路深度。
电路深度缩放： 理论算法深度缩放为 $O(nd)$。然而，当转译到 IBM 的 Heron 架构时，原生深度对于循环图缩放为 $O(n^{3.45}d)$ ，对于 2D-环面图缩放为 $O(n^{2.2}d)$ ，这凸显了硬件映射带来的显著开销。
IBM 硬件上的实验表现：
- 在 ibm_kingston (Heron r2) 处理器上的实验显示，由于噪声和退相干，成功概率随问题规模增加而迅速下降。
- 系统仅在问题规模 (3, 1) 时成功通过了阈值。随后的大小，成功概率骤降至与随机猜测相当的水平，唯独问题规模 (4, 1) 除外，但它并不构成连续的成功序列。因此，在“充分性能”场景下，循环图的量子行走评分被确定为 5。
- 对于较大的实例（例如深度 > 700 个门），结果退化到与随机猜测无法区分的水平。
- 对比 Heron r2、Heron r3 和 Nighthawk r1 的表现，显示出相似的趋势，尽管 Heron r3 提供了略好的准确度，但所有当前架构在处理超过 ~1000 个门的电路时都显得力不从心。

意义与主张
本文声称 QWS 是弥合抽象硬件指标与实际应用性能之间差距的必要工具。通过专注于图节点查找问题，它直接评估了硬件执行优化和搜索任务所需的关键量子原语（DTQW 和 AA）的能力。

作者强调，该基准测试突出了算法参数与硬件限制之间的相互作用。结果表明，虽然理论框架允许解决大规模问题，但当前的 NISQ 设备受限于电路深度和误差累积。论文总结道，QWS 提供了一个有意义且可解释的分数，用于追踪量子计算机的成熟度，并能区分 NISQ 与未来容错量子计算 (FTQC) 设备之间的性能差异。当前硬件实现的微小分数（5 分）凸显了在这些算法能够应用于大规模实际问题之前，仍面临着巨大的技术挑战。

技术摘要：量子行走评分 (Quantum WalkScore, QWS)

类似论文