# 主特征向量的经典输出：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. 小例子

$$
A=\begin{pmatrix}2&1\\1&2\end{pmatrix}.
$$

$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$ 时迭代数变化。

## 参考文献

- Zoo 编号 462：Chen、Gilyén 与 de Wolf, [A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix](https://arxiv.org/abs/2405.14765).