1998年那道老题，正在重新定义“量子优势”|宇宙-百探网

文丨恩里科排版丨恩里科

行业动向：4200字丨12分钟阅读

抬高门槛的居然不是量子计算机？

8月12日，IBM博客介绍了一个榜单及其相关网页。

榜单叫QOBLIB，全称为“量子优化基准库”，可以理解成量子计算的公开考题：10类公认的难题摆在那里，经典方法和量子方法都可以提交解法，成绩公开挂榜，谁都能查。

项目论文2026年6月发表于《Nature Computational Science》，由柏林Zuse研究所的Thorsten Koch与IBM的研究者共同领衔，论文副标题把这10类题目称作难解的10项全能。

博文当中，IBM以其中一道题目为例进行介绍：库中已解出的最大实例，从大约60个变量涨到了110个，但这个变化里没有任何量子计算机参与。

就在7月底，IBM刚联合芝加哥大学以及Qedma、Algorithmiq两家公司同日发布三项结果，宣称量子计算已经进入优势时代。

而在这篇博文里，IBM自己写道，优化并不是那几项演示的重点。

可优化恰恰是产业最想用量子计算去做的方向之一，排产、调度、路径规划都在其中。

IBM一边高调宣布量子计算的优势时代到来，一边参与维护一块经典成绩还在上涨的公开榜单。

而在同一篇博文里，它写下这样一句：一项量子优势主张的可信度，取决于它背后的经典基线，而这条基线还在往上走。

IBM在评价标准这件事上是常客，我们此前那篇通用量子计算不缺纪录，缺的是一把好尺子就写过它更换标准的经过——从量子体积到后来的多维性能框架，它反复调整过衡量一台量子计算机的方式。

不同的是，那些指标衡量的是机器本身；

这一次要回答的是另一个问题：把同一道题交给经典和量子两边，谁给出的方案更好。

这10类问题里，有一大半能直接说出用途：球赛赛程编排、多期投资组合调整、芯片布线、货运车辆路径、电信网络规划，以及面向低时延通信的拓扑设计。

另一半是专门构造出来考验求解程序的数学难题。

选题只有一条硬标准：在大约100到10万个决策变量的规模上，现有最好的经典算法就已经吃力。

这个门槛是刻意设定的，它同时也是今天的量子硬件勉强够得着的规模。

这等于把题目选在两边能力的交界处，谁也没有主场。

全库1264个实例，其中533个已被解到可以证明的最优；

其余的榜首成绩只是目前找到的最好结果，没人知道还有没有更好的。

被讨论最多的那道题，已经难了20多年

10道题里，被反复刷新、也被IBM拿来举例的，是左上角那道叫市场分割（Market split）的题。

问题很短：一家大公司有两个事业部，向一批零售商供货，卖若干种产品。

现在要把每家零售商整体划给其中一个事业部——不能拆开——并且让每一种产品的销量都恰好对半分在两边。

难点全在“恰好”两个字：不是接近对半，是一分不差。

这道题的规模由两个数字决定：产品有几种、零售商有几家。

问题中两者是绑定的——产品每多一种，零售商就多10家。

榜单里的实例从3种产品配20家零售商，一直到15种配140家。

每家零售商只有划给这边或那边两种选择，家数就是变量数；

每多一家，可能的分法翻一番。

1998年，运筹学家Cornuéjols和Dawande提出这道问题。

他们在论文里说，这类题看着并不起眼，却让当时的主流求解方法束手无策，于是把它作为公开挑战抛给了整数规划学界，并写明：截至当时，7种产品、60个变量的实例无人能解。

题目的数据一页纸就写得下。

它难住主流方法不是意外，因为它正是照着主流路线的死角设计出来的——两位作者表示，常规方法连很小的实例都极难处理，换了几套别的路子也收效甚微。

20多年后，同一批实例上做过一组公开对照：最主流的商用求解器Gurobi第11版，三天时限。

7种产品、60个变量那一档解了出来；

再往上一档，8种产品、70个变量，内存直接耗尽，一个也没解出——那台机器有480GB内存。

60个变量，恰好是1998年公开挑战时的那条线。

现成的求解软件在这道题上几乎停在原地。

把门槛抬上去的，是两套定制算法

20多年里，这道题的纪录不是靠现成软件变快推上去的，而是靠两套绕开主流路线、专为它写的程序。

一套程序把1981年的老算法搬上了GPU：变量拆成两半、各自列出所有组合、两边对撞找匹配，用存储空间换搜索时间。

它在90个变量以内解得很快，最远做到11种产品、100个变量（在系数取值范围最小的一档上）。

论文特意说明，占的便宜来自GPU的大规模并行和访存带宽，不是更高的主频。

上面那组商用求解器的对照数据，正出自这篇论文。

另一套程序则是走格点几何，把整道题转化成在规则点阵里寻找短向量。

今年6月，拜罗伊特大学的Wassermann用它在一台8核工作站的单个处理器核心上，解出了含130个变量的实例（同样在系数最小的一档上）——比榜单上记录的那110个还要大。

他论文里的时间表把台阶写得很直白：110个变量约10分钟，120个约一个半小时，130个约39小时。

图1：市场分割求解耗时台阶图，数据出自Wassermann论文

而那套GPU方法的论文，作者之一是Thorsten Koch——这块榜单论文的第一作者，建榜单的人同时在刷榜。

他所在的柏林Zuse研究所，维护着经典优化界用了30多年的公开测试题集MIPLIB。

榜单由跨机构的工作组建设，出题的规矩来自经典阵营。

门槛每一次上移，靠的都不是把原来的求解器搬上更快的机器，而是换一套思路、再用新的硬件把它重新实现。

量子计算的位置也由此清楚：它本质上也是又一次换方法，要证明的不是比现成的求解软件快，而是比GPU对撞和格点枚举这些为这道题量身定制的算法更划算。

解法不设限，成本必须报全

榜单的规则有两条，一松一紧。

松的一条是不限制硬件，也不要求统一的数学模型。

同一道题可以写成整数规划，也可以转成另一种叫QUBO的形式。

QUBO的优势不是把问题变简单，而是把不同来源的组合优化任务统一成二元变量和二次耦合的形式，便于量子退火、Ising型求解器处理，也可以进一步映射成部分门模型量子优化算法所需的Hamiltonian。

但转换不是免费的：变量怎么编码、约束怎么处理，都会改变最后那道题的难度，转换本身还会改变问题的规模与结构。

榜单把两种形式的实例分别画成了图，对照着看很直观：写成整数规划时，约束密度最低探到百万分之一，稀疏得很；

同一批题转成QUBO之后，不少实例向更高稠密度区域移动，一些原本较稀疏的问题明显变密。

图2：QOBLIB论文的复杂度全景图，上下两联同轴对照：上联是整数规划形式；

下联是同一批题的QUBO形式图源：QOBLIB论文

10类问题在规模和结构上的差异非常大。

拓扑设计可以延伸到百万变量级，而市场分割问题却缩在图的左上角：只有几十到百余个变量，模型稠密度却接近全库最高。

它不是“大而难”，而是典型的“小而密、小而难”。

更有意思的是，同一批问题转换成QUBO以后，很多点的位置都会发生明显变化——数学表达方式本身，就会改变一场比较的起跑线。

所以不能因为某类硬件只接收QUBO，就规定经典方法也必须先转成QUBO再来比；

反过来也一样。

榜单把这一层放开，也在表示：把一道题翻译成什么形式，本身就是求解能力的一部分。

紧的一条写在提交要求里。

除了解的质量，还必须完整申报所用硬件，运行时间更是拆开来报：端到端的总运行时间、找到最好解所花的时间、CPU运行时间、GPU运行时间、QPU运行时间、其他硬件的运行时间，各占一栏。

混合方案最吃这一条。

一道题在量子处理器前后，要经过经典侧的建模编码、反复几十轮的参数更新、最后的筛选验证，量子部分只承担其中一段。

只报最终成绩的场合，这些经典算力很容易被略去，在这块榜单上却略不掉。

经典侧的开销不是零头。

量子机器真正跑起来的时候，旁边挂着的经典算力是以千万亿次每秒计的量级，这一点在我们此前文章拆解"量超智融合"：这七场报告都在讲同一件事有具体讨论。

这也是量超智融合在评测层面绕不过去的一步：讨论量子价值，要看整套系统为这个答案付出的全部计算成本。

现在，它还证明不了谁赢

新网站配了提交工具，填完自动校验，以合并请求的形式提交，每份要经至少两名委员会成员批准才能并入。

累计提交已超过2600份，来自24家机构：能源企业、国家级算力中心、多家高校与研究机构，IBM提交的实例数最多，把市场分割记录推到130的拜罗伊特大学也在其中。

规则比想象的宽：最优性从不作要求，启发式解照收；

连一次可行解都没找到的负面结果也欢迎，如实填零即可。

那么量子方法考得怎么样？它确实在榜上，网站为每一类题分别记录经典与量子的成绩，标出哪些已解到最优、哪些追平了当前最好、哪些还没解出。

上面那张图的角标里也能看出一点：全库实例中已求到最优的占500多个，未求到最优的主要落在规模更大的一端。

论文自己也写明，库里的量子结果是针对选定问题给出的样例基线，用来示范标准化的报告方式；

IBM的说法一致：这批提交让人看到量子方法的进展，也看到它们与最强经典求解器之间还差多远。

对经典一侧同样谨慎：预印本写明库里的数学模型未经充分调优、只作为示例，经典参照成绩也不主张代表极限。

还有一层：10道题里被反复刷新的主要是市场分割这一道——题面简单、成绩好比、进展看得见，所有人都盯着它，那些真正对应现实任务的题反而没有同等关注。

这是公开基准的通病。

所以这块榜单眼下证明不了谁赢。

它的作用是让成绩、作者、方法出现在同一个页面上，可以被别人逐条查证。

同一篇博文里，IBM还提到另一个社区维护的量子优势追踪器，走的是同一条路子。

更多热词推荐