Finite Imaginary-Time Evolution for Polynomial Unconstrained Binary Optimization

本文介绍了有限虚时演化（FinITE），这是一种非幺正量子算法，利用线性组合幺正算符框架求解多项式无约束二进制优化问题，在提供精确基态保真度保证和定点振幅放大的同时，避免了二次化的需求。

要点

想象你正试图在一片广阔而多雾的山脉中找到最低点。在计算机科学领域，这个“最低点”代表了解决复杂难题的完美方案，例如规划配送路线或安排工厂生产。这类难题被称为多项式无约束二进制优化（PUBO）。

几十年来，科学家们一直希望利用量子计算机更快地解决这些难题。一种流行的寻找最低点的理论方法称为虚时演化（ITE）。可以将 ITE 想象成一个神奇的过滤器，它慢慢冲刷掉所有的“高地”（糟糕的解决方案），只留下“谷底”（最佳解决方案）。

然而，这里有一个陷阱：这个神奇过滤器是非幺正的。用量子力学的语言来说，这意味着它就像试图把水倒进一个底部有洞的桶里。你无法直接构建一个标准的量子电路来执行此操作；数学计算与量子物理的规则并不兼容。

“无限”时间的问题

之前的尝试通过让过滤器运行非常长的时间（趋近于“无限”时间）来解决这个问题。其想法是，如果你等待足够长的时间，糟糕的解决方案就会完全消失。

由 Jaehee Kim 和 Joonsuk Huh 领导的本文作者发现了这种“永远等待”方法的一个重大缺陷。他们发现，对于许多此类难题，如果你等待太久，过滤器不仅会保留最佳解决方案，还会意外地过滤掉一切。量子计算机的成功率降至零，你一无所获。这就像试图通过烧毁整个干草堆来寻找一根针；最终，针也会消失。

解决方案：有限虚时演化（FinITE）

该团队开发了一种名为FinITE（有限虚时演化）的新方法。他们不再等待永远，而是计算出针对特定难题运行过滤器的确切时长，以便在获得良好结果的同时不丢失一切。

以下是他们如何做到的，使用了一些简单的类比：

1. “乐高”方法（LCU）
为了构建他们的量子过滤器，他们使用了一种称为**幺正算符线性组合（LCU）**的技术。想象你需要用许多小块、简单的乐高积木搭建一台复杂的机器。每一块积木代表难题的一部分。

• 由于他们特定难题（称为 PUBO）的各个部分互不冲突（它们“对易”），团队可以将这些乐高积木完美地拼接在一起，没有任何缝隙或错误。
• 这使得他们能够精确地构建过滤器，而无需先简化难题（通常称为“二次化”的过程，往往会增加不必要的复杂性）。

2. 权衡（跷跷板）
该论文发现了一个完美的数学平衡，或者说是一个“跷跷板”，涉及两个方面：

• 保真度：结果与完美解决方案的接近程度。
• 成功概率：量子计算机实际完成工作而不崩溃的可能性（即“桶底破洞”变大的程度）。

他们证明了一个精确的公式：当你为了获得更好的解决方案（更高的保真度）而加大过滤器力度时，计算机成功的几率就会下降。 但是，他们计算出了这种权衡可以接受的确切临界点。

3. “助推器”（振幅放大）
由于随着过滤器强度的增加，成功率会下降，团队添加了一个名为**定点振幅放大（FPAA）**的“助推器”。

• 想象你试图在嘈杂的房间里听到耳语。当你试图调出它时，耳语声会变得更轻，但你有一副特殊的耳机（FPAA），可以将那个特定的耳语放大回正常音量。
• 只要你知道最低的成功几率，这个助推器就能让计算机在自然成功率较低的情况下也能成功。

“甜蜜点”（阈值）

该论文最重要的结果是一个关于“甜蜜点”的公式。
作者不再猜测模拟运行多长时间，而是提供了一条清晰的规则。如果你了解一点关于难题的信息（有多少个解决方案是好的，以及最佳解决方案与次佳解决方案之间的距离），你就可以将这些数字代入他们的公式。

• 该公式告诉了你运行过滤器的确切时间量（称为 $\beta$）。
• 运行时间少于这个量，答案就不够好。
• 运行时间多于这个量，计算机很可能根本无法给出答案。
• 运行这个特定时间，你就能获得尽可能好的答案，并保证成功的几率。

现实世界测试

该团队在两类难题上测试了这种方法：

1. MaxCut（QUBO）：一个经典问题，旨在将一群人分成两组，使得两组之间的争论最多。他们在 5 个人的小组上测试了这一点。
2. HUBO：一个更复杂的版本，涉及三方互动（例如，三个朋友组成的群体，如果其中一人离开，动态就会发生变化）。他们在 8 个“量子比特”（qubits）上测试了这一点。

在这两种情况下，他们的计算机模拟都证实他们的数学是完美的。他们预测的“跷跷板”平衡完全按照公式所述发生，甚至精确到微小的小数点。

总结

简而言之，这篇论文解决了量子优化中的“金发姑娘”问题。它阻止了我们等待过久（这会破坏机器）或等待时间不足（这会给出糟糕的答案）。通过使用精确的数学公式和“助推器”技术，FinITE为我们提供了一套可靠、循序渐进的食谱，用于利用量子计算机找到复杂二进制难题的最佳解决方案，而无需先简化这些难题。

技术摘要

以下是论文《用于多项式无约束二进制优化的有限虚时演化》的详细技术总结。

1. 问题陈述

多项式无约束二进制优化（PUBO） 是一类基本的组合优化问题（包括 QUBO 和 HUBO），其目标是最小化二进制变量的多项式目标函数。这些问题自然地映射到对角泡利-Z 成本哈密顿量（$\hat{H}$），其中基态编码了最优解。

虚时演化（ITE） 是制备基态的标准理论原语，因为算符 $e^{-\beta \hat{H}}$ 会指数级抑制激发态分量。然而，ITE 是非幺正的，使其无法直接在量子硬件上实现。

现有的量子方法面临显著局限：

• 变分方法（VITE/QITE）： 依赖经典优化循环，并遭受近似误差或局部幺正拟合问题的困扰。
• 概率方法（PITE/LCU）： 最近的线性幺正组合（LCU）方法在有限 $\beta$ 下运行，但缺乏 LCU 成功概率 与 基态子空间保真度 之间的闭式解析关系。
• $\beta \to \infty$ 极限： 将虚时 $\beta$ 取至无穷大会导致大多数问题（尤其是非二分图）的标准 LCU 构造的成功概率消失，若无针对有限 $\beta$ 的特定策略，该方法将不切实际。
• 二次化： 高阶项（HUBO）通常通过辅助变量被约化为二次项（QUBO），这会扩大搜索空间并改变成本结构。

2. 方法论：有限虚时演化（FinITE）

作者提出了 FinITE，这是一种专为源自 PUBO 实例的对角泡利-Z 哈密顿量设计的有限-$\beta$ 构造。该方法论包含三个核心组件：

A. 逐项 LCU 块编码

FinITE 不近似完整演化或约化高阶项，而是利用 线性幺正组合（LCU） 框架。

• 因式分解： 由于 PUBO 哈密顿量中的泡利-Z 项相互对易，算符 $e^{-\beta \hat{H}}$ 可精确因式分解为逐项指数的乘积：$e^{-\beta \hat{H}} = \prod_\mu e^{-\beta x_\mu \sigma_\mu}$。
• 实现： 每个项使用辅助量子比特单独进行块编码。由于各项对易，这些块在组合时不会产生 Trotter（乘积公式）误差。
• 处理高阶项： 该方法直接处理高阶泡利-Z 项（三次、四次等），消除了对二次化（引入辅助变量）的需求。

B. 精确有限-$\beta$ 恒等式

论文推导了一个严格的闭式恒等式，将任意有限 $\beta$ 下的 LCU 成功概率（$P_{LCU}$）与基态子空间保真度（$F_g$）联系起来：
$$P_{LCU}(\beta) \cdot F_g(\beta) = \gamma_0 e^{-2\beta(W + E_0)}$$
其中：

• $\gamma_0$：与基态子空间的初始重叠。
• $W$：非恒等泡利系数的 $\ell_1$ 范数（$W = \sum |x_\mu|$）。
• $E_0$：基态能量。

该恒等式揭示了一种严格的权衡：随着 $\beta$ 增加，保真度 $F_g$ 趋近于 1，但成功概率 $P_{LCU}$ 呈指数衰减。

C. 定点振幅放大（FPAA）

为了抵消所需有限 $\beta$ 下消失的成功概率，FinITE 集成了 定点振幅放大。

• 与标准振幅放大不同，FPAA 不需要精确了解初始成功概率即可避免“过冲”。
• 它利用成功概率的已知下界（源自上述恒等式）将成功率提升至目标水平，并具有可证明的查询复杂度界限。

3. 主要贡献

1. 闭式解析框架： 论文提供了首个针对对易哈密顿量、将 LCU 成功概率与基态保真度联系起来的精确恒等式。这用精确的数学关系取代了启发式界限。
2. 闭式阈值规则（$\beta^\star$）： 利用该恒等式和基于能隙的保真度下界，作者推导出了达到目标保真度 $\bar{F}$ 所需的充分虚时 $\beta^\star$：
   $$\beta^\star(\bar{F}) = \max\left(0, \frac{1}{2\Delta} \log \frac{\bar{F}(1-\gamma_0)}{\gamma_0(1-\bar{F})}\right)$$
   其中 $\Delta$ 是谱隙。这使得能够基于估计的谱特性解析地选择 $\beta$。
3. 直接 HUBO 处理： 该方法原生处理高阶相互作用（HUBO），无需二次化，从而保留了原始问题结构并避免了辅助变量的开销。
4. 资源复杂度分析： 论文提供了 FPAA 阶段的显式查询复杂度界限，表明成本按 $O\left(\frac{\log(2/\delta)}{\sqrt{\gamma_0}} e^{\beta^\star(W+E_0)}\right)$ 缩放。

4. 结果与验证

作者在两个不同实例上利用态矢量和基于采样的模拟验证了 FinITE：

• 5 顶点 MaxCut（QUBO）：

  • 一个非二分图，其中 $\beta \to \infty$ 极限将导致零成功概率。
  • 验证： 态矢量模拟以机器精度（相对误差 $\sim 10^{-14}$）确认了恒等式 $P_{LCU} F_g = \frac{3}{16} e^{-4\beta}$。
  • FPAA 性能： 基于采样的模拟表明，只要查询复杂度 $L$ 足够，FPAA 即使在 $\beta$ 增加时也能维持高的基态子空间制备概率。

• 8 量子比特三次 HUBO：

  • 一个包含混合三次和二次项的原生高阶问题。
  • 验证： 该恒等式在三种不同的初始态机制（均匀、弱热启动、强热启动）下均成立。
  • 热启动影响： 模拟证实，增加初始重叠 $\gamma_0$（通过热启动）会线性缩放成功概率包络，显著减少达到目标保真度所需的 $\beta$。

5. 意义与启示

• 实用量子优化： FinITE 提供了一种具体的、非变分的算法，用于在近期和容错量子硬件上解决 PUBO 问题，避免了变分算法中常见的 barren plateau（ barren 平台）问题。
• 理论清晰度： 通过确立成功概率与保真度之间的精确权衡，该工作为选择算法参数（$\beta$）提供了清晰的“规则手册”，而非依赖试错法。
• 可扩展性： 直接处理高阶项的能力使 FinITE 对于二次化会导致量子比特数量指数级增加的问题特别有价值。
• 未来方向： 论文指出，虽然该方法需要谱隙和初始重叠的估计，但这些可以通过经典预处理或启发式热启动获得，从而使该方法在实际部署中可行。

总之，FinITE 将虚时演化从一个理论概念转变为一种有限资源、解析可处理的组合优化量子算法，弥合了非幺正理论与幺正量子实现之间的鸿沟。