量子科技中心_量科网

针对各类优化问题，经典求解方法的时间复杂度往往呈超多项式增长，基于传统比特计算硬件至今仍难以有效处理。数字退火器和量子退火器通过二次无约束二值优化（QUBO）问题建模，有望为此类优化问题寻找近似最优解。该工作通过两个工业级应用案例对组合优化问题的QUBO求解器进行基准测试，旨在评估基于QUBO建模与退火算法是否比经典混合整数规划（MIP）和约束规划（CP）求解器更具优势。研究人员采用多种QUBO指标与求解器指标进行评估，包括问题映射、定量互联性、惩罚结构、求解器最低成本（获取得最优值）及求解耗时等。测试对象涵盖约束型与非约束型QUBO求解器：富士通数字退火器（DA）、D-Wave多种混合量子退火求解器（QA/HQA），以及经典MIP/CP求解器HiGHS、Gurobi、SCIP和CP-SAT。 两个工业相关案例分别为反应网络路径分析和mRNA密码子选择。在反应路径分析中，经典MIP/CP求解器能在合理时间内求得最优解，而DA未能实现。对于mRNA密码子选择任务，CP-SAT在标准规模及大型蛋白质数据集（1500个氨基酸以下）中表现最优；在超大规模数据集（11000至14000个氨基酸）测试中，D-Wave非线性HQA求解器与CP-SAT性能相当，其中在4个问题中有2个案例的最低成本指标优于后者。