Quantum circuit evolutionary framework applied on set partitioning problem

本文提出了一种利用可变拓扑和伪反绝热演化项的量子电路演化框架，通过克服收敛停滞并消除对经典优化器的需求，有效求解集合划分问题。

要点

想象一下，你正在尝试解决一个庞大而复杂的拼图。目标是将一群人（例如航空机组人员）分成若干团队，使得每架航班恰好被覆盖一次，既无重叠也无遗漏，同时将成本降至最低。在数学领域，这被称为集合划分问题。这是一个臭名昭著的难题，随着人员和航班数量的增加，其难度呈指数级增长。

本文介绍了一种让量子计算机解决此类拼图的新方法。作者构建了一个框架，使计算机能够在工作过程中自行演化其“配方”，而非遵循大多数量子算法所采用的标准“配方”。

以下是他们方法的简要解析，辅以简单的类比：

1. 旧方法：“固定蓝图”（VQE）

目前大多数量子算法，如变分量子本征求解器（VQE），其工作方式就像一位厨师遵循一本严格且不可更改的食谱书。

• 设置：“电路”（计算机执行的步骤）的结构是固定的。你无法添加或移除“食材”，只能调整“用量”（即参数）。
• 问题：随着拼图变大，厨师往往会陷入“平坦山谷”。想象你在一片雾气弥漫的田野中行走，地面完全平坦。无论你朝哪个方向迈步，既不上升也不下降。你无法判断自己是否更接近解。在量子物理中，这被称为** barren plateau（ barren 高原/平坦区）**。由于找不到改进的方向，计算机便停止了学习。

2. 新方法：“演化的雕塑家”（QCE）

作者提出了一种名为量子电路演化（QCE）的框架。与其使用固定配方，不如想象一位雕塑家，他从一个微小的黏土块开始，并允许在每一步添加、移除或重塑黏土。

• 工作原理：计算机从一个非常简单的电路（可能仅包含一个门）开始。随后，它通过随机变异结构（添加新步骤、删除旧步骤或改变连接），生成自身的一系列略微不同的“后代”。
• 选择：它测试所有这些版本。其中最能解决拼图的那个版本将存活下来，成为下一轮的“亲本”，其余则被丢弃。
• 优势：由于结构本身在不断变化，计算机不会被困在平坦山谷中。它能够重塑其整体方法，从而找到走出迷雾的路径。

3. 测试的两种策略

本文测试了这种“演化的雕塑家”方法的两种具体变体：

• 策略 A：纯演化主义者（无 Ansatz）
  该版本几乎从零开始，让计算机完全通过试错来构建结构，类似于自然选择。它不猜测解应为何种形态，而是直接演化直至奏效。

• 策略 B：受物理启发的演化主义者（伪反绝热）
  这是本文的“明星”。作者基于问题的物理特性，为计算机提供了一个提示。他们在电路中引入了一种特殊的“推动力”（称为伪反绝热项）。

  • 类比：想象你要将一个大箱子推上山坡。“纯演化主义者”只是随机推，直到找到上山的路径。而“受物理启发的”版本则知晓山坡的形状，并施加一种特定的反向力，以保持箱子平稳移动，防止其卡在平坦区域。
  • 结果：该策略表现最佳。即使面对非常大的拼图，它在避免“停滞”（收敛停滞）方面也比其他方法出色得多。

4. 结果

作者在模拟器（一种模拟量子计算机行为的计算机程序）上，使用 35 种不同版本的航空调度拼图测试了这些方法。

• 获胜者：受物理启发的演化方法（APCD-QCE）始终比标准的“固定蓝图”方法（VQE）找到了更优的解。
• 瓶颈：尽管新方法表现更佳，但当拼图变得极其庞大（约 20 个量子比特）时，它们仍面临困难。即便是“演化的雕塑家”，有时也会因时间或复杂度限制而无法找到完美解。
• 噪声：他们还测试了计算机出错时（模拟现实世界的“噪声”）会发生什么。新方法表现尚可，尽管性能有所下降，但这符合预期。

核心结论

本文主张，通过让量子电路自行改变其形状，而不仅仅是微调其设置，我们可以避开当前算法所陷入的“死胡同”。具体而言，在这一演化过程中加入基于物理的“推动力”，有助于计算机更快地找到更优解。

虽然这尚未解决所有问题（尤其是那些最大的问题），但它为利用量子计算机解决复杂的优化问题（如调度和资源管理）提供了一条充满希望的新路径，有望绕过传统计算机在优化方面承担繁重工作的需求。

技术摘要

技术摘要：应用于集合划分问题的量子电路进化框架

问题定义
本文探讨了集合划分问题（SPP），这是一个众所周知的 NP 难组合优化挑战。SPP 涉及将一个元素集合划分为互斥且穷尽的子集，以在确保每个元素恰好属于一个子集的前提下最小化总权重。其实际应用包括航空公司机组人员排班。为了在量子硬件上求解该问题，作者将 SPP 表述为二次无约束二进制优化（QUBO）问题，随后将其映射为伊辛哈密顿量。本研究特别针对当前变分量子算法（VQAs）（如变分量子本征求解器 VQE）的局限性，这些算法常受困于“ barren plateaus（ barren 高原）”现象——即随着量子比特数量的增加，梯度呈指数级消失，导致收敛停滞。

方法论
作者提出了一种**量子电路进化（QCE）**框架，该框架不同于标准的 VQE 方法。与利用固定电路拓扑（ansatz）并通过经典优化器优化可变参数的 VQE 不同，QCE 框架进化电路拓扑本身。本研究在该框架内评估了两种不同的策略：

1. 无 Ansatz 量子电路进化（AF-QCE）：

   • 受先前文献 [13] 启发，该方法从一个最小电路（单个随机门）开始，在没有预定义 ansatz 的情况下迭代进化。
   • 进化依赖于变异操作：插入（INSERT）（添加一个门）、删除（DELETE）（移除一个门）、交换（SWAP）（替换一个门）和修改（MODIFY）（调整门参数）。
   • 生成一组电路并进行测量，选择表现最佳的电路作为下一代的父代，从而确保成本函数单调递减。

2. 带有伪反绝热进化项的 Ansatz（APCD-QCE）：

   • 该方法将受物理启发的结构引入 ansatz 以改善收敛性。它利用哈密顿量 $H_T(\lambda) = H_{ad}(\lambda) + H_{pcd}(\lambda)$，其中 $H_{ad}$ 代表绝热时间演化哈密顿量，$H_{pcd}$ 是伪反绝热进化项。
   • 酉算子定义为 $U = U_{ad}U_{pcd}$。$U_{ad}$ 分量是固定的（一个 Trotter 步），而 $U_{pcd}$ 使用与 AF-QCE 相同的进化变异策略进行进化。
   • 初始态制备使用 $|+\rangle^{\otimes n}$，并应用特定参数设置（$\beta=0, \delta=0.5$）以促进对希尔伯特空间的探索。

实验设置
实验使用 Qiskit 库在高性能模拟器（KUATOMU）上进行，分为两种场景：

• 无噪声： 测试了 35 个 SPP 实例（范围从 6 到 20 个量子比特）。
• 有噪声： 模拟在特定量子比特上包含去极化错误通道（$\epsilon = 0.01$），以模拟 NISQ 设备的局限性。
• 对比： 将 QCE 策略与标准 VQE（使用双局部线性纠缠 ansatz 和 COBYLA 优化器）进行基准测试。
• 指标： 性能使用**近似比率（$R$）**进行衡量，定义为经典参考值（Gurobi 求解器）与量子算法找到的最小期望值之比。

关键结果

• 优于 VQE： 在无噪声场景中，AF-QCE 和 APCD-QCE 均显著优于 VQE。随着量子比特数量增加，VQE 性能迅速下降（对于 $\ge 10$ 个量子比特的实例，通常无法收敛），而进化方法保持了更好的性能。
• APCD-QCE 性能： APCD-QCE 策略表现出最稳健的结果，在 35 个实例中有 25 个实现了 1.00 的近似比率（最优）。它在大多数 VQE 和 AF-QCE 遇到困难的案例中有效地避免了收敛停滞。
• 可扩展性限制： 尽管有所改进，可扩展性挑战依然存在。对于 20 量子比特实例（特别是 20.1、20.6 和 20.7），包括 APCD-QCE 在内的所有方法都显示出收敛停滞的迹象，近似比率显著下降。
• 噪声影响： 在有噪声的模拟中，所有算法的性能均有所下降，特别是在较小实例中。然而，QCE 框架总体上保持了与 VQE 相当或更好的性能。

意义与主张
本文声称，所提出的 QCE 框架为整数优化问题提供了一种有前途的替代方案，可替代固定 ansatz 的变分算法。主要贡献包括：

• 缓解停滞： 该框架，特别是 APCD-QCE 变体，展现了避免标准 VQAs 中与 barren plateaus 相关的收敛停滞的非凡能力。
• 消除经典优化器： 通过直接进化电路拓扑，该过程绕过了使用经典优化器（如 COBYLA）来调整参数的需求，解决了当前 VQA 工作流程中的一个瓶颈。
• 通往可扩展性的路径： 虽然该方法并未完全解决 20 量子比特的停滞问题，但结果表明，可变拓扑电路为解决更大规模的优化问题提供了一条“有趣的路径”。作者指出，给定足够多的代数，APCD-QCE 策略对收敛停滞效应“几乎免疫”，尽管在变异景观中跳出局部最小值仍然是一个挑战。

作者总结道，尽管该方法随着量子比特数量的增加面临可扩展性障碍，但将受物理启发的项（伪反绝热）整合到进化电路搜索中，为在 NISQ 设备上求解组合问题带来了令人鼓舞的结果。