作者: No'e Olivier, Michel Nowak

1. 核心物理图象

• 任务: 本文的核心是提出一种名为“Quantum WalkScore (QWS)”的基准测试协议，用于评估量子计算机在执行图节点寻找任务时的性能。该任务可直观理解为：在一个给定的图结构（如环形或二维环面网格）中，从已知起点出发，利用量子行走和振幅放大两种量子操作，以足够高的概率找到指定的目标节点。论文的贡献在于设计了一套可扩展、面向应用的评分体系，并首次在IBM多代超导量子处理器上进行了实验验证，给出了当前硬件的基准得分。

• 目标: 即使读者不了解量子行走或振幅放大的具体数学形式，也能理解本文是在为量子计算机建立一套“跑分”标准——就像用3DMark测试显卡一样，用图搜索问题来量化量子硬件的实际算法执行能力。

2. 关键术语解释

• 离散时间量子行走 (Discrete-Time Quantum Walk, DTQW): 一种量子版本的随机行走，行走者（量子态）在图的节点间移动时，其方向由额外的“硬币”量子比特控制。在本论文中，DTQW是遍历图结构、将概率分布向目标节点集中的核心算法步骤。

• 量子振幅放大 (Quantum Amplitude Amplification, AA): 一种对目标态振幅进行放大的量子 routine，是Grover搜索算法的推广。在本论文中，AA被用来在DTQW之后进一步提升找到目标节点的成功概率，但代价是增加电路深度。

• Quantum WalkScore (QWS): 本论文提出的基准评分，定义为在成功概率超过给定阈值的前提下，量子计算机所能解决的最大问题规模。它直接量化了硬件执行DTQW+AA组合算法的能力。

3. 主要贡献 (Key Contributions)

• 提出了首个基于离散时间量子行走与振幅放大的应用导向基准协议 (QWS)：该协议将图节点寻找问题形式化为可扩展的评分体系，填补了现有量子基准测试中缺乏对量子行走类算法评估的空白。

• 设计了两种图族（环形图和二维环面图）及配套的阈值概率函数：环形图作为一维基线，二维环面图作为更高维度的挑战，阈值概率的设计确保了通过测试意味着显著优于随机猜测，且阈值不随问题规模增大而增加，保证了统计验证的样本量有界。

• 在IBM Heron r2、Heron r3和Nighthawk r1三代超导量子处理器上完成了实验演示：在“足够性能”场景下，当前硬件在环形图问题上达到了QWS = 5的基准分，揭示了当前硬件在执行深电路时的噪声瓶颈。

• 量化了电路深度随问题规模的缩放关系：理论电路深度随问题规模呈多项式增长（环形图约O(nd)，二维环面图约O(nd)），而经过硬件原生门编译后的深度增长更快（环形图约O(n^3.45 d)），为未来硬件改进提供了明确的资源估算依据。

4. 研究方法 (Methodology)

• 问题建模：将图节点寻找问题定义在环形图（2^{n个节点）和二维环面图（2}n × 2^n个节点）上，给定源节点和目标节点距离d，要求以超过阈值p*(n,d)的概率找到目标节点。

• 算法流程：首先初始化量子态到源节点，然后执行num-w步DTQW（使用Hadamard硬币和对称硬币初态），接着执行num-aa次AA迭代。DTQW负责在图中扩散概率，AA负责放大目标节点振幅。理论上，只要num-w ≥ d且num-w ≡ d (mod 2)，总存在合适的num-aa使成功概率超过阈值。

• 评分规则：从最小问题规模(2,1)开始，逐步增加距离d直至d_max，再增加图尺寸n。记录连续成功通过测试的最大问题规模，最终QWS由公式QWS_cycle = 2ñ - 1 + d̃ 或 QWS_torus = 2ñ + d̃ 给出。

• 实验设置：在IBM量子处理器上，对每个问题实例运行4批各1000次采样，计算平均成功概率，并与阈值比较。使用了两种参数选择场景：“足够性能”(suff-perf)场景以最小化AA迭代为目标，“最佳性能”(best-perf)场景以最大化成功概率为目标。

5. 实验结果与结论 (Results and Conclusion)

• 关键结论：

• 在无噪声模拟中，环形图问题可成功解决至问题规模(6,32)，对应QWS_cycle ≥ 64；二维环面图问题可成功解决至(5,10)，对应QWS_torus = 41。
• 在IBM真实硬件上（以ibm_kingston为例），suff-perf场景下仅能成功解决至问题规模(3,1)，QWS_cycle = 5。成功概率从理想的0.5下降至0.39，随后迅速跌至随机猜测水平。
• 电路深度是主要瓶颈：当前硬件在维持75%量子态完整性的前提下，最大可执行深度约850，而成功解决更大规模问题需要数千甚至上万深度的电路。
• 二维环面图的电路深度增长慢于环形图（O(n^2.2 d) vs O(n^3.45 d)），意味着在相同评分范围内，提升二维环面图得分可能相对容易。

• 对领域的意义：QWS提供了一个可扩展、可复现、面向应用的量子计算机基准，能够随着硬件进步持续跟踪性能提升。当前结果显示，即使是最先进的超导量子处理器，在执行DTQW+AA这类组合算法时仍受限于噪声和电路深度，距离解决实际规模问题还有很大差距。

• 开放性问题与未来启示：

• 如何将QWS推广到更复杂的图结构（如更高维度、变节点度）以更好地反映实际应用？
• 错误缓解和纠错技术能在多大程度上提升QWS得分？
• 对于中性原子阵列等其它量子硬件平台，QWS的表现如何？特别是里德堡原子阵列具有可重构连接性，可能更适合实现环面图等复杂拓扑。
• 如何优化num-w和num-aa的参数选择策略，以在电路深度和成功概率之间取得最佳平衡？

6. 论文标签 (Tags)

量子算法, 物理硬件, 量子信息, 编译与优化, 模拟

📄 点击此处展开/折叠原文 PDF

原文链接： Quantum WalkScore: Benchmarking Quantum Computers on the Graph Nodefinding Problem