技术摘要：改进的量子配分函数自适应估计及其海森堡缩放

1. 问题陈述

本文解决了估计 $n$-比特量子哈密顿量 $H$ 在逆温度 $\beta$ 下的对数配分函数 $f(\beta) = \ln Z(\beta)$ 的基本问题。配分函数 $Z(\beta) = \text{Tr}(e^{-\beta H})$ 决定了自由能，并编码了平衡态的热力学性质。目标是在实现精度方面达到海森堡缩放（Heisenberg scaling），即在加性误差 $\epsilon$ 下，查询复杂度按 $\tilde{O}(1/\epsilon)$ 缩放，同时最小化对系统规模 $n$ 的依赖以及对热态访问资源的依赖。

本研究是在哈密顿量通过 $\alpha$-块编码（$\alpha$-block encoding，其中 $\alpha = \Theta(h)$ 且 $0 \preceq H \preceq hI$）提供的假设下进行的，并区分了两种热态访问模型：

1. 固定温度相干访问： 算法在经典上选择一个温度，并访问用于制备热场双重态（Thermofield Double, TFD）$|\psi_\theta\rangle$ 的酉算符 $U_\theta$。
2. 相干温度访问： 逆温度存储在一个量子寄存器中，允许使用酉算符 $U_{\text{coh}}$ 相干地制备 TFD 态的叠加态 $|\theta\rangle|\psi_\theta\rangle$。

2. 方法论与算法框架

2.1 重构框架

核心贡献是一个重构框架，该框架将对数配分函数表示为一个关于缓慢变化冷却方案（slowly-varying cooling schedule）的级数和，其中 $0 = \beta_0 < \dots < \beta_\ell = \beta$。如果相邻 TFD 态之间的平方重叠度被下界限制在 $1/C$ 以上，则称该方案是 $C$-缓慢变化的。

增量 $f(\beta_{i+1}) - f(\beta_i)$ 使用递归倍增恒等式（recursive-doubling identity）进行分解。该恒等式将增量表示为以下各项的加权和：

• 重叠度（Overlaps）： $O(\theta, s) = |\langle \psi_\theta | \psi_{\theta+s} \rangle|^2$，与 $f$ 的二阶有限差分相关。
• 重加权比率（Reweighting ratios）： $R(\theta, s) = \text{Tr}(\rho_\theta e^{-sH})$，与 $f$ 的一阶差分相关。

具体而言，对于区间 $\Delta_i = \beta_{i+1} - \beta_i$，作者选择步长 $\delta_i$ 使得 $h\delta_i \leq 1$，以及整数 $k_i$ 使得 $2^{k_i}\delta_i = \Delta_i$。增量重构为：
$$f(\beta_{i+1}) - f(\beta_i) = 2^{k_i} B(\beta_i, \delta_i) + \sum_{j=1}^{k_i} 2^{k_i-j} A(\beta_i, 2^j \delta_i)$$
其中 $A = -\ln O$ 且 $B = \ln R$。这种分解确保了所有涉及的概率都保持在远离零的均匀范围内，从而实现稳定的对数估计。

2.2 估计策略

论文根据访问模型提出了两种算法：

A. 固定温度算法 (Algorithm 2)

• 方法： 使用近无偏量子振幅估计器（基于 Cornelissen 和 Hamoudi [10]）独立估计每个对数项（$A$ 和 $B$）。
• 方差分配： 根据重构系数（$a_{i,j}$）自适应地分配每个项的估计深度，以在控制加权和总方差的同时最小化总查询成本。
• 机制： 利用量子奇异值变换（QSVT）来实现 $B$ 所需的短虚时重加权步骤。

B. 相干温度算法 (Algorithm 3)

• 方法： 避免单独估计各项。相反，它准备一个所有重构项的叠加态，其概率与其系数成正比。
• 估计器： 利用量子逆二项式对数估计器（quantum inverse-binomial log estimator）。对于每个分支，通过重复相干试验来统计第一次成功前的失败次数，将该计数转换为近似负对数成功概率的调和数。
• 聚合： 直接对这些样本的加权和应用量子均值估计（Montanaro [19]）。这消除了由于对独立估计求和而产生的 $\sqrt{\ell}$ 因子。

2.3 方案生成

作者改编了 Arunachalam 等人 [2] 的自适应冷却方案生成程序，使其适用于实值谱。通过对 TFD 重叠度进行二分查找，他们构建了一个长度为 $\ell = \tilde{O}(\sqrt{n})$ 的方案（针对具有常数温度的广延哈密顿量），且不需要能量间隙（spectral gap）假设。

3. 主要结果与复杂度界限

假设哈密顿量是广延的（$h = O(n)$）且处于常数逆温度 $\beta = \Theta(1)$ 下，预期的查询复杂度（调用状态制备和块编码的次数）如下表所示：

访问模型	查询复杂度	对比
固定温度	$\tilde{O}\left(\frac{n^{5/4}}{\epsilon}\right)$	通过比非自适应策略提升了 $n^{1/4}$ 倍。
相干温度	$\tilde{O}\left(\frac{n}{\epsilon}\right)$	达到了理论下界（在忽略多项式对数因子的情况下）。

下界最优性：
论文在隐藏偏移模型（hidden-offset model）中建立了 $\Omega(\alpha \beta / \epsilon)$ 的块编码查询下界。对于 $\alpha = \Theta(n)$，相干温度算法实现了 $\tilde{O}(n/\epsilon)$，证明其在多项式对数因子范围内是优化的。固定温度算法与该基准相比，在系统规模上存在 $\tilde{O}(n^{1/4})$ 的差距。

电路复杂度 (1D Spin Chains)：
对于具有高效 TFD 制备（例如通过拟绝热连续化）的一维系统，作者将查询界限转化为门计数。

• 固定温度： $\tilde{O}(n^{9/4}/\epsilon)$ 个门。
• 相干温度： $\tilde{O}(n^2/\epsilon)$ 个门。
  相干方法保留了 $n^{1/4}$ 的门计数优势，前提是相连的 TFD 制备不会产生过高的额外开销（通过带有参数化角度的共享电路结构是可以实现的）。

4. 重要性与主张

该论文声称将其自适应量子算法从经典吉布斯分布扩展到了通过块编码访问的通用量子哈密顿量。其重要性在于：

1. 消除经典假设： 不同于以往依赖于整数谱或高效能量评估的工作，该方法使用可通过 QSVT 实现的平滑量（TFD 重叠度和重加权），从而避免了分辨单个能级的需求。
2. 海森堡缩放： 它为通用量子哈密顿量实现了最优的 $1/\epsilon$ 缩放，相比之前在精度上的二次方缩放有了显著改进。
3. 更强模型下的最优性： 它证明了相连温度控制是一种真正的资源，能够达到块编码查询的理论下界，而固定温度访问则会带来关于系统规模的多项式惩罚。
4. 实际适用性： 该框架包含了一个完整的流程，从方案生成到端到端的一维系统电路资源估计，展示了理论上的查询优势如何转化为门计数的改进。

作者指出，虽然相干温度模型提供了最优的缩放，但其实现开销并非微不足道。他们提供了一个充分条件（命题 7.1）以及一个针对一维自旋链的具体构造（命题 8.1），表明在这种情况下，额外的开销是可以接受的，从而保留了渐近优势。