Penalty-free quantum optimization applied to lattice protein folding

本文提出了一种用于晶格蛋白质折叠的无惩罚量子优化方法，该方法利用为最大独立集问题设计的 QAOA 混合器来避免二次惩罚，并通过经典模拟成功验证了该方法在小规模蛋白质上的有效性，并将其扩展到更大规模的系统（长度 $N$ 高达 14）是通过一种启发式迭代局部搜索方案实现的。

要点

核心理念：像玩拼图一样折叠蛋白质

想象你有一根长长的、具有柔韧性的珠子链。其中一些珠子是“粘性”的（疏水性），而另一些是“滑溜”的（极性）。你的目标是将这根链条折叠成一个紧凑的形状，让那些粘性的珠子聚集在中间，远离水。这就是蛋白质折叠。

在现实世界中，这是自然发生的。但在计算机上，试图为即使是很短的一段链条寻找“完美”的形状是非常困难的。这就像是在解一个巨大的拼图，拼图块可以有数十亿种排列方式，而你必须找到那一种能消耗能量最少的特定排列方式。

旧方法的缺陷

科学家们曾尝试使用量子计算机来解决这个问题。通常，当你要求量子计算机解开一个谜题时，你必须告诉它规则：

1. “链条必须是连续的。”
2. “链条不能自我交叉。”
3. “每个珠子必须占据一个位置。”

过去，为了让计算机遵守这些规则，科学家不得不添加“惩罚分”来评分。如果计算机犯了错（比如链条断裂），它会受到巨额惩罚。这就像是在玩一场游戏，每当你违反规则时，都会被罚款。问题在于，这些惩罚在数学上是极其复杂的（二次项），这使得量子计算机的工作变得更加困难且缓慢。

新思路：“无惩罚”区域

这项研究引入了一个巧妙的技巧，旨在完全避开这些复杂的惩罚机制。

类比：“冲突图”（Conflict Graph）
想象拼图块是参加派对的人。

• 有些人互相讨厌（代表那些不能在同一位置或相邻的珠子）。
• 我们在互相讨厌的人之间画一条线。这就创建了一个“冲突图”。

派对的规则很简单：只有当互不相识（不互相讨厌）时，你才能邀请这些人进入 VIP 区。 用数学术语来说，你正在寻找一个独立集（即没有任何连线的群体）。

通过使用这个图，研究人员意识到他们不需要告诉计算机“不要让这两个珠子接触！”，因为图本身已经禁止了这种行为。如果计算机选择了一个有效的群体（一个独立集），规则就会自动得到遵守。无需任何惩罚！

工具：QAOA-MIS

研究人员使用了一种特定的量子算法，称为 QAOA（量子近似优化算法）。

• 标准 QAOA： 试图解决谜题，但必须不断检查是否违反规则。
• 他们的新版本 (QAOA-MIS)： 使用了一种特殊的“混合器”（一种用于打乱可能性的量子工具），这种混合器被设计为仅在有效的群体之间进行移动。这就像是一个夜总会的保安，他只允许已经在有效群体中的人进入。如果你试图违反规则，保安根本不会让你移动到那里。

这意味着计算机只会把时间花在寻找有效解上，而不是浪费在无效解上。

结果：小规模 vs 大规模拼图

团队在二维网格（类似于平坦的棋盘）上，使用两种类型的珠子进行了测试。

1. 小规模拼图（4 到 6 颗珠子）：
   他们在常规超级计算机上模拟了量子计算机。他们发现，这种新的“无惩罚”方法效果非常好。对于最小规模的拼图，即使使用非常简单的设置，它也能几乎立即找到完美解。

2. 大规模拼图（高达 14 颗珠子）：
   真实的量子计算机和模拟过程会随着谜题变大而迅速不堪重负。一个 14 颗珠子的谜题，目前需要的量子计算机部件数量过多，难以模拟。

解决方案：“局部搜索”（QLS）
为了处理更大的谜题，他们发明了一种策略，称为量子局部搜索 (QLS)。

• 类比： 想象你在试图解开一个巨大的、缠绕在一起的毛线团。与其试图一次性解开整个线团，不如将注意力集中在一个 3 英寸的小段上，只解开那一小部分，然后移动到下一段。
• 他们将大的蛋白质问题分解成微小的“邻域”（小规模的珠子组）。他们使用量子计算机只解决那一个小邻域，然后继续处理下一个。
• 他们还使用了“钉住”（pinning）技巧：一旦某个珠子被正确放置，他们就会将其“钉住”，这样在解决下一个部分时，计算机就不会意外移动它。

最终成果：
通过使用这种“缩放”方法，他们成功找到了长达 14 颗珠子的蛋白质正确形状。这种规模对于目前的完整规模量子计算机模拟来说是无法实现的。

总结

• 目标： 找到蛋白质链的最佳形状。
• 旧方法： 使用量子计算机，但通过增加沉重的“惩罚分”来应对违反规则的情况，这会降低速度。
• 新方法： 将规则映射到“冲突图”上，使得只有有效的移动成为可能。这消除了对惩罚的需求。
• 策略： 对于大问题，不要一次性解决整个问题。使用量子计算机逐一解决一个个微小的“局部邻域”。
• 结果： 他们成功折叠了小型蛋白质，并利用这种混合方法解决了更大的问题（高达 14 颗珠子），证明了这种“无惩罚”方法是使用量子计算机处理生物学问题的强大新途径。

技术摘要

技术摘要：应用于晶格蛋白质折叠的无惩罚量子优化

问题陈述
识别晶格蛋白质的最低能量结构是一个具有挑战性的离散优化问题，已知属于 NP-完全问题。本研究调查的具体模型是二维疏水-极性（HP）模型，其中蛋白质被表示为在正方形晶格上的 H 和 P 残基的自回避链。目标是找到最小化非相邻疏水（H-H）接触数量的链构象。

传统的量子方法，如量子近似优化算法（QAOA）和量子退火（QA），通常将此问题映射到二次无约束二进制优化（QUBO）形式。这种标准的映射需要包含二次惩罚项来强制执行物理约束：每个氨基酸必须占据且仅占据一个晶格位点（自回避），以及珠子必须形成连续的链。这些惩罚项增加了问题哈密顿量的复杂度，并且需要对拉格朗日乘数进行仔细调优。

方法论
作者提出了一种名为 QAOA$_{MIS}$ 的无惩罚 QAOA 变体，该变体通过利用冲突图的结构而非依赖二次惩罚，将搜索空间限制在有效构象内。

1. 冲突图与独立集：
   问题被映射到一个冲突图中，其中的节点代表二进制变量（量子比特），指示氨基酸的位置。边代表源自用于构建有效链结构的惩罚能量（$E_1, E_2, E_3$）的二次约束。如果激活比特（值为 1）的集合在图中是一个独立集（没有两个激活节点通过边相连），则比特配置对应于一条有效的链。全长链对应于最大独立集（MIS）。

2. QAOA$_{MIS}$ 公式化：
   作者没有使用标准的横向场混合器（$X$-mixer）或 XY 混合器，而是采用了一种专门为 MIS 问题设计的混合器。该混合器保持了独立集的子空间。因此，目标函数被简化为：
   $$E_{MIS} = E_{HP} - \lambda_1 \sum_{i,n} b_{i,n}$$
   这里，$E_{HP}$ 是蛋白质能量，第二项是一个简单的线性偏置，旨在鼓励形成全长链。至关重要的是，二次惩罚项被消除了。

3. 针对更大系统的量子局部搜索（QLS）：
   由于由于量子比特和门数量呈指数级增长，全规模 QAOA 模拟在链长 $N > 6$ 时变得难以处理，因此作者引入了一种启发式**量子局部搜索（QLS）**方案。

   • 局部邻域： 算法迭代地选择冲突图的局部邻域（子图），其大小限制在 $\le 26$ 个量子比特。
   • 钉扎机制： 为了防止系统陷入局部最小值，作者使用了一种动态“钉扎”策略：成功移动到新位置的氨基酸会以一定概率被“钉扎”（冻结），而其他氨基酸则被“解钉扎”以允许探索。
   • 准备运行： 一个准备阶段的 QAOA 运行专注于在全链优化开始之前，将疏水（H）残基填充进低能量核心。
   • 混合处理： 对于超过 26 个量子比特的邻域，作者测试了一种混合方法，即由经典方式解决这些特定的子问题。

关键结果
该研究通过量子电路的经典模拟验证了该方法：

• 短链 ($N=4, 6$)：

  • 将 QAOA$_{MIS}$ 与标准 QAOA（$X$-mixer）和 QAOA$_{XY}$ 进行了对比。
  • 对于 $N=4$，QAOA$_{MIS}$ 在单层（$p=1$）下实现了接近 1.0 的成功概率，在低深度下优于其他变体。
  • 对于 $N=6$，QAOA$_{MIS}$ 在 $p=5$ 时达到了 $\approx 0.77$ 的成功概率。其表现呈现出双峰分布（接近 0 或 1），这表明虽然该方法很强大，但随着参数空间维度的增加，参数优化变得困难。
  • 初始状态的选择对较小的 $p$ 值有显著影响。从“无珠子”状态（$I_0$）或特定的全链状态（$I_1, I_2$）开始，其成功率取决于与基态的汉明距离以及能量景观中是否存在下坡路径。

• 长链 ($N=4$ 到 $14$)：

  • 使用限制在 26 个量子比特以内的局部邻域 QLS 方案，作者成功折叠了长度达 $N=14$ 的序列。
  • 该方法在至少一次运行中找到了所有测试序列的基态（成功率 $\ge 0.1$）。
  • 序列 $S_{12}$ 显示出最低的成功率（1/10 次运行），作者将其归因于其较大的平均邻域规模。
  • 当大于 26 个量子比特的邻域由经典方式处理而非跳过时，成功率显著提高（例如，$N \le 14$ 时 $\ge 0.6$），并找到了高达 $N=18$ 的序列的基态。
  • QLS 方法将有效量子比特数量减少了约一个数量级，相比于全系统模拟（例如，对于 $N=14$，全系统需要 188 个量子比特，而 QLS 使用的平均邻域仅为 14–19 个量子比特）。

意义与主张
本文声称，通过将搜索空间限制在冲突图的独立集中，可以在晶格蛋白质折叠中移除二次惩罚项，从而将目标函数简化为线性偏置加物理能量。这种“无惩罚”方法被认为是一种处理具有类似 QUBO 结构的优化问题（如旅行商问题）的可行策略。

作者强调，虽然 QAOA$_{MIS}$ 变体对于小系统非常有效，但所提出的 QLS 启发式方案对于扩展到更大的蛋白质至关重要。他们得出结论，通过使用能够处理所需局部邻域大小（目前 $\le 26$ 个量子比特）的硬件，这种局部搜索方法可以解决远超全规模 QAOA 处理能力的晶格蛋白质折叠问题。这项工作证明，基于图的限制可以有效地管理量子优化中的约束，而无需承担惩罚调优的开销。