Tensor-Network Formulation of the Traveling Salesman Problem and Variants

本文提出了一种针对旅行商问题及其变体的张量网络表述，该方法利用玻尔兹曼加权层和计数滤波器，通过序贯边际规则识别最优路径，旨在作为小规模工业应用的启发式方法，而非作为优于专用经典求解器的替代方案。

要点

以下是用通俗语言和创意类比对该论文的解读。

宏观视角：用新型计算器解决“旅行商”难题

想象你是一名旅行推销员。你有一张包含 10 个、20 个甚至 100 个城市的地图。你需要访问每一个城市恰好一次，然后返回起点，但你希望以最短的距离完成，从而节省燃油和时间。这就是著名的旅行商问题（TSP）。

问题在于，随着城市数量的增加，可能的路线数量呈爆炸式增长。这就像试图在一堆钥匙中找到完美的那一把，而这堆钥匙的增长速度如此之快，以至于检查每一把钥匙所需的时间将超过宇宙的年龄。这就是计算机难以应对它的原因。

本文介绍了一种利用张量网络（Tensor Networks）解决该问题的新方法。不要将张量网络视为计算机程序，而要将其想象为一个巨大的、多层级的过滤系统。

类比：“金尘”筛子

想象你有一大袋混合了金粉的沙子。

• 沙子：代表所有糟糕、漫长且低效的路线。
• 黄金：代表完美、最短的路线。
• 目标：你希望在不逐一查看每一粒沙子的情况下，将黄金从沙子中分离出来。

作者构建了一台机器（即张量网络）来完成这项工作：

1. 初始混合（叠加态）：首先，机器创建一个“叠加态”。想象它神奇地同时生成了所有可能的路线的副本。这就像拥有百万个不同版本的自己，每个版本都走不同的路径。
2. 加权（热度）：接下来，机器施加一个“温度”（称为 $\tau$）。将其想象成一盏加热灯。
   • 那些漫长、低效的路线（沙子）会变热并转化为光，逐渐消散。
   • 那些短小、高效的路线（黄金）保持凉爽且沉重。
   • 机器利用数学（玻尔兹曼因子）使糟糕的路线比好的路线消失得更快。
3. 过滤器（规则）：这是最重要的部分。你不能拥有任意路线；你不能重复访问同一个城市。作者构建了特殊的计数过滤器。
   • 想象每个城市都有一名保安。如果旅行者试图访问一个已经去过的城市，保安就会将那特定路线的大门砰地关上。
   • 这些过滤器是“稀疏”的，意味着它们非常高效地阻挡错误路径，而无需手动检查每一个可能性。
4. 结果（边缘分布）：在经过热力和过滤器的作用后，机器将所有内容压缩。它问道：“如果我看第一个城市，哪一个最有可能成为获胜路线的一部分？”它选定那个城市，将其锁定，然后对第二个城市重复此过程，依此类推，直到构建出整条路线。

他们实际做了什么（实验）

作者并未声称这种方法是一个能瞬间解决所有问题的灵丹妙药。他们非常诚实地指出了其局限性。

• 小型测试：他们在小型地图（5 到 12 个城市）上测试了他们的方法。
• 校准：他们发现“温度”设置（$\tau$）至关重要。如果太低，糟糕的路线无法充分消散；如果太高，计算机会被微小的数学误差搞糊涂。他们必须针对每种地图大小仔细调整此设置。
• 结果：
  • 当他们完美调整设置时，在这些小型地图上，他们的方法在约95%的情况下找到了完美路线。
  • 当他们将其与标准计算机方法（如“贪婪”或“模拟退火”）进行比较时，他们的方法在寻找完美路线方面往往更胜一筹。
  • 然而，他们承认，对于非常大的地图，数学计算仍然变得过于沉重（指数级复杂度），就像旧方法一样。这并非“多项式时间”的奇迹；它只是一种不同的、结构化的数学运算方式。

现实世界测试：工作重新分配问题

为了验证该方法在理论之外是否有效，他们将其应用于ONCE（西班牙盲人组织）的一个实际工业问题。

• 问题：他们有一些被分配到工作的员工和一些空缺的工作岗位。他们需要判断将一名员工调动到新岗位是否能使整个团队的生产力更高。
• 转折：这并不完全是一个“旅行”问题，但很相似：你必须将独特的岗位分配给独特的人，而不能重复预订。
• 结果：他们将张量网络方法与另外两种强大的工具（量子退火器和数字退火器）进行了比较。
  • 在总生产力增益方面，结果完全相同。
  • 唯一的区别在于“平局打破”的情况，即两个选项在数学上完全相等时；机器只是随机选择了不同的选项。
  • 结论：这证明了他们的方法在现实世界中是可行的，并且可以集成到工业软件中，即使它在此特定任务上并未击败专用工具。

核心结论

本文提出了一套用于解决路由和分配难题的新数学工具包。

• 优点：它提供了一种非常清晰、模块化的方式来处理复杂规则（如“不要重复访问同一个城市”），并且可以在小型问题上找到完美解。这就像拥有一位高度组织化、遵守规则的助手，它从不厌倦检查约束条件。
• 缺点：它不会神奇地让巨大的问题变得容易。随着问题规模的扩大，数学计算仍然会呈指数级变难。它需要仔细调整（校准）才能有效工作。
• 启示：这是一种思考这些问题的强大新方式，也是针对特定、小规模工业任务的可靠工具，但它目前还不足以取代所有现有的超快速求解器。

简而言之：他们构建了一个精密的筛子，可以过滤掉糟糕的路线并找到最佳路线，但你仍然需要输入正确的设置才能获得黄金。

技术摘要

技术摘要：旅行商问题及其变体的张量网络表述

问题定义
本文探讨了旅行商问题（TSP）及其若干推广形式，包括时间相关 TSP（TDTSP）、工作重分配问题（JRP），以及涉及非重复约束、优先规则、组约束和瓶颈目标的变体。TSP 被定义为寻找访问 $N$ 个节点各一次并返回起点的最短路径，这是一个已知的 NP 难问题。尽管存在 Held-Karp（$O(N^2 2^N)$）和分支定界等精确算法，但它们面临指数级复杂度，限制了其在工业案例中的可扩展性。相反，启发式方法（如遗传算法、局部搜索）提供近似解，但不保证最优性。作者指出，新兴的量子算法（QAOA、VQE）目前受限于硬件噪声（NISQ 时代），这促使人们探索模仿量子系统特性的经典技术。

方法论
核心贡献是一种张量网络（TN）表述，将候选路径表示为张量积空间中的状态。该方法通过三种主要机制运作：

1. 张量网络构建：

   • 初始化（'+'）： 为每个时间步创建所有可能节点分配的均匀叠加态。
   • 优化（'S'）： 应用虚时演化算符 $U = e^{-\tau C(\vec{y})}$，其中 $\tau$ 为阻尼因子，$C(\vec{y})$ 为路径成本。这指数级地抑制高成本配置，类似于在量子系统中寻找基态。
   • 约束过滤（'F'）： 引入矩阵乘积算符（MPO）层以强制执行约束。对于标准 TSP，这些层作为计数过滤器，确保每个节点恰好出现一次。过滤器利用二元键索引来跟踪特定节点是否已被访问，有效地实现了 Levi-Civita 符号约束 $|\epsilon_{y_0, \dots, y_{\hat{N}-1}}|^2$。
   • 提取（'+'）： 迹层对振幅求和以产生边缘权重。

2. 顺序边缘提取：
   解是迭代提取的。对于固定的路径前缀，算法计算下一个位置每个候选节点 $a$ 的边缘权重 $Z_p(a; \tau)$。在 $\tau \to \infty$ 且算术精确的极限下，最大化该权重的节点保证属于最优路径（命题 3.2）。算法选择最大化节点，更新前缀，并重复此过程直到路径完成。

3. 推广：
   该框架通过修改过滤器和演化层以适应各种 TSP 变体：

   • DNSNN（不同步数/节点数）： 过滤器允许节点出现 $N^0$ 到 $N^f$ 次。
   • NMTSP（非马尔可夫）： 使用高阶 MPO 处理依赖于前 $K$ 步的成本。
   • BTSP（瓶颈）： 用跟踪遇到的最大边成本的层替换成本演化。
   • PTSP（组约束）： 过滤器强制每类恰好访问一个节点。
   • TSPP（优先）： 局部投影子在其所需的前驱尚未出现时抑制节点。
   • JRP（工作重分配）： 建模为线性分配问题，其中“不移动”状态可重复，而特定空缺是唯一的。

4. 近似与复杂度：
   完整张量网络的精确收缩是指数级的，对于稠密逐层收缩，其规模约为 $O(\hat{N}^4 2^{\hat{N}})$。为了解决更大规模的问题，作者提出：

   • 层消融： 仅应用约束层的子集以降低复杂度，将结果视为启发式方法。
   • 稀疏 - 局部收缩： 利用局部过滤器张量的确定性稀疏特性，在不改变指数级缩放的情况下降低多项式前因子（例如，从 $O(\hat{N}^4 2^{\hat{N}})$ 降至 $O(\hat{N}^3 2^{\hat{N}})$）。
   • 有限-$\tau$ 启发式： 使用有限精度和有限 $\tau$ 来近似零温极限，承认数值对比度和简并性会影响解的质量。

主要贡献

• 显式边缘公式： 推导了一个张量网络边缘方程，其零温、精确算术极限通过顺序边缘规则识别最优可行路径。
• 约束编码： 定义了适用于各种组合问题的计数约束（非重复）MPO 层。
• 推广框架： 一种模块化构建，通过改变特定张量层，将 TN 形式化适应于 TSP 变体（TDTSP、JRP、BTSP 等）。
• 启发式实现： 一种有限精度、有限-$\tau$ 的实现，作为校准启发式方法运行，并分析了其在数值对比度和简并性方面的行为。

结果
实验研究侧重于小型合成实例（$N \in \{5, \dots, 12\}$），以验证方法的正确性和数值行为，而非声称在计算上优于专用求解器。

• 校准： 虚时参数 $\tau$ 依赖于规模。校准扫描（$\tau \in \{1, \dots, 40\}$）将评估集上的最优解率从 55.56%（在 $\tau=1$ 时）显著提高到 95.56%。
• 求解器比较： 在小型实例上，校准后的 TN 求解器达到了 95.24% 的最优率，优于 NetworkX 贪婪算法（26.67%）和模拟退火（59.05%），但不及精确 Held-Karp 参考（100%）。
• 层消融： 移除约束层降低了解的质量，证实了完整的过滤器集对于高精度是必要的。
• 工业案例（JRP）： 在 ONCE 工作重分配问题的概念验证中，TN 方法产生的解具有与 Azure 数字退火器相同的累积成本，仅在存在多个最优分配的简并情况下有所不同。

意义与主张
作者明确对该方法的计算能力表示谦逊。他们不声称在通用 TSP 方面具有超越专用经典求解器（如 Held-Karp、分支切割或特定分配算法）的通用计算优势。

• 形式化表述： 该工作被呈现为“形式化的精确算术指数时间表述”以及“受控近似和扩展的平台”。
• 启发式性质： 有限-$\tau$ 实现被描述为“校准的有限精度启发式方法”，其行为取决于数值对比度和简并性。
• 效用： 主要价值在于模块化的张量网络框架，它允许在统一形式化内系统地整合各种约束（优先、组、非马尔可夫成本）并应用近似技术（层移除、稀疏收缩）。
• 局限性： 该方法在最坏情况下仍保留指数级缩放。数值稳定性问题（下溢、简并情况下的对比度丢失）以及对规模依赖校准的需求被确定为重大局限性。

总之，本文提供了 TSP 及其变体的严格张量网络形式化，展示了其在小型实例上恢复最优解的能力以及整合工业约束的能力，同时承认它并未克服该问题的根本指数级复杂度。