⚛️ 量子物理

Solving the traveling salesman problem on $\lceil \log_2 (N-1)! \rceil$ qubits with a variational quantum Kolmogorov--Arnold network: exact-gradient CVaR training and generalization over time-dependent graphs

本文证明了通过使用精确梯度 CVaR 和盆地跳跃重启训练的变分量子 Kolmogorov–Arnold 网络，仅需 $\lceil \log_2 (N-1)! \rceil$ 个量子比特即可解决时变图上的旅行商问题，在处理多达十个站点的场景下实现了最优解，并与传统的独热编码相比显著降低了对量子比特的需求。

原作者： Hikaru Wakaura

发布于 2026-10-15

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Hikaru Wakaura

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一位必须按顺序访问列表中的每座城市一次并返回出发地，且目标是行驶最短距离的送货司机。这就是旅行商问题（Traveling Salesman Problem），一个处于物流、调度和电路设计核心的经典谜题。虽然寻找几个城市的完美路线很容易，但随着城市数量的增加，难度会呈爆炸式增长；每增加一座城市，可能路径的数量就会迅速倍增，以至于即使是最快的超级计算机也会在试图寻找最优解时陷入困境。几十年来，科学家们一直寻求利用量子计算机——利用亚原子粒子的奇特规则来处理信息的机器——来更快地解决这些难题。然而，一个主要的障碍始终存在：如何将问题转化为量子计算机能够理解的语言，而不至于让计算过程淹没在误差和不必要的复杂性之中。

QuantScape Inc. 的一名研究人员现在展示了一种引导量子计算机穿过这一迷宫的新方法，成功找到了包含多达十座城市的地图的最短路径。这项工作依赖于对量子硬件的模拟，而非物理机器，它引入了一种比以往方法使用更少量子比特（量子计算机的基本信息单位）的方法。更重要的是，它表明一套指令可以适应不断变化的路况，例如全天变化的交通状况，而无需针对每个新场景进行重新训练。结果表明，通过正确的编码和训练技术，量子计算机很快就能应对目前仍难以触及的优化问题，前提是硬件能够持续改进。

挑战的核心在于如何为机器编写该问题。传统方法为路径中城市与位置的每种可能组合都分配一个独立的量子比特。对于一张包含十座城市的地图，这种方法需要 81 个比特，并且迫使计算机不断检查并丢弃无效路径，从而在惩罚项上浪费时间和能量。这项新研究使用了一种不同的策略，灵感来自一种被称为“莱默码”（Lehmer code）的数学系统，它本质上是根据列表中的顺序对每条可能的路径进行排名。这种方法对于十座城市仅需 19 个比特，实现了显著的缩减。通过使用这种紧凑的代码，量子计算机的每一个状态都代表一条有效的路径，从而消除了对惩罚检查的需求。为了使搜索变得高效，研究人员对这些状态进行了排列，使得代码中单个比特的翻转对应于路径中一个微小且逻辑性的变化，从而允许计算机平滑地探索解空间。

为了引导量子计算机，研究人员采用了一种名为“变分量子柯尔莫哥洛夫-阿诺德网络”（variational quantum Kolmogorov–Arnold network）的混合系统。可以将它想象成一个智能控制器，它观察地图和时间，然后调整量子电路的旋钮至正确位置。该控制器并非为每张特定的地图硬编码设置，而是学习一种通用规则：如何根据城市间的距离和当前时间来调整电路。这使得该系统能够处理随时间变化的图（time-dependent graphs），例如电力网或存在高峰时段交通的道路网络。控制器的训练目标非常明确：最小化选择长路径的风险。与其仅仅寻找绝对平均长度，训练重点在于那些位于最可能结果前百分之几中的最坏情况，从而确保最终结果具有鲁棒性和可靠性。

训练过程本身非常严苛，旨在避免常见的陷阱——即陷入局部极小值（即计算机停留在“足够好”的答案而非最优解处）。研究人员采用了多步策略，从广泛搜索开始，逐渐缩小关注范围，并结合了一种通过刻意“扰动”设置来跳出死胡同的技术。他们还使用了一种称为“盆地跳跃”（basin hopping）的方法，这就像是一次轻微的摇晃，帮助系统从搜索景观中的浅谷中跳出。在针对四到十座城市的地图（包括对称形状和随机、不规则的网络）进行测试时，这种方法在较小的地图中每次都找到了完美路径。对于难度显著增加的十座城市地图，该方法在 120 次试验中成功找到了最优路径 112 次，其余失败案例与完美距离的差距也仅为 1%。

至关重要的是，该研究排除了几种看似有前景的替代方案。研究人员测试了一种仅使用十个比特（每个城市一个，用于追踪驾驶员的步骤进度）的更简单方法，但该方法在处理六个或更多城市的地图时完全失效，因为它无法表示连续停靠点之间的复杂关系。他们还将结果与一种被称为 2-opt 的标准经典算法进行了对比，该算法通过交换两个路段来优化路径。虽然 2-opt 非常有效，但量子电路提供了更好的初始起点，且两者的结合优于任何单一方法。研究证实，成功归功于问题编码的具体方式以及对控制器的复杂训练，而不仅仅是依靠量子电路本身的威力。

研究结果还强调了该方法在测量方面的效率。在真实的量子计算机中，读取答案需要重复多次过程以获得清晰信号。模拟显示，即使只有一百次读取，系统也能可靠地识别出最佳路径。这表明，当具备足够比特数的物理量子计算机问世时，该方法可以快速交付结果，而不需要进行数百万次重复。研究人员指出，虽然目前的工作是在模拟量子行为的经典计算机上完成的，但这些技术旨在适用于实际硬件。接下来的步骤包括在真实机器的噪声条件下测试该系统，并将其规模扩大到那些可能的路径数量庞大到无法手工检查的更大规模地图。

这项工作代表了使量子优化走向实用的重要一步。通过解决编码问题并创建了一个能够跨不同地图和时间进行泛化的控制器，研究人员展示了一条高效解决复杂路由问题的路径。能够通过单一参数处理随时间变化的动态变化，对于现实世界中条件永不静止的应用场景而言尤其具有前景。尽管通往全功能量子优化器的旅程仍在继续，但这项研究为如何训练这些机器在复杂世界中找到最短路径提供了清晰的蓝图。

技术摘要：利用 Lehmer 码 VQKAN 解决旅行商问题 (TSP)

问题陈述
旅行商问题 (TSP) 是一个基础的 NP-hard 组合优化问题。虽然精确的经典方法随规模呈指数级增长，但变分量子算法 (VQA) 为嘈杂中型量子 (NISQ) 设备提供了一条潜在路径。然而，标准的 TSP 量子编码面临着显著障碍：

独热编码 (One-hot encoding)： 对于 $N$ 个站点，需要 $(N-1)^2$ 个量子比特。大多数基态都是无效的（不是巡回路径），这需要惩罚项来主导代价景观，且难以调节。
二进制编码 (Binary encoding)： 将量子比特数减少到 $(N-1)\lceil \log_2 N \rceil$ ，但仍会留下需要惩罚或修复的无效字符串。
置换编码 (Lehmer code)： 通过排列中的秩来标记巡回路径，仅需 $n = \lceil \log_2(N-1)! \rceil$ 个量子比特。至关重要的是，每个基态都对应一个有效的巡回路径，从而消除了对惩罚项的需求。然而，以往使用这种编码的变分求解器由于缺乏秩景观的局部性以及成功率的崩溃，在规模超过六个站点时表现不佳。

方法论
作者提出了一种结合紧凑型 Lehmer 码编码、变分量子 Kolmogorov–Arnold 网络 (VQKAN) 以及专门训练方案的流水线。

编码与读取：
- 巡回路径由存储在 $n = \lceil \log_2(N-1)! \rceil$ 个量子比特中的 Lehmer 码表示。
- 为了解决秩景观的非局部性，从量子比特中读取的整数被解释为二进制反射格雷码 (binary-reflected Gray code)。这确保了通过单比特翻转差异化的状态对应于连续的 Lehmer 码，而后者仅在最后访问站点的顺序上有所不同。
- 电路是一个浅层的、硬件高效的拟设 (ansatz)（深度 $d=2$ ），由单量子比特 $R_y$ 旋转和最近邻 $CZ$ 门组成。
VQKAN 角度生成：
- 并非直接为每个实例优化电路角度，而是通过 VQKAN 生成旋转角度。
- 每个角度是输入特征的、可学习的二次样条函数，输入特征包括时间 $t$ 和距离矩阵 $D$ 的特征（具体为距离矩阵行平均值除以其最大值进行归一化）。
- 这使得一组参数集可以推广到距离随时间变化的图族（例如交通或电网路由），从而消除了针对每个实例重新训练的需求。
损失函数与训练：
- 电路旨在最小化巡回路径长度的条件风险价值 (CVaR)。CVaR 将概率质量集中在最短的巡回路径上，使优化目标与“最佳采样 (best-of-shots)”读取策略保持一致。
- 使用伴随法 (adjoint method) 精确计算梯度（因为电路使用实数振幅，该方法是可行的）。
- 优化器采用了四种特定策略来应对 CVaR 景观并避免局部极小值：
  - 多起点 (Multi-start)： 从不同的随机种子开始进行多次独立的运行。
  - 风险水平调度 (Risk-level schedule)： 一种课程学习方法，从 $\alpha=0.5$ 开始并逐渐降低到 $\alpha=0.02$ ，在早期平滑景观，在后期集中于最优解。
  - 小角度初始化 (Small-angle initialization)： 参数初始化在恒等映射附近，以避免贫瘠高原 (barren plateaus)。
  - 盆地跳跃重启 (Basin-hopping restarts)： 在收敛后，对参数进行扰动并重新优化，以逃离残余的局部极小值。
读取与后处理：
- 对状态进行 $M$ 次采样（例如 $10^2$ 到 $10^5$ 次采样）。返回最短的采样巡回路径。
- 可选的经典后处理对前 20 个采样巡回路径应用 2-opt 以精细化解。

关键结果
该方法在 $N=4, 6, 8, 10$ 的对称多边形和非对称随机图上进行了评估。

成功率： 全功能优化器（包含所有训练策略）在三轮协议下，对于 $N=4$ 到 $10 $的所有情况均返回了最优巡回路径（36/36 次成功）。在更严格的$ N=10$ 轮三十次重复实验中，它在 120 次中实现了 112 次最优（93.3%），其余失败案例也都在最优长度的 1% 以内。
量子比特效率： 对于 $N=10$ ，该方法使用 19 个量子比特，而独热编码需要 81 个。
测量效率： 最优巡回路径仅需 $10^2$ 次测量采样即可找到。在 $N=10$ 时，未能找到最优解的原因是状态矢量本身不包含最优巡回路径（训练限制），而非采样噪声。
泛化能力： 在时间依赖图中，仅在距离特征和时间上训练的网络成功推广到了未见的时间点，而仅在时间上训练的网络无法实现有效插值。
消融研究：
- 盆地跳跃 (Basin hopping) 被确定为消除 $N=10$ 时残余局部极小值的关键组件。
- 更深的电路 (Deeper circuits)（深度 4）并未比深度 2 的电路提升性能，反而需要显著更多的参数。
- 格雷码读取 (Gray code read-out) 和距离特征 (distance features) 对于高成功率和泛化能力至关重要。
- 经典控制： 一个“ $N$ 量子比特独热行走 (N-qubit one-hot walk)”（使用 $N$ 个量子比特逐步移动销售商）在 $N \ge 6$ 时无法找到有效的巡回路径，证实了 $N$ 个量子比特不足以表示巡回路径的分布。经过训练的电路表现优于从随机巡回路径开始的 2-opt。

意义与主张
本文声称解决了置换编码 TSP 求解器的优化瓶颈，此类求解器此前在超过六个站点时表现不佳。通过将量子比特高效的 Lehmer 码与能够学习从图特征到电路参数映射的 VQKAN 相结合，作者展示了：

可扩展性： 使用比标准编码显著更少的量子比特，可靠地解决高达 $N=10$ 的 TSP 实例。
泛化性： 能够通过单一参数集处理时间依赖图，避免了针对特定实例的重新训练。
优化策略： 明确了特定的优化组件（盆地跳跃、风险水平调度）对于克服置换秩的非局部景观是必要的。

作者明确指出，虽然模拟验证了该编码和优化器的可行性，但尚未展示其相对于大规模 $N$ 下最先进经典启发式算法的量子优势，也未考虑梯度估计中的采样噪声。这项工作是针对 NISQ 硬件上扩展置换编码 VQA 的概念验证。

类似论文