谱和与行列式

很多实际问题要的并不是矩阵的单个 eigenvalue，而是所有 eigenvalue 的某种汇总。举三个例子：

• 统计物理与贝叶斯推断中，配分函数、Gaussian 分布的归一化常数、模型的 log evidence 都归结为 $\log \det A$；
• 量子信息中，密度矩阵 $\rho$ 的 von Neumann 熵 $S(\rho )=-\mathrm{Tr}(\rho \log \rho )$ 衡量态的混合程度；
• 图论中，图的生成树数目、三角形数目都可以写成 Laplacian 或邻接矩阵 eigenvalue 的函数之和。

这些问题有一个统一的抽象形式：给定维数 $D=2^n$ 的 Hermitian matrix $A$（稀疏、或可以 block-encode），以及一个标量函数 $f$，估计谱和 (spectral sum)

$$\mathrm{Tr}f(A)=\sum _{j=1}^{D}f({\lambda }_j),$$

其中 ${\lambda }_1,\dots ,{\lambda }_D$ 是 $A$ 的 eigenvalues（按重数计）。注意我们不要求输出任何 eigenvalue 本身，只要一个标量。这一点至关重要：输出 $D$ 个 eigenvalue 的经典描述显然需要 $\Omega (D)$ 时间，而输出一个数没有这种平凡下界，量子加速的空间正来自这里。

本词条讲两条互补的量子路线。第一条基于一个简单观察：maximally mixed state $I/D$ 在 eigenbasis 中是均匀分布，所以对 $e^{iAt}$ 做 phase estimation 就相当于均匀随机抽取一个 eigenvalue；多次采样后对 $f(\tilde{\lambda })$ 取平均即可。第二条用 QSVT 直接构造 $f(A)$ 的近似 block encoding，再利用 maximally entangled state 把 normalized trace 写成一个 expectation，用 Hadamard test / amplitude estimation 读出。两条路线的思想不同，但共享同一个关键步骤：先把目标归一化为 $\frac{1}{D}\mathrm{Tr}f(A)$。

历史上，determinant 与谱和的量子算法长期被视为”看起来该有加速、但细节很微妙”的典型：早期工作（如 determinant estimation 方向）已经指出相位估计可以抽样 eigenvalue，而系统地把谱和作为一类问题处理、并给出 QSVT 与采样两条路线的复杂度刻画，见文末参考文献中 Luongo 与 Shao 的工作（Zoo 编号 527）；determinant estimation 的最新进展见 Giovannetti、Lloyd 与 Maccone 2025 年的算法（Zoo 编号 528）。本词条的结论与这些文献一致：归一化谱和通常可以有效估计，而未归一化的谱和、行列式的相对精度估计则可能指数昂贵——理解这一分界是本词条的核心目标。

阅读本词条需要相位估计（相位估计（QPE））、振幅放大与振幅估计（振幅放大）、Hamiltonian simulation 与 block encoding / QSVT（量子奇异值变换（QSVT））的基本结论；我们会引用这些结论但不重新推导。

1. 问题定义：先归一化输出尺度

在开始任何算法之前，先做一件看似琐碎、实则决定成败的事：把输出尺度归一化。定义归一化谱和

$$s_f(A)=\frac{1}{D}\mathrm{Tr}f(A)=\frac{1}{D}\sum _{j=1}^{D}f({\lambda }_j)={\mathbb{E}}_{j\sim U[D]}[f({\lambda }_j)],$$

其中 $j\sim U[D]$ 表示从 $\{1,\dots ,D\}$ 中均匀随机取一个指标。最后一个等号只是把”除以 $D$ 的求和”重新解读为”均匀分布下的期望”，但它指明了算法的形状：只要能从特征值的经验分布中采样，$s_f$ 就是一个普通的 Monte Carlo 期望。

量子算法（无论哪条路线）自然输出的是 $s_f$ 的加性 $ϵ$ 近似：

$$|{\hat{s}}_f-s_f(A)|\le ϵ.$$

由此立刻得到未归一化谱和的误差：

$$\left|D{\hat{s}}_f-\mathrm{Tr}f(A)\right|=D\left|{\hat{s}}_f-s_f(A)\right|\le Dϵ.$$

这个 $D$ 倍的放大是本词条一切”难度声明”的根源。两个极端情形：

• 如果我们只想要归一化的 $s_f$（例如 per-dimension 的 log-likelihood、平均能量），加性误差 $ϵ$ 就够了，代价通常关于 $1/ϵ$ 多项式；
• 如果我们想要原谱和的 absolute error $O(1)$（例如精确的整数谱和、或行列式的相对精度），就必须取 $ϵ=O(1/D)$。由于 $D=2^n$，这意味着精度要随比特数指数提高，而本词条所有算法的代价都含 $1/ϵ$（或更差）的因子，于是总代价指数膨胀。

因此，文献中凡声称”superpolynomial speedup in dimension”的结果，对应的几乎都是 normalized/additive promise：估计 $s_f$ 到加性误差，而不是估计 $\mathrm{Tr}f(A)$ 到与维数无关的绝对误差。这不是技术上的偷懒，而是由上面的简单放缩决定的硬性分界。读任何谱和算法的复杂度声明时，第一件事就是确认它用的是哪一种误差约定。

2. 经典基线：对角化与随机迹估计

评价量子算法之前，先弄清经典算法能做到什么，否则”加速”无从谈起。

2.1 精确对角化

最直接的经典方法：对 $A$ 做完整的特征分解，得到全部 ${\lambda }_j$，然后逐个算 $f({\lambda }_j)$ 求和。稠密矩阵的特征分解约需 $O(D^3)$ 时间；如果只需要谱和而不需要特征矢量，也仍然需要 $\Omega (D^2)$ 量级去读取全部矩阵元。当 $D=2^n$ 时，$D^3=8^n$ 关于 $n$ 是指数的——这正是”superpolynomial in dimension”加速的参照物。

但要小心：这个参照物只在 $A$ 以某种紧凑隐式形式给出时才有意义。如果 $A$ 本身就是硬盘上一个 $D\times D$ 的显式数组，那么任何算法（包括量子算法）光读入数据就要 $\Omega (D^2)$，所谓指数加速无从谈起。第 9 节会回到这个输入模型问题。

2.2 Hutchinson 随机迹估计

经典算法并不只有对角化。估计 $\mathrm{Tr}M$（取 $M=f(A)$）有一个著名的随机技巧，通常归于 Hutchinson。取随机矢量 $v\in {\mathbb{R}}^D$，其各分量独立、均值为 $0$、方差为 $1$（例如各分量独立取 $\pm 1$ 各半）。则

$$\mathbb{E}[v^{T}Mv]=\mathbb{E}\left[\sum _{i,k}{v}_i{M}_{ik}{v}_k\right]=\sum _{i,k}{M}_{ik}\mathbb{E}[v_i{v}_k]=\sum _{i,k}{M}_{ik}{\delta }_{ik}=\mathrm{Tr}M,$$

其中第三个等号用了分量独立性：$\mathbb{E}[v_i{v}_k]=\mathbb{E}[v_i]\mathbb{E}[v_k]=0$（$i\ne k$）且 $\mathbb{E}[v_i^2]=1$。所以 $v^{T}Mv$ 是 $\mathrm{Tr}M$ 的无偏估计量，多次采样取平均即可。每次采样只需要一次 matrix-vector product $Mv$，成本为 $O(\mathrm{nnz}(M))$（非零元个数），对稀疏矩阵可以远低于 $D^2$，即 subquadratic。

这个基线告诉我们两件事：

• 经典随机迹估计同样是”采样 + 平均”，和本词条的量子采样路线结构平行；比较时必须计一次 matvec 的真实成本与矩阵稀疏度，而不是笼统地说”经典要 $D^3$”；
• Hutchinson 估计的是 $\mathrm{Tr}M$，且要求能算 $Mv=f(A)v$——对一般的 $f$（如 $\log$、$1/x$），经典计算 $f(A)v$ 本身就要多项式逼近或迭代法，难度同样由谱区间与 condition number 控制。量子路线遇到的 $\kappa$ 依赖并不是量子特有的缺陷。

3. 核心直觉：最大混态是”特征值上的均匀分布”

在进入形式推导前，先用一句话讲清第一条路线的全部思想：

相位估计需要一个输入态；如果输入态在 eigenbasis 里”均匀涂抹”，那么相位估计的输出就是均匀随机的一个 eigenvalue。

回顾相位估计（相位估计（QPE））：对酉算子 $U$ 与输入态 $|\psi ⟩$，若 $|\psi ⟩=|u_j⟩$ 恰是 $U$ 的 eigenvector（$U|u_j⟩=e^{i{\varphi }_j}|u_j⟩$），输出寄存器给出相位 ${\varphi }_j$ 的近似；若 $|\psi ⟩={\sum }_j{c}_j|u_j⟩$ 是叠加态，输出以概率 $|c_j{|}^2$ 给出 ${\varphi }_j$——测量把叠加”坍缩”到某一支，各支的概率由振幅平方决定。

现在的问题是：我们不知道 $A$ 的 eigenvectors，无法制备任何一个 $|u_j⟩$。但我们想要的是均匀抽一个 eigenvalue，而这恰好不需要知道 eigenbasis——取 $U=e^{iAt}$（与 $A$ 共享 eigenvectors，eigenvalue 为 $e^{i{\lambda }_{j}t}$），并把输入态取为 maximally mixed state

$$\frac{I}{D}=\frac{1}{D}\sum _{j=1}^D|u_j⟩⟨u_j|.$$

右边的等号不是近似：$I={\sum }_j|u_j⟩⟨u_j|$ 对任何正交归一基成立（完备性关系），所以 $I/D$ 在 eigenbasis 中就是”以概率 $1/D$ 处于 $|u_j⟩$“的经典混合。对混合态做相位估计，等价于先按混合的概率分布掷骰子选中某个 $|u_j⟩$，再对它做相位估计——于是输出寄存器以概率 $1/D$ 给出 ${\lambda }_j$ 的近似 $\tilde{\lambda }$。均匀性来自单位矩阵的基无关性，这是整条路线唯一”量子”的诀窍；剩下的都是采样统计。

如何制备一个 mixed state？纯态线路无法直接产生混合，标准技巧是纯化 (purification)：制备一对最大纠缠态，丢弃（或等价地，从不触碰）其中一半，剩下的一半就是 maximally mixed state。这就是下一节 Bell pairs 的由来。

第二条路线的直觉同样一句话可以说完：

QSVT 把多项式逼近 $f$ 变成 $A$ 的矩阵函数 $f(A)$ 的 block encoding；而最大纠缠态把”矩阵的归一化迹”变成”一个可测量的期望值”。

即恒等式 $⟨\Phi |(M\otimes I)|\Phi ⟩=\frac{1}{D}\mathrm{Tr}M$：左边是一个量子态上的 expectation，可以用 Hadamard test 或振幅估计读出；右边正是我们想要的 $s_f$（取 $M=f(A)$）。第 5 节会证明这个恒等式并补全细节。

4. 路线一：最大混态采样 + 相位估计

4.1 Bell 态制备与约化态

取两个各含 $n$ 个 qubit 的寄存器（每个寄存器维数 $D=2^n$），制备 $n$ 对 Bell pairs，即

$$|\Phi ⟩=\frac{1}{\sqrt{D}}\sum _{x=0}^{D-1}|x⟩|x⟩.$$

制备线路是标准的：对每对 qubit 先加 Hadamard 再用 CNOT，$n$ 对并行共 $O(n)$ 个门。

我们只对第一个寄存器施加后续操作（相位估计），第二个寄存器全程闲置。形式上，第一个寄存器的状态由约化密度矩阵描述。计算偏迹：

$${\mathrm{Tr}}_2(|\Phi ⟩⟨\Phi |)={\mathrm{Tr}}_2(\frac{1}{D}\sum _{x,y}|x⟩⟨y|\otimes |x⟩⟨y|)=\frac{1}{D}\sum _{x,y}|x⟩⟨y|\cdot \mathrm{Tr}(|x⟩⟨y|)=\frac{1}{D}\sum _{x,y}|x⟩⟨y|{\delta }_{xy}=\frac{I}{D},$$

其中第三个等号用了 $\mathrm{Tr}(|x⟩⟨y|)=⟨y|x⟩={\delta }_{xy}$。再由完备性关系（取 $A$ 的 eigenbasis $\{|u_j⟩\}$，谱分解 $A={\sum }_j{\lambda }_j|u_j⟩⟨u_j|$）：

$$\frac{I}{D}=\frac{1}{D}\sum _{j=1}^D|u_j⟩⟨u_j|.$$

所以”制备 $|\Phi ⟩$、只对一半动手”与”以概率 $1/D$ 随机制备某个 $|u_j⟩$“在一切测量统计上不可区分——尽管我们完全不知道 $|u_j⟩$ 是什么。

4.2 相位估计输出均匀随机特征值

对第一个寄存器执行以 $U=e^{iAt}$ 为目标酉算子的相位估计（受控的 $U^{2^k}$ 由 Hamiltonian simulation 实现，见 Trotterization）。由于

$$U|u_j⟩=e^{i{\lambda }_{j}t}|u_j⟩,$$

当第一个寄存器处于 $|u_j⟩$ 时，相位估计输出 ${\lambda }_{j}t$（进而 ${\lambda }_j$）的近似 $\tilde{\lambda }$；而第 4.1 节说明输入等效于以概率 $1/D$ 取 $|u_j⟩$。合起来：

$$\mathrm{Pr}[\text{输出}\approx {\lambda }_j]=\frac{1}{D},j=1,\dots ,D,$$

其中 eigenvalue 按重数计（$k$ 重 eigenvalue 被抽中的概率是 $k/D$，因为它在求和 ${\sum }_j|u_j⟩⟨u_j|$ 中出现 $k$ 次）。这正是第 1 节里 $j\sim U[D]$ 的分布。每次实验还顺带消耗 $n$ 对 Bell pairs 与一次相位估计；重复 $M$ 次得到独立样本 ${\tilde{\lambda }}_1,\dots ,{\tilde{\lambda }}_M$，定义估计量

$${\hat{s}}_f=\frac{1}{M}\sum _{r=1}^{M}f({\tilde{\lambda }}_r).$$

若相位估计完全精确（${\tilde{\lambda }}_r={\lambda }_{j_r}$），则每个 $f({\tilde{\lambda }}_r)$ 的期望恰为

$$\mathbb{E}[f(\tilde{\lambda })]=\sum _{j=1}^D\frac{1}{D}f({\lambda }_j)=s_f(A),$$

即估计量无偏。相位估计的分辨率误差会让每个样本的值略有偏移，第 4.5 节处理这部分偏差。

4.3 从采样到估计：样本复杂度

设 $f$ 在谱区间上有界：$|f(x)|\le B$。每个样本 $f({\tilde{\lambda }}_r)$ 是取值于 $[-B,B]$（区间宽度 $2B$）的独立随机变量，均值为 $s_f$。用 Hoeffding 不等式（$M$ 个独立有界变量的均值偏离期望的概率界）：

$$\mathrm{Pr}[|{\hat{s}}_f-s_f|\ge ϵ]\le 2\exp (-\frac{M{ϵ}^2}{2B^2}).$$

要求右端不超过常数（如 $1/3$），解出

$$M=O\left(\frac{B^2}{{ϵ}^2}\right).$$

逐项解释这个表达式：因子 $B^2$ 来自单次样本的（最坏情形）方差量级——样本散布在宽度 $2B$ 的区间里，方差至多与 $B^2$ 同阶；因子 $1/{ϵ}^2$ 是 Monte Carlo 平均的标志：$M$ 个独立样本的标准差按 $1/\sqrt{M}$ 收缩，要把标准差压到 $ϵ$ 就需要 $M\sim 1/{ϵ}^2$。

4.4 用振幅估计做二次加速

$1/{ϵ}^2$ 是经典采样的极限，但量子算法可以把”对采样结果取平均”这一步也相干化，用振幅估计把对 $ϵ$ 的依赖改进为 $1/ϵ$（这正是 Grover 型二次加速在估计问题上的版本，见 振幅放大）。

构造分两步。第一步，把 $f$ 相干地算进振幅。为简单起见先设 $0\le f(x)\le B$（一般情形可把 $f$ 拆成正负两部分分别处理，或平移缩放后处理）。在相位估计输出 $\tilde{\lambda }$ 之后，附加一个辅助 qubit，执行受控旋转

$$|\tilde{\lambda }⟩|0⟩⟼|\tilde{\lambda }⟩(\sqrt{\frac{f(\tilde{\lambda })}{B}}|1⟩+\sqrt{1-\frac{f(\tilde{\lambda })}{B}}|0⟩),$$

即把 $\arcsin \sqrt{f(\tilde{\lambda })/B}$ 的角度转进振幅（$f$ 本身若是可有效计算的函数，这一步是标准的相干算术；若 $f$ 只能以 oracle 形式给出，则计入一次 $f$ 的查询）。对整个叠加态而言，辅助位测得 $|1⟩$ 的概率是

$$p=\sum _{j=1}^D\frac{1}{D}\cdot \frac{f({\lambda }_j)}{B}=\frac{s_f(A)}{B}.$$

第二步，对”辅助位为 $1$“这一事件做振幅估计：以 $Q$ 次调用（每次调用含一次相位估计与一次受控旋转）把 $p$ 估到加性误差 $O(1/Q)$。于是 $s_f=Bp$ 的误差为 $O(B/Q)$，要求其不超过 $ϵ$ 得

$$Q=O\left(\frac{B}{ϵ}\right).$$

对比第 4.3 节的 $M=O(B^2/{ϵ}^2)$：对 $ϵ$ 的依赖从平方改进为线性，这是振幅估计带来的标准二次增益；代价是每次调用的线路更深（需要相干地控制整个”采样 + 求值”过程，不能简单地测量后重来）。

4.5 相位分辨率与总成本

采样路线还有一笔账：相位估计本身的有限分辨率。设相位估计把每个 eigenvalue 定到误差 $\delta$ 以内（$|\tilde{\lambda }-\lambda |\le \delta$）。为了让函数值的偏移不破坏总精度，需要

$$|f(\lambda )-f(\tilde{\lambda })|\le O(ϵ).$$

若 $f$ 在谱区间上 $L$-Lipschitz（$|f(x)-f(y)|\le L|x-y|$），取 $\delta =O(ϵ/L)$ 即可。而相位估计要把相位定到 $\delta$，需要演化时间 $t=\Omega (1/\delta )=\Omega (L/ϵ)$——相位估计中受控 $U^{2^k}$ 的最大幂次反比于分辨率，这是其标准性质。

于是每次”采样”的成本 = Bell 态制备 $O(n)$ + Hamiltonian simulation $e^{iAt}$ 的成本。对 $s$-sparse 的 $A$，后者的代价随稀疏度 $s$、演化时间 $t$ 与 simulation 精度增长（具体依赖所用 simulation 算法，见 Trotterization）。总成本为

$$\underset{\text{振幅估计调用数}}{\underbrace{O\left(\frac{B}{ϵ}\right)}}\times \underset{\text{单次相位估计}}{\underbrace{(\text{simulation 成本：}s,t=O(L/ϵ)\text{的函数})}}.$$

注意分辨率要求 $|f(\lambda )-f(\tilde{\lambda })|\le O(ϵ)$ 把 $f$ 的光滑性 $L$ 也带进了复杂度：**$f$ 越陡（如 $1/x$ 在 $x$ 小时），$L$ 越大，需要的相位分辨率越高，演化时间越长。**这与下一节 QSVT 路线中”多项式次数随奇异性增长”是同一个困难的不同表现形式。

5. 路线二：QSVT + 最大纠缠恒等式

采样路线把谱和化为 Monte Carlo 期望；本节路线更”直接”：先构造矩阵函数 $f(A)$ 本身（的 block encoding），再测量它的归一化迹。

5.1 Block encoding 与多项式逼近

设已有 $A/\alpha$ 的 block encoding（$\alpha \ge \Vert A\Vert$ 是归一化因子；block encoding 的构造见 块编码（Block Encoding））。QSVT 的基本结论是：给定在区间 $[-1,1]$ 上逼近某个目标函数的奇/偶多项式 $p$，可以把 $p(A/\alpha )$ 实现为新的 block encoding，调用次数正比于多项式次数 $\mathrm{deg}p$（结论的精确表述与证明见 量子奇异值变换（QSVT），此处直接使用）。

要估计 $s_f$，取目标函数为 $f(\alpha x)/B$（自变量 $\alpha x$ 把 $A/\alpha$ 的谱映回 $A$ 的谱区间；除以 $B$ 把值域压进 $[-1,1]$，这是 QSVT 对多项式的硬性要求）。选多项式 $p$ 在谱区间上一致逼近：

$$\underset{x\in \text{谱区间}}{\max }|p(x)-\frac{f(\alpha x)}{B}|\le {ϵ}^{\prime },$$

QSVT 即给出 $f(A)/B$ 的近似 block encoding $\tilde{U}$，其 block $\tilde{M}$ 满足 $\Vert \tilde{M}-f(A)/B\Vert \le {ϵ}^{\prime }$（逼近误差从逐点函数值传递到算子范数，因为 QSVT 在 eigenbasis 中逐 eigenvalue 地作用多项式）。

多项式次数从哪来？ 三条：$f$ 的光滑性（越光滑次数越低；在奇点附近，如 $1/x$、$\log x$ 在 $x\to 0$ 处，次数随奇点的靠近程度——即 condition number $\kappa$——增长）、谱区间的长度与位置、以及逼近误差 ${ϵ}^{\prime }$。对光滑且谱区间远离奇点的 $f$（如多项式 $x^p$），次数是常数或很低；对 $1/x$、$\log x$ 这类在 $0$ 附近奇异、而谱被 promise 在 $[1/\kappa ,1]$ 内的函数，次数随 $\kappa$ 增大而增大、随 $1/{ϵ}^{\prime }$ 增长——这就是”对 singularity 附近的 $1/x,\log x$ 复杂度含 condition number”的准确含义。本词条只用这一定性事实，具体次数界见 QSVT 文献。

5.2 最大纠缠恒等式

有了 $f(A)/B$ 的 block，如何读出它的迹？关键是一个恒等式。

Lemma 1（最大纠缠恒等式）. 设 $|\Phi ⟩=\frac{1}{\sqrt{D}}{\sum }_{x=0}^{D-1}|x⟩|x⟩$ 为两个 $D$ 维寄存器间的最大纠缠态，$M$ 为任意 $D\times D$ 矩阵。则

$$⟨\Phi |(M\otimes I)|\Phi ⟩=\frac{1}{D}\mathrm{Tr}M.$$

证明。直接展开：

$$⟨\Phi |(M\otimes I)|\Phi ⟩=\frac{1}{D}\sum _{x,y}(⟨y|\otimes ⟨y|)(M|x⟩\otimes |x⟩)=\frac{1}{D}\sum _{x,y}⟨y|M|x⟩⟨y|x⟩.$$

由 $⟨y|x⟩={\delta }_{xy}$，双重求和坍缩为对角项：

$$\frac{1}{D}\sum _{x,y}⟨y|M|x⟩{\delta }_{xy}=\frac{1}{D}\sum _x⟨x|M|x⟩=\frac{1}{D}\mathrm{Tr}M,$$

最后一步是迹的定义（对任意正交归一基求对角元之和）。Q.E.D.

值得同时记住一个伴生恒等式（习题 1）：$(M\otimes I)|\Phi ⟩=(I\otimes M^T)|\Phi ⟩$——算子可以在最大纠缠态的两半之间”转移”，代价是取转置。它说明最大纠缠态把两个寄存器紧密锁定，是这类恒等式成立的结构性原因。

取 $M=f(A)$，恒等式给出

$$⟨\Phi |(f(A)\otimes I)|\Phi ⟩=\frac{1}{D}\mathrm{Tr}f(A)=s_f(A),$$

即 normalized trace 被精确地写成了一个纯态 expectation。

5.3 期望值读出

剩下的问题是：给定 $\tilde{M}\approx f(A)/B$ 的 block encoding，如何估计 $⟨\Phi |(\tilde{M}\otimes I)|\Phi ⟩$？

• 相干 Hadamard test + 经典平均：用受控的 block encoding 与辅助位干涉，把 $\mathrm{Re}⟨\Phi |(\tilde{M}\otimes I)|\Phi ⟩$ 编成辅助位的测量概率（$M=f(A)$ Hermitian，期望值是实数，只需实部）；每次实验是独立样本，$O(B^2/{ϵ}^2)$ 次重复把 $s_f$ 估到 $ϵ$（与第 4.3 节同样的 Hoeffding 分析，注意被估的量是 $s_f/B$，乘以 $B$ 还原）。
• 振幅估计：把 Hadamard test 的概率估计相干化，$O(B/ϵ)$ 次调用，与第 4.4 节同样获得二次加速。

两种读出的 $B/ϵ$（或 $B^2/{ϵ}^2$）因子与采样路线一致；差别在于单次调用的成本：采样路线是”演化时间 $t=O(L/ϵ)$ 的 Hamiltonian simulation”，QSVT 路线是”$O(\mathrm{deg}p)$ 次 block encoding 调用”。哪条更省取决于 $f$ 与输入模型：$f$ 光滑、谱区间友好时 QSVT 的多项式次数低，且不需要高精度相位估计；反之若已有高效的 $e^{iAt}$ simulation，采样路线常常更直接。

6. 应用一：对数行列式

6.1 从 log det 到谱和

设 $A$ 正定（PSD 且可逆），eigenvalues ${\lambda }_j>0$。行列式是 eigenvalues 之积，取对数把积变和：

$$\log \det A=\log \prod _{j=1}^D{\lambda }_j=\sum _{j=1}^D\log {\lambda }_j=\mathrm{Tr}\log A=D{s}_{\log }(A),$$

其中 $\log A$ 是矩阵函数（在 eigenbasis 中对每个 eigenvalue 取 $\log$），第三个等号是迹在 eigenbasis 中的展开。于是 log-determinant 是 $f=\log$ 的谱和，本词条的两条路线都适用。

先 rescale：把 $A$ 换成 $A/\Vert A\Vert$（以下仍记为 $A$），使谱落在

$$\mathrm{spec}(A)\subseteq [1/\kappa ,1],$$

其中 $\kappa$ 是（rescale 后的）condition number。rescale 只贡献一个可解析加回的常数：$\log \det (cA)=\log \det A+D\log c$。在 $[1/\kappa ,1]$ 上，$|\log x|\le \log \kappa$，所以取 $B=\log \kappa$；同时 $\log x$ 在区间左端点附近越来越陡（$(\log x{)}^{\prime }=1/x\le \kappa$），多项式逼近次数与相位分辨率要求都随 $\kappa$ 增长——即复杂度含 $\kappa$ 或 $\log \kappa$ 与到端点的距离，与第 4.5、5.1 节的一般讨论一致。

6.2 误差传播：为什么相对精度难

假设我们把 per-dimension log-determinant

$$\ell =\frac{1}{D}\log \det A$$

估到加性误差 $ϵ$：$|\hat{\ell }-\ell |\le ϵ$。还原成行列式：

$$\log \det A=D\ell ,\hat{\det }=e^{D\hat{\ell }}=e^{D\ell \pm Dϵ}=\det A\cdot e^{\pm Dϵ}.$$

也就是说，$\ell$ 的加性误差 $ϵ$ 经过 $D$ 倍放大再取指数，变成行列式的乘性因子 $e^{\pm Dϵ}$——这不是一个小扰动。若要行列式的 $(1\pm \eta )$ 相对精度，需要 $e^{Dϵ}\le 1+\eta$，即 $Dϵ\lesssim \eta$，也就是

$$ϵ=O\left(\frac{\eta }{D}\right)⟺\text{logdet 的 absolute error }O(\eta ),\text{normalized error }O(\eta /D).$$

归一化误差要与 $D=2^n$ 成反比，而算法代价含 $1/ϵ$ 因子，于是总代价指数增长——行列式的相对精度估计是指数难的（在本词条框架下）。这个结论与第 1 节的一般性观察一致：困难不在 $\log$ 这个函数，而在”还原成未归一化量”这一步。

反过来说，实践中很多时候我们直接要的就是 $\ell$ 本身：高维 Gaussian 的 log-likelihood、贝叶斯模型比较中的 log evidence、统计物理中每格点的自由能，天然都是 per-dimension 量。对这些应用，加性 $ϵ$ 的 $\hat{\ell }$ 就是有用的输出，量子算法多项式可得。讨论 logdet 量子加速时，先确认应用需要的是哪一种量，比纠结复杂度表达式更重要。

6.3 一个可手算的小例子

取 $D=2$，$A=\mathrm{diag}(1,\frac{1}{2})$（已经满足 $\mathrm{spec}(A)\subseteq [1/2,1]$，$\kappa =2$）。

• eigenvalues：${\lambda }_1=1$，${\lambda }_2=1/2$；
• $\log \det A=\log 1+\log \frac{1}{2}=0-\ln 2=-\ln 2\approx -0.693$；
• 归一化量 $\ell =s_{\log }(A)=\frac{1}{2}(-\ln 2)=-\frac{\ln 2}{2}\approx -0.347$。

检验误差传播：设 $\hat{\ell }=\ell +ϵ$，取 $ϵ=0.1$。则

$$e^{D\hat{\ell }}=e^{2(-\frac{\ln 2}{2}+0.1)}=e^{-\ln 2+0.2}=\frac{1}{2}\cdot e^{0.2}\approx 0.5\times 1.221=0.611,$$

而真值 $\det A=0.5$，乘性偏差 $e^{Dϵ}=e^{0.2}\approx 1.22$——归一化误差只有 $0.1$，行列式却已偏离 $22\%$。把 $D$ 换成 $2^{20}$，同样的 $ϵ=0.1$ 会变成 $e^{10^5}$ 量级的荒谬因子。这个玩具例子已经把第 6.2 节的机制演示完整了。

再验证采样路线在这个例子上的行为：maximally mixed state $I/2$ 以各 $1/2$ 概率抽到 ${\lambda }_1,{\lambda }_2$；样本 $f(\tilde{\lambda })$ 等概率取 $0$ 与 $-\ln 2$，均值 $-\frac{\ln 2}{2}=\ell$，与理论一致。

6.4 非 PSD 情形

以上都假设 $A$ 正定。对一般（非 PSD）矩阵，行列式可以是负数甚至复数：$\det A={\prod }_j{\lambda }_j$ 含符号或复相位，而 $\mathrm{Tr}\log A$ 涉及分支切割，不能直接套用。处理办法是把问题拆开：用 singular values（即对 $|A|=\sqrt{A^{†}A}$ 这个 PSD 矩阵估计 $\log \det |A|=\frac{1}{2}\log \det (A^{†}A)$）得到 $|\det A|$；符号或相位部分（如实矩阵负 eigenvalue 的个数的奇偶性）需要另行估计。本词条的基本表述以 PSD 为主，非 PSD 的推广保留这一拆分结构。

7. 应用二：熵、Schatten 范数与逆迹

von Neumann 熵。 对密度矩阵 $\rho$（PSD、迹为 1），

$$S(\rho )=-\mathrm{Tr}(\rho \log \rho )=-\sum _j{\lambda }_j\log {\lambda }_j,$$

即 $f(x)=-x\log x$ 的谱和（差一个符号）。注意 $f(x)=-x\log x$ 在 $[0,1]$ 上有界（最大值 $1/e$ 在 $x=1/e$ 处），所以采样路线直接用 maximally mixed 输入、对抽出的 $\tilde{\lambda }$ 计算 $-\tilde{\lambda }\log \tilde{\lambda }$ 取平均即可，$B=1/e$ 是常数。真正的麻烦在小 eigenvalues：$x\log x$ 在 $x=0$ 处导数发散（不是 Lipschitz 的），多项式逼近在 $0$ 附近次数膨胀，相位分辨率要求也失控。标准处理是引入 cutoff $\delta$（把 $\lambda <\delta$ 的项截断，其对熵的总贡献可用秩的 promise 控制）或直接假设秩 $r\ll D$ 且非零 eigenvalues 有下界。这是一个 promise 依赖的结果：没有对谱下端的假设，熵的加性估计没有统一的高效保证。

Schatten $p$-范数。

$$\Vert A{\Vert }_p^p=\mathrm{Tr}|A{|}^p=\sum _j{\sigma }_j^p,$$

其中 ${\sigma }_j$ 是 singular values。$f(x)=x^p$ 在 $[0,1]$ 上光滑有界，对整数 $p$ 它本身就是 $p$ 次多项式——QSVT 路线此时没有逼近误差，次数就是 $p$。$p=2$ 即 Frobenius 范数平方 $\Vert A{\Vert }_F^2=\mathrm{Tr}(A^{†}A)$，是最简单的非平凡谱和。

逆迹。

$$\mathrm{Tr}{A}^{-1}=\sum _j\frac{1}{{\lambda }_j},$$

$f(x)=1/x$ 在 $0$ 处奇异；若 $\mathrm{spec}(A)\subseteq [1/\kappa ,1]$，则 $B=\kappa$、Lipschitz 常数 $L={\kappa }^2$、多项式次数随 $\kappa$ 增长——复杂度被 condition number 全面控制。这与 HHL 类线性求解器的 $\kappa$ 依赖同源（HHL 算法）。

这三个例子共享一个信息：谱和问题的难度由 $f$ 在谱区间端点附近的行为决定——光滑有界的 $f$（$x^p$、$x\log x$ 的体部）容易，端点奇异或发散的 $f$（$1/x$、$\log x$、$x\log x$ 在 $0$ 处）需要 condition number / cutoff / rank 等 promise 来控制。effective resistance（有效电阻，涉及 Laplacian 伪逆的迹）、Gaussian covariance 归一化常数、Bayesian log evidence 等应用量都可以归约到上述谱和，因而继承同样的 promise 结构。

8. 应用三：图谱中的谱和

8.1 生成树计数与 matrix-tree theorem

设 $G$ 为 $n$ 个顶点的连通图（此处 $n$ 是顶点数，别与前面的 qubit 数混淆），$L$ 为其 Laplacian。$L$ 总有一个 eigenvalue $0$，对应的 eigenvector 是 $1$（全一向量）；记非零 eigenvalues 为 ${\lambda }_2,\dots ,{\lambda }_n$。Matrix-tree theorem 给出图的生成树数目

$$\tau (G)=\frac{1}{n}\prod _{j=2}^n{\lambda }_j.$$

取对数：

$$\log \tau (G)=\sum _{j=2}^n\log {\lambda }_j-\log n.$$

右端的和是 $\log$ 的谱和，但有一个技术性障碍：必须把 zero eigenvalue 排除在外（$\log 0$ 发散）。两个办法：把问题投影到 $1^{\perp }$ 子空间上（在受控操作中以 $1$ 为标记做排除），或把 $L$ regularize 成 $L+\delta I$ 之类的可逆矩阵再修正。无论哪种，复杂度都含 $1/{\lambda }_2$（谱隙的倒数，充当 condition number 的角色）——谱隙越小的图越难。

小例子：取三角形图 $K_3$（3 个顶点两两相连）。其 Laplacian

$$L=\left(\begin{array}{ccc}2& -1& -1\\ -1& 2& -1\\ -1& -1& 2\end{array}\right)$$

的 eigenvalues 为 $0,3,3$（$1$ 张成零空间；在 $1^{\perp }$ 上 $L=3I$，因为 $L=3I-11^T$，而 $11^T$ 在 $1^{\perp }$ 上为零）。代入 matrix-tree theorem：

$$\tau (K_3)=\frac{1}{3}\cdot 3\cdot 3=3,$$

与直接枚举一致（$K_3$ 的生成树恰是删掉任意一条边，共 3 棵）。进而 $\log \tau (K_3)=\log 3+\log 3-\log 3=\log 3$，公式自洽。

8.2 三角形计数

图的三角形数目是另一个多项式谱和：邻接矩阵 $A_G$ 的三次幂的迹数的是长度为 3 的闭 walk，而每个三角形贡献 6 条（3 个起点 × 2 个方向），故

$$\#△=\frac{\mathrm{Tr}(A_G^3)}{6}.$$

这是 $f(x)=x^3$ 的谱和（对 QSVT 路线是精确的次数-3 多项式，无逼近误差），本身很容易估计到加性精度。真正的困难在另一端：$\#△$ 本身可能很小（甚至为 0 或 1），此时有意义的是相对精度，而由第 1 节的分析，相对精度要求绝对误差 $O(\#△)$，归一化误差再除以 $D$，代价随目标量的缩小而上升。这与 Grover 计数中”目标越少越难”的现象完全同构：谱和算法高效估计的是归一化的量，稀有结构仍需额外精度。

9. 什么时候真有量子优势：输入模型与总账

把两条路线的成本放在一起，并补上最容易被忽略的一笔——输入读取。

若 $A$ 以显式的 $D\times D$ 稠密数组给出，那么把它加载进量子 oracle / QRAM 的成本本身就可能与经典直接计算同阶甚至指数于 $n$；此时谈论”指数加速”没有意义。可信的加速场景包括：

• $A$ 由 local rule / sparse oracle 隐式定义（如图的邻接关系、局部 Hamiltonian），每次查询只花 $\mathrm{poly}(n)$；
• block encoding 来自已有的量子过程（例如 $A$ 是某个量子线路天然实现的算子、$\rho$ 是某个线路输出的密度矩阵），根本没有”经典读出”这一步；
• 应用只需要 normalized scalar（如 per-dimension 的 $\ell$），而非未归一化的谱和或相对精度；
• 谱有 condition / gap promise（$\kappa$、${\lambda }_2$、rank 等有界），端点奇异性受控。

经典一侧的账也要记清楚：Hutchinson 类随机迹估计（第 2.2 节）用随机矢量与 matrix-vector products，每次采样只花 $O(\mathrm{nnz})$，总成本可以 subquadratic 于 $D$。因此公平比较的单位是一次 matvec / 一次 oracle 查询的成本与稀疏度，而不是笼统地拿量子算法对比经典对角化的 $D^3$。量子的结构性优势在两点：其一，采样的是 eigenvalue 分布本身（一次相位估计同时”对角化并抽样”），而 Hutchinson 估计的是 $\mathrm{Tr}M$，对一般 $f$ 还需先经典地逼近 $f(A)v$；其二，振幅估计把 Monte Carlo 的 $1/{ϵ}^2$ 降为 $1/ϵ$。这两点是否转化为端到端加速，取决于上面列出的输入模型与 promise。

10. 小结与习题

小结：

• 谱和 $\mathrm{Tr}f(A)$ 的统一处理分两步：先归一化为 $s_f=\frac{1}{D}\mathrm{Tr}f(A)={\mathbb{E}}_{j\sim U[D]}[f({\lambda }_j)]$，再选择采样或 QSVT 路线估计；还原到未归一化量时误差放大 $D$ 倍，故”superpolynomial in dimension”的加速对应 normalized/additive promise。
• Maximally mixed state $I/D$ 在 eigenbasis 中均匀（完备性关系），对它做 phase estimation 即以 $1/D$ 概率抽出每个 eigenvalue（按重数）；Monte Carlo 平均需 $O(B^2/{ϵ}^2)$ 个样本，振幅估计改进为 $O(B/ϵ)$ 次调用，相位分辨率需满足 $|f(\lambda )-f(\tilde{\lambda })|\le O(ϵ)$。
• QSVT 用次数由光滑性/谱区间/逼近误差决定的多项式构造 $f(A)/B$ 的 block，最大纠缠恒等式 $⟨\Phi |(f(A)\otimes I)|\Phi ⟩=\frac{1}{D}\mathrm{Tr}f(A)$ 把 normalized trace 变成可读出的 expectation。
• Log-determinant、entropy、inverse trace、Schatten norms 都是特例；难度由谱区间端点处的奇异性控制（condition number、cutoff、rank promise），这些保留条件不是技术细节而是复杂度声明的一部分。
• 行列式的相对精度、未归一化的整数谱和、稀有结构（如极少的三角形）需要随 $D$ 缩小的归一化误差，可能指数昂贵；per-dimension 的量（如 $\ell =\frac{1}{D}\log \det A$）才是量子算法高效输出的自然对象。

习题（难度大致递增）：

1. 证明伴生恒等式 $(M\otimes I)|\Phi ⟩=(I\otimes M^T)|\Phi ⟩$，并用它重新证明 Lemma 1。（提示：两边都在基 $|x⟩|y⟩$ 上展开比较系数。）
2. 对 $A=\mathrm{diag}(1,\frac{1}{2})$（$D=2$）：（a）计算 $\log \det A$ 与 $\ell =\frac{1}{D}\log \det A$；（b）设 $\hat{\ell }$ 有加性误差 $ϵ=0.05$，计算行列式估计的乘性偏差 $e^{\pm Dϵ}$；（c）$ϵ$ 要取多小，才能保证行列式的相对误差在 $1\%$ 以内？
3. 设 $v\in {\mathbb{R}}^D$ 的各分量独立取 $\pm 1$ 各半。（a）证明 $\mathbb{E}[v^{T}Mv]=\mathrm{Tr}M$；（b）证明方差 $\mathrm{Var}(v^{T}Mv)={\sum }_{i\ne k}{M}_{ik}^2+2{\sum }_i{M}_{ii}^2-\text{（对角修正项）}$ 的量级由 $\Vert M{\Vert }_F^2$ 控制，并据此说明 Hutchinson 估计 $\mathrm{Tr}M$ 的样本复杂度为何含 $\Vert M{\Vert }_F^2/{\text{（目标误差）}}^2$。
4. 由 matrix-tree theorem 推导 $\log \tau (G)={\sum }_{j=2}^n\log {\lambda }_j-\log n$，并对 $4$ 个顶点的完全图 $K_4$（Laplacian 的非零 eigenvalues 全为 $4$）验证 $\tau (K_4)=16$。
5. 比较两条路线的”每次采样成本”：设 $A$ 为 $s$-sparse、$\mathrm{spec}(A)\subseteq [1/\kappa ,1]$、$f=\log$。（a）采样路线中，$f$ 的 Lipschitz 常数是多少？相位分辨率 $\delta$ 与演化时间 $t$ 应如何取？（b）QSVT 路线中，多项式需要在哪个区间上以什么精度逼近什么函数？（c）定性讨论：哪些情形下你预期 QSVT 路线占优，哪些情形下采样路线占优？
6. （开放）第 8.2 节指出三角形计数的困难在相对精度。设图有 $T$ 个三角形，要把 $T$ 估到 $(1\pm \eta )$ 相对精度：用第 1 节的框架写出所需的归一化误差 $ϵ$，并说明为什么 $T$ 很小时任何”先归一化再还原”的路线都会失效。经典算法如何绕开这一困难（例如直接抽样边或顶点）？这对你评价量子加速有何启示？

参考文献

• Zoo 编号 527：Luongo 与 Shao, Quantum Algorithms for Spectral Sums.
• Zoo 编号 528：Giovannetti、Lloyd 与 Maccone 关于 determinant estimation 的 2025 算法。

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch15-learning-spectral/spectral-sums
• 内容遵循 CC BY-NC-SA 4.0 许可协议