技术摘要：二维网格上通勤门的高效电路转译

问题陈述

组合优化问题（如最大割 (MC) 和最大独立集 (MIS)）是许多应用的核心，但它们通常是 NP 完全的。量子近似优化算法 (QAOA) 提供了一种通过将这些问题映射到哈密顿量的量子方法。然而，在数字量子计算机上的实际实现面临着显著障碍，主要是由于受限的硬件连通性。

问题哈密顿量 $H_C$ 通常会在许多对量子比特之间诱导相互作用。在具有受限连通性（例如 2D 网格）的硬件上，这些非相邻相互作用必须使用 SWAP 门将量子比特路由到相邻位置。这个路由过程增加了电路深度和累积误差，往往抵消了量子算法带来的益处。此外，为全连接图设计的预定 SWAP 网络对于稀疏代价哈密顿量而言是低效的，而标准的转译方法（如 Qiskit 中的方法）通常使用随机初始映射和固定路由，往往会产生次优的电路。

方法论

作者提出了一种专门针对由通勤两量子比特门块组成的电路（QAOA 的典型特征）在二维 (2D) 点阵硬件上进行的转译方案。核心方法涉及在构建依赖于问题的 SWAP 层序列与更新量子比特布局之间进行交替。

论文引入并比较了几种策略：

1. 线性策略 ($S_{line}, C_{line}^{grid}$)：这是最先进的基准方案，将 2D 网格视为 1D 线。SWAP 层在网格中最长线的奇偶边之间交替。
2. 混合策略 ($S_{line}, C_{grid}$)：线性策略的一种修改版本，它应用基于线的 SWAP 路由，但在不改变底层 SWAP 网络的情况下，利用 2D 网格中未使用的边来直接应用 $R_{ZZ}$ 门（相互作用）。
3. 网格策略 ($S_{grid}, C_{grid}$)：一种利用定制的 SWAP 层基组 ($B_{grid}$) 的策略，该基组通过交替水平和垂直交换来充分利用 2D 连通性。
4. 贪婪问题依赖策略 ($S_{greedy}, C_{grid}$)：作者的主要贡献。该方法采用贪婪搜索算法，根据特定优化问题的代价哈密顿量实例来定制 SWAP 序列和初始量子比特映射。
   • 内层循环：使用深度优先搜索 (DFS) 来探索可达量子比特配置的树。它寻找实现所有所需相互作用的最短 SWAP 层路径。为了控制复杂度，在选择最佳部分序列之前，搜索被限制在最大深度 $k_{max}$ 以内。
   • 外层循环：使用基于 SAT 的映射求解器迭代更新初始量子比特映射 ($\pi_0$)。如果当前 SWAP 序列长度超过参考长度，算法会使用新的初始映射重新开始搜索，以期找到更短的序列。
   • 基组：搜索使用扩展基组 ($B_{extended}^{grid}$)，其中包括除了标准网格基组之外的额外 SWAP 层，以通过增加搜索开销来换取降低电路深度。

核心贡献

1. 问题依赖型转译：论文引入了一种贪婪算法，能够动态构建针对特定优化问题相互作用图定制的 SWAP 策略和初始映射，而不是依赖固定的、与问题无关的网络。
2. 混合基准：提出了一个混合策略，该策略在保持线性 SWAP 主干的同时，利用 2D 网格边进行相互作用，作为一个中间基准。
3. 可扩展性分析：理论和实证表明，对于稀疏图，网格策略（尤其是贪婪策略）在电路复杂度指标（SWAP 层、深度、门计数）上比线性策略实现了 $O(\sqrt{n})$ 的渐近改进，而线性策略的规模为 $O(n)$。
4. 硬件验证：在 IBM 的矩形点阵硬件上执行了高达 80 个量子比特的 QAOA 电路，验证了其模拟结果。

结果

作者在随机正则 (RR) 图（度 $d=3$）上的 MC 实例和 Erdős–Rényi (ER) 图（边概率 $q=0.08$）上的 MIS 实例上对他们的方案进行了基准测试。

• 电路复杂度：与标准方法（包括线性策略和 Qiskit 的 SABRE 转译器）相比，贪婪策略对于稀疏图减少了约一倍的电路深度和两量子比特门计数。
  • 对于 RR 图，线性策略的 SWAP 层数、深度和 CZ 门数分别随 $n$、$n$ 和 $n^2$ 缩放，而贪婪策略保持了较低的常数和更好的缩放行为。
  • 对于 ER 图，贪婪策略显著优于线性策略，其 CZ 门数随 $O(n^{5/2})$ 缩放，而线性策略为 $O(n^3)$。
• 可行性区间：门计数的减少扩展了噪声硬件上的可行问题规模。对于固定的 CZ 门预算（例如 3,600 个门），贪婪策略能够执行高达 100 个节点的实例，而线性策略仅限于约 60 个节点。
• 近似比：硬件实验展示了性能的提升：
  • 最大割 (MC)：与线性策略相比，贪婪策略将平均近似比提高了高达 6.62%（在 72 个量子比特时）。
  • 最大独立集 (MIS)：改进更为显著，在 56 个量子比特时达到了 9.32%。
• 截断对比：不同于通过截断代价哈密顿量来减少深度的方法（这会牺牲理论保证），贪婪策略在相同的 SWAP 层下实现了显著更大规模的目标相互作用子集，从而保留了更多的题目结构。

意义与主张

论文声称，高效的转译对于 QAOA 在近期的硬件上的实际表现至关重要。作者断言，其问题感知型转译方案是提高量子算法在噪声设备上性能的关键，特别是对于稀疏优化问题。

关于意义的关键主张包括：

• 实现更大规模的实验：通过减少电路深度和误差累积，该方法使得在当前硬件上进行高达 80 个量子比特的实验成为可能。
• 放大硬件改进的效果：随着硬件质量的提高（可用 CZ 门预算的增加），高效转译带来的益处会被放大。随着门预算的增长，与线性策略相比，贪婪策略允许更大规模的可访问问题规模。
• 与量子优势的相关性：该方法对于探测潜在量子优势的领域特别相关，包括经典求解器难以处理的困难领域（例如 500 个节点的低密度 MIS 实例）。
• 面向未来：这项工作强调，随着纠错码（如双变量自行车码）需要基于矩形点阵的结构化、非局部连通性，调整转译策略以利用 2D 连通性对于降低未来架构的电路复杂度将至关重要。

作者总结道，虽然他们的方法依赖于预定义的 SWAP 层，但它证明了问题感知型转译是弥合理论量子算法与实际、有噪声硬件执行之间差距的必要步骤。