稀疏矩阵幂对角元：谱矩、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. 与字符串重写的统一

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

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

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

7. 小例子

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

\(H^{2r}=I\)、\(H^{2r+1}=X\)，所以

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

谱测度在 \(\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 相容。

参考文献