Efficient Fourier-Based Linear Combination of Unitaries and Applications in Quantum Optimization

本文提出了一种无需辅助量子比特的、基于傅里叶变换的酉算子线性组合（LCU）框架，该框架通过将电路复杂度转化为多项式采样开销，高效地分解用于优化任务的复杂量子电路，从而在保持严格性能保证的同时，使诸如量子近似优化算法（QAOA）等算法能够在近期量子设备上实现硬件友好的部署。

要点

想象你正在尝试解决一个巨大且极其复杂的拼图。在量子计算的世界里，这个拼图通常是一个优化问题：寻找事物的最佳排列方式（例如最高效的配送路线或最佳的投资组合）。

Carrera Vazquez、Egger 和 Woerner 的论文介绍了一种利用量子计算机解决这些拼图的新颖方法，特别是针对那些仍处于早期“噪声”发展阶段的量子计算机。

以下是他们想法的分解，使用简单的类比：

问题：“全员上阵”电路

传统上，要在量子计算机上解决这些拼图，你需要构建一台特定的机器（量子电路），其中拼图的每一个部分都必须与其他所有部分同时“对话”。

• 类比：想象你要组织一场派对，100 位客人都需要在完全相同的时刻与每一位其他客人握手。在现实房间中，这是不可能的；人们会互相碰撞，房间会过于拥挤，活动也会失败。
• 量子现实：在量子术语中，这需要“全对全连接”以及非常深、非常复杂的电路。当前的量子计算机就像小房间；它们无法在不犯错（噪声）的情况下处理如此多的同时握手。

解决方案：“食谱书”方法（LCU）

作者提出了一种名为**线性组合幺正算符（Linear Combination of Unitaries, LCU）**的新策略。与其试图构建那台不可能的“全员上阵”机器，他们将该复杂任务分解为一系列更简单、更小的任务。

• 类比：与其试图一次性烘焙一个巨大而复杂的婚礼蛋糕（这可能会坍塌），不如烘焙 100 个简单的小纸杯蛋糕。
  • 有些纸杯蛋糕是香草味的，有些是巧克力味的，有些撒了糖珠。
  • 你不需要一个巨大的烤箱；你可以一次烘焙一个，或者分小批次烘焙。
  • 之后，你将结果混合在一个盘子里。如果你按正确的比例混合，盘子的“味道”尝起来就完全像你想要的那个巨大婚礼蛋糕。

在论文中，这些“纸杯蛋糕”是简单的量子电路，只需要单量子比特门（一个人只与另一个人握手）。“混合”是在量子部分完成后，在经典计算机（普通计算机）上进行的。

秘密武器：傅里叶变换

他们如何知道要烘焙哪些纸杯蛋糕以及混合多少比例？他们使用了一种名为傅里叶变换的数学工具。

• 类比：想象一首复杂的歌曲。傅里叶变换将这首歌分解为单个音符（频率）。作者利用这一点，将复杂的量子“歌曲”（电路）分解为一系列简单、重复的音符（单量子比特旋转）。
• 结果：他们可以将一个非常困难、复杂的量子操作表示为一系列非常简单的操作的加权和。

权衡：质量与数量

这里有一个陷阱。因为你没有直接构建那台巨大的机器，所以你必须进行更多次的“纸杯蛋糕”实验才能获得可靠的答案。

• 类比：如果你想了解人群的平均身高，你可以测量每个人一次（如果所有人都在移动，这很难做到）。或者，你可以测量 10 个随机的人，然后再测 10 个，再测 10 个，然后取平均值。你会得到相同的结果，但你必须进行更多的测量。
• 论文主张：作者表明，虽然你需要运行更多次简单电路（一种“采样开销”），但额外运行的次数是可控的（多项式级别），而非不可能。这种权衡使他们能够在当前硬件上运行那些原本不可能运行的问题。

现实世界应用：“最密子图”

为了证明这行之有效，他们在一个名为“最密 k-子图”（在庞大的社交网络中寻找关系最紧密的一群朋友）的具体问题上进行了测试。

1. 小规模：他们在 12 个节点的图（就像一个小型社区）上模拟了该过程，以证明数学原理完美运作。
2. 大规模：他们在拥有106 个量子比特的真实 IBM 量子计算机（一个大型社区）上运行了该过程。
   • 他们成功找到了高质量的解决方案。
   • 他们比较了两种方法：一种使用“惩罚”（类似于违反规则的罚款），另一种使用特殊的“混合器”（一种遵守规则的舞蹈）。
   • 发现：“混合器”方法结合他们新的傅里叶方法，表现异常出色，即使在真实且有噪声的硬件上，也能找到几乎与理论最佳解一样好的解决方案。

“无需助手”的窍门

通常，为了将这些“纸杯蛋糕”混合在一起，你需要一个额外的辅助量子比特（“辅助比特”）来跟踪数学运算。

• 创新：作者开发了一种无需助手的方法。
• 类比：与其需要一个裁判来告诉你哪支球队得分，不如让球员们随机比赛，然后在事后查看记分牌来确定获胜者。这从量子电路中移除了巨大的复杂性，使其对当今的机器更加友好。

总结

这篇论文提出了一种在当下不完美的硬件上运行复杂量子优化算法的新方法。与其试图构建一台将一切与一切相连的庞大而脆弱的机器，他们将该问题分解为许多微小、简单的部分，运行这些部分，然后在经典层面组合结果。

他们通过在 106 个量子比特的量子计算机上解决一个困难的图问题证明了这一点的有效性，表明我们可以通过用“电路复杂度”（机器构建的难度）交换“采样开销”（我们需要运行测试的次数），在今天解决更大、更复杂的问题。

技术摘要

技术摘要：基于傅里叶变换的酉算子线性组合及其在量子优化中的应用

问题陈述
量子优化算法，特别是量子近似优化算法（QAOA），在近期硬件上面临重大的实施障碍。优化问题的数学结构，尤其是涉及约束（例如基数约束）的问题，通常要求具有高连通性（全对全相互作用）、深层电路深度以及大量双量子比特门的量子电路。这些要求经常超出当前超导量子处理器的能力。虽然存在电路切割或电路近似等策略，但它们往往以牺牲解的质量来换取复杂度的降低，或者需要大量的采样开销且缺乏严格的性能保证。

方法论
作者提出了一种**基于傅里叶变换的酉算子线性组合（LCU）**框架，旨在利用更简单、更易于硬件实现的电路集合来近似复杂的量子电路。核心方法论包括：

1. 用于采样的无辅助量子比特 LCU：与使用辅助量子比特相干地实现酉算子线性组合（需要受控操作）的标准 LCU 实现不同，本工作专注于基于采样的应用。通过去除与准概率分解（QPD）相关的符号因子，并用经典随机性替代辅助量子比特，该方法消除了对辅助量子比特和受控门的需求。这将实现转化为简单电路的概率混合，其中采样开销由因子 $\Gamma$ 量化。
2. 对角酉算子的傅里叶分解：对于对角酉算子（常见于成本函数和惩罚项），作者利用离散傅里叶变换。目标酉算子 $U_f(\gamma) = \sum_x e^{-i\gamma f(g(x))} |x\rangle\langle x|$ 被分解为更简单酉算子 $V(\theta_j)$ 的线性组合，这些酉算子通常只是单量子比特 $R_Z$ 门的层。系数源自定义该酉算子的函数的傅里叶变换。这种方法用单量子比特层替换了复杂的多量子比特相互作用（例如需要 $O(n^2)$ 个门的二次惩罚），代价是采样开销 $\Gamma \le m+1$。
3. 扩展到非对角置换不变酉算子：该框架被推广到非对角酉算子，例如用于保持汉明权重约束的全连接XY 混合器。利用 Schur-Weyl 对偶性和 $SU(2)$的表示论，作者将置换不变酉算子表示为集体单量子比特旋转$R(g)^{\otimes n}$的连续线性组合。这使得仅使用单量子比特门即可实现高度非局域的混合器，其理论采样开销上界为$O(n^3)$。
4. 与拉格朗日松弛的联系：本文建立了基于傅里叶变换的量子惩罚与经典拉格朗日松弛之间的形式联系。优化 LCU 分解的单个分支被证明等同于优化拉格朗日参数，为约束处理提供了统一的视角。

主要贡献

• 框架开发：引入了一种无辅助量子比特、基于傅里叶变换的 LCU 框架，将广泛的对角和非对角酉算子类别分解为单量子比特门层的集合。
• 硬件效率：证明了复杂的全连接算子（如基数惩罚和 XY 混合器）可以被显著更简单的电路所替代，以多项式采样开销换取电路深度和连通性的降低。
• 理论保证：提供了严格的性能界限，表明在 LCU 方法中采样高质量比特串的概率下界为相干概率除以 $\Gamma$。本文还将条件风险价值（CVaR）优化与这些界限联系起来。
• 可扩展性验证：在真实 IBM 量子硬件上成功将该框架应用于多达106 个量子比特的最密 $k$-子图问题实例，这一规模对于此类约束的完全相干实现而言此前是不可处理的。

实验结果
作者通过在 12 节点实例上的精确态矢量模拟以及在 106 量子比特设备上的大规模实验验证了他们的方法：

• 12 节点模拟：完全相干 QAOA 与基于傅里叶变换的 LCU 方法之间的比较显示，虽然 LCU 电路的原始期望值较低（由于采样开销），但优化单个 LCU 基电路（从 LCU 导出的变分 ansatz）产生了采样最优解的最高概率，在特定指标上优于相干基线。
• 106 节点硬件实验：在 106 量子比特的重六边形图（通过 SWAP 层扩展）上，执行了基于惩罚和基于 XY 混合器的 LCU 方法。结果表明，实际采样开销显著低于最坏情况理论界限（$\Gamma \approx 10^4$）。单分支 LCU ansatz 成功找到了高质量解（最密子图中多达 81 条边），可行概率范围为 2.7% 至 4.8%，表明该方法适用于大规模问题。
• XY 混合器与惩罚的比较：基于 XY 混合器的 LCU 方法通常优于基于惩罚的方法，特别是在使用单个优化后的基电路时，这表明约束保持型混合器与这种分解结合时更为有效。

意义与主张
本文主张，基于傅里叶变换的 LCU 框架为扩展近期量子优化的实际适用范围提供了一条系统途径。通过将复杂的相干操作替换为更简单电路的加权组合，该方法扩大了可在当前硬件上执行的实例范围（特别是具有全局约束的实例）。作者强调，这种方法不需要精确复现目标分布，而是专注于采样高质量解，这一目标非常适合优化任务。该研究表明，电路复杂度与采样开销之间的权衡是有利的，因为理论界限在实践中往往较为宽松，且该方法使得研究原本超出硬件能力的算法和问题实例成为可能。文章结论指出，这为更兼容硬件的量子算法（特别是 QAOA 中的约束处理）提供了一种灵活的设计原则。