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

给维数 $D=2^n$ 的稀疏/可 block-encode Hermitian matrix $A$，目标不是输出 eigenvalues，而是估计

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

Maximally mixed state 在 eigenbasis 中均匀，所以 phase estimation 直接抽取均匀随机 eigenvalue；QSVT 也可实现 $f(A)$ 并把 normalized trace 写成 maximally entangled expectation。Log-determinant、entropy、inverse trace 与 Schatten norms 都是特例。

## 1. 先归一化输出尺度

定义

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

Quantum algorithm 自然估计 $s_f$ 到加性误差 $\epsilon$。原谱和误差是 $D\epsilon$；若需要 absolute error 1，就要 $\epsilon=1/D$，通常指数昂贵。因此“superpolynomial in dimension”结果对应 normalized/additive promise，而非精确整数谱和。

## 2. Maximally mixed eigenvalue sampling

制备 $n$ Bell pairs

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

只在第一 register 对 $e^{iAt}$ 做 phase estimation。写 $A=\sum_j\lambda_j|u_j\rangle\langle u_j|$，reduced state 是

$$
I/D=\frac1D\sum_j|u_j\rangle\langle u_j|,
$$

故 phase estimation 输出每个 eigenvalue（按 multiplicity）概率 $1/D$。对输出 $\widetilde\lambda$ 计算 $f(\widetilde\lambda)$ 并平均：

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

若 $|f|\le B$，经典 averaging 需 $M=O(B^2/\epsilon^2)$；可相干计算 $f$ 并用 amplitude estimation 改到 $O(B/\epsilon)$ calls。

Sparse Hamiltonian simulation 成本依 sparsity、$t$ 与 eigenvalue precision；phase-estimation resolution 要让

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

## 3. QSVT / block-encoding 路线

若有 $A/\alpha$ 的 block encoding，选 polynomial $p$ 在谱区间一致逼近

$$
f(\alpha x)/B.
$$

QSVT 构造 $f(A)/B$ 的近似 block。Maximally entangled identity

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

将 normalized trace 变成 Hadamard/amplitude-estimation expectation。Polynomial degree 由 $f$ 的 smoothness、谱区间与逼近误差决定；对 singularity 附近的 $1/x,\log x$ 会含 condition number。

## 4. Log-determinant

对 positive definite $A$：

$$
\log\det A
=\operatorname{Tr}\log A
=D\,s_{\log}(A).
$$

若 rescale 使

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

$\log x$ bounded by $\log\kappa$，polynomial/phase precision含 $\kappa$ 或 $\log\kappa$ 与 endpoint distance。估计

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

到 $\epsilon$ 意味着 determinant 的 multiplicative factor

$$
e^{\pm D\epsilon},
$$

并不小；若要 $(1\pm\eta)$ relative determinant，需要 logdet absolute error $O(\eta)$，即 normalized error $O(\eta/D)$，可能指数难。实践更常直接需要 per-dimension log-likelihood $\ell$。

非 PSD matrix 的 determinant 还含 sign/complex phase，需分别估计负 eigenvalue parity 或使用 singular values；本算法基本表述以 PSD 为主。

## 5. 其他 spectral sums

对 density matrix $\rho$：

$$
S(\rho)=-\operatorname{Tr}(\rho\log\rho).
$$

这里 sampling distribution 若用 maximally mixed并计算 $-\lambda\log\lambda$，仍可；小 eigenvalues 的 approximation需 cutoff/rank promise。

Schatten $p$-norm：

$$
\|A\|_p^p=\operatorname{Tr}|A|^p.
$$

Inverse trace：

$$
\operatorname{Tr}A^{-1}=\sum_j1/\lambda_j
$$

含 condition number。Effective resistance、Gaussian covariance normalization、Bayesian log evidence 都可归约到这些量。

## 6. 图谱应用

Graph Laplacian $L$ 非零 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.
$$

需排除 zero eigenvalue（投影到 $\mathbf1^\perp$ 或 regularize）。Triangle count

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

也是 polynomial spectral sum；但它可能很小，相对估计 again 需要更高精度。

## 7. Classical comparison 与输入读取

若 $A$ 以显式 dense $D^2$ 数组给出，量子 oracle/QRAM 构建可能已指数成本。可信 speedup 场景：

- $A$ 由 local rule/sparse oracle 隐式定义；
- block encoding 来自已有 quantum process；
- 只需 normalized scalar；
- spectrum 有 condition/gap promise。

Classical stochastic trace estimation 也用随机 vectors 与 matrix-vector products，成本可 subquadratic；比较应计一次 matvec 与 sparsity，而不是总说经典 diagonalization $D^3$。

## 8. 小结与习题

- Maximally mixed state 在 eigenbasis 均匀，phase estimation 把 normalized spectral sum变 Monte Carlo expectation。
- QSVT + maximally entangled state 直接估计 $\operatorname{Tr}f(A)/D$。
- Logdet、entropy、inverse trace 的难度由 spectrum endpoint/condition 控制。
- 原谱和、相对 determinant 或稀有 eigenvalue 可能需要指数精度。

1. 证明 maximally entangled trace identity。
2. 对 diagonal $A=\operatorname{diag}(1,1/2)$ 计算 logdet 与 normalized logdet。
3. 推导 matrix-tree log formula。
4. 比较 Hutchinson trace estimator 与 quantum amplitude estimation 的 oracle 成本。

## 参考文献

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