主特征向量的经典输出：Robust Power Method、量子 Matvec 与无偏 Tomography

制备 principal eigenvector quantum state 在某些 block-encoding 模型中相对直接；真正困难的是输出 \(d\) 个经典坐标。Chen--Gilyén--de Wolf 给 entry-query Hermitian matrix 的算法，以 \(d^{1.5+o(1)}\) 时间输出 top eigenvector classical approximation，优于 classical \(\Omega(d^2)\) entry lower bound，并接近 quantum \(\widetilde\Omega(d^{3/2})\)。

1. 问题与 gap promise

\(A\in\mathbb C^{d\times d}\) Hermitian，entry oracle

\[ O_A|i,j,z\rangle =|i,j,z\oplus A_{ij}\rangle. \]

Eigenvalues

\[ \lambda_1>\lambda_2\ge\cdots \]

且 top eigengap/ratio 有常数或已知 lower bound。目标输出 classical vector \(\widetilde v\)：

\[ \min_{|\omega|=1} \|\widetilde v-\omega v_1\|_2 \le\epsilon. \]

Global phase 不可辨；实矩阵只剩 sign。若 gap 任意小，top eigenvector 对 entry perturbation 不稳定，复杂度必含 \(1/\Delta\)。

2. Classical power method

从

\[ x_0=\sum_jc_jv_j,qquad c_1\ne0 \]

开始：

\[ x_t=\frac{A^tx_0}{\|A^tx_0\|}. \]

展开

\[ A^tx_0 =\lambda_1^t \left(c_1v_1+ \sum_{j>1}c_j(\lambda_j/\lambda_1)^tv_j\right). \]

误差约

\[ \frac{\sqrt{1-|c_1|^2}}{|c_1|} \left|\frac{\lambda_2}{\lambda_1}\right|^t. \]

随机 unit vector 有 \(|c_1|\sim d^{-1/2}\)，常数 relative gap 时

\[ t=O(\log(d/\epsilon)). \]

Dense classical matvec 需 \(d^2\) entry operations，每轮已触及整个输入。

3. 为什么量子 state matvec 还不够

Block encoding \(U_A\) 可把

\[ |x\rangle \mapsto \frac{A|x\rangle}{\|Ax\|} \]

（成功 amplitude/放大后）。若下一轮只需要 quantum state，可迭代；但最终 classical \(v_1\) 需 tomography。朴素 full tomography 每轮或末轮高精度读取，可能回到 \(d^2/\epsilon^2\)。

算法需要两点：matvec error 可以是有结构、无偏的；power method 对每轮独立 benign noise robust，不必每个 coordinate 都极高精度。

4. 方法一：逐 entry Gaussian Phase Estimation

给当前 classical approximation \(x\)，第 \(i\) 个输出

\[ y_i=(Ax)_i=\sum_jA_{ij}x_j. \]

制备按 \(x_j\) 权重的叠加，对 row-\(i\) entry query phase kickback，把 \(y_i\) 编进近 Gaussian pointer phase/shift。Gaussian phase estimation 产生近无偏 estimator，variance 可调；量子求和把长度 \(d\) inner product 的 entry queries 降到平方根级。

对 \(d\) 个 coordinates 分配不同精度并在 power iteration 中容忍噪声，第一算法总时间约

\[ \widetilde O(d^{7/4}) \]

（精度/gap 因子另计），比逐行 \(d^{3/2}\) 每轮再高精度重复更精细。

5. 方法二：State Matvec + Unbiased Pure-State Tomography

更快算法：

  1. Block-encode/相干应用 \(A\) 得 \(|y\rangle\propto A|x\rangle\)；

  2. 用 time-efficient unbiased pure-state tomography 输出 random classical estimator \(\widehat y\)；

  3. 保证 $\( \mathbb E[\widehat y]\approx y, \)$ 且 covariance/尾界适合 robust power analysis；

  4. 归一化后进入下一轮。

Tomography 不要求每次重建到最终 \(\epsilon\)；独立噪声在 spectral gap contraction 下不累积为 adversarial bias。配合快速 state preparation 与 randomized coordinate recovery，总时间

\[ d^{3/2+o(1)} \]

对 constant gap/error，且显式输出 \(d\) 坐标。

6. Lower bound 与 top-\(q\) 子空间

Classical adversary 可把决定 top eigenvector 的小 rank perturbation藏在 \(d^2\) entry 中，少于 \(\Omega(d^2)\) queries 难发现。Quantum adversary/communication reduction给

\[ \widetilde\Omega(d^{3/2}) \]

，所以第二算法近最优，不可能仅因输出 \(d\) 数就做到 \(O(d)\) entry queries。

要输出 top-\(q\) eigenspace，可用 deflation/block subspace iteration：维护 \(d\times q\) classical orthonormal basis，量子加速每列 matvec，成本

\[ q,d^{3/2+o(1)} \]

另含相邻 eigenvalue gap 与 reorthogonalization。

7. 小例子

\[\begin{split} A=\begin{pmatrix}2&1\\1&2\end{pmatrix}. \end{split}\]

\(v_1=(1,1)/\sqrt2\)、\(\lambda_1=3\)；\(v_2=(1,-1)/\sqrt2\)、\(\lambda_2=1\)。从 \(x_0=(1,0)=(v_1+v_2)/\sqrt2\)：

\[ A^tx_0=\frac1{\sqrt2}(3^tv_1+v_2), \]

归一化 error 以 \((1/3)^t\) 衰减。若每轮 matvec 有零均值小噪声，gap 会压低旧误差；固定方向 bias 则可能累积，这解释“unbiased”关键。

8. 小结与习题

  • Power method 收敛由 eigenvalue ratio/gap 和初始 overlap 控制。

  • 量子 matvec state 不等于 classical eigenvector 输出；tomography 是核心成本。

  • 无偏、受控 variance 的近似 matvec 可在 gap contraction 下迭代。

  • \(d^{3/2+o(1)}\) 算法接近量子 lower bound，优于 classical entry-query \(d^2\)。

  1. 推导 power-method error bound。

  2. 对 \(2\times2\) 例子算 \(t=1,2\) 的归一化向量。

  3. 解释 adversarial bias 与 zero-mean noise 的不同累积。

  4. 讨论 eigenvalue gap 缩为 \(1/d\) 时迭代数变化。

参考文献