2025-11-10T02:42:02.274836

A Predictive Approach for Selecting the Best Quantum Solver for an Optimization Problem

Volpe, Quetschlich, Graziano et al.
Leveraging quantum computers for optimization problems holds promise across various application domains. Nevertheless, utilizing respective quantum computing solvers requires describing the optimization problem according to the Quadratic Unconstrained Binary Optimization (QUBO) formalism and selecting a proper solver for the application of interest with a reasonable setting. Both demand significant proficiency in quantum computing, QUBO formulation, and quantum solvers, a background that usually cannot be assumed by end users who are domain experts rather than quantum computing specialists. While tools aid in QUBO formulations, support for selecting the best-solving approach remains absent. This becomes even more challenging because selecting the best solver for a problem heavily depends on the problem itself. In this work, we are accepting this challenge and propose a predictive selection approach, which aids end users in this task. To this end, the solver selection task is first formulated as a classification task that is suitable to be solved by supervised machine learning. Based on that, we then propose strategies for adjusting solver parameters based on problem size and characteristics. Experimental evaluations, considering more than 500 different QUBO problems, confirm the benefits of the proposed solution. In fact, we show that in more than 70% of the cases, the best solver is selected, and in about 90% of the problems, a solver in the top two, i.e., the best or its closest suboptimum, is selected. This exploration proves the potential of machine learning in quantum solver selection and lays the foundations for its automation, broadening access to quantum optimization for a wider range of users.
academic

A Predictive Approach for Selecting the Best Quantum Solver for an Optimization Problem

基本信息

  • 论文ID: 2408.03613
  • 标题: A Predictive Approach for Selecting the Best Quantum Solver for an Optimization Problem
  • 作者: Deborah Volpe, Nils Quetschlich, Mariagrazia Graziano, Giovanna Turvani, Robert Wille
  • 分类: quant-ph cs.ET
  • 发表时间: 2024年8月7日 (arXiv)
  • 论文链接: https://arxiv.org/abs/2408.03613

摘要

量子计算在优化问题求解方面具有巨大潜力，但使用量子求解器需要将优化问题转换为QUBO（二次无约束二进制优化）形式，并为特定应用选择合适的求解器及其参数设置。这需要深厚的量子计算、QUBO建模和量子求解器专业知识。本文提出了一种预测性选择方法，将求解器选择任务建模为分类问题，使用监督机器学习来自动选择最佳量子求解器。基于500多个不同QUBO问题的实验评估表明，该方法在70%以上的案例中选择了最佳求解器，在约90%的问题中选择了前两名求解器。

研究背景与动机

问题定义

  1. 核心挑战: 量子优化求解器的选择对非专业用户来说极其困难，需要深入的量子计算知识
  2. 实际需求: 不同优化问题需要不同的量子求解器才能获得最佳性能，符合"没有免费午餐"定理
  3. 现有局限: 虽然存在QUBO建模工具，但缺乏求解器选择的自动化支持

重要性分析

  • 应用广泛: 量子优化在金融、资源分配、调度等领域具有重要应用价值
  • 技术壁垒: 当前量子优化技术的复杂性阻碍了更广泛的应用
  • 成本考量: 执行所有求解器进行比较在时间和经济成本上不可行

研究动机

通过机器学习自动化求解器选择过程，降低量子优化的使用门槛，使领域专家能够在不具备深度量子计算知识的情况下利用量子优化技术。

核心贡献

  1. 首次提出基于机器学习的量子求解器自动选择框架
  2. 建立包含500+不同QUBO问题的综合评估数据集
  3. 开发QUBO问题特征提取方法，用于求解器性能预测
  4. 设计求解器参数自动配置策略
  5. 集成到MQT Quantum Auto Optimizer框架，提供开源实现
  6. 验证在70%+案例中选择最佳求解器，90%案例中选择前两名求解器

方法详解

任务定义

  • 输入: QUBO问题的数学表示
  • 输出: 最适合该问题的量子求解器及其参数配置
  • 目标: 最大化求解质量，同时最小化计算成本

求解器覆盖范围

本文考虑以下求解器：

  1. Quantum Annealer (QA): 专用量子退火设备
  2. Quantum Approximate Optimization Algorithm (QAOA): 混合量子-经典变分算法
  3. Variational Quantum Eigensolver (VQE): 变分量子本征求解器
  4. Grover Adaptive Search (GAS): 基于Grover搜索的自适应算法
  5. Simulated Annealing (SA): 经典模拟退火作为对照

特征提取方法

从QUBO问题中提取以下9个特征：

  • 变量数量
  • 非零一阶项数量和统计特性（均值、方差）
  • 非零二阶项数量和统计特性（均值、方差）
  • 所有系数的统计特性（均值、方差）

评价指标设计

提出综合评分系统：

Fs = -αps + β(Eopt-Eref) + γ(Eavg-Eref) + δEvar - ηpv

其中：

  • ps: 获得最优解的百分比
  • Eopt: 获得的最佳值
  • Eref: 问题的参考最优值
  • Eavg: 平均值
  • Evar: 方差
  • pv: 满足约束的解的百分比

机器学习模型

使用五折交叉验证评估10种分类器：

  • Ada Boost, Decision Tree, Gradient Boosting
  • k-nearest neighbors (KNN), Logistic Regression
  • Naive Bayes, Neural Network, Random Forest
  • Support Vector Machine (SVM), XGBoost

参数自动配置策略

Quantum Annealer:

TTTS = 10^(b√N), b = 0.7

QAOA:

reps = ⌈2√N⌉

GAS:

threshold = 2N

VQE: 使用标准ansatz配置

Simulated Annealing: 类似QA的时间复杂度缩放

实验设置

数据集构建

  • 规模: 500+ QUBO问题
  • 来源:
    • 传统优化基准测试集
    • 不同规模、密度和系数范围的生成问题
    • 投资组合优化问题
    • 基于Iris数据集的线性回归问题

数据预处理

  • 类别不平衡处理: QAOA占约50%，QA和VQE各约20%，GAS和SA各约10%
  • 特征缩放: 标准化到公共范围
  • 降维技术:
    • PCA: 2, 3, 4, 9个主成分
    • LDA: 2, 3, 4个判别成分

评价指标

  • 准确率: 正确预测的百分比
  • Top-2准确率: 预测前两名求解器的比例
  • 平均ps误差: 最佳求解器与预测求解器在成功概率上的差异

实验结果

主要结果

Random Forest表现最佳:

  • 准确率: 73.18%
  • Top-2准确率: 91.12%
  • 平均ps误差: 2.16%

模型比较

模型准确率(%)Top-2(%)ps误差(%)
Random Forest73.1891.122.16
Gradient Boosting72.6389.862.40
Logistic Regression71.0188.593.70
XGBoost69.5687.503.01
Decision Tree68.6587.503.22

降维效果分析

  • Random Forest: 降维技术未显著提升性能
  • SVM/Naive Bayes: 降维技术有明显帮助
  • Neural Network: 在某些降维配置下性能提升

求解器性能分析

不同问题类型展现出不同的最优求解器：

  • Set Packing: QA表现最佳
  • K-clique: QAOA表现最佳
  • Portfolio Optimization: VQE表现最佳
  • Max Cut: GAS表现最佳
  • Minimum Vertex Cover: SA表现最佳

相关工作

QUBO建模工具

现有库包括：pyqubo, qubovert, dimod, Qiskit-optimization, Fixstarts Amplify, openQAOA等

自动化框架

  • AutoQUBO: 专注于QUBO公式化
  • QUBO.jl: Julia生态系统的QUBO工具
  • MQT QAO: 综合优化框架

研究空白

本文首次系统性地解决了量子求解器自动选择问题，填补了该领域的重要空白。

结论与讨论

主要结论

  1. 可行性验证: 机器学习方法能够有效预测最佳量子求解器
  2. 实用性证明: Random Forest在73.18%的案例中正确选择最佳求解器
  3. 鲁棒性展示: 90%以上的案例中选择了前两名求解器

局限性

  1. 数据集规模: 需要更大规模的训练数据集提高预测可靠性
  2. 问题规模限制: 受量子模拟器限制，无法处理大规模问题
  3. 参数设置: 主要依赖经验推导，有待进一步优化
  4. 时间复杂度: 未充分考虑不同求解器的执行时间差异

未来方向

  1. 扩展数据集: 包含更多样化的优化问题
  2. 参数优化: 使用机器学习方法优化求解器参数
  3. 多标签方法: 处理求解器性能相当的情况
  4. 强化学习: 探索替代监督学习的方法

深度评价

优点

  1. 创新性强: 首次系统性地将机器学习应用于量子求解器选择
  2. 实用价值高: 显著降低了量子优化的使用门槛
  3. 实验充分: 基于500+问题的综合评估，结果可信
  4. 开源贡献: 集成到MQT框架，促进社区发展
  5. 方法系统: 从特征提取到模型选择的完整pipeline

不足

  1. 理论分析不足: 缺乏对为什么某些特征有效的深入理论解释
  2. 可扩展性限制: 受当前量子硬件限制，难以验证大规模问题效果
  3. 基准测试局限: 主要基于经典优化问题，量子优势问题覆盖不足
  4. 参数设置简化: 求解器参数配置策略相对简单

影响力

  1. 学术价值: 为量子计算自动化开辟新方向
  2. 实用意义: 使非量子专家能够利用量子优化技术
  3. 产业应用: 有望推动量子优化在实际应用中的普及
  4. 可复现性: 开源实现保证了研究的可复现性

适用场景

  1. 教育培训: 量子计算课程和培训项目
  2. 原型开发: 快速评估量子优化可行性
  3. 跨学科研究: 帮助领域专家探索量子解决方案
  4. 工业应用: 为实际优化问题提供求解器选择指导

参考文献

论文引用了68篇相关文献，涵盖量子计算、优化算法、机器学习等多个领域的重要工作，为研究提供了坚实的理论基础。

总体评价: 这是一篇具有重要实用价值的研究工作，首次系统性地解决了量子求解器自动选择问题。虽然在理论深度和可扩展性方面存在一些局限，但其创新性、实用性和开源贡献使其成为量子计算自动化领域的重要进展。该工作有望显著降低量子优化技术的使用门槛，促进其在更广泛领域的应用。