谱和与行列式：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)
其中 \(\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）、Hamiltonian simulation 与 block encoding / QSVT（ch05）的基本结论；我们会引用这些结论但不重新推导。
本课知识点
归一化谱和与误差放大——能把 \(\operatorname{Tr}f(A)\) 改写成 \(s_f=\mathbb E_{j\sim U[D]}[f(\lambda_j)]\)，并推导未归一化谱和的误差被放大 \(D\) 倍。
经典基线：对角化与随机迹估计——能比较 \(O(D^3)\) 对角化与 Hutchinson 迹估计的成本，并证明 \(v^TMv\) 是 \(\operatorname{Tr}M\) 的无偏估计。
最大混态采样：均匀性与纯化——能解释 \(I/D\) 为何在任意 eigenbasis 中均匀、由 Bell 态偏迹得到 \(I/D\)，并写出相位估计输出各特征值的概率。
样本复杂度与振幅估计——能用 Hoeffding 不等式推出 \(M=O(B^2/\epsilon^2)\)，说明振幅估计如何改进为 \(O(B/\epsilon)\)，并把相位分辨率要求计入总成本。
QSVT 路线与最大纠缠恒等式——能写出 QSVT 所需的多项式逼近目标，证明 \(\langle\Phi|(M\otimes I)|\Phi\rangle=\frac1D\operatorname{Tr}M\)，并比较两种期望值读出方式。
对数行列式与相对精度——能把 \(\log\det A\) 化为 \(f=\log\) 的谱和，推导加性误差 \(\epsilon\) 产生乘性偏差 \(e^{\pm D\epsilon}\)，并手算 \(D=2\) 的例子。
谱和应用：熵、范数、逆迹与图谱——能写出熵、Schatten 范数与逆迹对应的函数 \(f\) 及其界 \(B\)，并用 matrix-tree 定理计算生成树数目。
量子优势的条件：输入模型与总账——能列出可信加速所需的输入模型与 promise 条件，并说明与经典随机迹估计比较时哪些成本必须计入。
1. 问题定义：先归一化输出尺度¶
在开始任何算法之前，先做一件看似琐碎、实则决定成败的事：把输出尺度归一化。定义归一化谱和
其中 \(j\sim U[D]\) 表示从 \(\{1,\ldots,D\}\) 中均匀随机取一个指标。最后一个等号只是把"除以 \(D\) 的求和"重新解读为"均匀分布下的期望"，但它指明了算法的形状：只要能从特征值的经验分布中采样，\(s_f\) 就是一个普通的 Monte Carlo 期望。
量子算法（无论哪条路线）自然输出的是 \(s_f\) 的加性 \(\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)\) 到与维数无关的绝对误差。这不是技术上的偷懒，而是由上面的简单放缩决定的硬性分界。读任何谱和算法的复杂度声明时，第一件事就是确认它用的是哪一种误差约定。
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_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\) 依赖并不是量子特有的缺陷。
3. 核心直觉：最大混态是"特征值上的均匀分布"¶
在进入形式推导前，先用一句话讲清第一条路线的全部思想：
相位估计需要一个输入态；如果输入态在 eigenbasis 里"均匀涂抹"，那么相位估计的输出就是均匀随机的一个 eigenvalue。
回顾相位估计（ch03）：对酉算子 \(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
右边的等号不是近似：\(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，即
制备线路是标准的：对每对 qubit 先加 Hadamard 再用 CNOT，\(n\) 对并行共 \(O(n)\) 个门。
我们只对第一个寄存器施加后续操作（相位估计），第二个寄存器全程闲置。形式上，第一个寄存器的状态由约化密度矩阵描述。计算偏迹：
其中第三个等号用了 \(\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|\)）：
所以"制备 \(|\Phi\rangle\)、只对一半动手"与"以概率 \(1/D\) 随机制备某个 \(|u_j\rangle\)"在一切测量统计上不可区分——尽管我们完全不知道 \(|u_j\rangle\) 是什么。
4.2 相位估计输出均匀随机特征值¶
对第一个寄存器执行以 \(U=e^{iAt}\) 为目标酉算子的相位估计（受控的 \(U^{2^k}\) 由 Hamiltonian simulation 实现，见 ch05）。由于
当第一个寄存器处于 \(|u_j\rangle\) 时，相位估计输出 \(\lambda_j t\)（进而 \(\lambda_j\)）的近似 \(\widetilde\lambda\)；而第 4.1 节说明输入等效于以概率 \(1/D\) 取 \(|u_j\rangle\)。合起来：
其中 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\)，定义估计量
若相位估计完全精确（\(\widetilde\lambda_r=\lambda_{j_r}\)），则每个 \(f(\widetilde\lambda_r)\) 的期望恰为
即估计量无偏。相位估计的分辨率误差会让每个样本的值略有偏移，第 4.5 节处理这部分偏差。
4.3 从采样到估计：样本复杂度¶
设 \(f\) 在谱区间上有界：\(|f(x)|\le B\)。每个样本 \(f(\widetilde\lambda_r)\) 是取值于 \([-B,B]\)（区间宽度 \(2B\)）的独立随机变量，均值为 \(s_f\)。用 Hoeffding 不等式（\(M\) 个独立有界变量的均值偏离期望的概率界）：
要求右端不超过常数（如 \(1/3\)），解出
逐项解释这个表达式：因子 \(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）。
构造分两步。第一步，把 \(f\) 相干地算进振幅。为简单起见先设 \(0\le f(x)\le B\)（一般情形可把 \(f\) 拆成正负两部分分别处理，或平移缩放后处理）。在相位估计输出 \(\widetilde\lambda\) 之后，附加一个辅助 qubit，执行受控旋转
即把 \(\arcsin\sqrt{f(\widetilde\lambda)/B}\) 的角度转进振幅（\(f\) 本身若是可有效计算的函数，这一步是标准的相干算术；若 \(f\) 只能以 oracle 形式给出，则计入一次 \(f\) 的查询）。对整个叠加态而言，辅助位测得 \(|1\rangle\) 的概率是
第二步，对"辅助位为 \(1\)"这一事件做振幅估计：以 \(Q\) 次调用（每次调用含一次相位估计与一次受控旋转）把 \(p\) 估到加性误差 \(O(1/Q)\)。于是 \(s_f=Bp\) 的误差为 \(O(B/Q)\)，要求其不超过 \(\epsilon\) 得
对比第 4.3 节的 \(M=O(B^2/\epsilon^2)\)：对 \(\epsilon\) 的依赖从平方改进为线性，这是振幅估计带来的标准二次增益；代价是每次调用的线路更深（需要相干地控制整个"采样 + 求值"过程，不能简单地测量后重来）。
4.5 相位分辨率与总成本¶
采样路线还有一笔账：相位估计本身的有限分辨率。设相位估计把每个 eigenvalue 定到误差 \(\delta\) 以内（\(|\widetilde\lambda-\lambda|\le\delta\)）。为了让函数值的偏移不破坏总精度，需要
若 \(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）。总成本为
注意分辨率要求 \(|f(\lambda)-f(\widetilde\lambda)|\le O(\epsilon)\) 把 \(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\|A\|\) 是归一化因子；block encoding 的构造见 ch05）。QSVT 的基本结论是：给定在区间 \([-1,1]\) 上逼近某个目标函数的奇/偶多项式 \(p\)，可以把 \(p(A/\alpha)\) 实现为新的 block encoding，调用次数正比于多项式次数 \(\deg p\)（结论的精确表述与证明见 ch05，此处直接使用）。
要估计 \(s_f\)，取目标函数为 \(f(\alpha x)/B\)（自变量 \(\alpha x\) 把 \(A/\alpha\) 的谱映回 \(A\) 的谱区间；除以 \(B\) 把值域压进 \([-1,1]\)，这是 QSVT 对多项式的硬性要求）。选多项式 \(p\) 在谱区间上一致逼近：
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 y|x\rangle=\delta_{xy}\)，双重求和坍缩为对角项：
最后一步是迹的定义（对任意正交归一基求对角元之和）。Q.E.D.
值得同时记住一个伴生恒等式（习题 1）：\((M\otimes I)|\Phi\rangle=(I\otimes M^T)|\Phi\rangle\)——算子可以在最大纠缠态的两半之间"转移"，代价是取转置。它说明最大纠缠态把两个寄存器紧密锁定，是这类恒等式成立的结构性原因。
取 \(M=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，采样路线常常更直接。
6. 应用一：对数行列式¶
6.1 从 log det 到谱和¶
设 \(A\) 正定（PSD 且可逆），eigenvalues \(\lambda_j>0\)。行列式是 eigenvalues 之积，取对数把积变和：
其中 \(\log A\) 是矩阵函数（在 eigenbasis 中对每个 eigenvalue 取 \(\log\)），第三个等号是迹在 eigenbasis 中的展开。于是 log-determinant 是 \(f=\log\) 的谱和，本文的两条路线都适用。
先 rescale：把 \(A\) 换成 \(A/\|A\|\)（以下仍记为 \(A\)），使谱落在
其中 \(\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
估到加性误差 \(\epsilon\)：\(|\widehat\ell-\ell|\le\epsilon\)。还原成行列式：
也就是说，\(\ell\) 的加性误差 \(\epsilon\) 经过 \(D\) 倍放大再取指数，变成行列式的乘性因子 \(e^{\pm D\epsilon}\)——这不是一个小扰动。若要行列式的 \((1\pm\eta)\) 相对精度，需要 \(e^{D\epsilon}\le 1+\eta\)，即 \(D\epsilon\lesssim\eta\)，也就是
归一化误差要与 \(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\)。则
而真值 \(\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 的推广保留这一拆分结构。
7. 应用二：熵、Schatten 范数与逆迹¶
von Neumann 熵。 对密度矩阵 \(\rho\)（PSD、迹为 1），
即 \(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\)-范数。
其中 \(\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)\)，是最简单的非平凡谱和。
逆迹。
\(f(x)=1/x\) 在 \(0\) 处奇异；若 \(\operatorname{spec}(A)\subseteq[1/\kappa,1]\)，则 \(B=\kappa\)、Lipschitz 常数 \(L=\kappa^2\)、多项式次数随 \(\kappa\) 增长——复杂度被 condition number 全面控制。这与 HHL 类线性求解器的 \(\kappa\) 依赖同源（ch06）。
这三个例子共享一个信息：谱和问题的难度由 \(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 给出图的生成树数目
取对数：
右端的和是 \(\log\) 的谱和，但有一个技术性障碍：必须把 zero eigenvalue 排除在外（\(\log 0\) 发散）。两个办法：把问题投影到 \(\mathbf1^\perp\) 子空间上（在受控操作中以 \(\mathbf1\) 为标记做排除），或把 \(L\) regularize 成 \(L+\delta I\) 之类的可逆矩阵再修正。无论哪种，复杂度都含 \(1/\lambda_2\)（谱隙的倒数，充当 condition number 的角色）——谱隙越小的图越难。
小例子：取三角形图 \(K_3\)（3 个顶点两两相连）。其 Laplacian
的 eigenvalues 为 \(0,3,3\)（\(\mathbf1\) 张成零空间；在 \(\mathbf1^\perp\) 上 \(L=3I\)，因为 \(L=3I-\mathbf1\mathbf1^T\)，而 \(\mathbf1\mathbf1^T\) 在 \(\mathbf1^\perp\) 上为零）。代入 matrix-tree theorem：
与直接枚举一致（\(K_3\) 的生成树恰是删掉任意一条边，共 3 棵）。进而 \(\log\tau(K_3)=\log3+\log3-\log3=\log3\)，公式自洽。
8.2 三角形计数¶
图的三角形数目是另一个多项式谱和：邻接矩阵 \(A_G\) 的三次幂的迹数的是长度为 3 的闭 walk，而每个三角形贡献 6 条（3 个起点 × 2 个方向），故
这是 \(f(x)=x^3\) 的谱和（对 QSVT 路线是精确的次数-3 多项式，无逼近误差），本身很容易估计到加性精度。真正的困难在另一端：\(\#\triangle\) 本身可能很小（甚至为 0 或 1），此时有意义的是相对精度，而由第 1 节的分析，相对精度要求绝对误差 \(O(\#\triangle)\)，归一化误差再除以 \(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 估计的是 \(\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 节）
设 \(D=2^{10}\)、\(|f(x)|\le 1\)。若算法把 \(s_f(A)\) 估到加性误差 \(\epsilon=0.01\)，计算未归一化谱和 \(\operatorname{Tr}f(A)\) 的绝对误差上界；再回答：要把该绝对误差压到 \(O(1)\)，\(\epsilon\) 必须取到什么量级？
某文献声称其谱和算法相对经典对角化有"superpolynomial in dimension"加速。用第 1 节的放缩论证：该声明的误差约定几乎必然是归一化加性误差，并解释为什么"未归一化绝对误差 \(O(1)\)"的保证会摧毁这一加速。
提示：还原未归一化量时误差乘以 \(D=2^n\)，而本文两条路线的代价都含 \(1/\epsilon\) 因子。
练习 2【经典基线：对角化与随机迹估计】（→ 第 2 节）
分别写出精确对角化与 Hutchinson 单次采样的成本（用 \(D\) 与 \(\mathrm{nnz}(M)\) 表示），并解释为什么"\(A\) 以显式 \(D\times D\) 数组给出"时连量子算法也至少要 \(\Omega(D^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 节）
取 \(D=2\)、\(|\Phi\rangle=\frac{1}{\sqrt2}(|00\rangle+|11\rangle)\)，显式计算偏迹 \(\operatorname{Tr}_2(|\Phi\rangle\langle\Phi|)\)，验证结果为 \(I/2\)。
写出 \(U=e^{iAt}\) 与 \(A\) 的特征矢量、特征值之间的关系，并解释"对混合态 \(I/D\) 做相位估计"为什么等价于"先以概率 \(1/D\) 抽取某个 \(|u_j\rangle\)，再对它做相位估计"。
设 \(\lambda\) 是 \(A\) 的 \(k\) 重特征值。证明采样路线输出"\(\approx\lambda\)"的概率是 \(k/D\)，并说明这与第 1 节 \(j\sim U[D]\) 的约定一致。
提示：完备性关系 \(I=\sum_j|u_j\rangle\langle u_j|\) 按重数对特征矢量求和。
练习 4【样本复杂度与振幅估计】（→ 4.3 节）
设 \(|f(x)|\le B=1\)。要把 \(s_f\) 估到加性误差 \(\epsilon=0.05\)（常数失败概率），分别写出纯采样平均与振幅估计所需的重复次数量级，并指出后者改进的是哪个因子。
设 \(f\) 在谱区间上 \(L\)-Lipschitz。写出相位分辨率 \(\delta\) 与演化时间 \(t\) 应如何随 \(\epsilon\)、\(L\) 取值，并解释为什么 \(f\) 越陡（如 \(1/x\) 在 \(x\) 小时）总成本越高。
提示：用 \(|f(\lambda)-f(\widetilde\lambda)|\le L\,\delta\) 控制单次样本的偏差。
练习 5【QSVT 路线与最大纠缠恒等式】（→ 第 5 节）
取 \(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。
设 \(\operatorname{spec}(A)\subseteq[1/\kappa,1]\)、\(f=\log\)、\(B=\log\kappa\)。写出 QSVT 路线中多项式 \(p\) 需要逼近的目标函数与区间，并说明次数为何随 \(\kappa\) 增长。
证明伴生恒等式 \((M\otimes I)|\Phi\rangle=(I\otimes M^T)|\Phi\rangle\)，并用它重新证明 Lemma 1。
提示：第 3 题两边都在基 \(|x\rangle|y\rangle\) 上展开比较系数。
练习 6【对数行列式与相对精度】（→ 第 6 节）
对 \(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)\)。
对 \(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 节）
分别写出 von Neumann 熵、Schatten \(p\)-范数的 \(p\) 次幂与逆迹所对应的函数 \(f\)，并给出 \(f(x)=-x\log x\) 与 \(f(x)=1/x\)（\(\operatorname{spec}\subseteq[1/\kappa,1]\)）情形下的界 \(B\)。
由 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\)。
（开放）设图有 \(T\) 个三角形，要把 \(T\) 估到 \((1\pm\eta)\) 相对精度：用第 1 节的框架写出所需的归一化误差 \(\epsilon\)，并说明为什么 \(T\) 很小时任何"先归一化再还原"的路线都会失效；再简述经典算法（如直接抽样边或顶点）如何绕开这一困难，以及这对你评价量子加速有何启示。
提示：\(\#\triangle=\operatorname{Tr}(A_G^3)/6\)，把相对精度换算成归一化谱和 \(6T/D\) 上的加性误差。
练习 8【量子优势的条件：输入模型与总账】（→ 第 9 节）
列出第 9 节给出的可信加速场景（至少两类），并解释为什么 \(A\) 以显式 \(D\times D\) 稠密数组给出时，谈论"指数加速"没有意义。
比较两条路线的"每次采样成本"：设 \(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.
Zoo 编号 528：Giovannetti、Lloyd 与 Maccone 关于 determinant estimation 的 2025 算法。