# 谱和与行列式：Maximally Mixed Phase Estimation 与 QSVT Trace Estimation

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

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

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

$$
\operatorname{Tr}f(A)=\sum_{j=1}^Df(\lambda_j),
$$

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

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

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

阅读本文需要相位估计（[ch03](../ch03-algo-basics/phase-estimation.md)）、振幅放大与振幅估计（[ch03](../ch03-algo-basics/amplitude-amplification.md)）、Hamiltonian simulation 与 block encoding / QSVT（[ch05](../ch05-hamiltonian-qsp/qsvt-tutorial.md)）的基本结论；我们会引用这些结论但不重新推导。

:::{admonition} 本课知识点
:class: tip

1. **[归一化谱和与误差放大](#normalized-spectral-sum)**——能把 $\operatorname{Tr}f(A)$ 改写成 $s_f=\mathbb E_{j\sim U[D]}[f(\lambda_j)]$，并推导未归一化谱和的误差被放大 $D$ 倍。
2. **[经典基线：对角化与随机迹估计](#classical-baseline-spectral-sums)**——能比较 $O(D^3)$ 对角化与 Hutchinson 迹估计的成本，并证明 $v^TMv$ 是 $\operatorname{Tr}M$ 的无偏估计。
3. **[最大混态采样：均匀性与纯化](#maximally-mixed-sampling)**——能解释 $I/D$ 为何在任意 eigenbasis 中均匀、由 Bell 态偏迹得到 $I/D$，并写出相位估计输出各特征值的概率。
4. **[样本复杂度与振幅估计](#sampling-complexity)**——能用 Hoeffding 不等式推出 $M=O(B^2/\epsilon^2)$，说明振幅估计如何改进为 $O(B/\epsilon)$，并把相位分辨率要求计入总成本。
5. **[QSVT 路线与最大纠缠恒等式](#qsvt-entangled-identity)**——能写出 QSVT 所需的多项式逼近目标，证明 $\langle\Phi|(M\otimes I)|\Phi\rangle=\frac1D\operatorname{Tr}M$，并比较两种期望值读出方式。
6. **[对数行列式与相对精度](#logdet-application)**——能把 $\log\det A$ 化为 $f=\log$ 的谱和，推导加性误差 $\epsilon$ 产生乘性偏差 $e^{\pm D\epsilon}$，并手算 $D=2$ 的例子。
7. **[谱和应用：熵、范数、逆迹与图谱](#spectral-sum-applications)**——能写出熵、Schatten 范数与逆迹对应的函数 $f$ 及其界 $B$，并用 matrix-tree 定理计算生成树数目。
8. **[量子优势的条件：输入模型与总账](#quantum-advantage-conditions-spectral-sums)**——能列出可信加速所需的输入模型与 promise 条件，并说明与经典随机迹估计比较时哪些成本必须计入。

:::

(normalized-spectral-sum)=
## 1. 问题定义：先归一化输出尺度

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

$$
s_f(A)=\frac1D\operatorname{Tr}f(A)
=\frac1D\sum_{j=1}^D f(\lambda_j)
=\mathbb E_{j\sim U[D]}\,[f(\lambda_j)],
$$

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

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

$$
|\widehat s_f-s_f(A)|\le \epsilon.
$$

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

$$
\left|D\,\widehat s_f-\operatorname{Tr}f(A)\right|
=D\left|\widehat s_f-s_f(A)\right|
\le D\epsilon.
$$

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

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

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

(classical-baseline-spectral-sums)=
## 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 随机迹估计

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

$$
\mathbb E[v^T M v]
=\mathbb E\Big[\sum_{i,k}v_i M_{ik} v_k\Big]
=\sum_{i,k}M_{ik}\,\mathbb E[v_i v_k]
=\sum_{i,k}M_{ik}\,\delta_{ik}
=\operatorname{Tr}M,
$$

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

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

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

(maximally-mixed-sampling)=
## 3. 核心直觉：最大混态是"特征值上的均匀分布"

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

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

回顾相位估计（[ch03](../ch03-algo-basics/phase-estimation.md)）：对酉算子 $U$ 与输入态 $|\psi\rangle$，若 $|\psi\rangle=|u_j\rangle$ 恰是 $U$ 的 eigenvector（$U|u_j\rangle=e^{i\phi_j}|u_j\rangle$），输出寄存器给出相位 $\phi_j$ 的近似；若 $|\psi\rangle=\sum_j c_j|u_j\rangle$ 是叠加态，输出以概率 $|c_j|^2$ 给出 $\phi_j$——测量把叠加"坍缩"到某一支，各支的概率由振幅平方决定。

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

$$
\frac{I}{D}=\frac1D\sum_{j=1}^D|u_j\rangle\langle u_j|.
$$

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

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

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

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

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

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

### 4.1 Bell 态制备与约化态

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

$$
|\Phi\rangle
=\frac1{\sqrt D}\sum_{x=0}^{D-1}|x\rangle|x\rangle.
$$

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

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

$$
\operatorname{Tr}_2\big(|\Phi\rangle\langle\Phi|\big)
=\operatorname{Tr}_2\Big(\frac1D\sum_{x,y}|x\rangle\langle y|\otimes|x\rangle\langle y|\Big)
=\frac1D\sum_{x,y}|x\rangle\langle y|\cdot\operatorname{Tr}\big(|x\rangle\langle y|\big)
=\frac1D\sum_{x,y}|x\rangle\langle y|\,\delta_{xy}
=\frac{I}{D},
$$

其中第三个等号用了 $\operatorname{Tr}(|x\rangle\langle y|)=\langle y|x\rangle=\delta_{xy}$。再由完备性关系（取 $A$ 的 eigenbasis $\{|u_j\rangle\}$，谱分解 $A=\sum_j\lambda_j|u_j\rangle\langle u_j|$）：

$$
\frac{I}{D}=\frac1D\sum_{j=1}^D|u_j\rangle\langle u_j|.
$$

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

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

对第一个寄存器执行以 $U=e^{iAt}$ 为目标酉算子的相位估计（受控的 $U^{2^k}$ 由 Hamiltonian simulation 实现，见 [ch05](../ch05-hamiltonian-qsp/trotterization-tutorial.md)）。由于

$$
U|u_j\rangle=e^{i\lambda_j t}|u_j\rangle,
$$

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

$$
\Pr[\text{输出}\approx\lambda_j]=\frac1D,\qquad j=1,\ldots,D,
$$

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

$$
\widehat s_f=\frac1M\sum_{r=1}^M f(\widetilde\lambda_r).
$$

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

$$
\mathbb E[f(\widetilde\lambda)]=\sum_{j=1}^D\frac1D f(\lambda_j)=s_f(A),
$$

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

(sampling-complexity)=
### 4.3 从采样到估计：样本复杂度

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

$$
\Pr\big[|\widehat s_f-s_f|\ge\epsilon\big]
\le 2\exp\Big(-\frac{M\epsilon^2}{2B^2}\Big).
$$

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

$$
M=O\Big(\frac{B^2}{\epsilon^2}\Big).
$$

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

### 4.4 用振幅估计做二次加速

$1/\epsilon^2$ 是经典采样的极限，但量子算法可以把"对采样结果取平均"这一步也相干化，用**振幅估计**把对 $\epsilon$ 的依赖改进为 $1/\epsilon$（这正是 Grover 型二次加速在估计问题上的版本，见 [ch03](../ch03-algo-basics/amplitude-amplification.md)）。

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

$$
|\widetilde\lambda\rangle|0\rangle
\longmapsto
|\widetilde\lambda\rangle\Big(\sqrt{\tfrac{f(\widetilde\lambda)}{B}}\,|1\rangle+\sqrt{1-\tfrac{f(\widetilde\lambda)}{B}}\,|0\rangle\Big),
$$

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

$$
p=\sum_{j=1}^D\frac1D\cdot\frac{f(\lambda_j)}{B}=\frac{s_f(A)}{B}.
$$

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

$$
Q=O\Big(\frac{B}{\epsilon}\Big).
$$

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

### 4.5 相位分辨率与总成本

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

$$
|f(\lambda)-f(\widetilde\lambda)|\le O(\epsilon).
$$

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

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

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

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

(qsvt-entangled-identity)=
## 5. 路线二：QSVT + 最大纠缠恒等式

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

### 5.1 Block encoding 与多项式逼近

设已有 $A/\alpha$ 的 block encoding（$\alpha\ge\|A\|$ 是归一化因子；block encoding 的构造见 [ch05](../ch05-hamiltonian-qsp/block-encoding-tutorial.md)）。QSVT 的基本结论是：给定在区间 $[-1,1]$ 上逼近某个目标函数的奇/偶多项式 $p$，可以把 $p(A/\alpha)$ 实现为新的 block encoding，调用次数正比于多项式次数 $\deg p$（结论的精确表述与证明见 [ch05](../ch05-hamiltonian-qsp/qsvt-tutorial.md)，此处直接使用）。

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

$$
\max_{x\in\text{谱区间}}\Big|p(x)-\frac{f(\alpha x)}{B}\Big|\le \epsilon',
$$

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

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

### 5.2 最大纠缠恒等式

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

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

$$
\langle\Phi|(M\otimes I)|\Phi\rangle=\frac1D\operatorname{Tr}M.
$$

**证明**。直接展开：

$$
\langle\Phi|(M\otimes I)|\Phi\rangle
=\frac1D\sum_{x,y}\big(\langle y|\otimes\langle y|\big)\big(M|x\rangle\otimes|x\rangle\big)
=\frac1D\sum_{x,y}\langle y|M|x\rangle\,\langle y|x\rangle.
$$

由 $\langle y|x\rangle=\delta_{xy}$，双重求和坍缩为对角项：

$$
\frac1D\sum_{x,y}\langle y|M|x\rangle\,\delta_{xy}
=\frac1D\sum_{x}\langle x|M|x\rangle
=\frac1D\operatorname{Tr}M,
$$

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

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

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

$$
\langle\Phi|\big(f(A)\otimes I\big)|\Phi\rangle=\frac1D\operatorname{Tr}f(A)=s_f(A),
$$

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

### 5.3 期望值读出

剩下的问题是：给定 $\widetilde M\approx f(A)/B$ 的 block encoding，如何估计 $\langle\Phi|(\widetilde M\otimes I)|\Phi\rangle$？

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

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

(logdet-application)=
## 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
=\operatorname{Tr}\log A
=D\,s_{\log}(A),
$$

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

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

$$
\operatorname{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)'=1/x\le\kappa$），多项式逼近次数与相位分辨率要求都随 $\kappa$ 增长——即复杂度含 $\kappa$ 或 $\log\kappa$ 与到端点的距离，与第 4.5、5.1 节的一般讨论一致。

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

假设我们把 **per-dimension log-determinant**

$$
\ell=\frac1D\log\det A
$$

估到加性误差 $\epsilon$：$|\widehat\ell-\ell|\le\epsilon$。还原成行列式：

$$
\log\det A=D\ell,\qquad
\widehat{\det}=e^{D\widehat\ell}
=e^{D\ell\pm D\epsilon}
=\det A\cdot e^{\pm D\epsilon}.
$$

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

$$
\epsilon=O\Big(\frac{\eta}{D}\Big)\quad\Longleftrightarrow\quad
\text{logdet 的 absolute error } O(\eta),\ \text{normalized error } O(\eta/D).
$$

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

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

### 6.3 一个可手算的小例子

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

- eigenvalues：$\lambda_1=1$，$\lambda_2=1/2$；
- $\log\det A=\log 1+\log\tfrac12=0-\ln 2=-\ln 2\approx-0.693$；
- 归一化量 $\ell=s_{\log}(A)=\frac12(-\ln 2)=-\frac{\ln2}{2}\approx-0.347$。

检验误差传播：设 $\widehat\ell=\ell+\epsilon$，取 $\epsilon=0.1$。则

$$
e^{D\widehat\ell}=e^{2(-\frac{\ln2}{2}+0.1)}=e^{-\ln2+0.2}=\frac12\cdot e^{0.2}\approx 0.5\times1.221=0.611,
$$

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

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

### 6.4 非 PSD 情形

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

(spectral-sum-applications)=
## 7. 应用二：熵、Schatten 范数与逆迹

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

$$
S(\rho)=-\operatorname{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 输入、对抽出的 $\widetilde\lambda$ 计算 $-\widetilde\lambda\log\widetilde\lambda$ 取平均即可，$B=1/e$ 是常数。真正的麻烦在**小 eigenvalues**：$x\log x$ 在 $x=0$ 处导数发散（不是 Lipschitz 的），多项式逼近在 $0$ 附近次数膨胀，相位分辨率要求也失控。标准处理是引入 cutoff $\delta$（把 $\lambda<\delta$ 的项截断，其对熵的总贡献可用秩的 promise 控制）或直接假设秩 $r\ll D$ 且非零 eigenvalues 有下界。这是一个 **promise 依赖**的结果：没有对谱下端的假设，熵的加性估计没有统一的高效保证。

**Schatten $p$-范数。**

$$
\|A\|_p^p=\operatorname{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 范数平方 $\|A\|_F^2=\operatorname{Tr}(A^\dagger A)$，是最简单的非平凡谱和。

**逆迹。**

$$
\operatorname{Tr}A^{-1}=\sum_j\frac1{\lambda_j},
$$

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

这三个例子共享一个信息：**谱和问题的难度由 $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 是 $\mathbf1$（全一向量）；记非零 eigenvalues 为 $\lambda_2,\ldots,\lambda_n$。**Matrix-tree theorem** 给出图的生成树数目

$$
\tau(G)=\frac1n\prod_{j=2}^n\lambda_j.
$$

取对数：

$$
\log\tau(G)=\sum_{j=2}^n\log\lambda_j-\log n.
$$

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

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

$$
L=\begin{pmatrix}2&-1&-1\\-1&2&-1\\-1&-1&2\end{pmatrix}
$$

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

$$
\tau(K_3)=\frac13\cdot3\cdot3=3,
$$

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

### 8.2 三角形计数

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

$$
\#\triangle=\frac{\operatorname{Tr}(A_G^3)}{6}.
$$

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

(quantum-advantage-conditions-spectral-sums)=
## 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 估计的是 $\operatorname{Tr}M$，对一般 $f$ 还需先经典地逼近 $f(A)v$；其二，振幅估计把 Monte Carlo 的 $1/\epsilon^2$ 降为 $1/\epsilon$。这两点是否转化为端到端加速，取决于上面列出的输入模型与 promise。

## 10. 本课小结

- 谱和 $\operatorname{Tr}f(A)$ 的统一处理分两步：先归一化为 $s_f=\frac1D\operatorname{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/\epsilon^2)$ 个样本，振幅估计改进为 $O(B/\epsilon)$ 次调用，相位分辨率需满足 $|f(\lambda)-f(\widetilde\lambda)|\le O(\epsilon)$。
- QSVT 用次数由光滑性/谱区间/逼近误差决定的多项式构造 $f(A)/B$ 的 block，最大纠缠恒等式 $\langle\Phi|(f(A)\otimes I)|\Phi\rangle=\frac1D\operatorname{Tr}f(A)$ 把 normalized trace 变成可读出的 expectation。
- Log-determinant、entropy、inverse trace、Schatten norms 都是特例；难度由谱区间端点处的奇异性控制（condition number、cutoff、rank promise），这些保留条件不是技术细节而是复杂度声明的一部分。
- 行列式的相对精度、未归一化的整数谱和、稀有结构（如极少的三角形）需要随 $D$ 缩小的归一化误差，可能指数昂贵；per-dimension 的量（如 $\ell=\frac1D\log\det A$）才是量子算法高效输出的自然对象。

## 练习题

**练习 1【归一化谱和与误差放大】**（→ [第 1 节](#normalized-spectral-sum)）

1. 设 $D=2^{10}$、$|f(x)|\le 1$。若算法把 $s_f(A)$ 估到加性误差 $\epsilon=0.01$，计算未归一化谱和 $\operatorname{Tr}f(A)$ 的绝对误差上界；再回答：要把该绝对误差压到 $O(1)$，$\epsilon$ 必须取到什么量级？
2. 某文献声称其谱和算法相对经典对角化有"superpolynomial in dimension"加速。用第 1 节的放缩论证：该声明的误差约定几乎必然是归一化加性误差，并解释为什么"未归一化绝对误差 $O(1)$"的保证会摧毁这一加速。

> 提示：还原未归一化量时误差乘以 $D=2^n$，而本文两条路线的代价都含 $1/\epsilon$ 因子。

**练习 2【经典基线：对角化与随机迹估计】**（→ [第 2 节](#classical-baseline-spectral-sums)）

1. 分别写出精确对角化与 Hutchinson 单次采样的成本（用 $D$ 与 $\mathrm{nnz}(M)$ 表示），并解释为什么"$A$ 以显式 $D\times D$ 数组给出"时连量子算法也至少要 $\Omega(D^2)$。
2. 设 $v\in\mathbb R^D$ 的各分量独立取 $\pm1$ 各半。（a）证明 $\mathbb E[v^TMv]=\operatorname{Tr}M$；（b）证明 $\operatorname{Var}(v^TMv)\le 2\|M\|_F^2$，并据此说明 Hutchinson 估计 $\operatorname{Tr}M$ 的样本复杂度含 $\|M\|_F^2/\epsilon^2$ 因子。

> 提示：（b）展开平方时把指标配对，用 $\mathbb E[v_iv_k]=0$（$i\ne k$）、$\mathbb E[v_i^2]=1$，以及 $2|M_{ik}M_{ki}|\le M_{ik}^2+M_{ki}^2$。

**练习 3【最大混态采样：均匀性与纯化】**（→ [第 3 节](#maximally-mixed-sampling)）

1. 取 $D=2$、$|\Phi\rangle=\frac{1}{\sqrt2}(|00\rangle+|11\rangle)$，显式计算偏迹 $\operatorname{Tr}_2(|\Phi\rangle\langle\Phi|)$，验证结果为 $I/2$。
2. 写出 $U=e^{iAt}$ 与 $A$ 的特征矢量、特征值之间的关系，并解释"对混合态 $I/D$ 做相位估计"为什么等价于"先以概率 $1/D$ 抽取某个 $|u_j\rangle$，再对它做相位估计"。
3. 设 $\lambda$ 是 $A$ 的 $k$ 重特征值。证明采样路线输出"$\approx\lambda$"的概率是 $k/D$，并说明这与第 1 节 $j\sim U[D]$ 的约定一致。

> 提示：完备性关系 $I=\sum_j|u_j\rangle\langle u_j|$ 按重数对特征矢量求和。

**练习 4【样本复杂度与振幅估计】**（→ [4.3 节](#sampling-complexity)）

1. 设 $|f(x)|\le B=1$。要把 $s_f$ 估到加性误差 $\epsilon=0.05$（常数失败概率），分别写出纯采样平均与振幅估计所需的重复次数量级，并指出后者改进的是哪个因子。
2. 设 $f$ 在谱区间上 $L$-Lipschitz。写出相位分辨率 $\delta$ 与演化时间 $t$ 应如何随 $\epsilon$、$L$ 取值，并解释为什么 $f$ 越陡（如 $1/x$ 在 $x$ 小时）总成本越高。

> 提示：用 $|f(\lambda)-f(\widetilde\lambda)|\le L\,\delta$ 控制单次样本的偏差。

**练习 5【QSVT 路线与最大纠缠恒等式】**（→ [第 5 节](#qsvt-entangled-identity)）

1. 取 $D=2$、$M=\operatorname{diag}(m_1,m_2)$，对 $|\Phi\rangle=\frac{1}{\sqrt2}(|00\rangle+|11\rangle)$ 直接展开计算 $\langle\Phi|(M\otimes I)|\Phi\rangle$，验证 Lemma 1。
2. 设 $\operatorname{spec}(A)\subseteq[1/\kappa,1]$、$f=\log$、$B=\log\kappa$。写出 QSVT 路线中多项式 $p$ 需要逼近的目标函数与区间，并说明次数为何随 $\kappa$ 增长。
3. 证明伴生恒等式 $(M\otimes I)|\Phi\rangle=(I\otimes M^T)|\Phi\rangle$，并用它重新证明 Lemma 1。

> 提示：第 3 题两边都在基 $|x\rangle|y\rangle$ 上展开比较系数。

**练习 6【对数行列式与相对精度】**（→ [第 6 节](#logdet-application)）

1. 对 $A=\operatorname{diag}(2,\tfrac12)$（$D=2$）分别计算 $\log\det A$、$\operatorname{Tr}\log A$ 与 $s_{\log}(A)$，验证 $\log\det A=\operatorname{Tr}\log A=D\,s_{\log}(A)$。
2. 对 $A=\operatorname{diag}(1,\tfrac12)$（$D=2$）：（a）计算 $\log\det A$ 与 $\ell=\frac1D\log\det A$；（b）设 $\widehat\ell$ 有加性误差 $\epsilon=0.05$，计算行列式估计的乘性偏差 $e^{\pm D\epsilon}$；（c）$\epsilon$ 要取多小，才能保证行列式的相对误差在 $1\%$ 以内？

> 提示：把乘性偏差 $e^{\pm D\epsilon}$ 与阈值 $1\pm 0.01$ 对应起来解出 $\epsilon$。

**练习 7【谱和应用：熵、范数、逆迹与图谱】**（→ [第 7 节](#spectral-sum-applications)）

1. 分别写出 von Neumann 熵、Schatten $p$-范数的 $p$ 次幂与逆迹所对应的函数 $f$，并给出 $f(x)=-x\log x$ 与 $f(x)=1/x$（$\operatorname{spec}\subseteq[1/\kappa,1]$）情形下的界 $B$。
2. 由 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$。
3. （开放）设图有 $T$ 个三角形，要把 $T$ 估到 $(1\pm\eta)$ 相对精度：用第 1 节的框架写出所需的归一化误差 $\epsilon$，并说明为什么 $T$ 很小时任何"先归一化再还原"的路线都会失效；再简述经典算法（如直接抽样边或顶点）如何绕开这一困难，以及这对你评价量子加速有何启示。

> 提示：$\#\triangle=\operatorname{Tr}(A_G^3)/6$，把相对精度换算成归一化谱和 $6T/D$ 上的加性误差。

**练习 8【量子优势的条件：输入模型与总账】**（→ [第 9 节](#quantum-advantage-conditions-spectral-sums)）

1. 列出第 9 节给出的可信加速场景（至少两类），并解释为什么 $A$ 以显式 $D\times D$ 稠密数组给出时，谈论"指数加速"没有意义。
2. 比较两条路线的"每次采样成本"：设 $A$ 为 $s$-sparse、$\operatorname{spec}(A)\subseteq[1/\kappa,1]$、$f=\log$。（a）采样路线中，$f$ 的 Lipschitz 常数是多少？相位分辨率 $\delta$ 与演化时间 $t$ 应如何取？（b）QSVT 路线中，多项式需要在哪个区间上以什么精度逼近什么函数？（c）定性讨论：哪些情形下你预期 QSVT 路线占优，哪些情形下采样路线占优？

> 提示：(a) 中 $(\log x)'=1/x$ 在区间左端点 $1/\kappa$ 处最陡。

## 参考文献

- Zoo 编号 527：Luongo 与 Shao, [Quantum Algorithms for Spectral Sums](https://arxiv.org/abs/2011.06475).
- Zoo 编号 528：Giovannetti、Lloyd 与 Maccone 关于 determinant estimation 的 2025 算法。