谱和与行列式：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 成本。

参考文献