2025-11-23T13:22:17.314370

Recent quantum runtime (dis)advantages

Tuziemski, Pawłowski, Tarasiuk et al.
We (re)evaluate recent claims of quantum advantage in annealing- and gate-based algorithms, testing whether reported speedups survive rigorous end-to-end runtime definitions and comparison against strong classical baselines. Conventional analyses often omit substantial overhead (readout, transpilation, thermalization, etc.) yielding biased assessments. While excluding seemingly not important parts of the simulation may seem reasonable, on most current quantum hardware a clean separation between "pure compute" and "overhead" cannot be experimentally justified. This may distort "supremacy" results. In contrast, for most classical hardware total time $\approx$ compute $+$ a weakly varying constant leading to robust claims. We scrutinize two important milestones: (1) quantum annealing for approximate QUBO PRL 134, 160601 (2025) [https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.134.160601], which uses a sensible time-to-$ε$ metric but proxies runtime by the annealing time (non-measurable); (2) a restricted Simon's problem PRX 15, 021082 (2025) [https://journals.aps.org/prx/abstract/10.1103/PhysRevX.15.021082] , whose advantageous scaling in oracle calls is undisputed; yet, as we demonstrate, estimated runtime of the quantum experiment is $\sim 100 \times$ slower than a tuned classical baseline. Finally, we show that recently claimed "runtime advantage" of the BF-DCQO hybrid algorithm (arXiv:2505.08663) does not withstand rigorous benchmarking. Therefore, we conclude that runtime-based supremacy remains elusive on NISQ hardware, and credible claims require a careful time accounting with a proper reference selections, and an adequate metric.
academic

Recent quantum runtime (dis)advantages

基本信息

  • 论文ID: 2510.06337
  • 标题: Recent quantum runtime (dis)advantages
  • 作者: J. Tuziemski, J. Pawłowski, P. Tarasiuk, Ł. Pawela, B. Gardas
  • 分类: quant-ph
  • 发表时间: 2025年10月16日 (arXiv v2)
  • 论文链接: https://arxiv.org/abs/2510.06337

摘要

本文重新评估了近期关于量子优势的声明，特别是在量子退火和基于门的算法中，测试这些报告的加速效果在严格的端到端运行时定义和与强经典基准比较下是否仍然成立。传统分析往往忽略了大量开销（读取、转译、热化等），导致评估偏差。作者审查了三个重要里程碑：(1) 近似QUBO的量子退火；(2) 受限Simon问题；(3) BF-DCQO混合算法。结果表明，在NISQ硬件上基于运行时的量子优势仍然难以实现。

研究背景与动机

研究问题

本文要解决的核心问题是：当前关于量子优势的声明在严格的运行时定义和公平的经典基准比较下是否仍然成立？

问题重要性

  1. 实用性考量：量子计算的最终目标是在实际应用中超越经典计算，而运行时性能是决定实用价值的关键指标
  2. 评估偏差问题：现有研究往往忽略量子硬件的显著开销，导致对量子优势的过度乐观评估
  3. 科学严谨性：需要建立公平、严格的基准测试方法来评估量子算法的真实性能

现有方法局限性

  1. 运行时定义不当：许多研究仅考虑"纯计算"时间，忽略读取、热化、转译等开销
  2. 基准选择偏差：经典基准算法选择不当，未使用最先进的并行化方法
  3. 统计分析不足：缺乏充分的统计分析，存在cherry-picking问题

研究动机

作者认为，随着量子技术的成熟，需要更严格的评估标准来验证量子优势的真实性，避免夸大宣传影响科学判断。

核心贡献

  1. 建立严格的运行时定义框架：提出包含所有必要组件（编程、执行、读取、热化）的完整运行时定义
  2. 重新评估三个重要量子优势声明：
    • 量子退火在近似QUBO问题上的优势
    • 受限Simon问题的查询复杂度优势
    • BF-DCQO混合算法的运行时优势
  3. 揭示评估偏差的根本原因：分析为什么量子硬件难以实现"纯计算"与"开销"的清晰分离
  4. 提供公平基准测试指南：为未来量子优势声明建立评估标准和方法论

方法详解

任务定义

本文重新评估量子算法在以下三个具体任务上的性能：

  • 输入：优化问题实例、Oracle查询、HUBO问题
  • 输出：问题解或查询结果
  • 约束：在现有NISQ硬件限制下的实际运行时性能

运行时定义框架

量子退火设备运行时

量子退火的完整运行时应包括：

总运行时 = 编程时间 + 退火时间 + 读取时间 + 热化时间

关键发现：

  • 读取时间约200μs，而退火时间仅0.5-27μs
  • 读取时间比退火时间长两个数量级
  • 这使得基于退火时间的性能评估严重失真

数字量子设备运行时

数字量子计算的完整运行时包括：

总运行时 = 预处理时间 + 转译时间 + 执行时间 + 读取时间 + 热化时间

时间到ε (TTε)指标

TTε=tf⋅log⁡(1−0.99)log⁡(1−pE≤E0+ε∣E0)TTε = t_f \cdot \frac{\log(1-0.99)}{\log(1-p_{E≤E_0+ε|E_0})}

其中：

  • tft_f：生成解的时间
  • pE≤E0+ε∣E0p_{E≤E_0+ε|E_0}：在ε最优性差距内找到解的概率

技术创新点

  1. 全面运行时计量：首次系统性地包含所有量子计算阶段的时间开销
  2. 强经典基准：使用GPU优化的并行算法（如SBM）作为基准
  3. 统计严谨性：避免cherry-picking，使用充分的实例数量进行统计分析

实验设置

评估案例

案例1：量子退火近似QUBO

  • 数据集：Sidon-28实例，规模N∈142, 1322
  • 量子设备：D-Wave量子退火机
  • 经典基准：模拟分岔机器(SBM)
  • 指标：TTε中位数

案例2：受限Simon问题

  • 问题规模：29位输入，Hamming权重w∈2,7
  • 量子设备：IBM Brisbane
  • 经典实现：GPU上的暴力破解算法
  • 指标：Oracle调用次数和实际运行时

案例3：BF-DCQO混合算法

  • 问题类型：高阶无约束二进制优化(HUBO)
  • 实例规模：N∈80, 100, 130, 156
  • 对比方法：CPLEX、模拟退火、SBM

实现细节

  • 硬件环境：双Intel Xeon Platinum 8462Y+ CPU，4×NVIDIA H100 GPU，1TB RAM
  • 统计方法：50个随机实例，多次独立运行
  • 参数优化：所有算法均进行超参数调优

实验结果

主要结果

量子退火结果

使用完整运行时定义后：

  • TTεMed几乎为常数：拟合指数α的不确定性过大，无法得出非零结论
  • 读取时间主导：占总运行时的主要部分
  • SBM表现更优：在相同问题上展现更好的扩展性

受限Simon问题结果

  • 查询复杂度优势确实存在：量子算法理论上需要更少Oracle调用
  • 实际运行时劣势显著：
    • N=29，w=7时：经典算法0.035s，量子算法2s
    • 量子算法慢约100倍
    • 预计交叉点在N≈60，但噪声限制了实际可达性

BF-DCQO混合算法结果

  • 方法论问题：运行时估算不准确，忽略重要开销
  • 统计问题：基于少量实例(5个)的cherry-picking
  • SBM优势明显：在相同问题上表现更好

消融实验

运行时定义敏感性分析

对比不同运行时定义的影响：

运行时定义量子退火扩展指数αSBM扩展指数α
仅退火时间2.23±0.25-
QPU总时间0.61±1.20-
完整运行时0.93±1.241.83±0.11

结果显示量子算法对运行时定义极其敏感，而经典算法相对稳健。

案例分析

HUBO实例的挑战性

生成的HUBO实例对不同算法表现出不同难度：

  • SBM：在Cauchy分布实例上成功率较低，但运行时优势明显
  • SA(QUBO)：解质量最好，但运行时较长
  • SA(HUBO)：在Pareto分布实例上表现优异

这说明实例特性对算法性能有重大影响，需要充分的统计分析。

相关工作

量子优势理论基础

  • Simon算法：指数级查询复杂度分离
  • Shor算法：基于因式分解困难性假设
  • 随机电路采样：首个实验量子优势声明

启发式量子算法

  • 量子退火：在特定NP-hard问题实例上寻求优势
  • 变分量子算法：NISQ时代的主要方向
  • 混合量子-经典算法：结合两种计算范式的优势

基准测试方法论

  • TTε指标：近似优化的标准评估方法
  • 查询复杂度框架：理论分析的重要工具
  • 经典基准选择：影响量子优势声明有效性的关键因素

结论与讨论

主要结论

  1. NISQ硬件上运行时量子优势仍然难以实现：在严格的运行时定义和公平基准比较下，所有检验的量子优势声明都不成立
  2. 运行时定义至关重要：量子硬件的高开销使得"纯计算"与"开销"难以分离，必须使用完整运行时
  3. 经典基准选择的重要性：使用最先进的并行化经典算法作为基准是公平评估的前提
  4. 统计严谨性必不可少：充分的实例数量和统计分析对于可信的量子优势声明至关重要

局限性

  1. 硬件限制：评估局限于当前NISQ设备，未来容错量子计算机可能改变结论
  2. 问题规模：受限于当前量子硬件的规模，无法评估大规模问题上的渐近行为
  3. 算法覆盖：仅评估了特定的量子算法，不能代表所有可能的量子方法

未来方向

  1. 改进的运行时测量方法：开发更精确的量子算法运行时测量工具
  2. 更强的经典基准：持续跟踪经典算法的最新进展
  3. 容错量子计算评估：为未来的容错量子设备建立评估框架
  4. 新的评估指标：除运行时外，考虑能耗、成本等其他实用指标

深度评价

优点

  1. 方法论严谨：建立了完整、公平的量子算法评估框架
  2. 实验充分：涵盖三个重要的量子优势声明，实验设计合理
  3. 统计可靠：使用充足样本量，避免cherry-picking偏差
  4. 实用价值高：为量子计算社区提供了重要的方法论指导
  5. 写作清晰：逻辑结构清楚，技术细节描述准确

不足

  1. 覆盖范围有限：仅评估了三个特定案例，可能不够全面
  2. 硬件依赖：结论可能随着量子硬件技术进步而改变
  3. 经典算法偏向：可能存在对经典方法的优化偏向
  4. 理论分析不足：更多关注实验结果，理论分析相对较少

影响力

  1. 学术影响：为量子优势评估建立了新的标准，可能影响未来研究方向
  2. 实用价值：帮助研究者和投资者更客观地评估量子计算的现状
  3. 政策意义：为量子计算投资和政策制定提供科学依据
  4. 可复现性强：提供完整的代码和数据，便于验证和扩展

适用场景

  1. 量子算法评估：为新量子算法的性能评估提供方法论
  2. 投资决策：为量子计算投资提供客观的技术评估
  3. 研究方向指导：帮助研究者识别真正有前景的量子应用
  4. 教育培训：作为量子计算课程的重要参考材料

参考文献

本文引用了量子计算领域的重要文献，包括：

  1. Feynman, R.P. - 量子计算的开创性工作
  2. Shor, P. - 量子因式分解算法
  3. Simon, D.R. - Simon算法的原始论文
  4. Arute, F. et al. - Google量子优势声明
  5. Munoz-Bauza, H. & Lidar, D. - 量子退火优势声明

总体评价：这是一篇具有重要学术和实用价值的论文，通过严格的实验和分析，为量子计算社区提供了关于量子优势评估的重要洞察。虽然结论可能令一些量子计算支持者失望，但其科学严谨性和方法论贡献对领域发展具有积极意义。