量子退火技术中的核心数学工具——二次无约束二元优化（QUBO）模型，常因其抽象性被视为“黑箱”。本文将以图论为桥梁，系统解析QUBO与伊辛模型的数学本质，揭示其如何通过哈密顿能量函数描述组合优化问题。从问题重构中的约束罚项设计，到逻辑量子比特图向物理硬件的子图嵌入，我们将以最小顶点覆盖问题为例，完整展现量子退火从理论建模到硬件执行的跨层实现路径。

图：量子退火器解决问题的工作流

首先，让我们来看看在量子退火器上解决问题的一般工作流程。我们从针对现实场景中的具体问题建立数学模型入手，将其转化为二次无约束二元优化模型（QUBO，后文将详细阐述其数学特性）。通过该模型，将问题映射为图结构，进而将此图结构嵌入量子退火器的物理量子比特连接架构。完成硬件映射后，退火器将执行量子退火过程，最终输出对原始优化问题的优质解。本文后续将深入解析各环节的技术细节，但读者需始终把握这一宏观框架。需要说明的是，本文假设读者已具备量子计算基础知识，建议零基础者先参阅文献[2]的入门指南，其中对量子退火的核心概念有系统阐释，可作为理解本文的前置知识准备。

QUBO基础

量子退火是一种基于量子力学原理的优化算法，其核心目标是通过量子效应寻找编码优化问题的基态（即系统最低能量态），从而获得原问题的最优或近似最优解。该算法由Farhi等人于2000年基于量子绝热定理提出[1]，其数学框架通过构建时变哈密顿量描述系统演化：

其中：

• H_init​为初始哈密顿量，其基态为所有量子比特处于∣0⟩和∣1⟩的叠加态，且易于制备；
• H_final​为问题哈密顿量，其基态对应优化问题的解，但通常未知；
• T为绝热演化总时间，需满足绝热条件以确保系统始终处于瞬时基态。

根据量子绝热定理，当系统以足够缓慢的速率演化（即演化时间T足够长）时，其量子态将始终保持在瞬时基态，最终收敛至终态哈密顿量\( H_{\text{final}} \)的基态，该基态即对应优化问题的最优解^[1-3]。这一过程的可行性取决于系统演化过程中哈密顿量的最小能隙（基态与第一激发态的能量差）：能隙越小，维持绝热条件所需的演化时间T越长。值得注意的是，虽然H_final​的构造在数学上具有明确形式（其基态直接编码优化问题的解），但该基态的具体量子态表征往往难以直接获取，这正是量子退火算法的核心价值所在。

具体而言，系统首先通过初始哈密顿量H_init​制备在易解基态，随后通过参数插值 H(t) = (1-t/T)H_init​+ (t/T)H_final​进行绝热演化。在此过程中，系统需始终维持基态占据，避免向激发态跃迁。理论分析表明，当演化速率满足绝热条件时（即T与最小能隙平方成反比），系统终态将无限逼近H_final​的基态，从而实现对优化问题解的精确提取^[1,2]。

伊辛模型与二次无约束二元优化模型（QUBO）

为了定义我们的问题哈密顿量，我们使用一种二元二次模型，该模型可直接映射到量子处理单元（QPU）的量子比特和耦合器上。构建问题哈密顿量的核心在于建立可直接映射至量子处理单元（QPU）物理架构的数学模型。其中，伊辛模型（Ising Model）作为统计物理中的经典范式，为此提供了重要理论基础。关于伊辛模型的（进阶）介绍，读者可参考文献 [4] 和 [5]。其哈密顿量由下式给出^[6]：

式中，σ_i​,σ_j​∈{−1,+1}表征量子比特的自旋态（分别对应"向上"和"向下"），其拓扑结构由图G(V,E)描述：顶点集V(G)对应量子比特，边集E(G)表征耦合作用。线性系数h_i表征量子比特的局域偏置场（即自旋所受的外部磁场），二次系数J_ij则量化耦合强度（铁磁相互作用时J_ij>0，无耦合时J_ij=0），μ为全局磁场强度参数。需特别指出，哈密顿量的具体形式虽可通过线性变换调整（如文献[7,8]所示），但最优解x*的分布特性保持不变。

伊辛模型采用自旋值 “向上” 和 “向下”（σ_i​,σ_j​∈{−1,+1}），而二次无约束二元优化（QUBO）问题源于计算机科学领域，使用的值为x∈{0,1}（真，假）。在 QUBO 模型中，我们试图最小化以下能量函数：

用矩阵表示法，Q是一个上三角矩阵，对角线上的元素对应线性系数，非零的非对角项对应二次系数。请注意，我们可以通过恒等式σ→2x-1，轻松地将一个伊辛模型问题转化为 QUBO 问题。

问题重构

为构建适用于量子退火器的问题哈密顿量（即目标函数），需采用二元二次模型。此限制源于量子退火硬件的物理架构——其量子比特遵循伊辛模型的自旋交互机制。为具体说明量子退火在组合优化问题中的应用，本文以最小顶点覆盖问题（MVCP）为例展开分析。

最小顶点覆盖问题（MVCP）的定义如下：给定无向图G=(V,E)，顶点覆盖指顶点子集S⊆V，使得图中每条边至少与S中一个顶点相连。MVCP的目标是找到包含最少顶点的覆盖集。定义二元变量x_i表示顶点i是否被选中（x_i=1为选中，x_i=0为未选中）。目标函数需最小化选中顶点总数：

它受限于“每条边都至少与覆盖集中的一个顶点相关联”这一约束条件：
然而，在二次无约束二元优化（QUBO）格式中，不允许存在约束条件，这就是为什么我们要重构我们的问题，需通过罚函数法将约束融入目标函数。具体方法是为每条边引入罚项，其设计原则为：

• 当边(i,j)满足约束（x_i或x_j为1）时，罚项值为0
• 当边(i,j)违反约束（x_i=x_j=0）时，罚项值为正数

对于MVCP，每条边的罚项可构造为(1 - x_i - x_j + x_i x_j)。此表达式在x_i与x_j全为0时取1，其他情况取0^[11]。将全部边的罚项加权求和后加入原目标函数，得到新的无约束优化问题：

对于每条边，如果至少有一端的顶点在覆盖集中（x_i或x_j为1），该罚项将为 0；如果两个关联顶点都不在覆盖集中（x_i和x_j都为0），该罚项为1。这使我们能够将目标函数写成如下形式：

其中λ是一个正的标量罚值，用于对罚项进行加权。现在我们能够写出这个方程，使其与二次无约束二元优化（QUBO）的表示法相似：

 其中m=|E|（|E|表示边集E中边的数量）。请注意，我们可以去掉所加的常数项，因为它对最优解没有影响。这应该能说明，对于最小顶点覆盖问题（MVCP）的一个特定实例，这个方程可以很容易地用QUBO表示法来写。 举个例子，考虑下面这个图：

图：MVCP 示例图（最小顶点覆盖以蓝色标记）

最小顶点覆盖已经用蓝色标记出来了；它由顶点3和顶点5组成。对于这个图的最小顶点覆盖问题建模如下： 

去掉所加的常数项5λ后，我们可以写出我们的QUBO模型，其对应的上对角矩阵Q由下式给出：

 

子图嵌入

在完成伊辛模型或二次无约束二元优化（QUBO）的问题建模后，需将目标函数映射至量子处理单元（QPU）的物理拓扑结构，这一过程称为子图嵌入。具体而言，我们首先将目标函数抽象为逻辑量子比特构成的图结构：设硬件拓扑由顶点集VV与边集EE构成的图G=(V,E)表示，其中顶点对应量子比特，边对应耦合器。目标函数的线性系数（如σ_i​或q_i​i​）映射为图的顶点，代表QPU中的逻辑量子比特；目标函数的二次系数（J_i​j或q_ij）成为图的加权边，这些边反过来代表 QPU 中的耦合器及其耦合强度。以最小顶点覆盖问题（MVCP）为例，其QUBO模型对应的图结构与原问题图完全一致。这种直接对应属于特例，源于问题本身具有图论属性。然而对于一般优化问题，只要可转换为二元二次模型，均可通过上述规则自动生成对应的逻辑量子比特图，无需额外构造图表示。实际嵌入过程需将逻辑量子比特图映射至物理量子比特的硬件拓扑。为明确讨论框架，定义两类关键图结构：

定义（输入图和硬件图）：

• 输入图H：由二元二次模型定义的无向图，顶点代表逻辑量子比特，边表示变量间的耦合关系。
• 硬件图G：量子退火器中物理量子比特的实际连接拓扑，其顶点与边对应芯片上的物理量子比特与耦合器。

图：通过子图嵌入，将表示优化问题的输入图H映射到量子退火器的硬件拓扑图G上

超顶点放置：由于硬件拓扑的限制，输入图中的单个逻辑量子比特可能需要由多个物理量子比特共同表示，这一机制称为超顶点。例如，当输入图HH包含完全连通子图K_3​（三个顶点两两相连）时，麒麟拓扑因缺乏闭环连接能力无法直接嵌入。此时需将多个物理量子比特通过强耦合形成"链"结构，共同表征一个逻辑变量（如图中红色标记的X_4​超顶点）：

图：将最小顶点覆盖问题（MVCP）的QUBO模型通过链式超顶点结构映射至Chimera单元硬件拓扑，利用物理量子比特的强耦合模拟逻辑连接，突破其十字交叉连接模式的固有约束。

这种链式结构通过增强物理量子比特间的耦合强度，确保其行为等价于单一逻辑量子比特，从而突破硬件拓扑的约束，实现任意QUBO问题的有效嵌入。

流程总结

以下为在量子退火器上解决实际问题所需的步骤总结：

1. 首先，明确要解决的问题，明确实际应用场景的具体需求，例如："如何识别通信网络中的核心路由器，确保其覆盖全网连接？"此类问题可抽象为图论中的最小顶点覆盖问题（MVCP）。

2. 随后，将实际问题转化为目标函数的数学表达。若非标准伊辛模型或QUBO形式，需通过约束重构技术（如引入罚函数）进行格式转换，确保低能态对应最优解。

3. 目标函数的线性系数映射为输入图H的顶点，二次系数映射为边权重。该图表征逻辑量子比特的交互关系。。

4. 为了在退火器的量子处理单元（QPU）上求解问题，我们要通过子图嵌入函数\phiϕ，将输入图HH映射至量子退火器的物理拓扑图GG。此过程需处理逻辑量子比特与物理量子比特的多对一映射（即超顶点链技术）。

5. 在实际的退火过程中，量子比特会展现出量子效应。通过相应地改变磁场，问题的目标函数会随时间引入，从而使能量图景能够代表我们的问题。嵌入图的顶点对应量子比特偏置，边对应耦合强度。

6. 最后，量子比特从叠加态坍缩至经典态。量子比特经历量子叠加态至经典态的坍缩，若全程保持基态，则最终态对应全局最优解。为应对误差，需多次重复退火过程。

 

为实现复杂逻辑映射，物理量子比特通过强耦合形成链式结构（超顶点），确保链内所有量子比特在最优解中取值一致。数学上，链定义为硬件图G中互连且不相交的子图，其边表示输入图HH中逻辑量子比特的连接关系。根据图论，当且仅当输入图HH是硬件图GG的子图时，此类属性方可成立^[12]，即要求HH可嵌入G中。

如 [12] 中所讨论的，为任意输入图和任意硬件图找到子图嵌入的问题是 NP 难问题。虽然我们确实考虑了硬件图的固定拓扑结构，但由于工程限制，并非所有的物理量子比特都可用于嵌入，也就是说，并非所有量子比特都能按预期工作，因此有些会被Shutdown。此外，在每次校准阶段之后，不同的量子比特可能无法使用（“损坏”），所以理想的硬件图（如麒麟图等）与用户在嵌入问题时所面对的实际硬件图G是不同的。这就是为什么研究人员 “对那些将G和H都作为输入的 子图嵌入算法感兴趣” ^[13]。正如在 [12] 中所述，我们认为从长远来看，嵌入问题仍然很重要，原因有二：其一，“损坏” 的量子比特数量可能会减少，但不会降至零；其二，目前还看不到完全连通的硬件拓扑结构。

 

---

原文链接：https://dominicplein.medium.com/intro-to-quantum-annealing-660085f4d02e

原文作者：Dominic Plein

翻译润色：鸭鸭哔哔哔

量子退火技术中的核心数学工具——二次无约束二元优化（QUBO）模型，常因其抽象性被视为“黑箱”。本文将以图论为桥梁，系统解析QUBO与伊辛模型的数学本质，揭示其如何通过哈密顿能量函数描述组合优化问题。从问题重构中的约束罚项设计，到逻辑量子比特图向物理硬件的子图嵌入，我们将以最小顶点覆盖问题为例，完整展现量子退火从理论建模到硬件执行的跨层实现路径。

图：量子退火器解决问题的工作流

首先，让我们来看看在量子退火器上解决问题的一般工作流程。我们从针对现实场景中的具体问题建立数学模型入手，将其转化为二次无约束二元优化模型（QUBO，后文将详细阐述其数学特性）。通过该模型，将问题映射为图结构，进而将此图结构嵌入量子退火器的物理量子比特连接架构。完成硬件映射后，退火器将执行量子退火过程，最终输出对原始优化问题的优质解。本文后续将深入解析各环节的技术细节，但读者需始终把握这一宏观框架。需要说明的是，本文假设读者已具备量子计算基础知识，建议零基础者先参阅文献[2]的入门指南，其中对量子退火的核心概念有系统阐释，可作为理解本文的前置知识准备。

QUBO基础

量子退火是一种基于量子力学原理的优化算法，其核心目标是通过量子效应寻找编码优化问题的基态（即系统最低能量态），从而获得原问题的最优或近似最优解。该算法由Farhi等人于2000年基于量子绝热定理提出[1]，其数学框架通过构建时变哈密顿量描述系统演化：

其中：

• H_init​为初始哈密顿量，其基态为所有量子比特处于∣0⟩和∣1⟩的叠加态，且易于制备；
• H_final​为问题哈密顿量，其基态对应优化问题的解，但通常未知；
• T为绝热演化总时间，需满足绝热条件以确保系统始终处于瞬时基态。

根据量子绝热定理，当系统以足够缓慢的速率演化（即演化时间T足够长）时，其量子态将始终保持在瞬时基态，最终收敛至终态哈密顿量\( H_{\text{final}} \)的基态，该基态即对应优化问题的最优解^[1-3]。这一过程的可行性取决于系统演化过程中哈密顿量的最小能隙（基态与第一激发态的能量差）：能隙越小，维持绝热条件所需的演化时间T越长。值得注意的是，虽然H_final​的构造在数学上具有明确形式（其基态直接编码优化问题的解），但该基态的具体量子态表征往往难以直接获取，这正是量子退火算法的核心价值所在。

具体而言，系统首先通过初始哈密顿量H_init​制备在易解基态，随后通过参数插值 H(t) = (1-t/T)H_init​+ (t/T)H_final​进行绝热演化。在此过程中，系统需始终维持基态占据，避免向激发态跃迁。理论分析表明，当演化速率满足绝热条件时（即T与最小能隙平方成反比），系统终态将无限逼近H_final​的基态，从而实现对优化问题解的精确提取^[1,2]。

伊辛模型与二次无约束二元优化模型（QUBO）

为了定义我们的问题哈密顿量，我们使用一种二元二次模型，该模型可直接映射到量子处理单元（QPU）的量子比特和耦合器上。构建问题哈密顿量的核心在于建立可直接映射至量子处理单元（QPU）物理架构的数学模型。其中，伊辛模型（Ising Model）作为统计物理中的经典范式，为此提供了重要理论基础。关于伊辛模型的（进阶）介绍，读者可参考文献 [4] 和 [5]。其哈密顿量由下式给出^[6]：

式中，σ_i​,σ_j​∈{−1,+1}表征量子比特的自旋态（分别对应"向上"和"向下"），其拓扑结构由图G(V,E)描述：顶点集V(G)对应量子比特，边集E(G)表征耦合作用。线性系数h_i表征量子比特的局域偏置场（即自旋所受的外部磁场），二次系数J_ij则量化耦合强度（铁磁相互作用时J_ij>0，无耦合时J_ij=0），μ为全局磁场强度参数。需特别指出，哈密顿量的具体形式虽可通过线性变换调整（如文献[7,8]所示），但最优解x*的分布特性保持不变。

伊辛模型采用自旋值 “向上” 和 “向下”（σ_i​,σ_j​∈{−1,+1}），而二次无约束二元优化（QUBO）问题源于计算机科学领域，使用的值为x∈{0,1}（真，假）。在 QUBO 模型中，我们试图最小化以下能量函数：

用矩阵表示法，Q是一个上三角矩阵，对角线上的元素对应线性系数，非零的非对角项对应二次系数。请注意，我们可以通过恒等式σ→2x-1，轻松地将一个伊辛模型问题转化为 QUBO 问题。

问题重构

为构建适用于量子退火器的问题哈密顿量（即目标函数），需采用二元二次模型。此限制源于量子退火硬件的物理架构——其量子比特遵循伊辛模型的自旋交互机制。为具体说明量子退火在组合优化问题中的应用，本文以最小顶点覆盖问题（MVCP）为例展开分析。

最小顶点覆盖问题（MVCP）的定义如下：给定无向图G=(V,E)，顶点覆盖指顶点子集S⊆V，使得图中每条边至少与S中一个顶点相连。MVCP的目标是找到包含最少顶点的覆盖集。定义二元变量x_i表示顶点i是否被选中（x_i=1为选中，x_i=0为未选中）。目标函数需最小化选中顶点总数：

它受限于“每条边都至少与覆盖集中的一个顶点相关联”这一约束条件：
然而，在二次无约束二元优化（QUBO）格式中，不允许存在约束条件，这就是为什么我们要重构我们的问题，需通过罚函数法将约束融入目标函数。具体方法是为每条边引入罚项，其设计原则为：

• 当边(i,j)满足约束（x_i或x_j为1）时，罚项值为0
• 当边(i,j)违反约束（x_i=x_j=0）时，罚项值为正数

对于MVCP，每条边的罚项可构造为(1 - x_i - x_j + x_i x_j)。此表达式在x_i与x_j全为0时取1，其他情况取0^[11]。将全部边的罚项加权求和后加入原目标函数，得到新的无约束优化问题：

对于每条边，如果至少有一端的顶点在覆盖集中（x_i或x_j为1），该罚项将为 0；如果两个关联顶点都不在覆盖集中（x_i和x_j都为0），该罚项为1。这使我们能够将目标函数写成如下形式：

其中λ是一个正的标量罚值，用于对罚项进行加权。现在我们能够写出这个方程，使其与二次无约束二元优化（QUBO）的表示法相似：

 其中m=|E|（|E|表示边集E中边的数量）。请注意，我们可以去掉所加的常数项，因为它对最优解没有影响。这应该能说明，对于最小顶点覆盖问题（MVCP）的一个特定实例，这个方程可以很容易地用QUBO表示法来写。 举个例子，考虑下面这个图：

图：MVCP 示例图（最小顶点覆盖以蓝色标记）

最小顶点覆盖已经用蓝色标记出来了；它由顶点3和顶点5组成。对于这个图的最小顶点覆盖问题建模如下： 

去掉所加的常数项5λ后，我们可以写出我们的QUBO模型，其对应的上对角矩阵Q由下式给出：

 

子图嵌入

在完成伊辛模型或二次无约束二元优化（QUBO）的问题建模后，需将目标函数映射至量子处理单元（QPU）的物理拓扑结构，这一过程称为子图嵌入。具体而言，我们首先将目标函数抽象为逻辑量子比特构成的图结构：设硬件拓扑由顶点集VV与边集EE构成的图G=(V,E)表示，其中顶点对应量子比特，边对应耦合器。目标函数的线性系数（如σ_i​或q_i​i​）映射为图的顶点，代表QPU中的逻辑量子比特；目标函数的二次系数（J_i​j或q_ij）成为图的加权边，这些边反过来代表 QPU 中的耦合器及其耦合强度。以最小顶点覆盖问题（MVCP）为例，其QUBO模型对应的图结构与原问题图完全一致。这种直接对应属于特例，源于问题本身具有图论属性。然而对于一般优化问题，只要可转换为二元二次模型，均可通过上述规则自动生成对应的逻辑量子比特图，无需额外构造图表示。实际嵌入过程需将逻辑量子比特图映射至物理量子比特的硬件拓扑。为明确讨论框架，定义两类关键图结构：

定义（输入图和硬件图）：

• 输入图H：由二元二次模型定义的无向图，顶点代表逻辑量子比特，边表示变量间的耦合关系。
• 硬件图G：量子退火器中物理量子比特的实际连接拓扑，其顶点与边对应芯片上的物理量子比特与耦合器。

图：通过子图嵌入，将表示优化问题的输入图H映射到量子退火器的硬件拓扑图G上

超顶点放置：由于硬件拓扑的限制，输入图中的单个逻辑量子比特可能需要由多个物理量子比特共同表示，这一机制称为超顶点。例如，当输入图HH包含完全连通子图K_3​（三个顶点两两相连）时，麒麟拓扑因缺乏闭环连接能力无法直接嵌入。此时需将多个物理量子比特通过强耦合形成"链"结构，共同表征一个逻辑变量（如图中红色标记的X_4​超顶点）：

图：将最小顶点覆盖问题（MVCP）的QUBO模型通过链式超顶点结构映射至Chimera单元硬件拓扑，利用物理量子比特的强耦合模拟逻辑连接，突破其十字交叉连接模式的固有约束。

这种链式结构通过增强物理量子比特间的耦合强度，确保其行为等价于单一逻辑量子比特，从而突破硬件拓扑的约束，实现任意QUBO问题的有效嵌入。

流程总结

以下为在量子退火器上解决实际问题所需的步骤总结：

1. 首先，明确要解决的问题，明确实际应用场景的具体需求，例如："如何识别通信网络中的核心路由器，确保其覆盖全网连接？"此类问题可抽象为图论中的最小顶点覆盖问题（MVCP）。

2. 随后，将实际问题转化为目标函数的数学表达。若非标准伊辛模型或QUBO形式，需通过约束重构技术（如引入罚函数）进行格式转换，确保低能态对应最优解。

3. 目标函数的线性系数映射为输入图H的顶点，二次系数映射为边权重。该图表征逻辑量子比特的交互关系。。

4. 为了在退火器的量子处理单元（QPU）上求解问题，我们要通过子图嵌入函数\phiϕ，将输入图HH映射至量子退火器的物理拓扑图GG。此过程需处理逻辑量子比特与物理量子比特的多对一映射（即超顶点链技术）。

5. 在实际的退火过程中，量子比特会展现出量子效应。通过相应地改变磁场，问题的目标函数会随时间引入，从而使能量图景能够代表我们的问题。嵌入图的顶点对应量子比特偏置，边对应耦合强度。

6. 最后，量子比特从叠加态坍缩至经典态。量子比特经历量子叠加态至经典态的坍缩，若全程保持基态，则最终态对应全局最优解。为应对误差，需多次重复退火过程。

 

为实现复杂逻辑映射，物理量子比特通过强耦合形成链式结构（超顶点），确保链内所有量子比特在最优解中取值一致。数学上，链定义为硬件图G中互连且不相交的子图，其边表示输入图HH中逻辑量子比特的连接关系。根据图论，当且仅当输入图HH是硬件图GG的子图时，此类属性方可成立^[12]，即要求HH可嵌入G中。

如 [12] 中所讨论的，为任意输入图和任意硬件图找到子图嵌入的问题是 NP 难问题。虽然我们确实考虑了硬件图的固定拓扑结构，但由于工程限制，并非所有的物理量子比特都可用于嵌入，也就是说，并非所有量子比特都能按预期工作，因此有些会被Shutdown。此外，在每次校准阶段之后，不同的量子比特可能无法使用（“损坏”），所以理想的硬件图（如麒麟图等）与用户在嵌入问题时所面对的实际硬件图G是不同的。这就是为什么研究人员 “对那些将G和H都作为输入的 子图嵌入算法感兴趣” ^[13]。正如在 [12] 中所述，我们认为从长远来看，嵌入问题仍然很重要，原因有二：其一，“损坏” 的量子比特数量可能会减少，但不会降至零；其二，目前还看不到完全连通的硬件拓扑结构。

 

---

原文链接：https://dominicplein.medium.com/intro-to-quantum-annealing-660085f4d02e

原文作者：Dominic Plein

翻译润色：鸭鸭哔哔哔