Thermodynamic significance of QUBO encoding on quantum annealers

本文表明，量子退火中的 QUBO 惩罚权重充当热力学控制旋钮，其中最优编码在计算可行性与最小能量耗散之间取得平衡，这一结论在经典计算机与 D-Wave Advantage 实验中通过求解器成功率和熵产生的急剧转变得到了证实。

要点

想象一下，你正在尝试解决一个非常复杂的谜题，就像在一家繁忙的工厂中组织工作：数十项任务需要按照特定顺序在特定机器上完成。这被称为“作业车间调度”问题。为了让量子计算机（具体来说是“量子退火器”）解决这个问题，你必须将谜题翻译成它所能理解的语言：一个由“开”或“关”开关组成的网格。这种翻译过程被称为QUBO 编码。

然而，这篇论文指出，翻译这个谜题并非只有一种方式。你可以用许多不同的方式进行翻译，而在翻译过程中你所选择的“规则”会改变计算机“感知”问题的方式。

以下是这篇论文的核心思想，通过简单的类比进行分解：

1. 惩罚旋钮：“守门员”与“重手”

当你翻译工厂谜题时，你必须告诉计算机如果规则被打破会发生什么（例如，两个任务试图同时使用同一台机器）。你通过添加“惩罚权重”来实现这一点。可以将这些权重想象成你可以调节的旋钮：

• 旋钮 A ($p_{sum}$)：控制“每台机器一个任务”的规则。
• 旋钮 B ($p_{pair}$)：控制“任务顺序”的规则。

研究人员发现，调节这些旋钮会改变问题的能量景观。想象这个问题是一片丘陵地形，计算机想要滚落到最低的谷底（即最佳解决方案）。

• 如果旋钮太松（惩罚太弱）：计算机可能会滚入一个看起来很低但实际上是“虚假”解决方案（即错误的调度）的谷底。这就像俱乐部里一位过于宽容的守门员，让没有门票的人混了进去。
• 如果旋钮太紧（惩罚太强）：计算机因为害怕违反规则而变得如此谨慎，以至于它无法看到真正的最佳解决方案，因为“真实”的谷底被惩罚能量的大山掩埋了。这就像一位过于严格的守门员，因为过于专注于检查身份证件，而不小心把贵宾赶了出去。

2. “甜蜜点”与相变

这篇论文发现，当你调节这些旋钮时，存在一个尖锐的“临界点”（即相变）。

• 在一侧，计算机很容易找到有效的解决方案。
• 在另一侧，它会感到困惑并找到错误的解决方案。
• 研究人员发现，这个临界点不仅仅关乎计算机是否能得到正确答案；它还关乎计算机在尝试过程中浪费了多少能量。

3. 热力学成本：机器的“汗水”

这是这篇论文最独特的部分。他们不仅仅问：“它解决谜题了吗？”，而是问：“机器为了解决它流了多少汗？”

他们将量子计算机视为一种热力学引擎（就像汽车引擎或蒸汽机）。

• 功：输入机器使其运行的能量。
• 热：机器变热或抖动时浪费的能量。
• 熵：衡量过程有多混乱或不可逆的指标。

重大发现：
当研究人员将惩罚旋钮调至“错误”的设置（使问题更难被计算机解决）时，机器不仅失败得更频繁，而且浪费了更多能量。

• 惩罚过弱：计算机在混乱的低能量迷雾中徘徊，浪费能量试图寻找一条不存在的路径。
• 惩罚过强：计算机必须付出极大的努力来冲破惩罚的“墙壁”，产生大量“热量”（不可逆性），从而降低其效率。

4. “反向退火”实验

为了测量这种“汗水”，研究人员使用了一种称为反向退火的技术。

• 想象你正在下山寻找营地（即解决方案）。
• 正向退火：你从山顶开始向下走。
• 反向退火（论文中使用的方法）：你从某个特定位置（一个猜测）开始，向上走进迷雾中一小段距离，然后尝试再次向下走。
• 通过测量机器在这次往返过程中能量的变化，他们可以计算出做了多少“功”以及损失了多少“热”，即使无法看到机器内部的部件。

5. 结论：设计至关重要

这篇论文得出结论，你编写代码（即编码）的方式与硬件本身同样重要。

• 旧观点：“只要把惩罚设得巨大，计算机就永远不会违反规则。”
• 新观点：“如果你把惩罚设得太大，你会让计算机变得低效且浪费。你需要找到一个‘金发姑娘’区域，那里的惩罚强度足以维持规则，但又不会强到淹没实际问题。”

简而言之：你将现实世界问题翻译成量子计算机语言的方式，就像控制机器能量效率的旋钮。如果调节不当，你得到的不仅仅是一个糟糕的答案；你还会让机器更努力地工作、变得更热、浪费更多能量。最佳的编码是在获得正确答案与保持机器凉爽高效之间取得平衡的那种。

技术摘要

技术摘要：QUBO 编码在量子退火器上的热力学意义

问题陈述
量子退火（QA）通过将离散优化问题映射到伊辛哈密顿量的低能态，提供了一种硬件原生的求解方法。然而，现实世界的任务（如作业车间调度问题，JSP）通常被表述为约束优化问题，而当前的量子退火器需要无约束二次无约束二进制优化（QUBO）形式。为了弥合这一差距，约束通过具有可调权重的惩罚项来强制执行。一个关键挑战在于，单个约束任务存在多种 QUBO 编码方式；惩罚结构和幅度的不同选择会重塑能量景观，从而影响找到可行解的概率以及退火动力学的耗散成本。虽然先前的研究主要集中在运行时间和解的概率上，但在含噪声中等规模量子（NISQ）设备上，不同编码的热力学成本（功、热、熵产生）仍未得到充分探索。

方法论
作者利用由惩罚权重控制的双参数 QUBO 编码族，研究了一个特定的作业车间调度实例：$p_{sum}$（强制执行 one-hot/求和约束）和 $p_{pair}$（强制执行优先顺序约束）。该研究采用双重分析途径：

1. 计算分析：作者扫描 $(p_{sum}, p_{pair})$ 参数空间以映射求解器性能。他们利用受经典退火启发的启发式方法（模拟退火、路径积分退火和转子模型退火）以及在 D-Wave Advantage 处理器上的实验运行。成功与否通过找到最优解的概率和基态的可行性来衡量。
2. 热力学分析：将退火器视为开放热力学系统，作者执行循环反向退火实验。处理器在 $s=1$ 处初始化为经典吉布斯态，退火至最小参数 $\bar{s}$，然后返回 $s=1$。通过测量多次运行中处理器能量的随机变化（$\Delta E_1$），他们应用热力学不确定性关系（TUR）来推断平均熵产生（$\langle \Sigma \rangle$）、功（$\langle W \rangle$）和交换热量（$\langle Q \rangle$）的下界。
3. 模拟：为了补充实验数据，作者使用绝热主方程模拟退火过程。这使得能够直接计算热力学量，并研究可能被硬件噪声掩盖的光谱特征（例如能级交叉和简并）。

主要结果

• 编码机制与相变：该研究确定了 $(p_{sum}, p_{pair})$ 参数空间中的急剧转变。这些转变将 QUBO 基态对应于可行解的区域与对应于不可行解的区域区分开来。此外，还识别出一个“混合”机制，其中可行和不可行的低能态在能量上是简并的或相互混合的。
• 热力学特征：编码引起的能量景观重排产生了不同的热力学机制。微弱的惩罚会产生不可行解的低能流形，而过强的惩罚则会抑制有效问题能量尺度。在求解器精度中观察到的转变边界与热力学可观测量（熵产生、功和热）的急剧变化相吻合。
• 惩罚的不对称性：结果表明 $p_{sum}$ 和 $p_{pair}$ 之间存在显著的不对称性。引入负对角项的 $p_{sum}$ 参数对计算难度和热力学耗散均具有主导影响。较小的 $p_{sum}$ 值可能被目标函数“否决”，导致简并度增加和不可逆性提高。
• 效率相关性：计算“难度”与热力学效率之间存在系统的负相关。使优化问题变得困难的编码（例如通过创建密集的低能流形或小的能隙），也会增加熵产生并降低热力学效率。
• 实验与模拟：虽然 D-Wave 设备上的实验结果由于模拟控制误差和退相干而显示出展宽的转变，但编码参数与热力学成本之间的定性相关性依然存在。模拟证实，这些热力学特征与特定的光谱特征（如避免交叉和能级简并）相关联。

意义与主张
本文确立了 QUBO 编码不仅仅是数学预处理步骤，而是一种具有物理后果的设计选择，充当“热力学控制旋钮”。作者主张：

1. 热力学作为诊断工具：热力学可观测量作为一种基于硬件的诊断工具，用于理解为何某些问题编码成功或失败，是对传统运行时指标的补充。
2. 协同设计的必要性：最优编码需要一种协同设计方法，平衡惩罚强度以强制可行性，同时保持相对于热波动和噪声可分辨的有效问题能量尺度。
3. 效率权衡：“过度惩罚”可能会通过隔离理想光谱中的可行流形，同时使其在硬件的噪声采样下难以区分，从而降低解的质量和热力学效率。
4. 操作框架：该研究提供了一个实用框架，将编码空间映射到耗散和效率的热力学相图中，激发了针对 NISQ 退火器的“热力学感知”编码策略。

作者得出结论，支配计算难度的相同编码转变也会重组耗散，这表明最小化功耗散是选择最优编码的一种可行策略。