2.1 TSP实例教学

Ising建模

本篇是基于TSP问题QUBO模型转换的Ising建模教程。

Ising模型定义

1. 变量定义

给定一张有权重的连接图$G(V,E)$，其中$V$是节点的集合，$E$是边的集合。

• 使用 自旋变量$s_{u,j}\in \{-1,1\}$表示节点$u$是否在第$j$个位置被访问：

$$s_{u,j}=\{\begin{array}{ll}1& \text{点 }u\text{ 在第 }j\text{ 个位置被访问}\\ -1& \text{否则}\end{array}$$

• $N=|V|$，表示节点的数量；
• 当两点$(u,v)$间不存在边时，权重为0。

2. 约束条件处理

(a) 节点唯一性约束

每个节点$u$必须唯一对应一个位置$j$，即：

$$\sum _{j=0}^{N-1}{s}_{u,j}=2-N(\mathrm{\forall }u\in 0,\dots ,N-1)$$

转换为Ising模型的能量项：

$$H_1=A\sum _{u=0}^{N-1}{(\sum _{j=0}^{N-1}\frac{1+s_{u,j}}{2}-1)}^2$$

(b) 位置唯一性约束

每个位置$j$必须唯一对应一个节点$u$，即：

$$\sum _{u=0}^{N-1}{s}_{u,j}=2-N(\mathrm{\forall }j\in 0,\dots ,N-1)$$

转换为Ising模型的能量项：

$$H_2=A\sum _{j=0}^{N-1}{(\sum _{u=0}^{N-1}\frac{1+s_{u,j}}{2}-1)}^2$$

(c) 非相邻节点约束

若$(u,v)\notin E$，则$u$和$v$不能连续出现在位置$j$和$j+1$（含循环边界）：

$$H_3=A\sum _{(u,v)\notin E}(\sum _{j=0}^{N-2}\frac{1+s_{u,j}}{2}\cdot \frac{1+s_{v,j+1}}{2}+\frac{1+s_{u,N-1}}{2}\cdot \frac{1+s_{v,0}}{2})$$

3. Ising模型的哈密顿量

总哈密顿量为约束项的加权和：

$$H=H_1+H_2+H_3$$

展开后分为线性项、二次项 和 常数项：

(a) 线性项系数$h_{u,j}$

1）来自节点与位置唯一性约束：

$$h_{u,j}=\frac{A}{2}-\frac{A(N-1)}{4}$$

2）来自非相邻节点约束：

$$h_{u,j}=\frac{A}{4}\sum _{(u,v)\notin E}({\delta }_{j,0}{\delta }_{v,\text{next}(u)}+{\delta }_{j,N-1}{\delta }_{v,0})$$

其中${\delta }_{a,b}$为Kronecker delta函数，$\text{next}(u)$表示与$u$相邻的位置。

(b) 二次项系数$J_{(u,j),(v,k)}$

1）来自节点唯一性约束：

$$J_{(u,j),(u,k)}=\frac{A}{4}(j\ne k)$$

2）来自非相邻节点约束：

$$J_{(u,j),(v,j+1\mathrm{mod}N)}=\frac{A}{4}\text{当 }(u,v)\notin E$$

(c) 常数项

所有常数项合并为$C$，不影响优化结果。

4. 最终Ising模型形式

$$H=\underset{\text{线性项}}{\underbrace{\sum _{u,j}{h}_{u,j}{s}_{u,j}}}+\underset{\text{节点内约束}}{\underbrace{\sum _{u,j\ne k}{J}_{(u,j),(u,k)}{s}_{u,j}{s}_{u,k}}}+\underset{\text{非相邻节点约束}}{\underbrace{\sum _{(u,v)\notin E}\sum _{j=0}^{N-1}{J}_{(u,j),(v,j+1\mathrm{mod}N)}{s}_{u,j}{s}_{v,j+1\mathrm{mod}N}}}+C$$

5. 参数说明

（１）惩罚系数$A$　需足够大以确保约束优先满足（通常远大于目标函数的权重）；

（２）变量范围：$s_{u,j}\in \{-1,1\}$，总变量数为$N^2$；

（３）循环边界：位置索引$j+1\mathrm{mod}N$表示路径的闭环（如TSP问题）。

关键点总结

（１）变量转换：QUBO的$x_{u,j}\in \{0,1\}$映射为Ising的$s_{u,j}\in \{-1,1\}$。

（２）约束映射：

• 唯一性约束通过节点内二次项$s_{u,j}{s}_{u,k}$实现；
• 非相邻节点约束通过跨节点二次项$s_{u,j}{s}_{v,j+1}$实现。

（３）适用场景：可直接用于量子退火机（如D-Wave）或经典优化算法求解组合优化问题（如TSP）。

如需进一步调整参数或验证模型细节，可提供具体图$G$的实例进行数值测试！