量子近似优化算法的自旋-玻色映射#

Sami Boulebnane,^1,* Abid Khan , 1,* Minzhao Liu ,^1,† Jeffrey Larson , Dylan Herman, Ruslan Shaydulin ,^1,‡ and Marco PistoiaGlobal Technology Applied Research, JPMorganChase, New York, New York 10001, USAMathematics and Computer Science Division, Argonne National Laboratory, Lemont, Illinois 60439, USA

(2025年11月24日收稿；2026年4月14日接收；2026年6月16日发表)

量子近似优化算法(QAOA)的性能随电路深度$p$单调提升，然而对高深度区域的研究一直受到现有精确评估技术中随$p$指数增长的计算成本的阻碍。在本快报中，我们证明，在无穷大尺寸极限下，用于Sherrington-Kirkpatrick (SK) 模型的深度$p$ QAOA态收敛于一个自旋与$p$个玻色子模耦合的态。我们利用矩阵积态模拟自旋-玻色系统，并给出数值证据表明，在平均情况下，QAOA以电路深度$\mathcal{O} ( n / \epsilon^{1.13} )$获得SK模型最优能量的$(1-\epsilon)$近似。我们方法的计算成本适中，使我们能够优化QAOA参数，并观察到在无穷大尺寸极限下，QAOA在$p=160$时达到$\varepsilon \lesssim 2.2 \%$，远远超出先前精确方法可及的$p \leq 20$范围。我们的映射提供了一条多体路径，用于在先前无法进行精确评估的区域内研究和优化高深度QAOA。

优化问题在科学和工业中无处不在，并且通常计算上难以求解。因此，利用量子计算机加速优化问题求解的兴趣日益增长。一个有前途的通用优化算法是量子近似优化算法(QAOA)，有证据表明，对于某些问题，相比于专门的经典算法，QAOA可实现多项式或指数加速[1-4]。

证明量子优势的一种方式是证明量子算法的扩展性优于任何经典算法，就像用于无结构搜索的Grover算法[5]那样。更常见的是，经典下界难以企及，量子优势的论证依赖于缺乏高效经典算法，例如在因子分解[6]以及使用解码量子干涉测量法(DQI)求解最优多项式交集[7]中的量子优势情况。重要的是，即使在对量子算法性能缺乏解析界的情况下，也已开发出专门的数值方案，以获得超出蛮力经典模拟的大规模量子算法的性能保证，使我们能够与现有经典算法进行基准测试，并寻找量子加速的实例。这种论证方式同时用于DQI和QAOA，是我们探索量子优势的关键工具[8]。

在无穷大尺寸极限下评估QAOA性能的形式体系允许与经典算法进行比较[9]。由于QAOA的性能随算法深度$p$单调提升，常见方法是评估尽可能大的$p$（例如，$p \leq 20$ [9]）下的性能，并与经典算法比较。此类方案的核心挑战在于，评估QAOA性能的计算成本随深度$p$呈指数增长。我们通过识别QAOA态在无穷大尺寸极限下与自旋-玻色系统态之间的等价性，并利用矩阵积态以适中成本模拟后者，克服了这一挑战。我们的技术评估QAOA性能；模拟QAOA电路和采样仍需量子计算机。

QAOA的目标是优化一个关于$n$比特串$z = ( z_{1} , \ldots , z_{n} ) \in \{+1, -1\}^n$的经典目标函数$C(z)$。将该目标函数提升为算符$C$，使得

其中$z$是一个计算基态，QAOA随后通过一个由整数参数$p \geq 1$刻画的量子电路，生成如下形式的量子态，以寻找低成本比特串：

这里，$s$代表计算基态上的均匀叠加，算符$\bar{U ( C , \gamma )} = e^{- i \gamma C}$在计算基上是对角的，而$U ( B , \beta ) = e^{- i \beta B}$，其中$B = \textstyle \sum_{j} X_{j}$是单量子比特泡利X算符之和。角度$\pmb{\gamma} = ( \gamma_{1} , . . . , \gamma_{p} )$和$\pmb{\beta} = ( \beta_{1} , . . . , \beta_{p} )$是定义QAOA态的经典参数。当在计算基上测量态$| \gamma , \beta , C \rangle$时，会产生一个比特串，其代价函数值的期望代价为$\langle \gamma , \beta , C | C | \gamma , \beta , C \rangle$。

在本文中，我们研究了应用于Sherrington-Kirkpatrick模型的QAOA。该模型是一个经典自旋系统，具有$n$个自旋之间的全连接耦合，其能量由下式给出：

其中$J_{jk} \sim \mathcal{N} ( 0 , 1 )$。SK模型通过代价算符$\begin{array} {r} {C^{\mathrm{SK}} = ( 1 / \sqrt{n} ) \sum_{j < k} J_{jk} Z_{j} Z_{k}} \end{array}$编码到量子比特上，其中$Z_{j}$是量子比特$j$上的泡利Z算符。SK模型最初是为了研究无序磁体而提出的[10]，但后来已成为理解复杂能量景观行为的典范模型。SK模型及其推广已被用于理解随机组合优化问题[11,12]、神经网络[13-15]以及其他系统[16]。

在无穷大尺寸极限下，典型实例的最低能量达到所谓的Parisi值[17-19]：

在最坏情况下，精确找到SK模型的基态是一个非确定性多项式时间困难（NP困难）的优化问题[20]，而在实践中，通用启发式算法需要超多项式时间[21-23]。存在一些基于Hessian上升法[24]和消息传递法[25]、使用时间与$1 / \epsilon$呈指数关系的算法，可以证明找到$( 1 - \epsilon )$近似解。缺乏可证明的精确求解器，加上其经验上的平均情况困难性，推动了针对SK模型的量子算法研究。

已有推测认为，QAOA能够以深度$p$（大约与$1 / \epsilon$成线性关系）高效地找到SK模型的$( 1 - \epsilon )$近似解[9,26]。具体来说，文献[26,27]精确计算了实例平均的无穷大尺寸QAOA能量密度：

其中期望是对 SK 耦合 J 的随机选择取平均，分别计算到 $p = 11$ 和 $p = 20$。由于复杂度随 p 呈指数增长，文献 [26,27] 未能研究更高深度。利用本文引入的自旋-玻色子映射（图1），我们计算了更大 p 下的 $\nu_{p}$，展示了 QAOA 能量向 $P_{*}$ 的收敛性。

图1：QAOA 态之间的等价关系。(a) 用于计算 SK QAOA 能量密度的双边树 S。我们特别考虑 $p = 3$ 和 $D = 2$。每个节点是一个量子比特，每条边表示 ZZ 相互作用。树的半部分是 $\mathcal{T}$。该树上的 QAOA 态在以 $\mathcal{D}_{j}^{\prime}$ 为根的子树的交换下是对称的。(b) 在 $D \to \infty$ 极限下构造 $\tau$ 上 QAOA 态所需的演化。根量子比特 ∅ 映射为一个自旋，每个子树映射为一个玻色子或真空。玻色子模式初始化为真空态。蓝色门是 X 旋转，黄色门是自旋控制的玻色子模式位移。

为了建立自旋-玻色子等价性，我们首先考虑树图上的 QAOA 态。下面，对于边集为 E 的 D-正则图 $G = \left( V , E \right)$，我们将成本哈密顿量记为 $C^{G} = ( 1 / \sqrt{D} ) \textstyle \sum_{( u , v ) \in E} Z_{u} Z_{v}$，将混合哈密顿量记为 $\begin{array} {r} {B^{G} = \sum_{v \in V} X_{v}} \end{array}$。我们选择这个问题，基于文献 [9] 的以下结果：

定理 1（文献 [9] 的定理 1）— 对于所有 p 和所有参数 $\gamma , \beta$，SK 模型上无限大无序平均 QAOA 能量密度，等于图1(a) 中 D 叉双边树 S 上 QAOA 态的 ZZ 期望值在 D → ∞ 极限下的结果：

在文献 [9] 中，树图源于如下观察：随机正则图以高概率局部呈树状。因此，足够大的随机正则图上的 QAOA 能量等价于树图上的 QAOA 能量。这一局域性论证已被推广，表明在广泛稀疏约束满足问题和自旋玻璃上，QAOA 能量具有等价性 [27]，这为将自旋-玻色子映射推广到其他问题提供了途径。

自旋-玻色映射#

我们的主要结果是，在 D → ∞ 极限下，单边树 $\tau$（双边树 S 的一半）上的 QAOA 态（在范数下）收敛到一个自旋-玻色子态，并且自旋的两时间自关联函数与无序平均 QAOA 能量密度一致。我们现在给出一个直观描述，详细证明见补充材料 [28]（第 VI 节）。

深度为 p 的树 ${\mathcal{T}} = {\mathcal{T}}^{( p )}$ 由一个根顶点 ∅ 和 D 份深度为 $( p - 1 )$ 的子树 $\scriptstyle{\mathcal{T}}^{( p - 1 )}$ 组成，这些子树的根为 $\mathbb{O}_{i}^{\prime}$，其中 $i \in [ D ]$。对于 QAOA 态 $| \gamma , \beta , C^{T} \rangle$，这 D 个子树的排列不改变该态。这种置换对称性自然地提供了将 $D$ 个子树视为 D 个玻色子的识别方式。

此外，对于第 t 层 QAOA，

因此，每个子树 $\scriptstyle{\mathcal{T}}^{( p - 1 )}$ 的根 $\mathbb{O}_{i}^{\prime}$ 通过 $e^{{- i \gamma_{t} Z_{\emptyset} Z_{\emptyset^{\prime}}} / {\sqrt{D}}}$ 与整棵树的根 $\varnothing$ 相互作用。

在每个 QAOA 层 t，我们仅在根量子比特上插入计算基下的单位分解，$\begin{array} {r} {I_{\otimes} = \sum_{z_{\otimes}^{[ t ]} = \pm 1} | z_{\otimes}^{[ t ]} \rangle \langle z_{\otimes}^{[ t ]} |} \end{array}$，从而将动力学重写为根自旋历史 $\boldsymbol{z}_{\emptyset} = ( z_{\emptyset}^{[ 1 ]} , . . . , z_{\emptyset}^{[ p ]} )$ 的和。对于固定的历史 $z_{\infty}$，第 t 层的根与子树 i 的根 $\mathbb{O}_{i}^{\prime}$ 之间的耦合简化为

因此，每一层贡献要么为单位算符，要么为在 $\mathbb{O}_{i}^{\prime}$ 上的单个 Z 插入，振幅为 $\mathcal{O} ( D^{- 1 / 2} )$。跨越 p 层后，结果得到一个无插入且振幅为 $\mathcal{O} ( 1 )$ 的项，以及 p 个在某个 $t \in [ p ]$ 处有单个 Z 插入且振幅为 $\mathcal{O} ( D^{- 1 / 2} )$ 的项；具有两个或更多插入的项在 $D \to \infty$ 时消失（对于固定的 $p$）。

将无 Z 插入的子树态记为 $| \Psi^{( p - 1 )} \rangle$，将在第 t 层有单个 Z 插入的子树态记为 $| \Psi_{t}^{( p - 1 )} \rangle$。在上述大 D 展开中，子树态的形式为

将 $\left| \Psi^{( p - 1 )} \right.$ 视为真空态，$| \Psi_{t}^{( p - 1 )} \rangle$ 视为玻色子模式 t 中的单激发，则每个子树得到一个 p 模式单粒子流形。子树之间的置换对称性进一步将其提升为自旋耦合到 p 个玻色子模式的描述。特别地，随着 $D \to \infty$，该态收敛到一个具有有限粒子数的明确定义的极限。

定理 2（非正式表述；证明见文献[28]）——当 $D \to \infty$ 时，态 $| \gamma , \beta , C^{T} \rangle$ 强收敛到 $\mathbb{C}^{2} \otimes \mathbf{L}_{2} ( \mathbf{R} )^{\otimes p}$ 中的一个极限；

通过适当选择 $c .$，求和遍历所有自然数元组 $\pmb{n} = ( n_{1} , . . . , n_{p} )$，这些元组定义了相应的数态 $| \pmb{n} \rangle = | n_{1} , . . . , n_{p} \rangle$。

为了说明粒子数是有限的，我们注意到每个子树状态为非真空（即处于状态 $| \Psi_{t}^{( p = 1 )} \rangle$）的概率是 $\mathcal{O} ( D^{- 1} )$，如公式(9)所示。拥有 D 个子树意味着对于固定的 $p .$ 总粒子数为 $\mathcal{O} ( 1 )$ ^{ð Þ}因此，我们可以将福克空间维数截断为有限数 $d .$

这一结果确立了相应玻色子态的存在性，但并未描述如何获得它。我们现在给出获得该态的过程，证明推迟到补充材料[28]（第一节）中给出。我们首先将自旋初始化到该态，并将玻色子模式初始化为真空态。然后，对于QAOA的每一层，由自旋控制的单模位移作用于所有玻色子模式，随后是对自旋态施加旋转 $\exp ( - i \beta_{t} X )$。对所有 $p$ 层重复此过程。自旋-玻色子态的演化如图1(b)所示。

数值结果与讨论#

演化这个自旋-玻色子系统，通过态矢量模拟将产生 $\mathcal{O} ( d^{p} )$ 的代价。幸运的是，我们发现 $d \lesssim 10$ 就足以精确演化自旋-玻色子系统，因为误差在 d 中呈指数消失，并且对 $p$ 的依赖性适中（见补充材料[28]，第五节）。此外，我们发现该系统在整体上的纠缠相对较低，可以利用矩阵乘积态来利用这一点。这些截断的成功可能具有独立的意义，因为它揭示了无限大极限下QAOA行为的基本方面。

利用我们的自旋-玻色子映射，我们通过将点 $( p , \nu_{p} )$ ^{ð Þ}拟合到以下方程，数值研究了相对误差 $\epsilon ( p )$ 如何趋近于零

我们拟合了图2中从 $p = 15$ 到 $p = 80$ 的数据，得到 $\eta = 0.88 \pm 0.03 , m = 1.34 \pm 0.10 , b = 0.002 \pm 0.003$，拟合优度为 $1 - R^{2} = 6.83 \times 10^{- 5}$。误差线是99.7%的置信区间（最多偏离均值三个标准差），通过自助法得到。

尽管我们不能排除无限接近 Parisi 值存在阻碍的可能性，但我们根据经验观察到 QAOA 收敛到 Parisi 值。因此，未来工作的一个有趣方向是证明 QAOA 能够以深度 $p o l y ( 1 / \epsilon )$ 实现任意小的 ϵ。在补充材料[28]（第三节）中，我们还按照文献[83]的做法，将函数拟合为 $\epsilon ( p ) =$ $m / ( p^{\eta} + c )$。

^{ð þ Þ}由于文献[26]建立的关于无序的浓度性质，无限大极限能量是典型大规模实例 QAOA 性能的良好预测指标。

图2：来自 Parisi 值的归一化 QAOA 能量偏差 $\epsilon ( p )$。QAOA 参数已优化至 $p = 80$。对于 $p \in \{120 , 160 \}$ 的参数是从 $p = 80$ 外推得到，但未经过优化。x 轴重新标度为 $1 / p^{\eta}$，其中 $\eta \approx 0.88$ 是为最大化公式(12)中描述的线性回归的 $R^{2}$ 值而选择的。

因此，使用无限大极限优化角度的 QAOA 应该在随机有限规模实例上表现良好。我们通过生成规模从 $N = 2$ 到 $N = 30$ 的随机 SK 模型实例（每个规模 2000 个实例）来验证这一点，结果如图3所示。

对于给定深度 $p$ 的特定实例，其性能通过近似比来衡量，定义为

其中 $E ( \gamma , \beta )$ 是由 QAOA 对该实例生成的按比特串平均的能量，$E_{\mathrm{min}} ~ \left( E_{\mathrm{max}} \right)$ 是该实例的最小（最大）能量值。我们使用近似比而非原始能量，因为有限尺寸 SK 实例的典型最优能量与无限尺寸最优能量（Parisi 值）不同。因此，不同尺寸之间的原始 QAOA 能量可能难以比较。

QAOA 随 $p$ 变化的近似比（针对选定的实例尺寸）如图3(a)所示。即使实例规模适中，在使用无限尺寸最优参数且无需实例特定优化的情况下，随着 $p$ 的增加，实例间的平均近似比也会提升。我们绘制了 $n \to \infty$ 极限下的预测近似比，即 $1 - \nu_{p} ( \gamma , \pmb{\beta} ) / \Pi^{*}$，以供参考。这表明使用在无限尺寸极限下优化的角度是一种实用的 QAOA 近似优化运行方式。

接下来，我们评估 QAOA 作为精确求解器的性能。在图3(b)中，我们展示了 QAOA 深度 $p$ 需要如何增长才能获得获取最优比特串的恒定概率 $\mathrm{P r^{*}}$。我们的结果表明，当深度 $p \propto n^{\varsigma}$ 且 $\varsigma \approx 1.3$ 时，QAOA 能够实现恒定的成功概率 $\mathrm{P r^{*}}$。我们注意到，对于不同的 $\mathrm{P r^{*}}$，得到的 $\varsigma$ 值存在微小变化；我们将其归因于数据集的有限规模以及有限尺寸效应。作为参考，取 $\mathrm{P r^{*}} = 0.5$ 时，预测用 QAOA 精确求解 SK 模型所需的电路深度约为 $0.88 \cdot n^{1.3}$。

我们还可以通过考察固定 $p$ 下成功概率随 $n$ 的衰减来估算 $p$ 的缩放比例。如图3(c)所示。对于小 $p$，结果表明成功概率随 $n$ 呈指数衰减。对于每个 $p$，我们将成功概率拟合为 $A ( p ) 2^{- \kappa ( p ) n}$。我们观察到指数满足 $\kappa ( p ) \propto p^{- 0.72}$。这表明深度 $p \propto n^{1 / 0.72} \approx n^{1.39}$ 足以实现恒定的 $\mathrm{P r^{*}}$，这与图3(b)一致。

(a)

讨论——我们的结果建立了 QAOA 极限行为与自旋-玻色子系统动力学之间的等价性。这一关联为将非平衡量子多体物理学技术应用于量子优化算法的研究打开了大门。所建立的等价性揭示了空间（$p$ 个玻色子模式）与时间（$p$ 个 QAOA 层）之间令人惊讶的对偶性，这值得进一步研究。我们相信，除了 Sherrington-Kirkpatrick 模型之外，许多优化问题都可以从类似的映射中受益，从而允许在比精确评估所能达到的更大深度上研究 QAOA。我们的映射很可能可以直接推广到更高阶的自旋玻璃，参考文献[27]给出了与本文考虑的 Sherrington-Kirkpatrick 模型类似的精确解析公式。另一个方向可能是将我们的映射和态构造过程扩展到度数大但有限的图。虽然由于交换对称性，在这种情况下存在 QAOA 态的玻色子解释，但高效地顺序构造该态可能更具挑战性。

图3：使用无限尺寸极限参数在有限尺寸实例上运行的 QAOA。(a) 无论 $n$ 如何，随着 QAOA 深度 $p$ 的增长，平均近似比趋近于 1。(b) 实现恒定成功概率 $\mathrm{P r^{*}}$ 所需的 QAOA 深度 $p$。(c) 在固定 $p$ 下，成功概率随系统规模 $n$ 呈指数衰减。我们在插图中拟合了指数 $\kappa ( p )$ 与 $p$ 的关系。

QAOA在实际中展现的性能优于SK模型经典算法的先前结果。首先，我们尚未发现任何经典算法能在$poly(n, 1/\epsilon)$时间内实现$(1 - \epsilon)$近似。文献[24,25]的方法或许可以通过扩展^{ð Þ}来证明对$1/\epsilon$的多项式依赖。在补充材料[28]（第VIII节）中，我们尝试改进复杂度。文献[25]报告的运行时间为$C(\epsilon) n^{2}$。我们展示了并行化能将其改进$n$倍，且$C(\epsilon) = \mathcal{O} [ e^{\mathcal{O} ( 1/\epsilon^{4} )} / \epsilon^{16} ]$，仍未能实现^{ð Þ ¼ ½ }多项式依赖。我们注意到有一个普遍观点，认为该复杂度可以改进到$\mathcal{O} ( n / \epsilon^{2} )$，但缺乏^{ð Þ}详细的实证研究来证明其复杂度优于已知的理论界。其次，我们尚未发现任何经典算法能在$poly(n)$时间内精确求解SK模型。通过扩展文献[24,25]的方法来解决这一问题似乎更具挑战性。需要指出的是，我们关于QAOA作为精确求解器的结果是通过模拟小规模实例的完整QAOA量子态得到的；还需要进一步研究来验证这一行为在更大$n$时是否依然成立。

虽然已知SK模型在最坏情况下是NP难的[20]，但其平均情况下的困难程度尚未被充分理解。某些类别的算法已被排除作为在平均情况下求解SK模型基态的方法。例如，没有稳定的算法能够在低温下近似采样SK吉布斯测度[84]。计算SK模型的配分函数是Sharp-P难的[11]。此外，SK模型对耦合中的微小扰动表现出混沌性[85]，这表明低次多项式（LDP）算法不应能成功求解它。然而，QAOA对SK模型的精确高效求解并不被这些结果排除。例如，$p = poly(n)$的QAOA不是LDP算法。我们希望我们的结果暗示了SK模型在平均情况下容易求解，这为自旋玻璃的行为提供了宝贵见解，因此在量子计算领域之外也具有趣味性。

致谢—作者感谢Leo Zhou、Kunal Marwaha和James Sud对本文草稿的有益评论，感谢Shouvanik Chakrabarti、Helmut Katzgraber、Sergey Knysh和Hidetoshi Nishimori对SK模型的有益讨论。作者感谢Katherine Klymko对数值实验的宝贵反馈以及对在Perlmutter超级计算机上执行计算的支持。作者感谢Shree Hari Sureshbabu、Zichang He、Atithi Acharya和Brajesh Gupt关于QAOA参数优化以及QAOA与自旋-玻色系统经典模拟的有益讨论。作者感谢摩根大通全球技术应用研究中心的同事们提供的支持和有益讨论。本工作基于美国能源部科学办公室国家量子信息科学研究中心的资助。本研究使用了阿贡领导力计算设施的资源，该设施是美国能源部（DOE）科学办公室位于阿贡国家实验室的用户设施，并基于美国DOE科学办公室-高级科学计算研究计划的资助，合同编号DE-AC02-06CH11357。本研究使用了国家能源研究科学计算中心（NERSC）的资源，该中心是美国能源部科学办公室的用户设施，获得NERSC奖项编号DDR-ERCAP0034098。

S. B.和R. S.构思了该项目。S. B.构思并发展了证明模拟QAOA能量与自旋-玻色系统等价的理論分析。S. B.实现了张量网络模拟的原型。A. K.改进了张量网络模拟，将其扩展到超级计算机上，并进行了数值实验。M. L.帮助改进了张量网络模拟。J. L.开发并集成了数值优化器。D. H.分析了文献[25]的经典消息传递算法。S. B.、A. K.、M. L.、J. L.、D. H.、R. S.和M. P.共同参与了技术讨论和论文撰写。

作者声明： 本文由摩根大通全球技术应用研究中心提供，仅供信息参考。本文并非摩根大通或其关联机构研究部门的产品。摩根大通及其任何关联机构均不对本文作任何明示或暗示的陈述或保证，且均不对与本文相关的任何责任负责，包括但不限于对本文所载信息的完整性、准确性或可靠性，以及其可能产生的法律、合规、税务或会计影响。本文档无意作为投资研究或投资建议，也不构成对任何证券、金融工具、金融产品或服务的购买或出售的建议、要约或招揽，也不得以任何方式用于评估参与任何交易的利弊。美国政府保留，并且通过接受发表本文，出版商承认美国政府保留，一项非排他性、已付费、不可撤销的、全球性的许可，以发表或复制本作品的已发表形式，或允许他人为美国政府目的这样做。

数据可用性——针对无限大极限下SK模型深度p的QAOA的所有优化角度可在QOKit [87]中找到。本工作中提出的完整数据见参考文献[86]。详细推导及其他数值结果见补充材料[28]。

[1] S. Boulebnane 和 A. Montanaro, PRX Quantum , 030348 (2024).

[2] R. Shaydulin 等人, Sci. Adv. , eadm6761 (2024).[3] E. Farhi, S. Gutmann, D. Ranard 和 B. Villalonga, arXiv: 2503.12789.

[4] A. Montanaro 和 L. Zhou, arXiv:2411.04979.

[5] L. K. Grover, 收录于《第二十八届年度ACM计算理论研讨会论文集——STOC '96》STOC '96 (ACM Press, New York, NY, 1996), 第212–219页.

[6] P. W. Shor, 收录于《第35届计算机科学基础年度研讨会论文集》FOCS 1994 (IEEE, Piscataway, NJ, 1994), 第124–134页.

[7] S. P. Jordan, N. Shutty, M. Wootters, A. Zalcman, A. Schmidhuber, R. King, S. V. Isakov, T. Khattar 和 R. Babbush, Nature (London) , 831 (2025).[8] H.-Y. Huang, S. Choi, J. R. McClean 和 J. Preskill, arXiv: 2508.05720.

[9] J. Basso, E. Farhi, K. Marwaha, B. Villalonga 等人, 收录于《第17届量子计算、通信与密码学理论会议 (TQC 2022)》, Leibniz国际信息学会议论文集 (LIPIcs) 第232卷 (Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2022), 第7:1–7:21页.

[10] D. Sherrington 和 S. Kirkpatrick, Phys. Rev. Lett. , 1792–1796 (1975).

[11] D. Gamarnik 和 E. C. Kızılda ´g, Ann. Appl. Probab. , 1474 (2021).

[12] M. M´ezard, G. Parisi 和 R. Zecchina, Science , 812 (2002).

[13] D. J. Amit, H. Gutfreund 和 H. Sompolinsky, Phys. Rev. A , 1007 (1985).

[14] A. Engel, 《学习的统计力学》（Statistical Mechanics of Learning）(Cambridge University Press, Cambridge, England, 2001).

[15] H. Nishimori, 《自旋玻璃与信息处理的统计物理学：导论》（Statistical Physics of Spin Glasses and Information Processing: An Introduction）, 国际物理专著系列第111卷 (Clarendon Press, Oxford, 2001).

[16] C. Villani, 《最优输运》（Optimal Transport）(Springer, Berlin Heidelberg, 2009).[18] A. Crisanti 和 T. Rizzo, Phys. Rev. E , 046137 (2002).[19] K. Binder 和 A. P. Young, Rev. Mod. Phys. , 801 (1986).

[21] M. Aramon, G. Rosenberg, E. Valiante, T. Miyazawa, H. Tamura 和 H. G. Katzgraber, Front. Phys. , 48 (2019).

[22] T. Leleu, F. Khoyratee, T. Levi, R. Hamerly, T. Kohno 和 K. Aihara, Commun. Phys. , 266 (2021).[23] K. Sankar, A. Scherer, S. Kako, S. Reifenstein, N. Ghadermarzy, W. B. Krayenhoff, Y. Inui, E. Ng, T. Onodera, P. Ronagh 和 Y. Yamamoto, npj Quantum Inf. , 64 (2024).

[24] D. Jekel, J. S. Sandhu 和 J. Shi, 收录于《2025年ACM-SIAM离散算法年度研讨会论文集 (SODA)》(SIAM, Philadelphia, PA, 2025), 第5307–5387页.

[26] E. Farhi, J. Goldstone, S. Gutmann 和 L. Zhou, Quantum , 759 (2022).

[27] J. Basso, D. Gamarnik, S. Mei 和 L. Zhou, 收录于《2022年IEEE第63届计算机科学基础年度研讨会 (FOCS)》(IEEE, Piscataway, NJ, 2022), 第335–343页.

[28] 详见 http://link.aps.org/supplemental/10.1103/2w94-rymn 的补充材料，其中包含自旋玻色子映射的详细证明、QAOA能量计算过程、Fock空间截断分析、替代拟合函数以及经典消息传递算法的分析，并引用了文献[29–82]。

[29] T. Ayral, T. Louvet, Y. Zhou, C. Lambert et al., PRX Quantum , 040304 (2023).

[30] J. Larson and M. Menickelly, Math. Program. Comput. , 1 (2024).

[31] J. Larson, M. Menickelly, J. P. O’Neal, and S. M. Wild, Interpolation-Based Composite Derivative-Free Optimization (2025), https://github.com/POptUS/IBCDFO.

[32] S. M. Wild, in Advances and Trends in Optimization with Engineering Applications, edited by T. Terlaky, M. F. Anjos, and S. Ahmed (SIAM, 2017), pp. 529–540.

[33] B. Villalonga, Performance of the QAOA on MaxCut over Large-Girth Regular Graphs (2022), https://github.com/benjaminvillalonga/large-girth-maxcut-qaoa.

[34] E. Farhi, J. Goldstone, and S. Gutmann, https://arxiv.org/abs/1411.4028.

[35] M. P. Harrigan, K. J. Sung, M. Neeley, K. J. Satzinger et al., Nat. Phys. , 332 (2021).

[36] S. Boulebnane, J. Sud, R. Shaydulin, and M. Pistoia, arXiv:2503.09563.

[37] F. Verstraete and J. I. Cirac, Phys. Rev. B , 094423 (2006).

[38] T. Hao, Z. He, R. Shaydulin, J. Larson, and M. Pistoia, Phys. Rev. Res. , 033179 (2025).

[39] Z. He, R. Shaydulin, D. Herman, C. Li et al., Parameter setting heuristics make the quantum approximate optimization algorithm suitable for the early fault-tolerant era, in ICCAD ’24: Proceedings of the 43rd IEEE/ACM International Conference on Computer-Aided Design (ACM, New York, NY, 2024), Vol. 63, pp. 1–7.

[40] M. Fishman, S. R. White, and E. M. Stoudenmire, SciPost Phys. Codebases 4 (2022).

[41] Argonne leadership computing facility.

[42] National energy research scientific computing.

[43] T. Hogg and D. Portnov, Inf. Sci. (NY) , 181 (2000).

[44] T. Hogg, Phys. Rev. A , 052311 (2000).

[45] S. Omanakuttan, Z. He, Z. Zhang, T. Hao, A. Babakhani, S. Boulebnane, S. Chakrabarti, D. Herman, J. Sullivan, M. A. Perlin, R. Shaydulin, and M. Pistoia, arXiv:2504.01897.

[46] R. Shaydulin and M. Pistoia, in 2023 IEEE International Conference on Quantum Computing and Engineering (IEEE, Piscataway, NJ, 2023), pp. 1074–1077.

[47] E. Pelofske, A. Bärtschi, and S. Eidenbenz, in Lecture Notes in Computer Science (Springer Nature, Switzerland, 2023), pp. 240–258.

[48] E. Pelofske, A. Bärtschi, L. Cincio, J. Golden, and S. Eidenbenz, npj Quantum Inf. , 109 (2024).

[49] B. Tasseff, T. Albash, Z. Morrell, M. Vuffray, A. Y. Lokhov, S. Misra, and C. Coffrin, J. Heuristics , 325 (2024).

[50] Z. He, R. Shaydulin, S. Chakrabarti, D. Herman, C. Li, Y. Sun, and M. Pistoia, npj Quantum Inf. , 121 (2023).

[51] Z. He, D. Amaro, R. Shaydulin, and M. Pistoia, Commun. Phys. , 217 (2025).

[52] Z. Zhang, J. Shen, N. Kumar, and M. Pistoia, arXiv:2504 .00987.

[53] G. Parisi, Proc. Natl. Acad. Sci. U.S.A. , 7948 (2006).

[54] A. Anshu and T. Metger, Quantum , 999 (2023).

[55] A. Apte, S. H. Sureshbabu, R. Shaydulin, S. Boulebnane, Z. He, D. Herman, J. Sud, and M. Pistoia, arXiv:2504.01694.

[56] R. Shaydulin, I. Safro, and J. Larson, in Proceedings of the IEEE High Performance Extreme Computing Conference (IEEE, Piscataway, NJ, 2019).

[57] A. E. Alaoui, A. Montanari, and M. Sellke, arXiv:2001 .00904.

[58] A. Auffinger and W.-K. Chen, Commun. Math. Phys. , 1429 (2014).

[59] JPMorgan Chase, QOKit, https://github.com/jpmorganchase/QOKit (2023), accessed: 2025-05-12.

[60] A. Jagannath and I. Tobasco, Proc. Am. Math. Soc. , 3135 (2016).

[61] A. Auffinger and W.-K. Chen, arXiv:1303.3573.

[62] Y. Jin, Z. He, T. Hao, D. Amaro, S. Tannu, R. Shaydulin, and M. Pistoia, arXiv:2504.21172.

[63] A. Auffinger, W.-K. Chen, and Q. Zeng, arXiv:1703.06872.

[64] P. C. Lotshaw, G. Siopsis, J. Ostrowski, R. Herrman, R. Alam, S. Powers, and T. S. Humble, Phys. Rev. A , 042411 (2023).

[65] V. Akshay, H. Philathong, E. Campos, D. Rabinovich, I. Zacharov, X.-M. Zhang, and J. D. Biamonte, Phys. Rev. A , 042438 (2022).

[66] J. A. Montanez-Barrera and K. Michielsen, npj Quantum Inf. , 131 (2025).

[67] L. Zhou, $g_{s} , t$ is the autocorrelation function (private correspondence).

[68] D. Panchenko, The Sherrington-Kirkpatrick Model (Springer Science & Business Media, New York, 2013).

[69] A. Auffinger and W.-K. Chen, arXiv:1606.05335.

[70] W.-K. Chen, M. Handschy, and G. Lerman, Probab. Theory Relat. Fields , 53 (2017).[71] D. Gamarnik, Proc. Natl. Acad. Sci. U.S.A. , e2108492118 (2021).

[72] A. E. Alaoui and A. Montanari, arXiv:2009.11481.

[73] M. Talagrand, Ann. Math. , 221 (2006).[74] O. Y. Feng, R. Venkataramanan, C. Rush, and R. J. Samworth, Found. Trends Mach. Learn. , 335 (2022).[75] A. E. Alaoui, A. Montanari, and M. Sellke, arXiv:2111.06813.

[76] H. E. Cheairi and D. Gamarnik, arXiv:2412.18014.

[77] Y. Nesterov et al., Lectures on Convex Optimization (Springer, New York, 2018), Vol. 137.

[78] M. Ivkov and T. Schramm, arXiv:2311.09017.

[79] L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Phys. Rev. X , 021067 (2020).

参考文献#

[81] S. Aaronson and A. Arkhipov, in Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC ’11 (Association for Computing Machinery, New York, 2011), pp. 333–342.

[82] A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, Nat. Phys. , 159 (2019).

[83] L. Zhou, The QAOA at high girth for MaxCut and the Sherrington-Kirkpatrick model, Talk at the TQC 2022 Conference (2022).

[84] A. E. Alaoui, A. Montanari, and M. Sellke, arXiv:2203.05093.

[85] S. Chatterjee, arXiv:0907.3381.

[86] S. Boulebnane, A. Khan, M. Liu, J. Larson, D. Herman, R. Shaydulin, and M. Pistoia, Data for “A spin-boson mapping of the quantum approximate optimization algorithm”, 10.5281/zenodo.15103145 (2025).

[87] D. Lykov, R. Shaydulin, Y. Sun, Y. Alexeev, and M. Pistoia, in Proceedings of the SC ‘23 Workshops of the International Conference on High Performance Computing, Network, Storage, and Analysis, SC-W 2023 (ACM, New York, 2023). https://github.com/jpmorganchase/QOKit.

附录：补充材料#

量子近似优化算法的自旋-玻色子映射补充信息#

I. 无限大尺寸极限下 QAOA 能量的计算 A. 先前工作 B. 自旋-玻色子映射 C. 步骤 D. MPS 算法 E. MPS 性能 II. 在无限大尺寸极限下优化的 QAOA 参数 9 III. 备选参数拟合 11 IV. 基于自旋-玻色子系统的广义 SK-QAOA 迭代（命题 1 的证明）12 V. 截断福克空间维度的解析估计 20 A. 截断阈值的解析估计证明 20 B. 辅助技术结果 24 VI. D-正则 MAXCUT-QAOA 中映射的解释 25 A. 基本定义及作为时间关联的 G 矩阵 25 B. 第 p 层 QAOA 到 p-模自旋-玻色子系统的映射 44 VII. SK 模型的经典算法 56 VIII. 关于 SK 近似消息传递算法的复杂度 57 A. [25, 62]的算法 58 B. SK 的近似消息传递算法 60 C. 漂移和扩散系数的光滑性 61 D. ε 依赖性的上界 62

I. 无限大尺寸极限下 QAOA 能量的计算#

A. 先前工作#

文献[9]提出了一种经典方法，用于评估高围长 D-正则图上的 MAXCUT 和 SK 模型的 QAOA 能量。该工作进一步表明，在问题哈密顿量的适当归一化下，这两个能量在 MAXCUT 的无限度数极限 $( D \to \infty )$ 和 SK 的无限尺寸极限 $( n \to \infty )$ 下是相等的。在下文中，我们将这个公共能量称为 SK-QAOA 能量，或简称为 QAOA 能量。具体来说，将 p 层 QAOA 的平均情况无限大尺寸极限能量记为

其中期望值是对随机选择的耦合 $J$ 取的。

在文献[9]的形式体系中，$\nu_{p} ( \gamma , \beta )$ 可以从矩阵 $G^{( p )} \in \mathbb{C}^{( 2 p + 1 ) \times ( 2 p + 1 )}$ 基本地计算为

矩阵 $G^{( {p} )}$ 具有如下的索引顺序

并通过矩阵 $G^{( m )} \in \mathbb{C}^{( 2 p + 1 ) \times ( 2 p + 1 )}$（对于 $0 \leq m \leq p$）递归定义。这种关系构造如下。首先，引入一个 $( 2 p + 1 )$ 维向量 a，其条目 $a_{i} \in \{+ 1 , - 1 \}$，索引顺序为

我们也将这个向量称为一个比特串，其中比特被理解为取 $\{1 , - 1 \}$ 中的值。然后递归关系为

其中

且

更明确地说，在 $f \left( a \right)$ 中出现的 $2 \times 2$ 矩阵元为：

重要的是，$G^{( m )}$ 矩阵满足以下性质。首先，元素共享以下对称性：

其中采用了约定 $1 \leq r < s \leq p$ 且 $j , k \in \left\{1 , \ldots , p , 0 , - p , \ldots , - 1 \right\}$。由于这些对称关系，整个 $( 2 p + 1 ) \times ( 2 p + 1 )$ 矩阵可以由矩阵的任意 $( p + 1 ) \times ( p + 1 )$ 角完全描述。其次，对于 $1 \leq r < s \leq m$，$G_{r , s}^{( m )}$ 仅依赖于 $G_{r^{\prime} , s^{\prime}}^{( m - 1 )}$，其中 $1 \leq r^{\prime} < s^{\prime} \leq m - 1$（见文献[9]附录A.4）。

方程4-5构成了一个迭代过程，当对初始矩阵 $G^{( 0 )}$ 迭代应用 $p$ 次时，可生成 $G^{( {p} )}$，进而得到 $\nu_{p} ( \gamma , \beta )$。这个G-迭代是比特串上的有限和，因此可以在有限步内精确（达到算术误差）计算。然而，该求和中的项数按 $\mathcal{O} ( 4^{p} )$ 缩放，使得暴力求和方案在大 $p$ 时不实用。当前工作引入了该迭代过程与自旋-玻色系统之间的映射，从而降低了计算 $\nu_{p} ( \gamma , \beta )$ 的成本。

B. 自旋-玻色映射#

我们的主要理论结果是：在无限大极限下对随机耦合 J 取平均计算 SK-QAOA 能量这一任务，与模拟一个耦合到 $p$ 个玻色模的自旋-$1 / 2$ 粒子是等价的。这一结果背后的核心见解是，方程5可被解释为所述自旋-玻色系统的两点关联函数。配分函数具有路径积分测度

以及由隐式指定的作用量 $S$ 给出的费曼权重：

文献[9]表明配分函数

(13)

(14)

则矩阵元 $G_{j , k}^{( m )}$ 正是两点关联函数

现在我们描述自旋-玻色系统的构造。更具体地说，我们构建一个自旋-玻色系统，其中自旋的路径积分测度为

其中 $G$ 是任意复对称矩阵 $\in \mathbb{C}^{( p + 1 ) \times ( p + 1 )}$。通过令 $\begin{array} {r} {\dot{G} : = \check{G}^{( m - 1 )}} \end{array}$，该构造可应用于 SK-QAOA 的第 m 次迭代。物理系统的希尔伯特空间为：

其中 ${\mathcal{F}}_{i}$ 表示第 i 个玻色模的无限维福克空间。我们将通过将幺正操作作用于初始态来构造所需的态

其中横线用于区分玻色零模与量子比特计算零态。自旋-玻色系统的演化由 $p$ 个幺正层 $U_{1} , \dots , U_{p}$ 作用于初始态（方程18）来指定：

幺正算符 $U_{t}$ 由两个算符组成。第一个是作用于每个玻色模的位移算符的乘积。给定位移向量 $\pmb{\alpha} = ( \alpha_{1} , \ldots , \alpha_{p} )$，多模位移算符的形式为

其中 $D_{i}$ 是第 $i$ 个玻色子上的位移算符：

这里 $\hat{c}_{i}$ 表示玻色模 $i$ 的湮灭算符。$U_{t}$ 中的多模位移算符项为

换言之，位移向量的方向由自旋控制。$U_{j}$ 中的第二个算符是仅作用于自旋分量的 X 旋转。$U_{t}$ 的最终形式为

其中，算符 $K$ 中的 $\pmb{L_{t}} = ( L_{1 , t} , \dots , L_{p , t} )$ 是方阵 $L$ 的第 $t$ 列，该方阵定义为 $G$ 的 $( p + 1 )$ 维厄米角块 $G^{\mathrm{herm}}$ 的因式分解：

其中

$G^{\mathrm{herm}}$ 的厄米性源于 SK-QAOA 矩阵 $G^{( m )}$ 的对称性，我们假定 $G$ 满足该性质。为使方程24有意义，我们还需要 $G^{\mathrm{herm}}$ 是半正定的，我们将在下文中针对 SK-QAOA 迭代产生的矩阵序列 $G^{( m )}$ 证明这一点。在我们主要理论结果（命题1）的陈述中，下述状态（26）的变体（在两个连续幺正算符之间插入单个 $Z$ 算符）将发挥重要作用。对于 $1 \leq l \leq p$，我们定义

对于索引0，我们令

给定该系统，有如下结果成立：

命题1（自旋-玻色子态交叠的路径积分表示）。考虑状态 $| \Psi_{l} \rangle , \ l \in \{1 , \dots , p , 0 \}$，定义于方程26, 27。任意两个此类状态之间的点积可表示为

其中

因此，准概率测度 $f \left( \pmb{a} \right) H \left( \pmb{a} \right)$ 可视为生成我们所构造的自旋-玻色子系统中自旋的 $Z$ 时间关联函数的路径积分测度。

该命题的证明见附录四。将该命题递推应用于迭代5，我们得到以下用于计算 QAOA 能量的推论：

推论1（根据自旋-玻色子系统关联函数计算 SK-QAOA 迭代）。在随机选择耦合 $J$（方程1）的平均下，无限大尺寸极限下的 SK-QAOA 能量可通过自旋-玻色子态的交叠计算如下：

命题1的一个推论是，方程28中定义的量：

是一个 Gram 矩阵，因此是半正定的。由此可知，$G^{\mathrm{herm}} \succeq 0$ 自动蕴含 $\widetilde{G}^{\mathrm{herm}} \succeq 0$；将此归纳应用于 SK-QAOA 迭代 $G^{( m )}$，并将初始迭代的方程4重写为

其中显然 $G^{( - 1 )}$ 的 Hermitian 角非负，我们得到所有迭代 $G^{( m )}$ 都具有非负的 Hermitian 角。文献 [72] 曾提供一个较早的证明，说明所有 SK-QAOA 迭代的 Hermitian 角均为非负，但其利用的是当 $D \to \infty$ 时，$G^{( m )}$ 在 D-正则、高围长 MAXCUT QAOA 中作为 Pauli Z 算符时间自相关函数的解释。相比之下，在当前框架下，即使 G 可能并非作为 QAOA 电路的时间自相关函数实现，$\widetilde G^{\mathrm{herm}}$ 的非负性也自动由 $G^{\mathrm{herm}}$ 的非负性导出。

C. 步骤#

我们现在描述计算方程30中所述 QAOA 能量 $\widetilde{\nu}_{p} ( \gamma , \beta ; d , \chi_{\delta} )$ 的技巧。首先注意到，该计算依赖于评估 $( p + 1 )$ 维 Hermitian 矩阵 $G^{\mathrm{herm}}$，其元素可按如下方式计算

注意，元素 $G_{j , k}^{\mathrm{herm}}$ 仅依赖于 $j - 1$ 个幺正层。若定义以下状态

其中 |Ψ⟩ 的上标对应于所施加的幺正层层数，下标对应于 Pauli-Z 算符的位置，则对于 $1 \leq k \leq j \leq p$，$G_{j , k}^{\mathrm{herm}}$ 简化为

我们可以通过迭代演化方程35和36中描述的状态来构造 $G_{i , k}^{\mathrm{herm}}$，这些状态满足递归关系（假设 $1 \leq k \leq j$）

假设我们已使用状态集

计算了 $1 \leq r , s \leq t$ 时的 $G_{r , s}^{\mathrm{herm}}$。然后，利用方程39-41，我们可以使用这些已计算的状态来制备 $G_{t + 1 , s}^{\mathrm{herm}}$

总之，我们可以根据状态 $\left| \Psi^{( t )} \right. , \left| \Psi_{1}^{( t )} \right. , \ldots , \left| \Psi_{t}^{( t )} \right.$ 及算子 $Z$ 和 $U_{t} .$ ，将厄米矩阵 G^herm 从大小 t 迭代增长到大小 $( t + 1 )$，从而为下一次迭代生成一组新状态 ${\left| {\Psi^{( t + 1 )}} \right.} , {\left| {\Psi_{1}^{( t + 1 )}} \right.} , \ldots , {\left| {\Psi_{t}^{( t + 1 )}} \right.}$。为获得 $U_{t}$，我们需要 $\scriptstyle{\mathbf{L}}_{t}$，即矩阵 $L$（由分解 $G^{\mathrm{{herm}}} = L^{\dagger} L$ 得到）的第 t 列。在迭代 $t$ 处（此时 G 大小为 t），我们执行 Cholesky 分解以得到大小为 t 的矩阵 $L$，进而通过将 L 的第 t 列填充 $p - t$ 个零，得到 p 维向量 $\scriptstyle{\mathbf{L}}_{t}$。

D. 矩阵乘积态(MPS)算法#

要获得表达式(Eq.)30 中的 QAOA 能量，需要以数值方式计算并演化 Eq. 26 形式的状态。这可能看起来计算起来具有挑战性，因为代表 $p$ 个玻色子模式的量子态在福克基下是无限维的。实际上，我们发现使用一个较小的有限福克维度 d 就足以获得高精度的能量值。换句话说，对于每个玻色子，我们只考虑模式 $\left| \overline{{0}} \right. , \ldots \left| \overline{{d - 1}} \right.$。这会将 Eq. 21 中的位移算子 $D_{i} ( \alpha )$ 截断为一个 d 维的幺正算子。这种有限维近似使得状态 $\left| \Psi_{l} \right.$ 能够表示为一个 MPS，该 MPS 具有 p 个物理维度为 d 的玻色子位点和 1 个物理维度为 2 的自旋位点。在实践中，我们将 Eq. 26 表示为两个具有 p 个玻色子位点的 MPS：$\left| \psi_{0}^{( l )} \right.$ 和 $\left| \psi_{1}^{( l )} \right.$，其中

状态 $\left| \psi_{0}^{( l )} \right.$ 和 $\left| \psi_{1}^{( l )} \right.$ 分别是 $\left| \Psi_{l} \right.$ 投影到自旋态 |0⟩ 和 |1⟩ 上的结果，它们处于希尔伯特空间 $\mathcal{F}_{1} \otimes \dot{\cdot} \cdot \cdot \dot{\otimes} \mathcal{F}_{p} .$ 中。

模拟中计算量最大的部分是向这些状态应用 QAOA 层算子 $U_{t}$。初始状态对应于 Eq. 18 给出的乘积态，其键维度 $\chi = 1$。应用

K(α) 很直接：

此操作对每个位点应用了一个单一位点位移算子 $D_{i}$ 的乘积，因此这些算子是局域的，从而保持了 MPS 的键维度不变。另一方面，混合算子会增加 MPS 的键维度。它将 MPS 变换为

变换空间的键维度上限是输入状态键维度之和，因此键维度 $\chi$ 可能随应用的酉算子数量 $p$ 呈指数增长。然而，我们通过移除低于固定截断值的奇异值来控制键维度的增长。

计算能量 $\widetilde \nu_{p} ( \gamma , \beta )$ 的总体流程在算法 2 中概述，该算法描述了增长矩阵 $G^{\mathrm{herm}}$ ^e 的迭代过程。此方法需要存储、演化并计算自旋-玻色子态的重叠，这在算法 1 中有详细说明。我们使用 ITensor 库来执行所有张量网络方法 [45]，并在 Perlmutter [47] 和 Polaris [46] 超级计算机上部署。为了计算 QAOA 深度为 $p$ 时的单个能量值，我们使用 $p$ 块 Nvidia A100 GPU。

算法 1：AppLayer $\cdot ( \vec{\Psi}_{z} , \vec{\alpha} , \beta )$ 输入：$\Psi_{z} [ 1 , \ldots , l + 1 ] , \alpha [ 1 , \ldots , p ] , \beta$ 输出：$G_{l} [ 1 , \dots , l ] , \Psi_{z} [ 1 , \dots , l + 2 ]$ 如果 l + 1 = 0 则 $\begin{array} {r} {| \Psi^{( 1 )} ( \frac{1} {\sqrt{2}} | \overline{{0}}_{p} , \frac{1} {\sqrt{2}} | \overline{{0}}_{p} )} \end{array}$ $\begin{array} {r} {| \Psi_{1}^{( 1 )} ( \frac{1} {\sqrt{2}} | \overline{{0}}_{p} , - \frac{1} {\sqrt{2}} | \overline{{0}}_{p} )} \end{array}$ $\Psi_{z} \Big [ \Big | \Psi_{1}^{( 1 )} \Big \rangle , \Big | \Psi^{( 1 )} \Big \rangle \Big ]$ l ← 1 对于 i = 1 到 l + 1 执行 $( | \psi_{0} \rangle , | \psi_{1} \rangle ) \Psi_{z} [ i ]$ $| \psi_{0} \rangle \hat{D} ( \alpha [ 1 , \dots , p ] ) | \psi_{0} \rangle$ $| \psi_{1} \rangle \hat{D} ( - \alpha [ 1 , \dots , p ] ) | \psi_{1} \rangle$ $\binom{| \psi_{0} \rangle} {| \psi_{1} \rangle} \binom{\cos \beta} {- i \sin \beta} \quad \cos \beta \quad ( \frac{| \psi_{0} \rangle} {| \psi_{1} \rangle} )$ $\Psi_{z} [ i ] ( | \psi_{0} \rangle , | \psi_{1} \rangle )$ $| \Psi^{( l + 1 )} \Psi_{z} [ l + 1 ]$ $| \Psi_{l + 1}^{( l + 1 )} \hat{Z} | \Psi^{( l + 1 )} $ $\dot{\Psi}_{z} [ l + 1 ] | \Psi_{l + 1}^{( l + 1 )} $ 追加(Ψ$_{z}$, Ψ^(l+1)) $G_{l} [ 1 , \dots , l ] \gets [ 0 , \dots , 0 ]$ 对于 i = 1 到 l 执行 $\left| \Psi_{i}^{( l + 1 )} \right. \gets \Psi_{z} [ i ]$ $\overset{\vartriangle} {G_{l} [ i ]} \Psi_{i}^{( l + 1 )} \middle | \Psi_{l + 1}^{( l + 1 )} $

算法 2：计算 $\nu_{p} ( \vec{\gamma} , \vec{\beta} )$
输入：$\gamma [ 1 , \ldots , p ] , \beta [ 1 , \ldots , p ]$
输出：$\nu_{p}$
初始化 Ψ$_{z}$ ← 空向量
初始化 L ← 大小为 $( p + 1 ) \times ( p + 1 )$ 的零矩阵
$L [ 1 , 1 ] \gets 1$
对于 l = 1 到 $p$ 执行
α ← 长度为 $p$ 的零向量
$\alpha [ 1 , \ldots , l ] - i \cdot \gamma [ l ] \cdot \bar{L} [ 1 , \bar{\ldots} , l , l ]$
$( \dot{G}_{l} [ 1 , \dots , l ] , \Psi_{z} ) \longleftarrow \mathrm{AppLayer} ( \Psi_{z} , \alpha , \beta [ l ] )$
$L_{l} [ 1 , \dots , l ] \gets ( L [ 1 : l , 1 : l ]^{\dagger} )^{- 1} \cdot G_{l}$
$L [ 1 , \dots , l , l + 1 ] \gets L_{l} [ 1 , \dots , l ]$
$\begin{array} {r} {L [ l + 1 , l + 1 ] \gets \sqrt{1 - \sum_{i = 1}^{l} L_{l}^{*} [ i ] \cdot L_{l} [ i ]}} \end{array}$
G ← L<sup>†</sup>L
$\begin{array} {r} {\nu_{p} \gets \sum_{i = 1}^{p} \operatorname{Im} \bigl ( \gamma [ i ] G [ p + 1 , i ] \bigr )} \end{array}$

E. MPS 性能#

通过将 Fock 空间维度截断为 d 并将键维度截断为 $\chi$，我们计算出一个值 $\widetilde{\nu}_{p} ( \gamma , \beta ; d , \chi )$，该值近似于真实的 QAOA 能量 $\nu_{p} ( \gamma , \beta )$。然后，d 和 $\chi$ 是可调参数，决定了通过 MPS 计算的 QAOA 能量的绝对误差 $\Delta \nu_{p} ( d , \chi )$：

随着 $d \to \infty$ 和 $\chi 2^{p}$，有 $\Delta \nu_{p} ( d , \chi ) \to 0$。两个 MPS 位点之间的键维截断通过固定奇异值分解 (SVD) 截断参数 $\delta$ 来执行，因此键维由截断参数 $\chi = \chi_{\delta}$ 确定。实验上，我们发现绝对误差 $\Delta \nu_{p} ( d , \chi_{\delta} )$ 随 $d$ 呈指数衰减，随 $\log (1/\delta)$ 呈多项式衰减（参见下图 1）。

计算 QAOA 能量 $\widetilde{\nu}_{p}$ 的开销主要来自将酉层 $U_{t}$ 应用于自旋-玻色子 MPS 的开销。给定一个固定的键维 $\chi$，使用 SVD 和截断方案，将 $U_{t}$ 应用于一个 $p$ 位点态所需的时间为 $\mathcal{O} ( {p d \chi^{3}} )$。这里的奇异值分解 (SVD) 缩放开销值得注意，因为它涉及按 $\mathcal{O} ( d \chi^{3} )$ 规模缩放的操作。由于方程 30 中有 $( p + 1 )$ 个 MPS，每个 MPS 都需要对初始乘积态进行 $\mathcal{O} ( p )$ 次酉应用，因此计算 $\widetilde{\nu}_{p}$ 的总时间为 $\mathcal{O} \left( p^{3} d \chi^{3} \right)$。通过将单个酉 $U_{t}$ 的应用并行化到 $p + 1$ 个 MPS 上，我们将时间复杂度降低到 $\mathcal{O} \left( p^{2} d \chi^{3} \right)$。我们在算法 1 中总结了 $U_{t}$ 的应用。

我们现在在实验上证明，近似误差 $\Delta \nu_{p} ( d , \chi_{\delta} )$ 作为截断参数 $d$ 和 $\delta$ 的函数收敛到零，从而使我们能够以任意期望的精度计算 QAOA 能量 $\nu_{p} ( \gamma , \beta )$。我们通过如下方式验证收敛性。首先，我们以 $p = 15$ 的情况为例，将 $\widetilde{\nu}_{p} ( \gamma , \beta ; d , \chi )$ 与精确值进行比较。精确值是通过使用参考文献[9]提供的实现[38]，对方程 4 和 5 中的 G 矩阵迭代进行暴力求和，以 80 位浮点精度计算得出的。我们估计能量的不确定度小于 $10^{- 11}$。图 1(a-c) 显示了当我们调整 $d$ 和 $\delta$ 时的相对能量误差。精确能量值计算至 11 位有效数字。我们发现，正如预期的那样[42]，能量误差随截断参数 $\delta$ 呈多项式消失，但令人惊讶的是，它随 Fock 空间维数 $d$ 呈指数消失。例如，对于 $p \lesssim 40$ 的情况，Fock 空间维数 $d = 5$ 就足以使相对能量误差达到 0.01%。我们确实发现，当我们同时调整 Fock 空间维数和截断参数时，我们计算的能量收敛到精确值。

对于较大的 $p$ 值，由于暴力计算具有指数级缩放 $\widetilde{\mathcal{O}} \left( 4^{p} \right)$，我们无法获得精确能量，因此无法验证当我们调整参数 $d$ 和 $\delta$ 时，计算的能量是否收敛到精确值。取而代之的是，我们验证在 $p = 15$ 时观察到的关于 $d$ 和 $\chi_{b}$ 的收敛性对于更高的 $p$ 是否仍然成立。图 1(d-f) 显示了使用 Nvidia A100 GPU 上可计算的最大 $d$ 和最小 $\delta$（即 $d = 25 , \delta = 10^{- 11}$）得到的 $p = 40$ 能量的相对误差。对于 $p = 40$，最大的 $d$ 和最小的 $\delta$ 提供了精确能量的最佳近似。我们在 $p = 40$ 时观察到了与 $p = 15$ 时相同的误差单调衰减，这有力地证明了当我们调整 $d \to \infty$ 和 $\delta \to 0$ 时，能量收敛到精确值 $\nu_{p}$。在 $p = 15$ 和 $p = 40$ 两种情况下，我们都看到了几乎相同的趋势，除了在 $p = 40$ 的情况下，我们需要更小的截断参数才能达到相同的

图1：近似张量网络模拟方法的收敛性。顶行(a-c)展示了$p = 15$时的收敛情况，底行(d-f)对应$p = 40$。(a, d)对数相对误差$\begin{array} {r} {\epsilon = 1 - \frac{\widetilde{\nu}_{p}} {\nu_{p}}} \end{array}$作为福克空间维度d和SVD截断参数$\delta$函数的等高线图。虚线标记绝对误差为0.01%的位置。(b, e)图(a, d)的水平切片，展示了在不同福克空间维度$d$下，误差随SVD截断参数δ减小而收敛到零的过程。正如预期，观察到了明显的依赖于d的相对误差下限。(c, f)图(a, d)的垂直切片，展示了在不同SVD截断参数δ下，误差随福克空间维度d增大而收敛到零的过程。对于$p = 15$，误差是相对于通过其他方法获得的精确$\mathrm{QAOA}$能量计算的。对于$p = 40$，误差是相对于在$d = 25$和$\delta = 10^{- 11}$时获得的能量计算的。

相对能量误差与$p = 15$的情况相同。

除了观察到我们的方法可以高精度计算QAOA能量外，我们还发现适中的键维度和福克空间维度值就足以高精度计算QAOA能量。图2(a)展示了不同QAOA深度和精度水平下所需键维度的增长。令人惊讶的是，对于给定的期望精度水平，键维度经验上随$p$呈多项式增长。因此，总模拟时间也随$p$温和增长，如图2(b)所示。这里，我们使用p块Nvidia A100 GPU来计算$\widetilde{\nu}_{p}$。

II. 在无限尺寸极限下优化的QAOA参数#

我们描述如何找到优化的QAOA参数。由于精确评估$\nu_{p} ( \gamma , \beta )$需要随$p$指数增长的资源，在实际中，我们优化参数以最大化方程1的近似值，即方程50中的$\widetilde{\nu}_{p} ( \gamma , \beta ; d , \chi_{\delta} )$，其中δ是MPS截断参数，d是截断后的福克空间维度。对于所有模拟，我们发现$d = 10$就足够了。键维度$\chi_{\delta}$根据图1由期望的精度水平$\Delta \nu_{p}$决定。对于$p < 100$，我们设置$\Delta \nu_{p} = 10^{- 6}$；对于$p > 100$，我们设置$\Delta \nu_{p} = \mathrm{i} 0^{- 4}$。

我们必须对$\widetilde{\nu}_{p} \left( \gamma , \beta ; d , \chi_{\delta} \right)$进行数值优化，但由于我们的模拟无法提供$\widetilde{\nu}_{p}$关于$\gamma$或$\beta$的梯度，我们转而使用无导数方法。然而，我们确实注意到能量计算中存在相当的结构：该模拟不是一个只返回$\widetilde{\nu}_{p}$值的纯单输出黑箱，而是一个已知的多个模拟量的函数。我们不是将能量建模为$( \gamma , \beta )$的函数，而是可以建模$p$个元素$\{G_{p , i} ( \gamma , \mathbf{\hat{\boldsymbol{\beta}}} ) \}_{i = 1}^{p - 1}$，并使用已知的目标函数形式组合这些模型。为此，我们使用IBCDFO库中的方法进行基于插值的组合无导数优化[36]。利用此类目标函数信息通常可以减少达到特定解质量所需的目标函数查询次数（与通用方法相比）[35]。

图2：计算近似QAOA能量$\widetilde{\nu}_{p} ( \gamma , \beta ; d , \chi )$的成本 (a) 为实现不同QAOA深度p下的固定精度所需键维度的增长。对于给定的QAOA深度p，我们使用p块A100 GPU以给定精度计算QAOA能量。(b) 在不同精度水平和固定福克空间维度$d = 10$下，墙钟时间（分钟）与QAOA深度$p$的双对数图。GPU总小时数为p乘以墙钟时间。

我们可以稍微简化ν的定义，因为γ是纯实数：

我们发现G的p个分量在$(\gamma, \beta)$上足够平滑，从而允许我们用二次模型对求和中的每一项进行建模。我们利用上述ν的形式组合这些模型，以获得比直接构建ν的单一二次模型更精确（实际中）的$\widetilde \nu$^e模型。在IBCDFO库中，我们使用了基于无导数平方和实用优化方法（POUNDerS），并对其进行了修改，以显式考虑这种已知的函数映射（而非传统的用于最小二乘映射）[37]。我们使用该优化器寻找最优的SK-QAOA角度。

参数初始化对于限制我们模拟的计算开销以及找到好的最小值都至关重要。在QAOA中，可以通过从较小的深度$p^{\prime} < p$出发，利用傅里叶基展开外推来找到深度p的高质量初始参数[84]，不过也有其他方法被研究过[43, 60, 61]。对于初始参数，我们使用已针对给定QAOA深度$p$优化过的参数，并通过傅里叶展开进行外推，以获得深度为$p + \Delta p$的QAOA的初始参数。

我们将每次SK-QAOA优化的数值评估次数限制在最多20p次。在使用POUNDerS优化方法时，这些函数评估中的许多可以并发进行。这是因为优化器会请求几何（模型构建）点和优化点。前者类型的点是批量生成的，并且可以根据需要独立评估，而该方法要求的绝大多数点都是这种模型构建点。

图3显示了通过优化$\nu_{p} ( \gamma , \beta )$得到的QAOA参数。表I列出了使用这些优化参数得到的QAOA能量。

图3：各QAOA深度p（能量已评估）的γ（左）和β（右）参数值。参数索引r按QAOA深度p进行了归一化。

表I. 针对QAOA深度p获得的最佳无限尺寸极限QAOA能量$\widetilde \nu_{p} ( \gamma , \beta )$。对于$p \leq 80$，可能还可以进一步优化；而对于$p > 80$，我们报告的是通过从$p = 80$的优化参数外推得到的QAOA能量的未优化下界。最优值为$P_{*} \approx 0.763166$

III. 替代参数拟合#

在这里，我们遵循参考文献[29]，将优化角度下获得的深度p的QAOA能量$\nu_{p}$拟合到以下函数：

该函数具有参数$( m , \eta , c , b )$。我们对$p = 1$到$p = 80$的数据集$( p , \nu_{p} )$进行拟合。得到的拟合参数为：

(??) (??)

图4：将无限尺寸极限下深度$p$的QAOA能量$\nu_{p}$的数据点$( p , \nu_{p} )$拟合到公式51。所有数据点均使用从$p = 1$到$p = 80$的优化点进行拟合。完整的拟合结果见(a)，放大的版本见(b)。

拟合优度 $1 - R^{2} = 1.805 \times 10^{- 5}$。该拟合结果如图4所示。

IV. 自旋玻色子系统的广义SK-QAOA迭代（命题1的证明）#

本附录建立了本研究的主要技术结果（命题1），该结果指出：

其中

可以解释为自旋玻色子系统中一个自旋的路径积分权重。更具体地说，自旋玻色子系统的演化可以写成以下形式：

其直观思路可总结如下。利用参考文献[9, 26]在QAOA背景下引入的一个原创思想，我们通过对自旋的计算基路径求和来展开该状态：

注意，自旋的此类路径有 $( p + 1 )$ 步，而 $f \left( \pmb{a} \right) H \left( \pmb{a} \right)$ 中的比特串 a 有 $( 2 p + 1 )$ 位。这是因为后者的路径积分度量计算的是期望值而非状态振幅，因此路径步数加倍。从这一计算基路径展开出发，式56中的乘积性贡献 $f \left( a \right)$ 源自 $X$ 旋转 $\bar{\cdot} e^{- i \beta_{t} X}$ 所诱导的路径步之间的耦合。贡献 $H \left( \pmb{a} \right)$ 的来源可能不太明显。正如将在证明中详细展示的那样，该贡献本质上源于位移算子的乘法恒等式（为简单起见，这里考虑单模算子）：

最后一个表达式中的前置因子是位移算子参数的二次函数的指数。这直观地解释了 $H \left( a \right)$（即 ${\mathbf{}}^{a ,}$ 的二次函数的指数）是如何在路径积分权重中出现的。此外，我们会看到，G矩阵（式9）将 $G$ 不同角落的实部和虚部联系起来的对称性，自然地源于位移算子的同一乘法恒等式。

现在，我们更精确地阐述这一推导草图。考虑一个矩阵

我们将其视为一组列向量。然后，引入这些列向量的Gram矩阵，记为 $\breve{G}^{( \mathrm{herm} )}$

定义1（向量的Gram矩阵）。给定一个由式 $6\%$ 定义的列向量矩阵L，我们将这些列向量的Gram矩阵记为：

定义1中$\pmb{L}$与$G^{\mathrm{(herm)}}$的关系正是式24。在描述SK-QAOA G迭代的自旋-玻色子映射时（第I.B节），给定$G^{\mathrm{(herm)}}$，我们将L引入为这个厄米矩阵的多种可能分解之一。在本节中，从L出发并定义$G^{\mathrm{(herm)}} := L^{\dag} L$更为自然。事实上，如我们将展示的，自旋-玻色子系统构造显式地依赖于L，而自旋的路径积分测度（式11）则仅依赖于$G^{\mathrm{(herm)}}$。给定由$L$定义的$G^{\mathrm{(herm)}}$，引入该矩阵的对称对应形式会很方便——该矩阵具有相同的下三角，但为对称而非厄米的：

定义2（向量Gram矩阵的对称对应）。从定义1中引入的厄米非负Gram矩阵出发，我们定义其对称对应：

其中

定义3（广义QAOA态）。广义QAOA态存在于$p'$份$L^{2}(\mathbf{R}, \mathrm{d}x)$（玻色子空间）和$\mathbb{C}^{2}$（自旋空间）的张量积中。我们用

表示与$p'$份$L^{2}(\mathbf{R}, \mathrm{d}x)$相关的湮灭算符。我们一致地用

(70)

同样地，对于所有位移向量

我们用

表示独立作用于每个模的位移算符张量积。最后，我们记

为作用于$\mathbb{C}^{2}$上的泡利矩阵。那么，具有角度

的广义QAOA态定义为：

在上式中，每个玻色子模初始化为量子谐振子的基态，记为$\vert 0 \rangle_{L^{2}(\mathbf{R}, \mathrm{d}x)}$。在下文中，为简化记号我们将省略态矢上的空间下标，同时记住空间的顺序：首先是自旋空间，然后是$p'$个玻色子模。注意上式中的位移算符由于自旋算符Z出现在位移向量参数中，使得自旋空间与玻色子空间发生纠缠。

将广义QAOA态在相干态基下的坐标表示为自旋空间上的路径积分是“容易的”。为此，我们首先需要以下将在多处使用的引理：

引理1（基于Z值条件的位移算符乘积）。考虑广义QAOA态定义3中出现的位移算符乘积，但将所有Z替换为给定的自旋值

那么，该乘积满足恒等式：

其中 $G^{\mathrm{(sym)}}$，即 $G^{\mathrm{(herm)}} := L^{\dagger} L$ 的对称版本，已在定义2中引入。特别地，将此恒等式应用于 $p'$ 个玻色子模式的基态 $|0\rangle^{\otimes p'}$，

证明：我们通过对 $q = 1, \dotsc, p$ 进行归纳来证明

对于初始化 $q=1$，我们注意到

因此指数项计算为1，该等式平凡成立。

现在，假设恒等式对 $q$ 成立，让我们证明它对 $q+1$ 也成立。于是，

(84)

我们现在计算位移算子的乘积：

注意到

（后者因为 $1 \leq t \leq q + 1$），位移算子的乘积已被改写为：

将此代入方程84，完成了归纳步骤和整个证明。

我们现在证明辅助方程80、81，将算子等式79用对基态的作用重新表述。方程80是直接的，由恒等式

得到。至于方程81，它可以通过使用表示

对于单模位移算符。将其应用于多模位移算符，得到：

剩下的工作是计算指数中的范数，即：

将此范数平方的表达式代入指数，即可得到方程81。

现在我们可以应用引理1，将酉演化$77$产生的态表示为自旋计算基态上的路径积分。该路径积分是对$p$比特（每层之后自旋的计算状态）的有限求和，这可以被视为通常对$2p+1$比特的$G$矩阵迭代求和的“平方根”。

命题2（广义QAOA态的自旋路径积分表示）。考虑由方程中酉动力学产生的广义QAOA态，即：

该态具有如下作为自旋计算基态上的路径积分表示：

其中$f_{1 ; p + 1}$定义为：

除了定义3中引入的广义QAOA态（在命题2中以路径积分形式表示）之外，引入由相同酉算子序列（方程77）生成、但在给定酉层之后插入单个Z算子的态也将十分有用：

定义4（含单次Z插入的广义QAOA态）。在第r层之前插入单次Z的广义QAOA态定义如下：

注意，对于$r = p + 1$，该定义同样成立，此时有

与命题${\mathit{2}}$类似，这些态可以写成关于自旋计算基态的路径积分形式：

应用引理1，我们可以显式地恢复方程5中的QAOA迭代（对2p+1个自旋求和）。具体而言，方程5中迭代右侧的求和可以解释为作用于自旋的Z算子的时间自相关，这与早期工作Ref. [72]中为D-正则MAXCUT QAOA建立的结论类似。

命题1（自旋-玻色子态重叠的路径积分表示，重述）。设矩阵

由$G^{\mathrm{( h e r m )}}$及相关矩阵$G^{\mathrm{( s y m )}}$通过以下4个分块定义：

其中这4个方程中的$r , s \in [ p ]$。注意，G由构造即为对称矩阵。那么，对于所有$1 \leq j , k \leq p + 1$，Z插入态$| \Psi_{j} \rangle$与$\left| \Psi_{k} \right.$之间的点积具有如下路径积分表示：

其中求和遍及$( 2 p + 1 )$比特的位串

(109)

而$f \left( a \right)$是双边f张量（定义10）在位串a处的取值：

证明。为了应用引理1，更具体地说是方程81，我们将时间 $j , k \ ( 1 \leq j \leq k \leq p )$ 之间的时间自相关重写为两个向量的点积：

注意我们可以将乘积截断到第k层而不是 $p$ 。我们现在将每个态矢量分解为路径积分。对于带匕首的矢量：

其中最后一步我们使用了引理1中的方程81。非带匕首矢量的路径积分展开非常相似——由于插入的Z算符，被积函数仅多了一个因子 $ {\boldsymbol{a}}_{- j} {\boldsymbol{a}}_{- k}$：

现在可以根据路径积分展开来表达所需的内积：

利用约束条件 $a_{- p - 1} = a_{p + 1}$，可令 $a_{0} : = a_{p + 1} = a_{- p - 1}$，并将对 $\pmb{a}_{1 : p + 1} , \pmb{a}_{- 1 : - p - 1} \in \{1 , - 1 \}^{p + 1}$ 的求和替换为对

的求和。根据此记号，两个单侧的 $f$ 张量合并为一个双侧 $f$ 张量（定义10）：

接下来，我们评估指数化产生算符的矩阵元：

由此可得：

现在让我们定义一个矩阵

其由以下4个分块构成：

其中 $r , s \in [ p ]$ 在这四个方程中。注意 $G$ 按构造是对称的。最后定义

$$

= \left( \Gamma_{1} , \Gamma_{2} , \ldots , \Gamma_{p - 1} , \Gamma_{p} , - \Gamma_{p} , - \Gamma_{p - 1} , \ldots , - \Gamma_{2} , - \Gamma_{1} \right) ,\tag{121} $$

在路径积分展开中，$\langle \Psi_{k} | \Psi_{j} \rangle$ 的指数乘积可以重写为：

因此，

总结一下，命题1将状态 $| \Psi_{j} \rangle$ 的点积表示为与 SK-QAOA G 矩阵迭代（方程5）相同的比特串和（方程107）。与 SK-QAOA 迭代的区别在于，本节中方程107右侧的 G 矩阵并不假定来自前一次 SK-QAOA 迭代（即不作为某个递归计算的 $G^{( {\tilde{m}} )}$），而是可以是任何满足 SK-QAOA G 矩阵对称性（方程9）并由非负厄米角落块 $G^{\mathrm{herm}}$ 根据方程103–106指定的矩阵。

V. 截断福克空间维度的解析估计#

通过将福克空间截断至一个适中的维度，可以对附录IV中构建的自旋-玻色子系统进行近似的数值模拟。在本附录中，我们提供所需福克空间维度的解析估计。我们将这些估计的实际紧致性留待未来的数值探索。此外，我们注意到本节的分析尚不足以建立该系统的低纠缠特性，而这正是实现 MPS 模拟的另一个关键要素。

A. 截断阈值的解析估计证明#

在本节中，我们建立关于自旋-玻色子状态 $\left| \Phi \right. , \left| \Phi_{t} \right.$ 的保真度损失（由福克空间截断导致）的简单估计。我们证明，在福克空间维度阈值 $\mathcal{O} \left( \gamma_{\mathrm{max}}^{2} p^{2} \right)$ 之上，保真度损失呈指数下降，其中 $\gamma_{\mathrm{max}}$ 是最大的 $\gamma$ 角度。基本思想是 |Φ⟩ 或 $\left| {\Phi_{t}} \right.$ 可以表示为自旋路径 $\pmb{a}_{1 : p + 1} = ( a_{1} , \dots , a_{p + 1} )$ 上相干态的和，其形式为

然后我们利用如下观察：对于单模相干态 $| \alpha \rangle$，粒子数分布在阈值数 $| \alpha | ^{2}$ 之上呈指数下降，并将这一结果推广到 $p^{\prime}$ 个模式。

我们首先证明单模截断结果（命题3），然后将其扩展到多模情况（命题4）。以下引理简单地将单模和多模情况联系起来。

引理2（交换投影算子应用的非相干范数界）。设 $\Pi_{1} , \ldots , \Pi_{m}$ 为希尔伯特空间 H 中的一系列交换正交投影算子。则对于任意 $| \psi \rangle \in{\mathcal{H}}$，有

证明. 为了估计 $\left\| \left| \psi \right. - \Pi_{1} \ldots \Pi_{m} \left| \psi \right. \right\| _{2} = \left\| \left( I - \Pi_{1} \ldots \Pi_{m} \right) \left| \psi \right. \right\| _{2}$，我们将恒等算子与投影算子乘积之差表示为伸缩和，每次将一个投影算子替换为恒等算子：

将这个可加分解应用于向量 |ψ⟩，便给出了 |ψ⟩ 的一个正交分解。因此，这些项是非相干相加的：

其中最后一个不等式利用了正交投影算子缩小模长的性质。

我们现在展示单模情况下的一个显式截断界：

命题 3 (单模 Fock 空间截断的误差). 对于任意模式索引 $l \in [ p^{\prime} ]$ 和任意整数 $n \geq 0$，令 $\Pi_{l , n}$ 将模式 l 正交投影到数态 n 上。此外，给定某个整数 d，令 $\Pi_{l , \le d}$ 将模式 l 正交投影到数不超过 d 的态上。那么对于任意整数 $d_{l} \ge 0$ 和截断数

其中

对于广义 QAOA 态 |Φ⟩，以下 Fock 空间截断界成立：

对于带有单个 Z 插入的态，同样的误差界成立：

证明. 我们通过将所有玻色子数 $n > d$ 求和来分解误差：

回忆 Φ 的路径积分表示 (命题 2)：

以及恒等式

其中 $\hat{c}^{\dagger}$ 是单模产生算子，$\alpha \in \mathbb{C}$，我们得到：

其中我们用 $| n \rangle_{l}$ 表示玻色子模式 l 的粒子数 n 态。将此式平方并按照命题 1 中的推理可得

其中 $G = \left( G_{r , s} \right)_{r , s \in \pm \left[ p \right]}$ 由命题中的式 103-106 定义。

为了界定此式，我们将比特 ${\pmb a}_{t} ~ ( t \in \pm [ p ] )$ 的函数（提升至 n 次幂）视为这些 ±1 值变量的布尔多项式：

其中系数 $\hat{c}_{S}$ 的具体表达式并不重要。由线性性质，只需对所有的 $S \subset \pm [ p ]$ 界定

即可。但根据

作为自旋-玻色子系统路径积分测度（命题 1）的解释，上式可解释为 $Z$ 算符的时间自相关函数。即，带有 $\bar{Z}$ 插入的自旋-玻色子时间演化的矩阵元。例如，为明确起见取 $p = 3$ 和 $S = \{1 , 2 , - 2 \}$，

其中自旋-玻色子酉算符记为 $U_{t} : = e^{- i \beta_{t} X} D \left( - i \gamma_{t} Z L_{: , t} \right)$。由于 $\| Z \| \le 1$，任何此类求和的上界均为 1。因此，由三角不等式：

接下来容易看出，对于所有 $S \subset \pm [ p ]$，$| \hat{c}_{S} |$ 的上界由函数

的布尔系数 S 给出。因此，$\sum_{S} | \hat{c}_{S} |$ 的上界由上述函数在 $a_{t} : = 1$（对所有 $t \in \pm [ p ]$）处的取值给出，即

综上所述，我们证明了

令

借助引理4，可以将该上界对

求和。由此得到：

同样的证明适用于具有单个Z插入的态 $| \Phi_{t} \rangle$；实际上，额外的Z插入在路径积分测度中表现为一个因子 $a_{t}$，从而允许采用相同的自相关论证。□

命题3表明，只要Fock空间截断维度超过某个阈值 $d_{* , l}$，保真度误差便随该维度增加而指数衰减。由于L的各列已归一化，简单上界 $| L_{l , t} | \leq 1$ 给出：

其中 $\gamma_{\mathrm{max}} : = \operatorname*{max}_{1 \leq t \leq p} | \gamma_{t} |$ 是最大的γ角。特别地，截断阈值是 $p$ 的多项式。我们将此上界的紧性留待未来研究。

将单个模截断误差上界的命题3推广到所有 $p$ 个模，需借助引理2：

命题4（多模Fock空间截断的误差）。设 $\Pi_{\le d} : = \Pi_{1 , \le d} \cdot \cdot \cdot \Pi_{p^{\prime} , \le d}$ 为所有模数态中光子数至多为d的投影算子。那么，只要下式成立：

其中 $d^{\prime} \geq 0$，则Fock空间截断的2-范数误差可被界定为：

证明。调用引理2：

现在应用命题3，利用 $d \ge p^{2} \gamma_{\mathrm{max}}^{2} + d^{\prime} \ge e d_{* , l} + d^{\prime}$ 来界定每个单模投影误差。由此得到：

B. 辅助技术结果#

本节汇集了在建立截断主上界即命题3和命题4时所用的辅助技术结果。

引理3（粗糙的Stirling公式）。对所有整数 $n \geq 1$，有

引理4（指数函数泰勒系数的简单上界）。设 $x \geq 0$ 为任意非负实数。则对所有满足下式的整数n和实数y：

以下不等式成立：

证明。根据命题3中简化的Stirling公式：

其中我们引入了定义在正实数上的函数

该函数是严格凹的，临界点为

这意味着 $\varphi$ 在 $[ u^{*} , + \infty )$ 上严格递减，因此在 $[ e u^{*} , + \infty )$ 上尤为如此，并且进一步满足不等式

代入 $\varphi$ 和 $\varphi^{\prime}$ 的表达式，上述不等式变为：

因此，回到对 $x^{n} / n !$ 的界限

即得证。

VI. D-正则MAXCUT-QAOA中映射的解释#

在附录IV中，我们通过“直接计算”证明了本工作的主要理论结果（命题1），表明所构建的自旋-玻色子系统具有由比特串之和（推广了G矩阵迭代中的和）给出的Z时间关联。这一分析足以推导出定理并验证我们的数值模拟技术，即直接模拟自旋-玻色子系统，无需参考原始的QAOA量子比特系统。在本节中（纯粹是基础兴趣），我们展示了自旋-玻色子映射如何自然地出现在D-正则、高围长MAXCUT-QAOA中。更具体地说，我们在高围长D-正则图（或更具体地说，由于高围长假设而在树上产生的局部状态）上由MAXCUT-QAOA生成的状态与自旋-玻色子系统之间构造了一个显式等距。

A. 基本定义与G矩阵作为时间关联#

我们首先根据MAXCUT-QAOA的定义，定义状态所在的树。我们将这棵树命名为“替代Bethe格点”，以区别于标准的Bethe格点（一种无限正则树）。与Bethe格点的区别在于，本工作中树的深度有限为 $\Delta$，并且根节点的度数比其他非叶节点少一：

定义5（替代Bethe格点）。度数为 $D$、深度为 $\Delta$ 的替代Bethe格点是深度为 $\Delta$ 的树，其顶点集为：

• ^∅（根顶点）；

• 对于所有 $1 \le \Delta^{\prime} \le \Delta$，$v \in [ D ]^{\Delta^{\prime}}$（深度为 $\Delta^{\prime}$ 的顶点）

我们将 ^∅ 视为零长度元组，将单个整数 $j \in [ D ]$ 视为长度为1的元组。因此，顶点由长度为0到 $\Delta$（含）的整数 $\in [ D ]$ 元组标记。深度为 $\Delta$ 的替代Bethe格点的有向边集定义如下：

• 根 ^∅ 有子节点 j，其中 $j \in [ D ]$；

• 对于所有 $1 \le \Delta^{\prime} < \Delta$，$v \in [ D ]^{\Delta^{\prime}}$ 有子节点 $( v , j ) \in [ D ]^{\Delta^{\prime} + 1}$，其中 $j \in [ D ]$

在最后一条陈述中，$( v , j )$ 表示元组 u 与 $j$ 的连接。由上述边集定义的深度为 $\Delta$、度数为 D 的替代Bethe格点记为 $\mathcal{T}^{( \dot{\Delta} , D )} : = \big ( \mathcal{V}^{( \Delta , D )} , \mathcal{E}^{( \Delta , D )} \big )$，其中 $\boldsymbol{\nu}^{( \Delta , D )}$ 指顶点集，$\mathcal{E}^{( \Delta , D )}$ 指边集。

树 $\tau^{( \Delta , D )}$ 的顶点 $\boldsymbol{\nu}^{( \Delta , D )}$ 采用元组记法的一个优点是，父子关系可以通过以下简单的元组偏序来捕获：

定义6（变长元组的偏序）。给定变长元组 $u , v$，我们记 $u \prec v$ 表示 v 是 u 与任意数量元素（至少一个）的连接。我们也用 $u \preceq v$ 表示 ${u} \prec v$ 或 $u = v$。自然地，我们也令 $u \succ v$ 表示 $v \prec u$，$u \succeq v$ 表示 $v \preceq u$。由此定义的 $\prec$ 和 $\vdash$（分别对应 $\preceq$ 和 $\succeq$）构成了变长元组的偏序（分别对应严格偏序）。

当应用于标记 $\mathcal{T}^{{( \Delta , D )}}$（定义5）节点 $u , v \in \mathcal{V}^{( \Delta , D )}$ 的变长元组时，$u \prec v$ 意味着在 $\tau^{( \Delta , D )}$ 中，$v$ 是 $u$ 的后代。接下来，我们引入 $\check{\tau}^{( \Delta , D )}$ 子树的进一步符号，在将迭代 $G^{( m )}$（公式5）重新表述为深度 $m$ 的树格上某个量子算符的相关性时，我们需要考虑这些子树：

定义7（替代贝特晶格的子树）。考虑深度 $\Delta$ 和度数 $D$ 的替代贝特晶格 $\mathcal{T}^{{( \Delta , D )}}$（定义5）。对于该树的任意节点 $t \in \mathcal{V}^{( \Delta , D )}$，我们定义 $\mathscr{T}_{\succeq t}^{( \Delta , \dot{D} )}$ 为 $\mathcal{T}^{{( \Delta , D )}}$ 中以 $t$ 为根的子树，包括 $t$ 及其后代。我们用 $\mathcal{V}_{\succeq t}^{( \Delta , D )}$ 和 $\mathscr{E}_{\succeq t}^{( \Delta , D )}$ 分别表示该子图的对应顶点集和有向边集。

在引入了QAOA态所处的树格之后，让我们定义QAOA态本身。由于QAOA关联性的有限范围（例如，参见[9]），该态可以视为在高围常规图上理解QAOA能量（或任何其他局域可观测量）的可靠代理。

定义8（深度 $\Delta$ 树上的MAXCUT-QAOA）。代价哈密顿量为：

混合哈密顿量为：

具有角度

的QAOA态为

与定义 $\gamma$ 中的符号一致，我们用

表示代价和混合哈密顿量在 $\mathcal{T}^{( \Delta , D )}$ 的以 $u$ 为根的子树 $\mathcal{T}_{\succeq u}^{( \Delta , D )}$ 上的限制。

从定义8中引入的 $\mathrm{QAOA}$ 代价和混合哈密顿量，我们还定义了一个QAOA态的变体，该变体在晶格根上单次插入了 $Z$ 算符。该定义类似于公式167中引入的具有单个 $Z$ 插入的自旋玻色子态。我们将证明，在本附录构建的等距映射下，这些确实是相同的态：

定义9（插入 $Z_{\mathcal{O}}$ 的QAOA态）。我们定义

为在变分量子电路的 $l$ 层前插入单个 $Z_{\mathcal{O}}$ 后修改的 $Q A O A$ 变分态。

然后，我们需要引入SK-QAOA迭代（公式5）中出现的 $f \left( \pmb{a} \right) ( \pmb{a} \in \{1 , - 1 \}^{2 p + 1} )$ 张量的一个变体。我们将此张量称为 $f_{1 : p} \left( \pmb{a}_{1 : p + 1} \right) ( \pmb{a}_{1 : p + 1} \in \{1 , - 1 \}^{p + 1} )$ 单边 $f \left( a \right)$ 张量，因为其公式仅涉及 $f \left( a \right)$ 公式的一半。这个对象的直观理解是，$f \left( a \right)$ 出现在量子期望值（通过迭代评估的QAOA能量）的计算中，而 $f_{1 : p + 1} \left( \pmb{a} \right)$ 出现在态的表述中，因此张量次数减半：

定义10（$f$ 张量）。对于所有 (p+1) 比特位串

我们定义单侧 $f$ 张量为：

$$

= \frac{1} {\sqrt{2}} \prod_{1 \leq t \leq p} \left. a_{t + 1} \right. e^{- i \beta_{t} X} \left. a_{t} \right.\tag{170} $$

对于所有 $( 2 p + 1 )$ 比特位串

我们定义双侧 $f$ 张量为：

接下来的两个定义引入了名为 "$G$ 矩阵" 的矩阵（分别是对称 $G$ 矩阵和厄米 $G$ 矩阵）。重要的是，与公式5不同，我们并非将其定义为 SK-QAOA 迭代在 $D \to \infty$ 极限下的结果，而是定义为某个算子在所有有限 $D$ 下的时间自关联。本附录的第一个结果将证明，在 $D \to \infty$ 极限下，它们收敛到通常的 $G$ 矩阵。该结果可与早期工作参考文献[72]进行比较，该工作证明了 SK-QAOA 迭代 $G^{( m )}$ 在 $D \to \infty$ 极限下被识别为时间自关联。本证明可视为取相反方向，即证明有限 $D$ 下的时间自关联在 $D \to \infty$ 极限下收敛到 SK-QAOA 迭代。

定义11（对称 $G$ 矩阵 $G^{{\mathrm{( s y m ,} \Delta )}} .$ ）。我们令 $G^{( \mathrm{sym} , \Delta , D )}$ 为对称矩阵，其元素 $( j , k ) , j \leq k$ 由深度为 $\Delta$ 的替代贝特晶格上 $Z_{\mathcal{O}}$ 的两时间自关联定义，其中 $Z_{\mathcal{O}}$ 插入酉演化的位置 $j , k$ 处，即：

定义12（厄米 $G$ 矩阵 $G^{( \mathrm{herm} , \Delta )} )$ 。我们令 $G^{( \mathrm{herm} , \Delta )}$ 为定义9中引入的向量族的格拉姆矩阵，即

代入 $\left| \Psi_{j}^{\left( \Delta , D \right)} \left( \gamma , \beta \right) \right.$ 和 $\left| \Psi_{k}^{\left( \Delta , D \right)} \left( \gamma , \beta \right) \right.$ 的显式表达式（定义9）并与 $G^{( \mathrm{sym} , \Delta , D )}$ 的定义11进行比较，我们看到：

注意，从定义11、12可直接得出，$G^{( \mathrm{sym} , \Delta , D )}$ 和 $G^{( \mathrm{herm} , \Delta , D )}$ 的对角元素均为1。一个远非平凡的事实是，在极限 $D \to \infty$ 下，非对角元素也可以精确计算，并与文献[9]中引入的 $G$ 矩阵一致。这是以下命题的对象：

命题5（$G^{( \mathrm{sym} , \Delta , D )}$ 矩阵与 $G$ 矩阵的关系）。在无穷度极限 $D \to \infty$ 下，$G^{( \mathrm{sym} , \Delta , D )}$ 和 $\mathbf{\hat{\Pi}}_{G} ( \mathrm{herm} , \Delta , D )$ 收敛到文献[9]中定义的 $G$。更精确地说，当度数趋于无穷大时（角度 $\gamma , \beta$ 保持不变），这些矩阵存在极限：

并且这些极限与 $G^{( \Delta )}$（在迭代 $\Delta \geq 0$ 时计算的 $G$ 矩阵）的关系如下：

本节剩余部分致力于证明命题5。

鉴于 $G^{( \mathrm{sym} , \Delta , D )}$ 与 $G^{( \mathrm{herm} , \mathbf{\tilde{\Delta}} , \tilde{D} )}$ 之间的对应关系（定义12），只需证明 $G^{\mathrm{( s y m )}}$ 的收敛结果即可。为此，我们通过对格点深度 $\Delta \geq 0$ 进行归纳来证明。

a. 归纳基础：$\Delta = 0$

我们从基础情形 $\Delta = 0$ 开始。此时，格点只包含单个顶点，哈密顿量作用在单个量子比特上。对于 $1 \leq j < k \leq p$：

现在，在深度 $\Delta = 0$ 时，代价和混频哈密顿量简化为：

因此，

利用恒等式

可以简单计算出结果：

这与 $D$ 无关，因此当 $D \to \infty$ 时显然存在极限

。另一种方法是插入 $( 2 p + 1 )$ 个计算基完备性关系：

将方程184代入后，得到该量的路径积分表示：

G^{(sym, 0, D)}

引入记号

表示由路径积分展开比特构成的比特串，我们得到：

其中 $f \left( \pmb{a} \right) , \pmb{a} \in \{1 , - 1 \}^{2 p + 1}$ 已在方程7中定义。因此，

这与方程4中给出的 $G_{j , k}^{( 0 )}$ 表达式一致。至此，归纳初始步骤完成。

B. 一般归纳步骤#

现在假设归纳陈述已在树深度 $\Delta$（含）上得到证明，考虑在深度 $\Delta + 1$ 上证明。设 $1 \leq j < k \leq p$，考虑以下 $Z_{\mathcal{O}}$ 的自关联：

在上式中，我们用 $\mathcal{V}^{( \Delta + 1 , D )}$ 对$+$ 左矢和右矢进行索引，表示由 $\mathcal{V}^{( \Delta + 1 , D )}$ 索引的量子比特上的 $+$ 态。换言之，

我们更偏好左侧的符号而非右侧，因为用树节点而不是整数来标记量子比特会更方便。类似于基础归纳情形，让我们在根顶点的计算基态上插入 $( 2 p + 1 )$ 个完备性关系：

与归纳初始化类似，对 $- p \leq l \leq p$ 范围内 $z_{\alpha}^{[ l ]} \in \{1 , - 1 \}$ 的联合求和也将记为对 $z_{\mathcal{O}} \in \{1 , - 1 \}^{2 p + 1}$ 的求和，其中

为了简化符号，我们在后续公式中将不再写出单位矩阵。插入这些完备性关系后，所关注的关联可以重写为

在最后一步中，我们使用了 $Z_{\mathcal{O}}$ 算符在插入的计算基投影算子上的作用如同标量，即

现在我们需要计算插入的计算基态与QAOA幺正算符之间的“矩阵元”（更准确地说，是部分迹）。不失一般性，考虑对于某个 $1 \leq t \leq p - 1$ 有

为了将左边的左矢穿过相位分隔幺正算符

我们通过挑出涉及根顶点 $\varnothing$ 的边来分解代价哈密顿量：

其中在第三行中，我们将 $\mathcal{T}^{( \Delta + 1 , D )}$ 中不涉及根顶点的边枚举为子树 $\mathscr{T}_{\succ j}^{( \Delta + 1 , D )}$ 的边。注意哈密顿量的第二个加性贡献在根顶点^∅之外。根据这一改写，计算基左矢可以如下穿过相位分隔幺正算符：

由于混合算符的乘积形式，对其的处理是简单的。总而言之，所需的“矩阵元”为：

需要强调，最后两个方程中涉及单量子比特X旋转的括号是一个标量，而非作用在$\mathcal{V}^{( \Delta + 1 , D )} - \left\{\emptyset \right\}$上的算符。我们现在观察到，上述算符独立且等同地作用于所有子系统$\mathcal{V}_{\succeq j}^{( \Delta + \bar{1} , D )} , j \in [ D ]$。换句话说，最终方程中关于$j \in [ D ]$的乘积实际上可以视为张量积。为了在符号上体现这一点，我们选择按照序列$\mathcal{V}_{\succeq 1}^{( \Delta + 1 , D )} , \dots , \mathcal{V}_{\succeq D}^{( \Delta + 1 , D )}$对量子比特进行排序。每个树内部的量子比特顺序无关紧要，但各树之间的顺序应当（在同构意义上）保持一致。此外，我们采用树同构关系：

根据我们选择的张量积顺序并代入上述同构关系，方程204中的"矩阵元"可写为：

为了再次强调式 204 和式 206 之间重组的原理，新系统与原系统同构，现在由 $D$ 个独立的深度为 ∆ 且度为 $D$ 的树副本组成，即 $\mathcal{T}^{( \tilde{\Delta} , D )} = \big ( \mathcal{V}^{( \Delta , \grave{D )}} , \mathcal{E}^{( \Delta , D )} \big )$。对其他“矩阵元”进行类似处理，我们最终得到所需的 $Z_{\mathcal{O}} {}^{\mathrm{~ \tiny ~ \ . ~}}$ 的两时间关联的如下表达式：

在上面的表达式中，我们把标量贡献——包括在位置 $j , k$ 处的 $Z_{\mathcal{O}}$ 算符插入，以及用计算基路径 $z_{\mathcal{O}} -$ 的比特表示的 $\bar{X}$ 旋转的矩阵元——与张量积空间

中剩余的括号、右矢和算符乘积分开了。

我们识别出标量贡献为：

因此，剩下的任务是估计张量积空间中的点积。在此过程中，需记住对计算基路径 $z_{\mathcal{O}} \in \{1 , - \bar{1} \}^{2 p + 1}$ 的求和包含独立于 D 的项数。首先，由于态的张量积结构，点积可分解为单个树副本 $\mathcal{T}^{{( \Delta , D )}}$ 上的矩阵元素，并取 D 次幂：

于是问题简化为估计单个树 $\tau^{( \Delta , D )}$ 上的矩阵元素。为此，我们将把以下针对任意酉序列的引理应用于 QAOA 酉的特殊情形：

引理5（近单位算子时间关联的二阶展开）。考虑作用在有限维希尔伯特空间 ${\mathcal{H}}$ 上的一个包含 q 个酉的序列

并令 $| \psi \rangle \in{\mathcal{H}}$ 为该空间中的任意态。考虑厄米算子

并考虑期望值

(216)

我们关心的是该期望值在极限 $D \to \infty$ 下的行为，其中所有插入的算子 $e^{i O_{t} / \sqrt{D}}$ 都接近单位算子，但酉的数量 q 不随 D 增长。定义“零阶矩”为无插入算子时的期望值：

接下来，定义算子 $( O_{t} )_{t \in [ q + 1 ]}$ 的“一阶矩”为在位置 l 处插入单个 $O_{l}$ 后算子乘积 $V_{1} , V_{2} , \ldots , V_{q - 1} , V_{q}$ 的期望值：

类似地，定义算子 $( O_{t} )_{t \in [ q + 1 ]}$ 的“二阶矩”为在位置 l, m 处插入一对算子 $O_{l} , O_{m}$ 后算子乘积 $V_{1} , V_{2} , \ldots , V_{q - 1} , V_{q}$ 的期望值：

上述 $\mu^{( 2 )}$ 矩阵由前一方程仅在上三角定义，通过对称性补全到下三角。在前述 $\mu^{( 0 )} , \mu^{( 1 )} , \mu^{( 2 )}$ 的定义下，期望值 214 的关于 $1 \bar{/} \sqrt{D}$ 的二阶展开如下成立：

其中 O 中隐含的常数仅依赖于 q 和算子范数

（而不依赖于希尔伯特空间 H 的维度或酉算子 $V_{1} , V_{2} , \ldots , V_{q - 1} , V_{q} )$

证明。为方便起见，我们在酉算子序列末尾填入一个虚拟的单位算子：

于是我们可以写为

首先我们证明，每个近单位酉算子可以用其关于 $1 / \sqrt{D}$ 展开至二阶的项来替换，误差不超过 $\mathcal{O} \left( D^{- 3 / 2} \right)$，其中隐含常数仅依赖于 $q$ 和 $O_{t}$ 的算子范数。近单位酉算子展开至二阶的表达式为：

其中展开的主项为

误差项为

(232)

后者关于误差的界来源于不等式

对所有实数 $x$ 成立，并推广到厄米算符。我们迭代地执行替换。即，从 $e^{i O_{q + 1} / \sqrt{D}}$ 开始，以下界限在态误差上成立：

因此，我们用向量

来近似向量

直至所需的加性误差。现在我们通过将第二层中的近单位酉算符 $e^{i O_{2} / \sqrt{D}}$ 替换为其二阶展开 $O_{2}$ 来近似后一个向量。这给出：

(238)

推广之前的计算，

将所有不等式相加得到

从而在期望值误差上得到相同的上界：

需注意隐含常数仅取决于 $q$ 和算子范数 $\| O_{t} \|$。我们现在将近似态中近恒等酉的二阶近似展开：

其中在最后一行，我们引入了 $q_{1} \left( k \right)$ 和 $q_{2} \left( k \right)$，分别用于统计 k 中 1 和 2 出现的次数：

直观上，在误差 $D^{- 3 / 2}$ 范围内，只有满足

的那些 k 才贡献。那么我们来计算这些 K 的贡献：

上述求和中的第一项仅包含一个单项 $k = 0^{q + 1}$：

上述求和中的第二项是对仅包含一个 1（其余项全为 0）的 k 求和；因此，它等价于对 $l \in [ q + 1 ]$ 的选择求和，其中 $k_{l} = 1 \colon$

上述第三个求和遍历恰好包含两个1且其余项为0的序列k；接着可以对不同的位置$0 \leq l < m \leq q + 1$（此时$k_{l} = k_{m} = 1$）进行求和：

最后，方程245中的第四项贡献遍历恰好包含一个2且其余项为0的序列k。因此，它可以表示为对单一时间步$l \in [ q + 1 ]$（此时$k_{l} = 2$）的求和：

将方程246、247、248和249相加，即得到方程225所述展开式的主导项。现在我们证明，方程242中剩余项（满足$( q_{1} ( k ) , q_{2} ( k ) ) \not \in Q_{0}$）累计误差不超过$\mathrm{{\dot{\mathcal{O}}}} \left( D^{- 3 / 2} \right)$，其中隐含常数仅依赖于q和算子$O_{t}$的算子范数。利用三角不等式对这些剩余项的范数进行界定：

最后一个求和仅依赖于$( q + 1 )$元组k中0、1、2出现的次数。接着可以对这些出现次数（记为$q_{0} , q_{1} , q_{2}$）进行求和，并考虑组合数：

现在根据出现次数对元组进行归类。我们之前的界限变为：

其中减去的项分别对应于$( q_{1} , q_{2} ) = ( 0 , 0 ) , ( 1 , 0 ) , ( 2 , 0 ) , ( 0 , 1 )$。我们观察到这些减去的项恰好是前一项展开式中$1 / \sqrt{D}$阶数不超过2的贡献：

这证明了

其中隐含常数仅依赖于$q$和范数$\| O_{t} \|$，正如所期望的那样。

□

现在我们将引理5应用于期望值：

其中那些接近恒等算符$e^{i O_{t} / \sqrt{D}}$的酉算符指的是：

插入到扮演 $V_{t}$ 角色的 QAOA 幺正算符之间。更具体地，为方便起见调整引理 5 的索引，我们将期望 255 重写为

其中

注意对所有 $t \in [ p ]$，有 $V_{- t} = V_{t}^{\dagger}$；然而，$O_{t}$ 和 $O_{- t}$ 可能互为相反数或相等，这取决于独立路径积分位 $z_{\boldsymbol{\mathcal{O}}}^{[ t ]} , z_{\boldsymbol{\mathcal{O}}}^{[ - t ]}$ 的值。让我们用这些调整后的索引符号计算矩 $\mu^{( 0 )} , \mu^{( 1 )} , \mu^{( 2 )}$。首先，

一阶矩 $\mu^{( 1 )}$ 由于哈密顿量的 $\mathbf{Z}_{2}$ 对称性而为零。更明确地，固定 $l \in [ p ]$ 以确定起见（我们也需要考虑 $l \in - [ p ]$），

在第二行和第三行之间，我们利用了$\left| + \right. ^{\otimes \mathcal{V}^{( \Delta , D )}}$是$X^{\otimes \nu^{( \Delta , D )}}$算符的$+1$本征态这一事实。在第三行和第四行之间，我们利用了该算符与混频器和代价哈密顿量对易——对于后者，这是由于$[ X \otimes X , Z \otimes Z ] = 0$。在第四行和第五行之间，我们利用了该算符与$O_{l}$反对易，因为$O_{l} \propto Z_{\infty}$，而$X$与$Z$反对易。在接下来的几行中，我们再次利用了该算符与QAOA酉算子的对易性以及$\left| + \right. ^{\otimes \mathcal{V}^{( \Delta , D )}}$在该算符作用下的稳定性。总而言之，这表明

对于$l \in - [ p ]$的推理是类似的。现在让我们考虑二阶矩。令$l , m$为来自$\pm [ p ]$的指标。为明确起见，我们先考虑它们均为正的情况，并假设$l \leq m$。然后我们考虑：

$l , m$的其他符号情况可以通过抵消酉算子$V_{t} , V_{- t}$并利用复共轭（类似于该例子）来反映$Z_{\mathcal{O}}$算符插入从左到右的位置，从而简化为这种情况。例如，仍然假设$1 \leq l \leq m \leq p$，但现在计算$\mu_{- l , m}^{( 2 )}$

类似地，仍假设 $1 \leq l \leq m \leq p .$

$\mu_{l , m}^{( 2 )}$ 的表达式可以统一成对于 $l ,$ m 的所有符号形式

其中我们引入了对称矩阵

其元素对于 $1 \leq l \leq m \leq p ;$ 定义如下

(274)

引入此符号的动机如下：通过将归纳假设应用于 $G^{( \mathrm{sym} , \Delta , D )}$

其中 $G^{( \Delta )}$ 与文献 $[ 9 ]$ 中定义的在 $\Delta$ 步迭代下的 $G$ 矩阵一致。现在我们已经计算了矩 $\mu^{( 0 )} , \mu^{( 1 )}$ 和 $\mu^{( 2 )}$，引理5允许写出方程255中期望值在 $D \to \infty$ 极限下的渐近展开：

我们回顾误差项中的隐式常数只依赖于$q = 2 p$和算子$O_{t}$的范数，即$\| O_{t} \| = | \gamma_{t} |$；特别地，该隐式常数与$D_{\ast}$无关。将此渐近展开式提升到$D$次幂后，我们得到方程210中所有子树$\mathcal{T}^{{( \Delta , D )}}$上期望的如下估计：

在最后两行中，$o_{D} \left( 1 \right)$ 表示在极限 $D \infty$ 下趋于零的量（我们无需知道其趋于零的速度）。将此子树期望的估计（方程210）以及方程209代入方程207中的 $\dot{G}_{j , k}^{( \mathrm{sym} , \check{\Delta} + 1 , \check{D} )}$，得到该量的如下估计：

其中最后的化简利用了求和项数和量 $f \left( z_{\mathcal{O}} \right)$ 与 D 无关的事实。上述估计现表明

其中最后一步是根据G矩阵迭代的定义[9]。至此完成归纳假设$\Delta \to \Delta+1$的证明，也完成了命题5的证明。

B. 将level-p QAOA映射到p模自旋玻色子系统#

在本节中，我们推导树（定义5）上深度$\Delta$和度数$D$的QAOA态（定义8中引入）的一系列近似：

更具体地说，此近似在极限$D \to \infty$下成立。严格定义此极限下的态近似至少不是直接的，因为态所在的希尔伯特空间是不同的，其维度依赖于$D$。幸运的是，在某些嵌入下，态可以被视为"存在于同一空间中"。我们将在本段剩余部分概述此嵌入的原理。首先，类似于命题5的证明，我们注意到树$\mathcal{T}^{( \Delta , \dot{D} )}$由$D$个$\check{\mathcal{T}}^{( \Delta - 1 , D )}$副本与一个根顶点连接而成。这转化为以下量子态空间等同关系：

然后我们将观察到，$\left| \Psi^{\left( \Delta , D \right)} \left( \gamma , \beta \right) \right.$投影到根顶点的任何态上时，存在于$\mathcal{T}^{( \Delta - 1 , D )}$子树的对称子空间中：

该对称子空间又可以被视为Fock空间——更具体地说，是被截断到粒子数D的Fock空间——的子空间。在此嵌入下，QAOA态可以被视为存在于一个独立于$D$的公共空间中。我们最终将证明在极限$D \to \infty$下，嵌入态收敛到一个定义明确的Fock态。

现在我们形式化地陈述这些论断。为此，我们需要以下简单的技术性引理：

引理6（张量幂的近似）。设H为任意希尔伯特空间。那么，对于任意一对向量$\mathbf{\boldsymbol{u}} , \mathbf{\boldsymbol{v}} \in \mathcal{H}$，以下近似在极限$D \to \infty$下成立：

假设u ⊥ v正交，我们可以得到更紧的D依赖关系：

证明。我们从张量幂差分的如下 telescoping 和表示开始：

通常，将三角不等式应用于上述求和得到

这正是所需的界（方程285）。现在进一步假设正交性 $\textbf{\em u} \perp \textbf{\em v}$，使得伸缩求和中的项两两正交，意味着

这正是正交情况下的所需界（方程287）。

我们现在推导QAOA态的一系列近似（引理7和引理8），其中误差在极限 $D \to \infty$ 下消失。

引理7（大D极限下的QAOA态：第一近似）。定义对于 $l < m$，通过在第l层和第m层之前插入 $Z_{\mathcal{O}}$ 算符修改后的 QAOA 态：

类似定义9，但在两个位置插入 $Z_{\mathcal{O}}$ 而非一个。那么，对于深度为 $\Delta$ 的树上的 QAOA 态，以下关于深度为 $(\Delta - 1)$ 的树上的态的近似成立：

上式中，构成由 $\mathcal{T}^{( \Delta , D )}$ 的顶点 $\mathcal{V}^{( \Delta , D )}$ 索引的量子比特希尔伯特空间的张量积，假定其按命题5证明中的顺序排列，即：

证明。根据定义8引入的、在深度为 $\Delta$、度为 $D$ 的正则树上的 QAOA 为：

与命题5的证明类似，我们在根顶点$\mathcal{D}$量子比特的计算基态之间插入$(p+1)$个完备性关系：

我们将这些完备性关系的比特收集为一个比特串

这便将状态改写为：

按照命题5证明中的推理，我们可以通过单独处理根顶点$\varnothing$来分解代价哈密顿量和混频哈密顿量：

(299)

(301)

在这两个分解中，第二项的作用范围在根顶点$\varnothing$之外。这使得我们可以按如下方式求取最后方程中的“矩阵元”（更准确地说，是部分迹）：

然后我们注意到最终方程中的算符是$j \in [ D ]$上酉算符的乘积，它们对子树${\mathcal{T}}_{\succeq j}^{( \Delta , D )}$的作用完全相同。因此，使用与命题5证明中相同的同一性映射：

式(302)可改写为：

将其代入式(297)，得到QAOA态的如下表达式：

我们现在固定一个比特串 $z_{\mathcal{D}}$，并考虑态的张量幂D的近似。更具体地说，我们考虑由近恒等酉算子的泰勒展开主导项（在极限 $D \to \infty$ 下）得到的近似：

其中 $\mathcal{O}_{| | \cdot | |} \left( D^{- 3 / 2} \right)$ 表示算子范数阶数被常数乘以 $D^{- 3 / 2}$ 所界定的算子。重要的是（否则该陈述将毫无意义），这个常数不依赖于D。现在我们使用这个算子在每个p层中的渐近展开

以得到式(305)中态的张量幂 $D$ 的如下估计。为简化符号，我们临时引入以下符号来表示深度为 $( \Delta - 1 )$、度为D的树上的QAOA ansatz酉算子：

由这些符号，式(305)中态的$D$次张量幂为：

其中$\mathcal{O}_{\parallel \cdot \parallel_{2}} \left( D^{- 3 / 2} \right)$表示一个向量，其Hilbert空间范数被某个常数乘以$D^{- 3 / 2}$所界定，该常数可能依赖于$\beta , \gamma , p$，但肯定不依赖于$D$；其情形和推理与引理5的证明类似。现在我们使用引理，更具体地说是其一般（非正交）情形下的式(285)，将前述估计提升到张量幂$D$。更精确地说，我们将该估计重写为如下形式：

并令

从而有

在这种情况下，可以估计方程311中的误差项：

从而证明了引理。

引理8（大D极限下的QAOA态：二阶近似）。设设定和符号如引理7所示。那么，在深度$\Delta$和度数$D$的替代Bethe格子上，QAOA态在大D极限下成立如下另一个近似：

证明。我们从引理7中建立的状态近似开始：

根据目标公式方程315的提示，我们希望去除具有两个$Z$插入的状态：

在张量幂内，其中我们使用了与引理$7$证明中相同的QAOA酉算符记号：

为了实现这一点，我们考虑将$\left| \Psi_{l , m}^{( \Delta - 1 , D )} \right.$正交投影到$\big | \Psi^{( \Delta - 1 , D )} \big \rangle$上：

现在，我们观察到以下正交关系：

第一个关系式源自

这是由QAOA ansatz的$\mathbf{Z}_{2}$对称性得到的——参见方程265中的显式计算。第二个声称的正交关系以类似方式成立。结合这两个关系以及方程319中$\left| \Psi_{l , m}^{( \Delta - 1 , D )} \right.$的正交分解，可得额外的正交关系：

最后，我们显式计算$\left| \Psi_{l , m}^{( \Delta - 1 , D )} \right.$在$\left| \Psi^{\left( \Delta - 1 , D \right)} \right.$上的正交投影系数：

总而言之，我们将方程316中张量幂提升到$D$次的向量重新表示为：

我们现在观察最后一项：

由于之前建立的正交关系，该项与其余部分正交。这建议在取张量幂$D_{;}$时将其舍弃，并使用引理6的正交版本（方程287）。更具体地，我们令：

(330)

并将方程287中的估计重写为：

我们估计当前情况下的误差项：

其中 $\mathcal{O}$ 中的隐含常数依赖于 $p$ 和 $\gamma$ 角，但肯定不依赖于 $D$。从第一行到第二行估计 ${\mathbf{}} u + v$ 的范数所用的公式：

来自引理7的证明（方程314中的计算）。因此我们证明了

现在，利用近似

我们对前一个公式中升至张量幂 $D$ 的向量做进一步的近似。即，

其中 $\mathcal{O}_{\parallel \cdot \parallel_{2}} \left( D^{- 3 / 2} \right)$ 表示一个2-范数以常数倍 $D^{- 3 / 2}$ 为界的向量，且该常数与 $D$ 无关。再次使用引理6（方程285）的非正交版本，可将该估计提升至张量幂 $D$，得到：

将该估计代入方程334，再代入QAOA态的原始估计方程316，即得结果。□

与引理7相比，引理8的主要优势在于去除了临时定义的态 $\left| \Psi_{l , m}^{( \Delta - 1 , D )} \right.$。此外，矩阵 $G^{( \mathrm{sym} , \Delta - 1 , D )}$ 的出现已部分揭示了 $D \to \infty$ 极限的端倪。事实上，由命题5可知，系数

在态的表达式中当 $D \to \infty$ 时收敛到一个定义良好的极限。相比之下，对升到张量幂 $D$ 的态：

其极限对象仍不明确。但我们注意到该向量属于 $D$ 粒子对称子空间，其单粒子空间由以下向量张成：

直观上，我们将这些态中的第一个视为“真空态”，其余视为激发态。因此，使用由基变换矩阵 $\pmb{L}^{( \Delta - 1 , D )} \in \mathbb{C}^{p \times p}$ 定义的正交归一基 $\left( \left| \Psi_{\perp ; l}^{( \Delta - 1 , D )} \right. \right)_{1 \leq l \leq p}$ 来表示激发态更为方便：

计算这样一个矩阵仅需知道原始向量 $\left( \left| \Psi_{j}^{\left( \Delta - 1 , D \right)} \right. \right)_{1 \leq j \leq p}$ 的 Gram 矩阵。

回顾定义12，该 Gram 矩阵正是埃尔米特矩阵 G^(herm, $\Delta - 1 , D )$，根据命题5，它在极限 $D \to \infty$ 下也与早期工作[9]中计算的 $G^{( \Delta - 1 )}$ 矩阵的“埃尔米特角落”重合。更精确地说，通过直接计算，任何满足方程341的 $L$ 必须满足：

反之，若 $\pmb{L}^{( \Delta - 1 , D )}$ 满足后一方程且非奇异，则：

这定义了激发态的一组正交归一基。因此，假设 $G^{( \mathrm{herm} , \Delta - 1 , D )}$ 非奇异，$\pmb{L}^{( \Delta - 1 , D )}$ 的一个具体选择可以是

其中平方根定义良好，因为参数是一个Gram矩阵。将此正交分解代入公式315中的态后：

这个对称态现在可以用D粒子子空间中的

作为单粒子空间的一组正交归一基来表示。为此，我们首先精确定义这个子空间的一组基：

定义 13（子树的对称基）。给定整数

在子树 $\mathcal{T}^{( \Delta - 1 , D )}$ 上，占据数为 $( n_{l} )_{0 \leq l \leq p}$ 的对称态定义为：

在上述方程中，我们定义了

和

此外，我们使用了多项式系数

用于计算将 n₀ 个态 $\left| \Psi_{\perp ; 0}^{( \Delta - 1 , D )} \right. ~ = ~ \left| \Psi^{( \Delta - 1 , D )} \right.$、n₁ 个态 $\left| \Psi_{\perp ; 1}^{( \Delta - 1 , D )} \right.$、n₂ 个态 $\left| \Psi_{\perp ; 2}^{( \Delta - 1 , D )} \right.$ 等分布到 D 个张量积上的方式数。由于公式中的求和确实覆盖了这些张量积态，且单粒子态构成一组正交归一基，这一组合观察证实了 ${| n_{1} , n_{2} , . . . , n_{p - 1} , n_{p} \rangle}_{\Delta - 1 , D}$ 是正确归一化的。

我们现在将公式 347 中态的系数用定义 13 引入的基来表示：

引理 9（子树的态在对称基中的系数）。公式 347 中的子树态可以按下式展开为定义 13 中引入的对称态基：

此外，对于任何固定的（与 D 无关的）占据数集合 $\left( n_{l} \right)_{1 \leq l \leq p}$，对应数态 ${| n_{1} , . . . , n_{p} \rangle}_{\Delta - 1 , D}$ 的系数在 $D \to \infty$ 时收敛。

证明. 我们的目标是利用对称基表达

为此，我们通过分配律展开张量积。为简化符号，记

其中系数 $c_{l}$ 定义为：

(359)

注意这些系数依赖于 D。于是有：

现在，我们根据序列 $\left( l_{j} \right)_{j \in [ D ]}$ 中每个整数 $0 , \ldots , p$ 出现的次数来分组求和，记 $n_{l} ~ ( 0 \leq l \leq p )$ 为 l 出现的次数。注意，根据定义，$\left( n_{l} \right)_{0 \leq l \leq p}$ 之和为 $D$。于是得到：

这就是所宣称的展开式（方程354）。

引理9刚刚在对称基下建立了方程347所定义状态的展开式。我们回忆，该方程定义的状态出现在引理8推导的树状QAOA态的近似中。将对称基展开代入上一个引理，可得：

其中

且

在最后两个方程中，为了方便，我们对引理9的符号稍作修改，特别是对 $\left( n_{l} \right)_{1 \leq l \leq p}$ 求和（从索引 $l = 1$ 开始），并将引理9中的等式约束 $\begin{array} {r} {\sum_{0 \le l \le p} n_{l} = D} \end{array}$ 调整为当前上下文中的等价约束 $\begin{array} {r} {\sum_{1 \le l \le p} n_{l} \le D} \end{array}$。现在，我们可以通过嵌入的线性扩展，将近似状态 $\big | \Phi^{( \Delta , D )} \big \rangle$ 嵌入到由单个量子比特空间与 p 粒子福克空间的张量积 $\mathbb{C}^{2} \otimes \pmb{L}_{2} ( \mathbf{R} )^{\otimes p}$ 中：

其中，右侧的 $| n_{1} , \ldots , n_{p} \rangle$ 指的是数字 $n_{1} , \ldots , n_{p}$ 的福克基态（不涉及 $\mathrm{QAOA}$ 状态），这与左侧的态 ${| n_{1} , . . . , n_{p} \rangle}_{\Delta - 1 , D}$ 不同，后者是相对于深度为 $(\Delta - 1)$、度为 D 的交替贝特晶格上的 QAOA 定义的（定义13）。在这种嵌入下，

其中

我们现在证明，最后一个状态在极限 $D \to \infty$ 下收敛于一个良定义的状态。换句话说，在经过 $\big | \Phi^{( \Delta , D )} \big \rangle$ 的近似和 $\left| \widetilde{\Phi}^{\left( \Delta , D \right)} \right.$ 的福克空间嵌入后，树状 QAOA 状态 $\big | \Psi^{( \Delta , D )} \big \rangle$ 在极限 $D \to \infty$ 下收敛：

定理1（嵌入的近似树状态在 $D \to \infty$ 时的收敛性）。由方程367、364定义的态 $\left| \widetilde{\Phi}^{\left( \Delta , D \right)} \right.$ 以及 QAOA 态 $\left| \Psi^{( \Delta , D )} \right.$ 的嵌入近似 $\big | \Phi^{( \Delta , D )} \big \rangle$（方程363），在 $D \to \infty$ 时，在 $\mathbb{C}^{2} \otimes \mathbf{L}_{2} ( \mathbf{R} )^{\otimes p}$ 中强收敛于一个良定义的极限：

其中

且

证明. 我们首先证明 $\left| {\widetilde{\Phi}}^{( \Delta , D )} \right.$ 弱收敛于 $\left| {\widetilde{\Phi}}^{( \Delta )} \right.$ 。这等价于正交基中每个坐标的收敛；特别地，将计算基与p模Fock基做张量积，即为

上述极限可直接由两个系数的显式公式（方程364, 370）推出；关键在于这些公式中对 $\mathbf{a}_{1 : p} \in \{1 , 1 \}^{p}$ 的求和项数与D无关。这证明了弱收敛。

为由此推导强收敛，只需证明

第一个等式源于将 $\left| \widetilde{\Phi}^{( \Delta )} \right.$ 写为由作用于一个量子比特和玻色子模的酉量子电路产生的自旋-玻色子态；这是附录IV中详述的自旋-玻色子构造的实质。至于第二个极限，它由

（引理8）、

（作为量子电路产生的态）以及嵌入事实

是等距的。

VII. SK模型的经典算法#

在本节中，我们关注生成一个自旋串z的问题，该串对应能量$C(z)$的近最优（$\epsilon$近似）值。在$n \to \infty$极限下，有少数几种经典算法对该任务具有可证明的近似保证¹。这些算法在n上均为多项式时间，但至少在理论上，对$\epsilon$的依赖似乎较差。我们承认，经典工作的目标是产生多项式时间近似方案（PTAS），因此可能没有投入大量精力来降低对$\epsilon$的依赖。

然而，至少对于近似消息传递（AMP）方法而言，证明逆多项式阶的$\epsilon$依赖（即完全PTAS）似乎是一项具有挑战性的任务（见附录VIII）。此外，这些经典算法需要访问Parisi测度以及相应的Parisi PDE解，这被视为温和假设[25, 77]。

Montanari [25]提出了一种基于AMP变体的算法，该算法生成一个自旋序列，其能量在逆温度$\beta$下$\epsilon$近似于SK无穷大尺寸的自由能。如Montanari所示，这可用于生成零温设置$(\beta \to \infty)$下的近似方案，即也能找到SK问题的$\epsilon$近似优化器。原始工作中未指明对$\epsilon$的依赖，但如我们在附录VIII中所证明，其上界可以用$1 / \epsilon^{4}$的指数依赖关系限定。Ivkov和Schramm [83]还表明，SK的AMP可以通过半定规划层次结构高效模拟。

随后，Alaoui、Montanari和Sellke [62]将Montanari的方法推广到高阶自旋玻璃，同时修改了原始的SK AMP算法。文献[62]的方法虽然也基于AMP，但直接生成一个自旋序列，其能量$\epsilon$近似于零温Parisi解，而无需对$\beta$进行退火。不幸的是，由于零温下泛函序参量存在明显奇点[74]，文献[62]中对$\epsilon$的依赖似乎更难以界定，而这一奇点并不妨碍对文献[25]的分析。我们注意到，该算法在文献[77]中进行了基准测试，但对$\epsilon$依赖的研究不够详细，无法与QAOA进行比较。

尽管AMP已应用于多种统计推断问题[79]，但如何将SK的方法推广到其他优化问题似乎尚不明确。我们注意到，对于高围长正则图上的MAXCUT问题，一种置信传播算法在度数趋近无穷时表现出类似SK AMP迭代的行为[80]，这可以通过AMP的普适性[81]解释。此外，AMP已被用作高温下从SK模型中采样的子程序[30]。由于高温限制，这并未产生另一种近似优化算法。

最后，Jekel、Sandhu和Shi [24]提出了势能Hessian上升方法，该方法利用SK目标函数正则化版本的Hessian矩阵的谱投影进行迭代上升。该方法追踪一个与有限$\beta$ Parisi解相关的SDE系统，该解与AMP所追踪的系统对偶。与[25]类似，该方法也对$\beta$进行退火。由于步长在逆$\epsilon$上呈指数级小，其迭代复杂度在$1 / \epsilon^{2}$上呈指数级。与AMP不同，Hessian上升方法更类似于高维非线性优化中使用的下降技术[82]，因此可能具有更广泛的适用性。

VIII. 论SK模型近似消息传递算法的复杂度#

在本节中，我们给出SK模型近似消息传递（AMP）算法复杂度的完整上界。我们将这样做是为了比较QAOA的经验标度与最先进的SK算法。经典算法保证其输出的自旋在 $n \to \infty$ 时以概率1达到最优值的 $(1-\epsilon)$ 近似。对于有限的 $n$，还存在一个额外的失败概率。即使是在平均情况下对于有限 $n$，也存在数量级为 $\mathcal{O} ( n^{- \alpha} )$ 的额外误差需要考虑。在AMP的情况下，这是因为该算法试图追踪Parisi解，而该解仅在无穷大尺寸极限下有效。

在先前关于SK的AMP工作中，$\epsilon$ 依赖性未被明确指定，仅记为 $C ( \epsilon )$。这给出了深度为 ${\mathcal{O}} ( C ( \epsilon ) n )$，总工作量为 $\mathcal{O} ( C ( \epsilon ) n^{2} )$。所谓深度，是指无法并行化的最长操作序列。通过重现文献[25, 62]的证明，我们表明SK的AMP算法（具体来说是文献[25]中的算法）的深度可以上界为 $\mathcal{O} \left( n \frac{e^{\mathcal{O} ( 1 / \epsilon^{4} )}} {\epsilon^{16}} \right)$。文献[62]的方法（定理2）依赖于零温Parisi解的某些正则性，得到了一个 $\mathcal{O} ( n / \epsilon^{2} )$ 的深度。然而，由于先前文献[74]中提到的一个问题（我们称之为Parisi奇异性），目前存在一个障碍。因此，AMP算法能否达到 $\mathcal{O} ( \mathrm{poly} ( 1 / \epsilon ) )$ 的上界尚不清楚。具体来说，根据当前的分析，这需要证明零温下Parisi解的正则性（有界性、Lipschitz性和总变差），即对于 $t \in [ 0 , 1 - \epsilon ]$，函数序参量 $\gamma^{*} ( t ) : [ 0 , 1 ) \to \mathbb{R}$ 和相应的Parisi偏微分方程 (PDE) $\Phi_{*}^{( \infty )}$ 的解具有 $\mathcal{O} ( \mathrm{poly} \log ( 1 / \epsilon ) )$ 的阶。

我们注意到，上述AMP算法的深度比文献[24]的势Hessian上升算法更差，后者在 $\begin{array} {r} {\delta \le \frac{1} {22}} \end{array}$ 时具有 $\widetilde{\mathcal{O}} \left( n^{1 + \delta} e^{\mathcal{O} ( 1 / \epsilon^{2} )} \right)$ 的深度。此外，我们强调一个民间结论，即AMP算法的复杂度至少为 $\Theta ( \mathrm{i} / \epsilon^{2} )$。这是因为AMP利用Euler-Maruyama方案追踪一个随机微分方程系统，在最坏情况下，该方法的收敛速度为 $\mathcal{O} ( \sqrt{\delta} )$，其中 $\delta$ 与迭代次数有关。

在确定 $\epsilon$ 依赖性的过程中，我们（在一定程度上）简明地解释了SK的增量AMP算法如何以及为何有效。

A. 文献[25, 62]的算法#

回顾n个自旋的Sherrington-Kirkpatrick (SK)哈密顿量 $H_{n}$：

其中 $\begin{array} {r} {J_{ij} \sim \mathcal{N} ( 0 , \frac{1} {\sqrt{n}} )} \end{array}$，$W$ 是 $J$ 的向量化，得到一个二阶对称张量。对于逆温度 $\beta$，无穷体积对数吉布斯配分函数 $F ( \beta )$

由著名的Parisi变分公式[73, 78]刻画：

其中

且 $\mathcal{M}$ 是 $[0, 1]$ 上累积分布函数 (CDF) 的集合。注意 $\Phi$ 求解以下二维偏微分方程：

该方程被称为 Parisi 偏微分方程。当 $\alpha_{\beta}$ 为阶梯函数时，上式可通过递归的 Cole-Hopf 变换求解[63]，并连续延拓至整个 $\mathcal{M}$ 上。注意，方程 (377) 存在唯一极小值点，我们记之为 $\alpha_{\beta}^{\ast}$。

众所周知[25, 63, 73]，以下极限成立：

文献[74]还表明，在 $\beta \to \infty$ 时，一个类似变分公式成立。令 $\mathcal{U}$ 为 $[0, 1)$ 上所有非减、正、可积函数的集合。则

其中

且 $\Phi^{( \infty )}$ 求解

该无穷β（零温）变分问题也被证明有唯一极小值点，我们称之为 $\gamma^{*} ( t ) \ [ 75 ]$。

文献[74]中的方法是考虑分布函数 $\beta \alpha_{\beta}^{*} ( t )$ 在 $\beta \to \infty$ 下的弱极限，该极限在 $[0, 1)$ 上存在，但由于在 $t = 1$ 处存在明显奇点（即 $\lim_{t \to 1^{-}} \gamma ( t )$ 可能为无穷大），在 $[0, 1]$ 上并不存在。虽然当 $\beta < \infty$ 且 $t$ 远离 1 时，$\Phi$ 具有良好的正则性性质[75]，但很难对 $[0, 1]$ 整个区间做出断言。因此，我们将此问题称为 Parisi 奇点。

为了使 AMP 算法为 SK 模型提供多项式时间逼近方案 (PTAS)，我们需要假设 SK 模型在低温下满足完全复制对称破缺 (FRSB)，或者等价地，它不具有重叠间隙性质 (OGP) [76]。FRSB 意味着，对于超过某个临界值的 $\beta$，$\alpha_{\beta}^{\ast}$ 在某个区间 $[0, q^{*}], q^{*} \leq 1$ 上严格递增[66]。已经证明，$\dot{\alpha}_{\beta}^{\ast}$ 的步数随着 $\beta \to \infty$ 而发散[68]，这暗示了 FRSB 的可能性。

目前存在两个版本的 SK 模型 AMP 算法，它们之间存在重要差异：Montanari [25] 的算法与 Alaoui 等人[62] 的算法。后者论文的目的还在于将 [25] 中的算法扩展到更高阶自旋玻璃的算法阈值。两个 AMP 算法的目标都是生成自旋 $\sigma$，使得当 $n \to \infty$ 时，$n^{-1} H_{n} ( \sigma )$ 追踪以下量与如下 SDE 系统相关联的量

其中只有一个布朗运动 $B_{t}$。后者具有特定形式的 v 和 u（如下所示），被称为 Aufinger 和 Chen 的 SDE [66]。两者都表明，在 SK 模型的 FRSB 假设下，方程（381）可以任意接近 Parisi 泛函的最小值。因此，AMP 算法的主要目标是跟踪方程（381），使得对于固定的 $\epsilon$，总工作量为 $n$ 的多项式复杂度，即对于足够大的 $n$，这是一个 PTAS。

这些算法在 $v$、$u$ 和 $s$ 的选择上有所不同。具体来说，[62] 选择了

遵循零温下的 Parisi 公式，且 $t^{*} = 1 - \epsilon$。该算法的深度为 $\mathcal{O} ( n \boldsymbol{A} ( \epsilon ) / \epsilon^{2} )$，其中 $\boldsymbol{\mathcal{A}} ( \boldsymbol{\epsilon} )$ 取决于 u 和 v 的 Lipschitz 常数及全变差。如前所述，零温 Parisi 变分问题会遇到 Parisi 奇点。因此，当 $t^{*}$ 从下方趋近于 1 时，$\gamma^{\ast} ( t )$ 可能会发散。与有限 $\beta$ 的情形不同，这阻止了我们获得 u 和 v 正则性的界。具体来说，[75] 表明当 $t^{*}$ 远离 1 时，我们可以界定正则性，此时证明显然要求 $\gamma ( t^{*} )$ 是有限的。这对于固定的 $t^{*}$ 有效，但 $t^{*} = 1 - \epsilon$ 中的 $\epsilon$ 是变化的。上述问题对于 [25] 的方法似乎不是问题，但代价是其上界比 $1 / \epsilon^{2}$ 差得多。因此，看来 Parisi 奇点为 AMP 算法实现人们普遍认为的 $1 / \epsilon^{2}$ 迭代复杂度设置了障碍。

Montanari [25] 考虑了 $u$、$v$ 和 $s$ 的以下选择

这些对应有限 $\beta$ 下的 Parisi 变分问题，即 $\mathcal{P}_{\beta} ( \alpha_{\beta}^{*} )$。因此，对于固定的 $\beta$，该算法只跟踪有限 $\beta$ 下 Parisi 泛函的最小化子。然后，[25] 的引理 3.6 和 3.7 表明，对于 $\beta = \mathcal{O} ( 1 / \epsilon )$，我们可以让方程（381）在 $t^{*} = q^{*}$ 时 $\epsilon$-接近零温 Parisi 泛函的最小值。似乎我们实际上可以确定这种方法复杂度的上界，尽管 [25] 中并未明确展示。本附录的目的就是澄清这一点。

B. SK 模型的近似消息传递算法#

在本小节中，我们回顾 AMP 迭代。我们需要假设算法已经能够访问最小化（377）的 $\alpha_{\beta}^{\ast}$ 以及相应的 $\Phi_{*} ( t , x )$，及其一阶和二阶空间导数。这些假设是标准的 [24, 25, 77]，并且实际上相当于一个可以一次性完成的预处理步骤。

SK 模型的 AMP 迭代量 $\mathbf{z}^{( j )} \in \mathbb{R}^{n}$ 为：

其中 $d_{\ell , j}$ 构成 Onsager 修正项。并且

算法的输出是序列

其中 $f_{j}$ 是一个非线性函数。因此，基于之前的讨论，目标是确保对于 $\ell = \lfloor q^{*} / \delta \rfloor$，我们压制以下误差

函数 $f_{\ell}$ 按分量作用，即

选择非线性函数使得 $f_{k} ( \mathbf{z}^{0} , \ldots , \mathbf{z}^{k} )$ 执行

其中

注意，忽略 $\alpha_{\ell}^{( \delta )}$ 后，$f_{\ell}$ 在 z 上是 Lipschitz 的。还需注意，AMP 的每一步都会对 $H_{n}$ 的梯度进行一次查询，且给定迭代的总计算量为 $\mathcal{O} ( n^{2} )$。然而，从迭代过程可以很容易地观察到，该算法的深度实际上是 ${\mathcal{O}} ( n )$，因为最耗时的步骤 (386) 可以并行化。此外，还有一个额外的舍入过程，用于将输出 $\mathbf{m}^{( \ell )}$ 映射到 $\{- 1 , \bar{1} \}^{N}$ 中的自旋。

AMP 的关键结果是一个极限定理，它描述了其在 ℓ + 1 步 $\mathbf{z}^{( 0 )} , \ldots . \mathbf{z}^{( \ell )}$ 上的迭代过程，这被称为状态演化。首先我们需要一个定义：

定义 14 (伪 Lipschitz [25])。若 $\psi : \mathbb{R}^{D} \to \mathbb{R}$ 满足

则称 $\psi$ 是具有常数 $L > 0$ 的伪 Lipschitz 函数。

定理 2 (状态演化：命题 2.1 [25] 和命题 3.1 [62])。假设我们从 $Z_{0}$ 的初始先验 $p_{0}$（具有有限二阶矩）开始，并独立同分布地从分布 $p_{0}$ 中抽取初始迭代 $\mathbf{z}^{( 0 )}$。那么，对于任何伪 Lipschitz 函数 $\psi : \mathbb{R}^{\ell + 1} \to \mathbb{R}$，我们有

其中收敛是依概率的，$Z_{1} , \ldots , Z_{\ell}$ 是均值为零的高斯随机变量，独立于 $Z_{0}$，其协方差递归地由下式给出

对于 Lipschitz 函数 $f_{\ell} .$

为了强调上述定理的实用性，注意它意味着（至少对于常数 $\alpha_{\ell}^{( \delta )}$ 而言）在 $n \to \infty$ 极限下（依概率），AMP 迭代收敛到以下迭代：

其中

以上即为先前提到过的SDE系统的时间离散化。

我们注意到，在文献[25, 62]中，计算$a_{\ell}^{( \delta )}$和$q_{\ell}^{( \delta )}$时所使用的经验均值被替换为根据状态演化得到的极限期望，从而使$f_{\ell}$成为Lipschitz函数。然而，由于逆函数不具有任何阶的伪Lipschitz性质，状态演化结果是否适用于与$a_{\ell}^{( \delta )}$的缩放组合后的$f_{\ell}$尚不明确。此外，与经验均值不同，$a_{\ell}^{( \delta )}$的极限期望显然是我们无法事先获得的。不过，这一理论文献中未予解决的问题可能会增加整体复杂度。值得注意的是，在文献[77]的数值实现中，作者同样对$\alpha_{\ell}^{( \delta )}$使用了经验均值。

C. 漂移系数与扩散系数的光滑性#

以下结论已在文献[25]中被引用，且对于确定整体运行时间至关重要。 根据文献[63, 命题2.ii]，我们有

我们回忆有界强全变差的定义。

定义15（定义2.1 [62]）。若存在常数$C < \infty$，使得对于$[a, b]$的所有划分及$\mathbb{R}$中的序列$x_{i}$，有

则称$f : [a , b] \times \mathbb{R} \to \mathbb{R}$具有有界强全变差。

回忆

由于对于有限的$\beta$，$\alpha_{\beta}^{*}$是一个分布函数，我们当然有$\| \alpha_{\beta}^{*} \| _{\infty} = 1$。

因此，根据(390)可得

由于$\partial^{j} \Phi_{*}$在时间$t \in [0, 1]$上连续可微，关于时间的Lipschitz性质也有类似不等式成立。根据引理16 [65]，

根据引理6.14 [62]，如果$g$在空间上一致地关于时间是$L$ Lipschitz的，且$h : [a, b] \to \mathbb{R}$具有有界全变差，那么$f = gh$具有有界强全变差，即

注意，$\alpha_{\beta}^{*} ( t )$对于某个普适常数$C$具有有界全变差，这源于$\alpha_{\beta}^{\ast}$的单调性。因此，取$h = \alpha_{\beta}^{*} ( t )$，$g = \partial_{x} \Phi_{*} ( t , x )$。根据[63, 命题2.iii]，时间偏导数是连续的，故$L = \mathcal{O} ( 1 )$。通过查看文献[65, 定理4]中关于$\partial_{t} \partial_{x} \Phi_{*}$的PDE，也可以看出这一点。因此，$v$的强全变差为

其中$C_{1}$是一个普适常数。

[63, 命题2.iii]也表明$\partial_{x}^{2} \Phi$关于时间的偏导数在[0, 1]上连续，因此时间Lipschitz常数为$O ( 1 )$。由此可得

其中$C_2$为某个通用常数。

D. ϵ依赖性的上界#

以下内容基本上是文献[25, 62]中相关证明的复现与整合，仅在表述上做了轻微简化，并仅针对SK模型。目的是表明先前的工作实际上给出了关于ϵ的完整复杂度上界。

首先，我们回顾一下，基于扩散项u所选定的尺度$a_{\ell}^{( \delta )}$，序列$( Z_{j}^{( \delta )} , M_{j}^{( \delta )} )_{j \geq 0}$具有如下保证。

引理10（引理5.1及引理5.1 [62]）。假设$\Sigma_{\ell}^{( \delta )}$的选择如方程(389)所示。那么序列$( Z_{\ell} )^{( \delta )} )_{\ell \geq 0}$是一个从$Z_{0}^{( \delta )} = 0$开始的高斯过程。其增量$\Delta_{\ell}^{( \delta )} : = Z_{\ell}^{( \delta )} - Z_{\ell - 1}^{( \delta )}$是独立的，均值为零，方差为

另外，对于鞅$M_{\ell}^{( \delta )}$有

由于高斯性质，上述条件完全刻画了增量AMP输出的极限分布，即我们在SDE系统离散化中用作驱动布朗运动的对象。

下面的引理给出了SDE跟踪误差（强收敛误差）的界。我们将通过选择特定的耦合，得到Wasserstein-2误差的界，而非通常的$L_{2}$误差。

引理11（命题5.3 [62]，包含显式$\beta$依赖性）。存在一个$\{( Z_{\ell}^{\delta} , X_{\ell}^{( \delta )} \}_{\ell \ge 0}$与$( Z_{t} , X_{t} \}_{t \ge 0}$之间的耦合，使得以下结论成立。对于$0 < \delta < 1$且$\dot{\ell} \leq \delta^{- 1}$，有

证明。从标准布朗运动$( B_{t} )_{t \in [ 0 , 1 ]}$出发，我们将增量$Z_{\ell}^{( \delta )} - Z_{\ell - 1}^{( \delta )}$与$B_{t}$耦合如下：

根据伊藤等距、高斯性质以及前一个引理，在边缘化时，这些增量具有所需的分布。这种定义方式也确保$Z_{\ell}^{( \delta )} = Z_{\delta \ell}$。令$\Delta_{j}^{X} = X_{j}^{( \delta )} - X_{\delta{j}}$对应于X的跟踪误差。可以证明，在$\Delta_{0}^{X} = 0$和(388)的条件下，有

对于第一项，回顾v关于空间变量的Lipschitz性质（来自方程391），有

第二项通过全变差界（方程395）来界定。这导致

由此可得

于是有

我们还得到

第二项可以通过以下方式界定：

将上述两个界限代入，可得

利用 $\ell \delta \leq 1$ 的条件，我们有

现在我们可以应用Gronwall不等式的离散版本，得到

因此

引理12（摘自引理5.3 [62]的证明）。假设真实的 $M_{t}$ 满足 $\mathbb{E} [ M_{t}^{2} ] = t , \forall t \in [ 0 , q^{*} ]$ 。对于SK模型

证明。根据方程(389)

对于

因此

假设我们将每个一维期望替换为关于命题假设中定义的两个过程之间耦合的期望。那么由引理11可得：

回顾我们假设 $\mathbb{E} [ M_{t}^{2} ] = t , \forall t \in [ 0 , q^{*} ]$ ，并且根据伊藤等距，

由勒贝格微分定理和 $u$ 的连续性，对于所有 $t \in [ 0 , q^{*} ]$ ，有

因此

注意对于SK模型，由引理16 [65] 可知存在某个通用常数 $C^{\prime}$ ，使得

因此，我们可以说

因此，

□

现在定义

其中

于是有

引理 13（文献[62]中的引理5.5）。对于 $\ell = \lfloor q^{*} / \delta \rfloor$ ，在SK模型中有

在进入证明之前，注意在原始证明（针对任意阶自旋模型）中，存在一个需要界定的额外误差项。对于SK模型，这个误差项为零。

证明。由于 $q^{*} \leq 1$ ，为简化起见，下面的证明中将其省略。

利用AMP迭代并取内积，我们可以写出

利用状态演化和伪Lipschitz性质

由于 $M_{t}^{( \delta )}$ 是一个鞅，上面的最右边项消失。注意

根据独立性得到。因此，我们有

然后对 $k$ 求和，

由引理12，

其中 ${\widetilde{C}}$ 为通用常数。

因此对于 SK，

同样地，

第一项由引理11有上界 $C \beta^{5} e^{\mathcal{O} ( \beta^{4} )} \sqrt{\delta}$。对于第二项，由(397)式可得，

因此，第二项为 $C_{2} \beta^{3} \sqrt{\delta}$，其中 $C_{2}$ 为某通用常数。对于第三项，我们可以使用全变差上界（式(396)），

因此，综合所有结果，

现在，我们转向阈值化和取整过程以确保可行性。逐元素阈值化[62]过程如下：

引理14（[62]中的引理5.7）。对于SK模型，

证明。将函数$\psi : \mathbb{R} \mathbb{R}$定义为

状态演化表明

我们也有

这来自引理13，并且利用了$M_{\delta \ell}$几乎必然处于$[ - 1 , 1 ]$中。

其余部分与[62]的证明完全相同，其中所有常数均为通用常数。因此，该结果对某个通用常数成立。□

舍入过程的修改方式类似，因为它仅通过引理14中的界依赖于AMP迭代，而该界主导了误差。具体来说，这是针对[62]中引理5.8证明中的(d)步骤。

因此，我们得到以下结果。

定理3 ( $[ 25 ] \ \& \ [ 62 ]$ )。如果对于超过某个临界阈值的所有$\beta$，SK模型都是FRSB的，则存在一个深度为$\begin{array} {r} {\mathcal{O} \left( n \cdot \frac{e^{\mathcal{O} ( 1 / \epsilon^{4} )}} {\epsilon^{16}} \right)} \end{array}$且工作量为$\mathcal{O} \left( n^{2} \cdot \frac{e^{\mathcal{O} ( 1 / \epsilon^{4} )}} {\epsilon^{16}} \right)$的算法，该算法输出自旋$\sigma_{\mathrm{alg}} \in \{- 1 , 1 \}^{n}$，使得

这里我们看到，当前的上界比期望的$1 / \epsilon^{2}$指数级更差。如前所述，[62]的方法避免了导致这种爆炸的额外$\beta$因子。然而，如何处理Parisi奇异性并完全界定[62]方法中关于$\epsilon$的依赖关系尚不清楚。奇异性也可能导致关于$1 / \epsilon$的指数爆炸。然而，如果对于(385)式，当$t^{*} = 1 - \epsilon$时，第八C节中Lipschitz常数和全变差的界可以证明为$\mathcal{O} ( \mathrm{poly} \log ( 1 / \epsilon ) )$，则存在一个深度为${\mathcal{O}} ( n \cdot \mathrm{poly} ( 1 / \epsilon ) )$的AMP算法。

参考文献#

[1] S. Boulebnane and A. Montanaro, PRX Quantum 5, 030348 (2024).

[2] R. Shaydulin, C. Li, S. Chakrabarti, M. DeCross, D. Herman, N. Kumar, J. Larson, D. Lykov, P. Minssen, Y. Sun, Y. Alexeev, J. M. Dreiling, J. P. Gaebler, T. M. Gatterman, J. A. Gerber, K. Gilmore, D. Gresh, N. Hewitt, C. V. Horst, S. Hu, J. Johansen, M. Matheny, T. Mengle, M. Mills, S. A. Moses, B. Neyenhuis, P. Siegfried, R. Yalovetzky, and M. Pistoia, Science Advances 10, eadm6761 (2024), https://www.science.org/doi/pdf/10.1126/sciadv.adm6761.

[3] E. Farhi, S. Gutmann, D. Ranard, and B. Villalonga, arXiv:2503.12789 (2025).

[4] A. Montanaro and L. Zhou, arXiv:2411.04979 (2024).

[5] L. K. Grover, in Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC ’96 , STOC ’96 (ACM Press, 1996) p. 212–219.

[6] P. W. Shor, in Proceedings 35th Annual Symposium on Foundations of Computer Science (IEEE, 1994) pp. 124–134.

[7] S. P. Jordan, N. Shutty, M. Wootters, A. Zalcman, A. Schmidhuber, R. King, S. V. Isakov, T. Khattar, and R. Babbush, Nature 646, 831–836 (2025).

[8] H.-Y. Huang, S. Choi, J. R. McClean, and J. Preskill1, arXiv:2508.05720 (2025).

[9] J. Basso, E. Farhi, K. Marwaha, B. Villalonga, et al., in 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 232 (Schlos Dagstuhl – Leibniz-Zentrum f¨ur Informatik, Dagstuhl, Germany, 2022) pp. 7:1–7:21.

[10] D. Sherrington and S. Kirkpatrick, Physical Review Letters 35, 1792–1796 (1975).

[11] D. Gamarnik and E. C. Kızılda˘g, The Annals of Applied Probability 31, 10.1214/20-aap1625 (2021).

[12] M. M´ezard, G. Parisi, and R. Zecchina, Science 297, 812–815 (2002).

[13] D. J. Amit, H. Gutfreund, and H. Sompolinsky, Physical Review A 32, 1007–1018 (1985).

[14] A. Engel, Statistical Mechanics of Learning (Cambridge University Press, 2001).

[15] H. Nishimori, Statistical Physics of Spin Glasses and Information Processing: An Introduction, 111 (Clarendon Press, 2001).

[16] C. Villani, Optimal Transport (Springer Berlin Heidelberg, 2009).

[17] G. Parisi, Phys. Rev. Lett. 43, 1754 (1979).

[18] A. Crisanti and T. Rizzo, Phys. Rev. E 65, 046137 (2002).

[19] K. Binder and A. P. Young, Reviews of Modern Physics 58, 801–976 (1986).

[20] F. Barahona, Journal of Physics A: Mathematical and General 15, 3241–3253 (1982).

[21] M. Aramon, G. Rosenberg, E. Valiante, T. Miyazawa, H. Tamura, and H. G. Katzgraber, Frontiers in Physics 7, 10.3389/fphy.2019.00048 (2019).

[22] T. Leleu, F. Khoyratee, T. Levi, R. Hamerly, T. Kohno, and K. Aihara, Communications Physics 4, 10.1038/s42005-021- 00768-0 (2021).

[23] K. Sankar, A. Scherer, S. Kako, S. Reifenstein, N. Ghadermarzy, W. B. Krayenhof, Y. Inui, E. Ng, T. Onodera, P. Ronagh, and Y. Yamamoto, npj Quantum Information 10, 10.1038/s41534-024-00856-3 (2024).

[24] D. Jekel, J. S. Sandhu, and J. Shi, in Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (SIAM, 2025) pp. 5307–5387.

[25] A. Montanari, Optimization of the Sherrington-Kirkpatrick Hamiltonian (2019), arXiv:1812.10897 [math.PR].

[26] E. Farhi, J. Goldstone, S. Gutmann, and L. Zhou, Quantum 6, 759 (2022).

[27] J. Basso, D. Gamarnik, S. Mei, and L. Zhou, in 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2022) p. 335–343.

[28] See Supplemental Material at [URL will be inserted by publisher] for detailed proofs of the spin–boson mapping, the QAOA energy computation procedure, Fock-space truncation analysis, alternative fitting functions, and analysis of the classica message-passing algorithm, which includes Refs. [34–87].

[29] L. Zhou, The QAOA at high girth for MaxCut and the Sherrington-Kirkpatrick model, Talk at the TQC 2022 conference (2022).

[30] A. E. Alaoui, A. Montanari, and M. Sellke, arXiv:2203.05093 (2024).

[31] S. Chatterjee, arXiv:0907.3381 (2009).

[32] D. Lykov, R. Shaydulin, Y. Sun, Y. Alexeev, and M. Pistoia, in Proceedings of the SC ’23 Workshops of the International Conference on High Performance Computing, Network, Storage, and Analysis, SC-W 2023 (ACM, 2023).

[33] S. Boulebnane, A. Khan, M. Liu, J. Larson, D. Herman, R. Shaydulin, and M. Pistoia, Data for “A spin–boson mapping of the quantum approximate optimization algorithm” (2025).

[34] T. Ayral, T. Louvet, Y. Zhou, C. Lambert, et al., PRX Quantum 4, 10.1103/prxquantum.4.020304 (2023).

[35] J. Larson and M. Menickelly, Mathematical Programming Computation 16, 1 (2024).

[36] J. Larson, M. Menickelly, J. P. O’Neal, and S. M. Wild, Interpolation-based composite derivative-free optimization (2025).

[37] S. M. Wild, in Advances and Trends in Optimization with Engineering Applications, edited by T. Terlaky, M. F. Anjos, and S. Ahmed (SIAM, 2017) pp. 529–540.

[38] B. Villalonga, Performance of the QAOA on maxcut over large-girth regular graphs (2022).

[39] E. Farhi, J. Goldstone, and S. Gutmann, A quantum approximate optimization algorithm (2014), arXiv:1411.4028 [quantph].

[40] M. P. Harrigan, K. J. Sung, M. Neeley, K. J. Satzinger, et al., Nature Physics 17, 332–336 (2021).

[41] S. Boulebnane, J. Sud, R. Shaydulin, and M. Pistoia, Equivalence of quantum approximate optimization algorithm and linear-time quantum annealing for the Sherrington-Kirkpatrick model (2025), arXiv:2503.09563 [quant-ph].

[42] F. Verstraete and J. I. Cirac, Physical Review B 73, 10.1103/physrevb.73.094423 (2006).

[43] T. Hao, Z. He, R. Shaydulin, J. Larson, et al., End-to-end protocol for high-quality QAOA parameters with few shots (2024), arXiv:2408.00557 [quant-ph].

[44] Z. He, R. Shaydulin, D. Herman, C. Li, et al., Parameter setting heuristics make the quantum approximate optimization algorithm suitable for the early fault-tolerant era (2024), arXiv:2408.09538 [quant-ph].

[45] M. Fishman, S. R. White, and E. M. Stoudenmire, SciPost Phys. Codebases , 4 (2022).

[46] Argonne leadership computing facility.

[47] National energy research scientific computing.

[48] T. Hogg and D. Portnov, Information Sciences 128, 181–197 (2000).

[49] T. Hogg, Physical Review A 61, 10.1103/physreva.61.052311 (2000).

[50] S. Omanakuttan, Z. He, Z. Zhang, T. Hao, A. Babakhani, S. Boulebnane, S. Chakrabarti, D. Herman, J. Sullivan, M. A. Perlin, R. Shaydulin, and M. Pistoia, arXiv:2504.01897 (2025).

[51] R. Shaydulin and M. Pistoia, in 2023 IEEE Int. Conf. Quantum Comput. Eng. (IEEE, 2023) p. 1074–1077.

[52] E. Pelofske, A. B¨artschi, and S. Eidenbenz, in Lecture Notes in Computer Science (Springer Nature Switzerland, 2023) pp. 240–258.

[53] E. Pelofske, A. B¨artschi, L. Cincio, J. Golden, and S. Eidenbenz, npj Quantum Information 10, 10.1038/s41534-024-00906- w (2024).

[54] B. Tassef, T. Albash, Z. Morrell, M. Vufray, A. Y. Lokhov, S. Misra, and C. Cofrin, Journal of Heuristics 30, 325–358 (2024).

[55] Z. He, R. Shaydulin, S. Chakrabarti, D. Herman, C. Li, Y. Sun, and M. Pistoia, npj Quantum Information 9, 10.1038/s41534-023-00787-5 (2023).

[56] Z. He, D. Amaro, R. Shaydulin, and M. Pistoia, arXiv:2409.12104 (2024).

[57] Z. Zhang, J. Shen, N. Kumar, and M. Pistoia, arXiv:2504.00987 (2025).

[58] G. Parisi, Proceedings of the National Academy of Sciences 103, 7948–7955 (2006).

[59] A. Anshu and T. Metger, Quantum 7, 999 (2023).

[60] A. Apte, S. H. Sureshbabu, R. Shaydulin, S. Boulebnane, Z. He, D. Herman, J. Sud, and M. Pistoia, arXiv:2504.01694 (2025).

[61] R. Shaydulin, I. Safro, and J. Larson, in Proceedings of the IEEE High Performance Extreme Computing Conference (2019).

[62] A. E. Alaoui, A. Montanari, and M. Sellke, Optimization of mean-field spin glasses (2020), arXiv:2001.00904 [math.PR].

[63] A. Aufinger and W.-K. Chen, Communications in Mathematical Physics 335, 1429–1444 (2014).

[64] JPMorgan Chase, QOKit (2023), accessed: 2025-05-12.

[65] A. Jagannath and I. Tobasco, Proceedings of the American Mathematical Society 144, 3135–3150 (2015).

[66] A. Aufinger and W.-K. Chen, arXiv:1303.3573 (2013).

[67] Y. Jin, Z. He, T. Hao, D. Amaro, S. Tannu, R. Shaydulin, and M. Pistoia, arXiv:2504.21172 (2025).

[68] A. Aufinger, W.-K. Chen, and Q. Zeng, The sk model is infinite step replica symmetry breaking at zero temperature (2021), arXiv:1703.06872 [math.PR].

[69] P. C. Lotshaw, G. Siopsis, J. Ostrowski, R. Herrman, R. Alam, S. Powers, and T. S. Humble, Physical Review A 108, 10.1103/physreva.108.042411 (2023).

[70] V. Akshay, H. Philathong, E. Campos, D. Rabinovich, I. Zacharov, X.-M. Zhang, and J. D. Biamonte, Physical Review A 106, 10.1103/physreva.106.042438 (2022).

[71] J. A. Montanez-Barrera and K. Michielsen, arXiv:2405.09169 (2024).

[72] L. Zhou, $g_{s} , t$ is the autocorrelation function, Private correspondence (2022).

[73] D. Panchenko, The Sherrington-Kirkpatrick Model (Springer Science & Business Media, 2013).

[74] A. Aufinger and W.-K. Chen, Parisi formula for the ground state energy in the mixed p-spin model (2016), arXiv:1606.05335 [math.PR].

[75] W.-K. Chen, M. Handschy, and G. Lerman, Probability Theory and Related Fields 171, 53–95 (2017).

[76] D. Gamarnik, Proceedings of the National Academy of Sciences 118, e2108492118 (2021).

[77] A. E. Alaoui and A. Montanari, Algorithmic thresholds in mean field spin glasses (2020), arXiv:2009.11481 [cond-mat.statmech].

[78] M. Talagrand, Annals of Mathematics , 221 (2006).

[79] O. Y. Feng, R. Venkataramanan, C. Rush, R. J. Samworth, et al., Foundations and Trends in Machine Learning 15, 335 (2022).

[80] A. E. Alaoui, A. Montanari, and M. Sellke, Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree (2023), arXiv:2111.06813 [math.PR].

[81] H. E. Cheairi and D. Gamarnik, Algorithmic universality, low-degree polynomials, and max-cut in sparse random graphs (2024), arXiv:2412.18014 [cs.DS].

[82] Y. Nesterov et al., Lectures on convex optimization, Vol. 137 (Springer, 2018).

[83] M. Ivkov and T. Schramm, Semidefinite programs simulate approximate message passing robustly (2023), arXiv:2311.09017 [cs.DS].

[84] L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Physical Review X 10, 10.1103/physrevx.10.021067 (2020).

[85] W. Kretschmer, S. Grewal, M. DeCross, et al., arxiv preprint arXiv:2509.07255 (2025).

[86] S. Aaronson and A. Arkhipov, in Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC ’11 (Association for Computing Machinery, New York, NY, USA, 2011) p. 333–342.

[87] A. Bouland, B. Feferman, C. Nirkhe, et al., Nat. Phys 15, 159 (2019).

阅读笔记#

一句话概括#

本文针对Sherrington–Kirkpatrick (SK) 模型上无穷大尺寸极限的QAOA，提出自旋-玻色子映射方法：将深度$p$的QAOA态等价为一个自旋与$p$个玻色子模耦合的量子态，并利用矩阵积态（MPS） 高效模拟该自旋-玻色系统（Fock截断维数$d\lesssim10$）。核心结论：在$p=160$时达到相对误差$\varepsilon\lesssim2.2\%$（远超此前精确方法$p\leq20$的极限），经验上收敛到Parisi值，且有限尺寸验证表明精确求解需$p\propto n^{1.3}$——这给出了QAOA相比经典消息传递算法$\mathcal{O}[e^{\mathcal{O}(1/\epsilon^4)}/\epsilon^{16}]$复杂度的多项式优势。

核心论证链#

1. 问题定位：为何需要新方法——SK模型是平均情况困难的NP-hard自旋玻璃问题，QAOA性能随深度$p$单调提升，但现有精确评估技术（文献[26,27]）因计算成本随$p$指数增长，仅能处理$p\leq20$。因此必须寻找计算成本可控的方法来评估高深度QAOA性能，从而与经典算法做有意义的基准对比。

2. 树图等价性：将无穷大随机图映射为树——基于文献[9]的定理1：SK模型上无穷大无序平均QAOA能量密度等于$D$叉双边树$S$上QAOA态的ZZ期望值在$D\to\infty$极限下的结果。这一步将全连接随机图的全局计算问题简化为具有递归结构的树图上的局域计算，是后续映射成立的前提。

3. 置换对称性识别玻色子自由度——树$\mathcal{T}$由根节点和$D$个置换对称的子树构成。由于这$D$个子树的排列不改变QAOA态，该对称性自然地提供了将$D$个子树视为$D$个相同玻色子的识别方式。这是从"多个独立子系统"到"玻色子多体系统"的概念跃迁，为福克空间描述铺平道路。

4. 大$D$展开与单粒子流形构造（核心映射）——在每个QAOA层$t$，根与子树的耦合$e^{-i\gamma_t Z_\emptyset Z_{\mathcal{O}_i'}/\sqrt{D}}$在$D\to\infty$下泰勒展开为：单位算符（$\mathcal{O}(1)$振幅）加每层一个$Z$插入（$\mathcal{O}(D^{-1/2})$振幅），两个及以上插入的项消失。因此每个子树态分解为真空态$|\Psi^{(p-1)}\rangle$与$p$个单激发态$|\Psi_t^{(p-1)}\rangle$。这一展开直接确定了映射后的玻色子自由度数恰好等于QAOA层数$p$——空间模数与时间层数的对偶性由此诞生。

5. 极限态收敛与Fock空间截断——$D\to\infty$时QAOA态强收敛到自旋-玻色子态$|\Phi^{(p)}\rangle\in\mathbb{C}^2\otimes L_2(\mathbb{R})^{\otimes p}$。关键物理：每个子树非真空概率仅$\mathcal{O}(D^{-1})$，总粒子数$\mathcal{O}(1)$，因此Fock空间可截断至很小维数$d\lesssim10$，且误差在$d$中指数衰减。这保证了自旋-玻色子系统的模拟复杂度不随$p$指数爆炸，而是由低纠缠结构主导。

6. MPS数值模拟与幂律拟合——利用自旋-玻色系统整体纠缠较低的特点，用MPS高效演化至$p=160$。将数据点$(p,\nu_p)$拟合到$\epsilon(p)=m/p^\eta+b$，得到$\eta=0.88\pm0.03$，$b=0.002\pm0.003$（$1-R^2=6.83\times10^{-5}$）。结论：QAOA能量经验上收敛到Parisi值，且$\epsilon\sim1/p^{0.88}$意味着要达到$(1-\epsilon)$近似，所需深度为$p\propto 1/\epsilon^{1.13}$。

7. 有限尺寸验证与经典算法对比——在$n=2$到$30$的随机SK实例上验证：即使使用无限大极限优化的参数（无需实例调参），近似比随$p$持续提升；精确求解成功概率的指数衰减$\kappa(p)\propto p^{-0.72}$暗示所需深度$p\propto n^{1.3}$。与经典消息传递算法[25]的$\mathcal{O}[e^{\mathcal{O}(1/\epsilon^4)}/\epsilon^{16}]$复杂度对比，QAOA的$\mathrm{poly}(1/\epsilon)$依赖展现出显著优势，尽管该优势基于经验拟合而非严格证明。

实验参数详解#

批判性思考#

1. 大$D$展开的算子收敛性未严格证明——论文将$e^{-i\gamma_t Z_\emptyset Z_{\mathcal{O}_i'}/\sqrt{D}}$做泰勒展开至$O(D^{-1})$并声称高阶项在$D\to\infty$时消失。但$e^{-i\theta A/\sqrt{D}}$的展开并非普通数值泰勒级数（因$Z_\emptyset Z_{\mathcal{O}_i'}$算符范数为1），且在QAOA态的关联函数中，$D$个子树的大量弱贡献可能相干叠加而非简单消失，需要更严格的算子范数收敛分析。

2. Fock截断$d\lesssim10$缺乏系统误差传播分析——论文声称截断误差在$d$中指数衰减且对$p$依赖适中，但未给出不同$p$下截断误差的具体数值，也未与$p\leq20$区域的精确结果进行逐点交叉验证。当$p$从20增至160时，$d$是否需随之增长？缺少定量界。

3. $b=0.002\pm0.003$不等于收敛性证明——拟合常数$b$在$3\sigma$内不显著，可解读为支持收敛到Parisi值。但拟合区间仅覆盖$p=15$至$80$，且$p>80$的点使用外推参数而非真实优化值。不能排除$\epsilon(p)$在更大$p$下偏离幂律行为或收敛到一个微小但非零常数的可能性。

4. 经典算法比较的证据强度不对称——论文给出经典消息传递算法[25]的复杂度$\mathcal{O}[e^{\mathcal{O}(1/\epsilon^4)}/\epsilon^{16}]$系独立重新分析所得，且作者自述"普遍观点认为可改进到$\mathcal{O}(n/\epsilon^2)$，但缺乏详细实证研究"。QAOA的$\mathcal{O}(n/\epsilon^{1.13})$基于经验拟合，而经典算法的指数复杂度基于理论分析——两者证据类型不同，直接比较需谨慎。

5. 有限尺寸外推的风险——精确求解标度律$p\propto n^{1.3}$源自$n\leq30$的数值外推。小规模系统中，有限尺寸效应、能隙结构和纠缠特性可能与热力学极限下定性不同。成功概率随$n$呈指数衰减本身暗示了有限尺寸效应不可忽略，该标度律在$n\sim100$以上是否成立完全未知。

6. 自旋-玻色映射的适用范围窄——映射依赖三个条件：SK模型的全连接性、$D\to\infty$极限（即无穷大连通度）、置换对称性。对于更实际的有限度数图（如MaxCut on $3$-regular graphs），$D$固定，大$D$展开不成立，映射不直接适用。论文承认"度数有限时顺序构造该态可能更具挑战性"，这意味着该方法目前仅限于SK模型一类高度对称问题。

7. 缺少与张量网络精确方法的直接对比——论文使用MPS模拟自旋-玻色系统，但未对$p\leq20$区域提供与文献[27]精确结果的保真度对比。这种验证对于建立新方法在更高$p$下的可信度至关重要。

局限性#

• 无限尺寸极限与有限系统的鸿沟：核心结果$\nu_p$在$n\to\infty$极限下推导，而有限尺寸SK实例的基态能量密度与Parisi值存在$O(1/\sqrt{n})$量级的统计涨落，使用无限大角度在有限系统上的实际性能缺乏理论保证。
• $D\to\infty$极限仅对应全连接图：映射本质依赖于$D$叉树的$D\to\infty$极限，对应SK模型的全连接性质。对于有限度数图，$D$固定，大$D$展开崩溃，映射不可用。
• 经验拟合缺乏解析推导：$\epsilon(p)\sim m/p^\eta$是纯经验性幂律拟合，作者未给出任何解析论证$\eta\approx0.88$的起源。无法排除其他函数形式（如$\epsilon\sim e^{-\alpha p}$）或存在非零渐近值的可能。
• $p>80$的数据点参数未优化：图2中$p=120,160$使用的参数从$p=80$外推而非实际优化，意味着这些点不代表该深度下QAOA的最优性能，实际$\epsilon(p)$可能更低。
• Fock截断与MPS精度缺乏系统验证：未提供$d$取不同值时$\nu_p$的收敛曲线，也未与$p\leq20$精确结果进行保真度交叉验证。MPS的键维数（bond dimension）选择及其对结果的影响也未报告。
• 精确求解标度律受限于小规模数据：$p\propto n^{1.3}$基于$n\leq30$的数值外推，该标度律在更大$n$下可能因能隙闭合、纠缠熵增长等效应发生质变。
• 未考虑量子噪声和退相干：论文完全在无噪声QAOA框架下分析，实际量子硬件上的门错误、退相干和测量误差在高深度（$p=160$）下极为严重，可能使理论预测的精度在物理实现中完全不可达到。
• 经典复杂度比较的基准不确定性：与文献[25]的对比中，论文重新分析了经典算法复杂度但未提供复现基准。缺少在相同问题规模和近似比要求下，经典算法与QAOA的实际运行时间对比数据。
• 缺少对映射本身计算复杂度的分析：论文虽展示了$p=160$的计算可行性，但未系统分析MPS模拟自旋-玻色系统的计算复杂度如何随$p$标度（键维数增长、时间成本等），难以评估该方法可扩展到的最大$p$。

关键公式速查#

• $$C^{\mathrm{SK}}(z)=\frac{1}{\sqrt{n}}\sum_{j
• $$P_*=-\lim_{n\to\infty}\min_z\frac{C^{\mathrm{SK}}(z)}{n}=0.763166\ldots$$— SK模型热力学极限基态能量密度（Parisi值），式(4)
• $$\nu_p(\boldsymbol{\gamma},\boldsymbol{\beta})=\lim_{n\to\infty}\mathbb{E}_J\langle\boldsymbol{\gamma},\boldsymbol{\beta},C^{\mathrm{SK}}|C^{\mathrm{SK}}/n|\boldsymbol{\gamma},\boldsymbol{\beta},C^{\mathrm{SK}}\rangle$$— 无穷大无序平均QAOA能量密度，式(5)
• $$\nu_p(\boldsymbol{\gamma},\boldsymbol{\beta})=\lim_{D\to\infty}\langle\boldsymbol{\gamma},\boldsymbol{\beta},C^S|Z_LZ_R|\boldsymbol{\gamma},\boldsymbol{\beta},C^S\rangle$$— 能量密度与双边树$S$上ZZ期望值的等价关系（定理1），式(6)
• $$|\Phi^{(p)}\rangle=\sum_{\substack{z_\emptyset\in\{1,-1\}\\ \boldsymbol{n}\in\mathbb{N}^p}}c(z_\emptyset,\boldsymbol{n})|z_\emptyset\rangle\otimes|\boldsymbol{n}\rangle$$— $D\to\infty$极限下的自旋-玻色子态，$\boldsymbol{n}=(n_1,\ldots,n_p)$为数态标签，式(11)
• $$\epsilon(p)=1-\frac{\nu_p}{P_*}=\frac{m}{p^\eta}+b$$— 相对误差与深度的幂律拟合，$m=1.34,\eta=0.88,b\approx0$，式(12)
• $$\mathrm{AR}:=\frac{E(\boldsymbol{\gamma},\boldsymbol{\beta})-E_{\min}}{E_{\max}-E_{\min}}$$— 有限尺寸实例的近似比定义，$E_{\min}/E_{\max}$为实例最小/最大能量，式(13)
• $$|\boldsymbol{\gamma},\boldsymbol{\beta},C\rangle=U(B,\beta_p)U(C,\gamma_p)\cdots U(B,\beta_1)U(C,\gamma_1)|s\rangle$$— 深度$p$的QAOA态，$U(C,\gamma)=e^{-i\gamma C},U(B,\beta)=e^{-i\beta B}$，式(2)

术语对照#

延伸阅读#

• E. Farhi, J. Goldstone, S. Gutmann & L. Zhou, Quantum 6, 759 (2022) — 首次将SK模型的QAOA能量密度精确计算到$p=11$，建立了无序平均的解析公式体系，是本文的直接前期工作。

• J. Basso, D. Gamarnik, S. Mei & L. Zhou, FOCS 2022 — 将QAOA的局部树状论证推广到更广泛的稀疏约束满足问题和自旋玻璃，证明能量等价性的一般条件，为自旋-玻色映射的推广提供了理论基础。

• S. Boulebnane & A. Montanaro, PRX Quantum 5, 030348 (2024) — 提供了QAOA在组合优化问题上可实现多项式/指数加速的严格证明框架，与本文的经验性标度律形成互补。

• L. Zhou, S.-T. Wang, S. Choi, H. Pichler & M. D. Lukin, Phys. Rev. X 10, 021067 (2020) — 展示了QAOA参数优化中的景观结构，可作为理解本文中参数优化策略的辅助背景。

• 量子主成分分析 — Lloyd 等（2014）提出量子主成分分析（qPCA）算法，利用多份未知量子态副本通过密度矩阵指数化实现特征值与特征向量的量子形式提取，时间复杂度 O(log