神经网络增强的MCTS优化量子退火，腾讯量子研究成果登Nature子刊|mcts|神经网络|算法|量子

近日，腾讯量子实验室在《Nature Machine Intelligence》上发表了 AI + 量子的最新研究成果《Optimizing quantum annealing schedules with Monte Carlo tree search enhanced with neural networks》，提出一种蒙特卡洛树搜索（MCTS）算法及其由神经网络增强的增强版本——将其命名为 QuantumZero (QZero)——在混合量子-经典框架中自动设计退火 schedule。

论文链接：https://www.nature.com/articles/s42256-022-00446-y

对于本研究中考虑的 3-SAT 示例，即使在退火时间很短的情况下，MCTS 和 QZero 算法在发现有效退火计划方面也表现出色。此外，神经网络的灵活性使我们能够应用迁移学习技术来提高 QZero 的性能。在基准研究中证明 MCTS 和 QZero 在设计退火计划时比其他强化学习算法更有效。

量子技术的发展及挑战

在过去的 20 年里，量子技术一直在以令人难以置信的速度发展。显著的成就包括使用量子退火器实现绝热量子算法。与工业相关的应用，例如各种约束优化问题、整数分解、量子模拟和量子机器学习，都已通过实验证明。

尽管取得了这些初步成功，但要使用量子退火器进行大规模计算，仍有许多工作要做。特别是，量子位之间更好的连通性、误差和噪声抑制、工程非随机哈密顿量以及退火时间表的优化是绝热量子计算 (AQC) 面临的一些紧迫挑战。

量子退火是一种在现实环境中近似实现绝热量子计算模型的实用方法。绝热算法的目标是在退火路径的末端准备问题编码哈密顿量的基态。这通常是通过缓慢驱动量子系统的动态演化以增强绝热性来实现的。适当优化的退火 schedule 通常会大大加快计算过程。

受深度强化学习（例如 DeepMind 的 AlphaZero）成功的启发，通过提出使用蒙特卡洛树搜索（MCTS）的退火 schedule 的自动化设计来解决这些挑战之一，其增强版本——QuantumZero（QZero）结合了神经网络以进一步提高性能。

量子退火 schedule 作为最优控制问题

研究人员首先介绍了 AQC 模型的基本背景，并阐明了如何在 RL 框架下自动化退火时间的设计。接下来，提出了一个受约束的优化问题，3-SAT，用于在这项工作中对算法进行基准测试。

量子退火器通常用于解决 AQC 框架下的问题，该框架将问题的解决方案与问题编码的哈密顿量 Hfinal 的基态联系起来。准备任意哈密顿量的基态不是一项简单的任务。

在这项工作中，研究人员提出了一个混合量子经典框架，利用强化学习（部分受到 MCTS 和 AlphaZero 的启发）来设计最优 schedule s(t)。

图 1：设计退火计划的混合量子-经典框架。（来源：论文）

简而言之，研究人员使用候选 schedule s(t) 运行量子退火实验，并将结果反馈给基于 MCTS 的代理，以迭代方式调整和识别更好的退火 schedule。

在这项工作中，使用 3-SAT 问题来对算法进行基准测试。这是一个非确定性多项式问题的典型例子。

实验结果

接下来，研究人员描述了几个数值实验来说明所提方法的优势。

MCTS 设计的退火 schedule

以 3-SAT 为例，解释了基于 MCTS 的退火 schedule 自动化设计。蒙特卡罗树搜索对于解决高维优化问题非常有效。

图 2：MCTS 的设置。（来源：论文）

在这项工作中，主要关注频域中 s(t) 的设计。

根据以上等式，目标是选择一个序列 {x1, x2, x3 ... xM}（其中 xi 是控制参数）以最小化在退火路径末端相对于 Hfinal 的能量。

在图 3a 中，展示了在不同 T 下求解相同结构（n=11 和 m=33）的 3-SAT 实例的示例的成功概率。

图 3：解决几个具有不同结构的 3-SAT 实例的成功概率。（来源：论文）

SD（随机下降）单次运行需要对量子退火器进行大约 100 次查询以进行能量反馈，而 MCTS 的一集大约需要 50 次这样的查询。因此，为了公平比较对量子退火器的查询，认为 MCTS 集的数量是 SD 运行的两倍（即 40×100=80×50）。根据图 3a，SD 的那些大误差条表示一个复杂的优化环境，包括多个局部最小值，其中 SD 很容易陷入其中。另一方面，对量子退火器使用大致相同数量的查询，MCTS 找到的解决方案获得更高的成功概率。

在图 3b 中，展示了在相对较短的退火时间内解决几个具有不同结构的 3-SAT 实例的成功概率。如比较所示，当优化景观具有许多局部最小值时，SD 等局部方法很可能陷入困境，而 MCTS 等全局方法则显示出弹性，并有更好的机会摆脱这些陷阱。随着问题规模的扩大，优化环境更有可能变得更加坚固，从而扩大了 MCTS 和 SD 之间的性能。

退火 schedules 的转移

受 NN 灵活性的启发，研究人员通过合并 NN 进一步修改 MCTS，就像在 DeepMind 的 AlphaZero 中所做的那样。为清楚起见，将调整后的方法命名为 QuantumZero (QZero)。

在这里，研究了在三种不同场景下将从一组训练实例中学到的退火 schedule 转移到一组测试实例中的有效性。

在图 4a-d 中，对具有不同退火持续时间 T = 40, 60, 80, 100 的 3-SAT 实例的最优退火计划的可迁移性进行了数值研究。

图 4：转移退火 schedules 的图示。（来源：论文）

预训练的 QZero（黄色）在所有退火持续时间内给出了最好的结果。

图 5：SD 或 QZero 退火 schedule 后基态能量与时间演化量子态的预期能量之间的差异。（来源：论文）

分别在图 5a、b 中仔细研究了 SD 或 QZero 退火 schedule 后基态能量与时间演化量子态的预期能量之间的差异。能量差 ΔE 反映了沿不同路径违反绝热性的强度。如图所示，预训练的 QZero 不仅能够找到最佳解决方案，而且能够比 SD 更好地执行绝热性。

比较 QZero 和其他 RL 方法的学习效率

最后，研究人员将 QZero 的学习效率与其他流行的 RL 方法进行了比较。与 QZero 类似，这些 RL 方法能够找到全局最优值；然而，众所周知，训练典型的 RL 方法非常耗费资源。在这里，QZero 使用更少的计算资源实现了相同水平的性能。

评估基于每种方法所需的对量子退火器的查询数量。在这个基准测试中，研究人员比较了 MCTS 算法的两种变体，即带预训练的 QZero (QZero-pre) 和不带预训练的 QZero (QZero-nopre) 与其他三个 RL 模型（DQN、A2C 和 PPO）。

图 6：比较 RL 算法的学习效率。（来源：论文）