Dequantization and Hardness of Spectral Sum Estimation

基于提供的文本，以下是关于论文《谱和估计的去量子化与硬度》（Dequantization and Hardness of Spectral Sum Estimation）的技术摘要详细中文翻译。

问题陈述

本文研究了估计矩阵谱和（spectral sums）的计算复杂度问题。谱和定义为 $\text{tr}[f(A)] = \sum_{i=1}^N f(\lambda_i)$，其中 $\lambda_i$ 是厄米矩阵 $A$ 的特征值。典型的例子包括对数行列式 ($\log \det(A)$)、配分函数 ($\text{tr}[e^{-\beta A}]$)、幂次的迹 ($\text{tr}[A^p]$) 以及逆的迹 ($\text{tr}[A^{-1}]$)。

近期的量子算法已经证明，对于稀疏且良置（well-conditioned）的矩阵，这些量可以在关于维度 $N$ 的多项对数时间内（具体为 $\text{poly}(\log N, s, \kappa, 1/\epsilon)$，其中 $s$ 是稀疏度，$\kappa$ 是条件数）以相对误差 $\epsilon$ 进行近似。本文探讨了两个基本问题：

1. 去量子化（Dequantization）： 这些量子运行参数在多大程度上可以被经典算法复现？
2. 硬度（Hardness）： 当经典复现无法实现时，其背后的复杂度理论障碍是什么？

方法论

作者开发了两种截然不同的经典算法框架，并辅以复杂度理论的下界证明。

1. 经典算法

两种算法都基于这样一个观察：如果多项式 $p(x)$ 在 $A$ 的谱上一致逼近函数 $f(x)$，那么 $f$ 和 $p$ 的归一化谱和也是接近的。核心任务转化为估计矩阵多项式的归一化迹，即 $\frac{1}{2^n}\text{tr}[p(A)]$，这可以表示为对角线元素的期望值：$\mathbb{E}_{i}[p(A)_{ii}]$。

• 确定性稀疏幂运算（针对稀疏矩阵）：

  • 方法： 该算法采样一个随机对角线索引 $i$，并显式枚举所有以 $i$ 为起点和终点的长度至多为 $d$（逼近多项式的阶数）的闭合路径（closed walks）。
  • 机制： 对于 $s$-稀疏矩阵，此类路径的数量受限于 $s^d$。算法通过计算这些路径的加权和来评估 $p(A)_{ii}$。
  • 运行时间： $O^*(s^d \cdot f_{\max}^2 / \epsilon^2)$。
  • 应用： 通过使用切比雪夫截断（Chebyshev truncation）来逼近 $\log(x)$，作者推导出了一个用于 $s$-稀疏且条件数为 $\kappa$ 的矩阵的对数行列式算法。其运行时间为 $O^*(s^{c \cdot \sqrt{\kappa} \log(\kappa/\epsilon)})$。相比于以往与非零元素总数 $\|A\|_0$ 成比例的经典方法（例如 Hutchinson 估计器），这代表了指数级的改进。

• 随机游走估计器（针对局部哈密顿量）：

  • 方法： 该算法使用随机游走取代穷举枚举。从随机索引 $i$ 开始，游走根据与矩阵条目绝对值成正比的概率转移到相邻节点。
  • 机制： 算法维护一个运行权重，利用行 1-范数和复数符号来补偿转移概率。这确保了估计器的无偏性。
  • 优势： 对于具有有界总相互作用强度的 $k$-局部哈密顿量，$1$-范数$|H|_1$被限制在$2^{k/2}$以内，与局部项的数量$m$ 无关。
  • 运行时间： $O^*(2^{kd} \|p\|_1^2 / \epsilon^2)$。这消除了运行时间中指数部分对项数 $m$ 的依赖，使得该算法对于对数局部（log-local）哈密顿量是高效的。

2. 复杂度理论硬度

作者建立了下界，以确定经典算法何时无法达到与量子算法相同的效率。

• DQC1-完备性： 本文证明了对于对数局部哈密顿量，估计归一化谱和（幂次和逆的迹）在反多项式加性精度下是 DQC1-完备 的。这解决了关于 Schatten-$p$ 范数估计的一个开放问题。证明过程采用了电路到哈密顿量的构造（由 Brandão 改编的 Kitaev 构造），表明谱和编码了 DQC1 电路的拒绝概率。
• PP-完备性： 对于非归一化谱和，作者在温和的假设下（多项式可逼近性和非退化性）证明了其 PP-完备性。该归约涉及构造一个对角矩阵，其迹对应于布尔公式的满足赋值数量，从而将问题归约为 MAJSAT。

关键结果

1. 对数行列式的去量子化： 作者提供了一种针对稀疏、良置矩阵的对数行列式经典算法，其运行时间为 $O^*(s^{c \cdot \sqrt{\kappa} \log(\kappa/\epsilon)})$。虽然在所有参数（特别是 $\kappa$ 和 $\epsilon^{-1}$）下并非完全是多项式时间，但与随 $\|A\|_0$ 缩放的经典方法相比，它在维度 $N$ 上实现了指数级改进。
2. 复杂度图谱： 本文绘制了四种谱和（对数行列式、配分函数、幂次的迹、逆的迹）在不同参数机制下的复杂度图谱：
   • 常数参数： 所有问题均属于 BPP（可通过经典随机多项式时间解决）。
   • 对数多项式参数（如 $\kappa, \beta, p$）： 问题允许存在 经典拟多项式时间 算法。
   • 多项式参数： 对于对数局部哈密顿量，这些问题是 DQC1-完备 的，这意味着除非 DQC1 $\subseteq$ BPP，否则不存在高效的经典算法。
   • 反指数精度： 问题变为 PP-完备。
3. 解决开放问题： 本工作通过证明幂次和逆的迹具有 DQC1 硬度，完成了由 Cade 和 Montanaro (2018) 发起的关于这些谱和的复杂度图景。

意义与主张

本文声称其属于“去量子化”量子线性代数算法这一更广泛计划的一部分。其重要性在于：

• 部分去量子化： 证明了对于特定参数机制（特别是稀疏矩阵和局部哈密顿量），经典算法可以保留量子算法所实现的对维度 $N$ 的对数依赖性。
• 识别量子优势： 结果表明，谱和估计中表现出的所谓量子优势，并不在于能够实现更高的估计精度本身，而在于处理随 $n$ 呈多项式增长的谱参数（如条件数 $\kappa$ 或逆温度 $\beta$）的能力。在这些机制下，问题变为 DQC1-完备，且目前尚无已知的有效经典算法。
• 理论完备性： 通过建立幂次和逆的迹的 DQC1-完备性，本文填补了关于 DQC1 模型在谱和方面计算能力的理解空白。

作者指出，尽管其经典算法改进了以往的界限，但并未在所有参数机制下（特别是当 $\kappa$ 或 $\epsilon^{-1}$ 很大时）完全实现对量子算法的去量子化。此外，关于能否在 DQC1 中估计一般稀疏矩阵（而非仅限于对数局部哈密顿量）的归一化谱和，仍是一个开放问题，因为标准的块编码（block-encoding）技术在辅助比特（ancilla）效率方面可能不足以适配 DQC1 模型。