# 稀疏矩阵幂对角元：谱矩、Block Encoding 与 BQP 完备性

给一个维数 $N$ 可能指数大的稀疏实对称矩阵 $A$，只估计

$$
(A^m)_{jj}=\langle j|A^m|j\rangle
$$

的一个 entry。虽然不能读出整张矩阵，量子计算机可从基态 $|j\rangle$ 的 spectral measure 估计第 $m$ 阶矩；反过来，Feynman clock 把任意量子电路接受偏差编码进这种矩。指定归一化误差下，该问题是 PromiseBQP-complete。

## 1. 输入与 promise

$A\in\mathbb R^{N\times N}$ 对称，每行至多

$$
s=\operatorname{polylog}N
$$

个非零 entry。Sparse oracle 给：

1. 第 $r$ 行第 $\ell$ 个非零位置；
2. 对应实值 $A_{r,c}$。

已知

$$
\|A\|\le b.
$$

$m=\operatorname{polylog}N$，目标以加性误差

$$
\epsilon b^m,\qquad
1/\epsilon=\operatorname{polylog}N
$$

估计指定对角元。除以 $b^m$ 后等价估计

$$
\mu_m=\langle j|H^m|j\rangle,\qquad H=A/b, \|H\|\le1.
$$

若要求原值绝对误差 1，而 $b^m$ 指数大，复杂度口径完全不同；normalization 是问题定义核心。

## 2. Spectral measure 解释

谱分解

$$
H=\sum_r\lambda_r|u_r\rangle\langle u_r|,
\qquad\lambda_r\in[-1,1].
$$

则

$$
\mu_m=\sum_r
|\langle u_r|j\rangle|^2\lambda_r^m.
$$

定义基态 $|j\rangle$ 看到的概率测度

$$
\nu_j=\sum_r
|\langle u_r|j\rangle|^2\delta_{\lambda_r}.
$$

$\mu_m$ 就是随机变量 $\lambda\sim\nu_j$ 的 $m$ 阶矩

$$
\mu_m=\mathbb E_{\nu_j}[\lambda^m].
$$

量子相位估计对 $e^{iHt}$、输入 $|j\rangle$ 做测量，天然以这些 overlap 概率抽取本征值；经典算法若不读指数多矩阵结构，很难获得同一局部谱测度。

## 3. 两种量子估计实现

### 谱采样

Sparse Hamiltonian simulation 实现 $e^{iHt}$。Phase estimation 得 $\widetilde\lambda$，经典计算 $\widetilde\lambda^m\in[-1,1]$，重复平均。为使

$$
|\lambda^m-\widetilde\lambda^m|\le\epsilon,
$$

用

$$
|x^m-y^m|\le m|x-y|\quad(|x|,|y|\le1)
$$

可取 eigenvalue 精度 $O(\epsilon/m)$。普通 Monte Carlo 需 $O(1/\epsilon^2)$ 样本。

### Block encoding / QSVT

由 sparse oracle 构造 $H$ 的 block encoding。QSVT 对多项式

$$
p(x)=x^m
$$

实现 $H^m$ 的 block encoding，degree 为 $m$。Hadamard test 估计 $\langle j|H^m|j\rangle$；amplitude estimation 可把精度调用降至 $O(1/\epsilon)$。总成本关于 $s,m,\log N,1/\epsilon$ 为多项式。

原论文使用“测量 $A$ 并估计 spectral moment”的等价表述；现代 block-encoding 语言更直接显示 normalization 与 degree。

## 4. 为什么不是“快速输出 $A^m$”

$A^m$ 通常 dense，有 $N^2$ 个 entry；输出它至少 $\Omega(N^2)$ 时间。量子算法只回答一个 matrix element 或少量线性 functional。

即使经典 fast exponentiation 用 $O(\log m)$ 次矩阵乘法，矩阵维数 $N$ 仍指数大；sparsity 也不在乘方后保持。量子算法从局部 sparse oracle 直接访问谱函数，避免物化中间矩阵。

Off-diagonal entry 可用 polarization。对实对称 $B=H^m$：

$$
\langle i|B|j\rangle
=\langle +|B|+\rangle
-\frac12\langle i|B|i\rangle
-\frac12\langle j|B|j\rangle,
$$

其中 $|+\rangle=(|i\rangle+|j\rangle)/\sqrt2$。

## 5. BQP-hardness 的 Feynman clock 思路

给量子电路

$$
U_T\cdots U_1,\qquad T=\operatorname{poly}(n),
$$

构造 propagation matrix

$$
K=\sum_{t=0}^{T-1}
\left(
|t+1\rangle\langle t|\otimes U_{t+1}
+|t\rangle\langle t+1|\otimes U_{t+1}^\dagger
\right).
$$

$K$ Hermitian 且 sparse：每个 clock configuration 只连接前后两步。加入输入、输出 flag 与适当 gadget/padding，可让某基态 $|j\rangle$ 的谱测度在 accept/reject 电路间具有不同第 $m$ 阶矩：

$$
\langle j|K^m|j\rangle
$$

统计沿 computation history 前进/后退的闭合路径，其干涉权重包含门振幅。选择 poly-size $m$ 与 gap，使矩符号/区间决定接受。

构造甚至可把矩阵 entry 限制为 $-1,0,1$（通过门 gadget），说明困难不来自高精度输入数值。

## 6. 与字符串重写的统一

[字符串重写](string-rewriting.md)图的邻接矩阵也是 sparse Hermitian，重写路径数是其幂 entry。两项 BQP-complete 结果共享：

$$
\text{局部 transition rules}
\longrightarrow
\text{隐式 sparse matrix}
\longrightarrow
\text{高阶谱矩/路径振幅}.
$$

矩阵问题允许一般正负权，string rewriting 用两个非负路径计数之差制造符号。

## 7. 小例子

$$
H=\begin{pmatrix}0&1\\1&0\end{pmatrix}=X,\qquad |j\rangle=|0\rangle.
$$

$H^{2r}=I$、$H^{2r+1}=X$，所以

$$
\langle0|H^m|0\rangle=
\begin{cases}1,&m\text{ even},\\0,&m\text{ odd}.
\end{cases}
$$

谱测度在 $\lambda=\pm1$ 各有 $1/2$，矩为 $\frac12(1^m+(-1)^m)$，与直接计算一致。

## 8. 小结与习题

- 对角幂 entry 是基态 spectral measure 的矩。
- Sparse phase estimation 或 QSVT 可在 polylog 维数依赖下估计归一化矩。
- 算法不输出 dense $A^m$；误差是 $\epsilon b^m$。
- Feynman clock 把通用量子计算编码到 sparse matrix moment，证明 BQP-hard。

1. 推导 spectral moment 公式。
2. 检查 polarization 公式并写出精确系数。
3. 证明 $|x^m-y^m|\le m|x-y|$ 对 $[-1,1]$ 成立。
4. 解释 $m=\operatorname{polylog}N$ 为何与电路长度 polynomial in input qubits 相容。

## 参考文献

- Zoo 编号 60：Dominik Janzing 与 Pawel Wocjan, [Estimating Diagonal Entries of Powers of Sparse Symmetric Matrices Is BQP-Complete](https://arxiv.org/abs/quant-ph/0606229).