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

给定一个 Hermitian 矩阵 $A$ 的 entry 查询入口，能否用量子算法快速求出它的主特征向量（principal eigenvector，即最大特征值对应的特征向量）？如果只要求输出一个量子态 $|v_1\rangle$，在 block-encoding 模型下相位估计类的方法可以相当直接地做到这一点；本教程关心的是更难、也更实用的问题：把 $v_1$ 的全部 $d$ 个经典坐标显式地写出来。Chen、Gilyén 与 de Wolf 在这个"经典输出"设定下给出了时间复杂度 $d^{1.5+o(1)}$ 的量子算法，优于经典 entry-query 模型下的 $\Omega(d^2)$ 下界，并几乎匹配量子下界 $\widetilde\Omega(d^{3/2})$。

这篇教程的目标是把这个结果讲清楚：经典 power method 的收敛性由什么控制、为什么"能量子地做出矩阵–向量乘法"不等于"能输出经典特征向量"、以及两个关键想法——容忍有结构噪声的 robust power iteration 与无偏（unbiased）的高效纯态 tomography——如何把复杂度压到 $d^{3/2+o(1)}$。读完全文，你应当能自己推导出 power method 的误差界，能说清 $d^{7/4}$ 与 $d^{3/2}$ 两个复杂度里每个因子的来历，并理解为什么"无偏"二字是整个算法的命门。

本课知识点

问题设定与 gap promise——能写出 entry oracle 与"输出经典向量、误差按相位取最小"的目标定义，并解释为什么必须有特征值间隙承诺。
power method 的谱分析与误差界——能从谱展开出发推导误差界 $\min_\omega\|x_t-\omega v_1\|_2=O\bigl(\frac{\sqrt{1-|c_1|^2}}{|c_1|}r^t\bigr)$，并说明比值 $r$ 与初始重叠 $|c_1|$ 两个因子的来历。
随机初态与迭代复杂度——能计算随机初态的期望重叠 $\mathbb E|c_1|^2=1/d$，并推出常数间隙下所需的迭代轮数与经典总成本 $O(d^2\log(d/\epsilon))$。
相干 matvec 与读出瓶颈——能说明相干 matvec 近似实现的映射 $|x\rangle\mapsto A|x\rangle/\|Ax\|$，并解释为什么逐轮高精度 tomography 会把量子优势吃掉。
良性噪声与鲁棒迭代原则——能比较系统性偏差与零均值噪声的累积方式，写出"无偏优先、精度随迭代调度"两条设计原则。
Gaussian phase estimation 与精度分配——能计算逐坐标估计的每轮查询成本，并解释按坐标与按轮次的精度分配如何把总复杂度压到 $\widetilde O(d^{7/4})$。
无偏纯态 tomography 与收敛分析——能用间隙收缩解释旧误差为何被"洗掉"、无偏性为何不可替代，并比较 $d^{7/4}$ 与 $d^{3/2}$ 两个指数的来历。
查询下界与最优性——能复述经典 $\Omega(d^2)$ 与量子 $\widetilde\Omega(d^{3/2})$ 下界的论证直觉，并判断两个算法各自距离最优还有多远。

1. 问题背景与动机¶

1.1 主特征向量从哪里来¶

主特征向量是线性代数中出现频率最高的对象之一。几个典型来源：

谱方法与数据分析：主成分分析（PCA）取协方差矩阵的前几个特征向量作为数据的低维表示，第一个特征向量就是方差最大的方向；谱聚类、维度约化也都以特征向量为基本构件。
图与网络：邻接矩阵或转移矩阵的主特征向量携带图的重要全局信息（例如某些中心性度量与稳态分布的计算都与主特征向量密切相关）。
物理与化学：哈密顿量的基态就是最小特征值对应的特征向量；把 $A$ 换成 $-H$（或 $e^{-\beta H}$ 一类的函数），"主特征向量"就对应基态。

这些应用有一个共同点：真正想要的不是"一个存在于一台量子计算机里的态"，而是写在纸上的 $d$ 个数——后续的经典处理（画图、排序、代入别的计算）都需要显式坐标。这是本教程与很多"输出量子态"的量子算法（如相位估计制备特征态）之间的本质区别。

1.2 经典算法能做什么，瓶颈在哪里¶

经典地求 Hermitian 矩阵的主特征向量，标准方法是 power iteration（幂迭代）及其加速版（Krylov 子空间方法，如 Lanczos 算法）。它们的共同骨架是：反复做矩阵–向量乘法（matvec）$x \mapsto Ax$，利用特征值之间的间隙把 $v_1$ 方向"放大"出来。第 3 节会完整分析：当特征值相对间隙是常数时，收敛只需要 $O(\log(d/\epsilon))$ 次 matvec。

瓶颈不在迭代次数，而在单次 matvec 的成本：一个稠密 $d\times d$ 矩阵有 $d^2$ 个 entry，做一次 $Ax$ 必须读完整个输入，即 $\Theta(d^2)$ 次 entry 操作。这不是某个具体算法的缺点——后面第 7 节会看到，$\Omega(d^2)$ 是经典 entry-query 模型下的下界：任何经典算法想确定主特征向量，最坏情况下都得翻开几乎所有 entry。换句话说，经典算法在"读输入"这一步就已经被卡死在 $d^2$。

1.3 量子算法的真正障碍：输出是经典向量¶

但请注意输出的形态：这些子程序交付的是一个量子态，而我们需要的是 $d$ 个经典坐标。从量子态提取经典描述要做 tomography（态层析，ch07），而对一个 $d$ 维纯态做高精度层析的成本是关于 $d$ 多项式且精度越高越贵——如果每一轮迭代都把中间向量高精度地读出来，总成本很容易退回 $\Omega(d^2)$ 甚至更差，量子优势荡然无存。

因此本问题的真正难点可以浓缩为一句话：如何在"每轮只能得到带噪声的经典近似 matvec"的条件下，让整个 power iteration 仍然收敛，并把读出成本摊薄。 答案由两部分组成：

matvec 的误差不需要很小，但必须是有结构的、近似无偏的——零均值噪声会被特征值间隙持续压缩，而有方向的系统性偏差会累积；
tomography 不需要每轮都做到最终精度——旧的估计误差会被后续迭代的间隙收缩"洗掉"，只有最近几轮的误差真正影响输出。

1.4 历史与本文定位¶

Power iteration 是数值线性代数的经典方法（可追溯至 von Mises 的迭代法），配合 Krylov 子空间技术至今仍是经典求特征向量的主力；其收敛由特征值比率控制是教科书结果。量子方面，相位估计制备特征态早已是标准工具，但"输出主特征向量的经典描述"在 entry-query 模型下长期没有已知的量子加速——障碍正是上面说的读出瓶颈。Chen、Gilyén 与 de Wolf（arXiv:2405.14765，Zoo 编号 462）给出了该模型下第一个多项式级量子加速：两个算法分别用 $\widetilde O(d^{7/4})$ 与 $d^{3/2+o(1)}$ 时间输出主特征向量的经典近似，并证明了经典 $\Omega(d^2)$、量子 $\widetilde\Omega(d^{3/2})$ 的查询下界，从而第二个算法在 $d$ 的指数上基本最优。本教程以该文为主线。

前置知识。我们假设读者熟悉本教程第 1–8 章的内容：量子力学与量子计算基础、QFT 与相位估计、Grover 与振幅放大、block-encoding 与 QSP/QSVT 的基本概念、以及纯态 tomography 的常识（读出 $d$ 维态的经典描述需要随 $d$ 增长的样本数）。这些工具我们直接引用结论，不再重新推导。

2. 问题陈述与 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, \]

即给定行指标 $i$、列指标 $j$，oracle 把矩阵元 $A_{ij}$ 以可逆方式（异或到第三个寄存器）返回。这是"矩阵作为输入被逐项查询"的标准模型；经典模型对应于普通地读取 $A_{ij}$。一次量子查询可以在 $(i,j)$ 上叠加，这是量子加速的唯一来源。

记 $A$ 的特征值与对应的正交归一特征向量为

\[ \lambda_1>\lambda_2\ge\cdots\ge\lambda_d, \qquad Av_j=\lambda_j v_j . \]

$\lambda_1$ 严格最大，所以 $v_1$（在相位意义下）唯一。我们假设 top eigengap（或比值）有常数或已知的下界：存在已知 $\Delta>0$ 使 $\lambda_1-\lambda_2\ge\Delta$，或者等价地知道相对间隙 $\delta$ 使 $|\lambda_j|/\lambda_1\le 1-\delta$ 对 $j\ge2$ 成立（第 3 节会看到，收敛速度由比值控制，所以"已知下界"就够了）。这就是标题里的 gap promise。

目标是输出一个经典向量 $\widetilde v\in\mathbb C^d$，满足

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

为什么目标里有一个对相位 $\omega$ 取最小值？因为特征向量本身只定义到相位：若 $Av_1=\lambda_1 v_1$，则 $e^{i\theta}v_1$ 也是同样合格的特征向量，任何算法都无法区分它们（量子态的整体相位本来就不可观测）。所以误差只能在"差一个相位"的意义下定义。对实矩阵，相位退化为正负号：输出 $-v_1$ 与 $v_1$ 应视为同样正确。

为什么必须有 gap promise？ 直观地说，如果 $\lambda_1$ 与 $\lambda_2$ 任意接近，那么 $v_1$ 与 $v_2$ 张成的二维子空间内，"哪个方向是第一特征向量"对矩阵元极其敏感：对 $A$ 做一个范数远小于间隙的小扰动，主特征向量可以在该子空间内转过 $O(1)$ 的角度。定量地说，特征向量的扰动界（Davis–Kahan 型的 sin-$\theta$ 定理）具有"扰动大小除以间隙"的形式，间隙趋于零时界发散。这意味着任何输出 $\widetilde v\approx v_1$ 的算法，其复杂度必然含有 $1/\Delta$（或 $1/\delta$）一类的因子；没有间隙下界，问题本身就不适定。因此下文的复杂度表达式都默认带着对 gap 的依赖，我们主要在"常数级 gap"的设定下比较 $d$ 的指数。

3. 经典 power method：完整分析¶

power method 是整个故事的出发点：两个量子算法本质上都是"带噪声的 power iteration + 量子加速的近似 matvec"。这一节把经典版本的每一步推导补齐，后面分析噪声鲁棒性时可以直接套用。

3.1 迭代格式与谱展开¶

任取单位向量 $x_0$ 作为初态，power iteration 反复做"乘 $A$、归一化"：

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

为什么这会逼近 $v_1$？因为 Hermitian 矩阵有正交归一特征基 $\{v_j\}$，任何向量都可以按它展开。写

\[ x_0=\sum_{j=1}^d c_j v_j, \qquad c_j:=\langle v_j,x_0\rangle, \qquad \sum_j|c_j|^2=1, \]

并假设 $c_1\ne0$（$x_0$ 与 $v_1$ 不正交；随机取初态时这以概率 1 成立）。由 $Av_j=\lambda_j v_j$ 立刻有 $A^t v_j=\lambda_j^t v_j$，于是

\[ A^t x_0=\sum_{j=1}^d c_j\lambda_j^t v_j =\lambda_1^t\left( c_1 v_1+\sum_{j>1}c_j\left(\frac{\lambda_j}{\lambda_1}\right)^t v_j \right). \]

第二步只是把最大的一项 $\lambda_1^t$ 提出括号（这里默认 $\lambda_1>0$ 且 $\lambda_1$ 按模严格最大；若 $\lambda_1<0$ 或存在 $|\lambda_d|>\lambda_1$ 的情形，把讨论中的 $\lambda_j/\lambda_1$ 换成模的比值即可，结论形式不变）。括号里的第一项是要的方向 $c_1 v_1$，第二项是"污染"，其中每个分量都被压了因子 $(\lambda_j/\lambda_1)^t$。由于 $|\lambda_j/\lambda_1|<1$，这些因子随 $t$ 指数衰减——间隙越大，污染被压得越快，这就是 power method 收敛的全部机理。

3.2 误差界：逐步推导¶

现在把"指数衰减"变成定量的误差界。记比值

\[ r:=\max_{j\ge2}\left|\frac{\lambda_j}{\lambda_1}\right|<1, \]

以及括号里的污染项

\[ w_t:=\sum_{j>1}c_j\left(\frac{\lambda_j}{\lambda_1}\right)^t v_j . \]

由于 $\{v_j\}$ 正交归一，勾股定理（Parseval 恒等式）给出

\[ \|w_t\|_2^2 =\sum_{j>1}|c_j|^2\left|\frac{\lambda_j}{\lambda_1}\right|^{2t} \le r^{2t}\sum_{j>1}|c_j|^2 =r^{2t}\bigl(1-|c_1|^2\bigr), \]

第一步用正交归一性把范数平方化为系数模方和；第二步把每个比值放大到最大值 $r$；第三步用归一化条件 $\sum_j|c_j|^2=1$。所以

\[ \|w_t\|_2\le r^t\sqrt{1-|c_1|^2}. \]

未归一化的向量 $A^tx_0/\lambda_1^t=c_1v_1+w_t$ 与方向 $v_1$ 的偏差由 $\|w_t\|$ 控制，而归一化（除以向量总长）不会放大这个相对偏差：$x_t$ 与 $v_1$ 夹角 $\theta_t$ 满足（以 $c_1 v_1$ 为邻边、$w_t$ 为垂直方向的直角三角形估计）

\[ \sin\theta_t =\frac{\|w_t\|_2}{\|c_1v_1+w_t\|_2} \le\frac{\|w_t\|_2}{|c_1|-\|w_t\|_2} =\frac{r^t\sqrt{1-|c_1|^2}}{|c_1|-r^t\sqrt{1-|c_1|^2}}, \]

其中第二步用三角不等式 $\|c_1v_1+w_t\|\ge|c_1|-\|w_t\|$，要求分母为正（即污染还没有盖过信号）。当右端小于 $1/2$ 时（这在我们关心的参数范围内很快成立），分母中的减项只贡献常数因子，于是

\[ \sin\theta_t =O\!\left( \frac{\sqrt{1-|c_1|^2}}{|c_1|}\,r^t \right). \]

最后把夹角换成目标里的 $\ell_2$ 距离：取相位 $\omega$ 使 $\omega v_1$ 与 $x_t$ 同相，则 $\min_\omega\|x_t-\omega v_1\|_2=2\sin(\theta_t/2)\le\sqrt2\sin\theta_t$。合并起来，power method 的误差界为

\[ \min_{|\omega|=1}\|x_t-\omega v_1\|_2 =O\!\left( \frac{\sqrt{1-|c_1|^2}}{|c_1|} \left|\frac{\lambda_2}{\lambda_1}\right|^t \right), \]

即在常数相对间隙的设定下 $r=|\lambda_2/\lambda_1|$。这个表达式里每个因子都有明确含义：比值 $r$ 的 $t$ 次方来自"每迭代一次污染被压缩一次"；前置因子 $\sqrt{1-|c_1|^2}/|c_1|$ 是初态中"污染总量与信号强度之比"。

3.3 初始重叠：随机初态有多好¶

误差界里唯一的随机量是 $|c_1|=|\langle v_1,x_0\rangle|$。若取 $x_0$ 为均匀随机单位向量，它有多大？由对称性，随机单位向量在任何固定方向上的期望模方都相等，而 $d$ 个方向（取一组含 $v_1$ 的正交归一基）的模方之和为 1，所以

\[ \mathbb E|c_1|^2=\frac1d, \]

并且集中不等式保证以高概率 $|c_1|=\Theta(d^{-1/2})$（不会比 $1/\sqrt d$ 小太多）。代入误差界，前置因子

\[ \frac{\sqrt{1-|c_1|^2}}{|c_1|} \approx\frac{1}{|c_1|} =\Theta(\sqrt d). \]

也就是说，随机初始化只是多付出一个 $\sqrt d$ 的"启动代价"，而它出现在对数里（见下），几乎不影响迭代数。

3.4 迭代次数与总复杂度¶

要求误差降到 $\epsilon$，即要求

\[ \frac{\sqrt{1-|c_1|^2}}{|c_1|}r^t\le\epsilon \quad\Longleftrightarrow\quad r^t\le\frac{\epsilon|c_1|}{\sqrt{1-|c_1|^2}} \approx\frac{\epsilon}{\sqrt d}. \]

两边取对数（注意 $\log r<0$），解出

\[ t\ge\frac{\log(\sqrt d/\epsilon)}{\log(1/r)}. \]

若相对间隙为常数 $\delta$，即 $r\le1-\delta$，则由 $-\log(1-\delta)\ge\delta$（对 $0<\delta<1$ 成立的常用不等式，可由 $\log$ 的凸性或泰勒展开得到）有 $\log(1/r)\ge\delta=\Omega(1)$，于是

\[ t=O\!\left(\frac1\delta\log\frac{d}{\epsilon}\right) =O\!\left(\log\frac{d}{\epsilon}\right) \quad(\delta\text{ 为常数}). \]

迭代次数只有对数级——power method 很快。但每一轮的成本是一次稠密 matvec：计算 $Ax$ 的每个坐标 $(Ax)_i=\sum_jA_{ij}x_j$ 要读一整行 $d$ 个 entry，$d$ 个坐标共 $d^2$ 次 entry 操作。总成本

\[ O\!\left(d^2\log\frac{d}{\epsilon}\right). \]

关键是：每做一轮 matvec 就已经触及整个输入，所以 $d^2$ 是经典算法绕不开的地板；第 7 节的下界会说明这不是算法不够好，而是模型本身的限制。量子算法要赢，就必须让单轮 matvec（哪怕是近似的）的查询成本显著低于 $d^2$——而且最好连"迭代 $\times$ 读出"的总账也低于 $d^2$。

4. 为什么量子态 matvec 还不够¶

4.1 量子能做什么：相干 matvec¶

假设我们能从 entry oracle 构造 $A$ 的 block-encoding $U_A$（ch05 介绍过 block-encoding 的标准概念：把 $A/\alpha$ 嵌为某个酉矩阵的左上角块，$\alpha$ 为归一化因子）。配合把经典向量 $x$ 制备成量子态 $|x\rangle$ 的 state-preparation 子程序，再辅以振幅放大处理成功概率，我们可以近似实现映射

\[ |x\rangle\;\longmapsto\;\frac{A|x\rangle}{\|Ax\|}, \]

即以量子态的形式完成一步"乘 $A$ 并归一化"。若下一轮迭代只需要量子态作为输入，这个流程可以串起来：$|x_0\rangle\to|x_1\rangle\to\cdots\to|x_t\rangle$，末态就是 $|v_1\rangle$ 的好近似。事实上这正是"量子相位估计制备特征态"路线的基本形态。

4.2 障碍：读出¶

问题在于终点。我们要的不是 $|v_1\rangle$，而是它的 $d$ 个坐标。把 $d$ 维纯态逐坐标读成经典向量是纯态 tomography 的任务（ch07），其样本复杂度随维度 $d$ 增长、随精度提高而上升；要在 $\ell_2$ 误差 $\epsilon$ 内重建，朴素高精度层析的成本可达 $d/\epsilon^2$ 量级甚至更高（具体系数取决于层析方案与模型）。如果把这种高精度读出嵌进每一轮迭代（因为下一轮需要经典的 $x$ 来做 state preparation），总成本是"迭代数 $\times$ 每轮 tomography"，很容易回到 $d^2/\epsilon^2$ 甚至更差——比经典 power method 还慢。

所以困难不在"做 matvec"，而在迭代与读出之间的接口：量子态必须被经典化才能进入下一轮，而经典化是整条流水线上最贵的工序。

4.3 突破口：误差可以粗糙，但必须"良性"¶

突破口来自对 power iteration 误差结构的重新审视。设第 $t$ 轮我们没有算出精确的 $y=Ax_t$，只得到一个带噪声的估计 $\widehat y=y+e_t$。把噪声项代入 3.2 节的分析，可以发现两类噪声的命运截然不同：

有方向的系统性偏差（adversarial bias）：如果每轮误差都朝着同一个有害方向（比如始终把估计往某个垂直于 $v_1$ 的方向推），那么每轮新增的偏差只被间隙压缩一次、却不断有新的进来，最坏情形下稳态误差按几何级数 $\sigma(1+r+r^2+\cdots)=\sigma/(1-r)$ 累积，且这个误差是确定的、相干的；
零均值、逐轮独立的噪声（benign / unbiased noise）：若 $\mathbb E[e_t]\approx0$，误差的各次投影是随机涨落而非同向推进，典型累积按平方根增长（类似随机游走），而间隙收缩仍在每一轮把旧误差乘上 $r<1$。结果是：最终输出的误差主要由最近几轮的噪声决定，早期粗糙的估计会被后续迭代"洗掉"。

由此得到算法设计的两条原则，它们贯穿后面两个算法：

无偏性优先于精度：一个方差较大但均值为零的估计器，优于一个方差小但有系统性偏差的估计器——后者会污染收敛方向本身；
精度可以随迭代调度：不必每轮都做到最终精度 $\epsilon$，把高精度留到最后几轮即可，从而把 tomography/估计的总成本大幅摊薄。

5. 方法一：逐 entry 的 Gaussian Phase Estimation¶

第一个算法把 matvec 完全经典化：给定当前经典近似 $x$（单位向量），逐个坐标地估计

\[ y_i=(Ax)_i=\sum_{j=1}^d A_{ij}x_j, \qquad i=1,\dots,d, \]

每个坐标是一个长度 $d$ 的内积。

5.1 内积作为均值，量子求和的平方根加速¶

先看经典地算一个 $y_i$ 要多少查询：精确算要读整行 $d$ 个 entry。但如果我们只要求加性误差 $\sigma$ 的估计，可以把 $y_i$ 看成均值问题：取指标 $j$ 均匀随机，随机变量 $d\,A_{ij}x_j$ 的期望正是 $y_i$。经典 Monte Carlo 的均方误差以 $1/\sqrt{T}$ 收敛（$T$ 为样本数），达到加性误差 $\sigma$ 需要 $T=\Theta(1/\sigma^2)$ 次采样，即 $\Theta(1/\sigma^2)$ 次 entry 查询。

量子地，同一个均值问题可以用振幅估计/量子求和来做：把"按权重叠加 + 查询 + 相位回踢"组织成一个相位估计问题，达到同样加性误差 $\sigma$ 只需 $\widetilde O(1/\sigma)$ 次查询——相对经典的 $1/\sigma^2$ 是平方根级的加速。这就是"量子求和把长度 $d$ 的内积的 entry 查询降到平方根级"的含义：注意被省掉的是对精度 $\sigma$ 的依赖指数，而不是说单个内积只要 $\sqrt d$ 次查询；在这个逐坐标方案里，$d$ 的节省来自对所有坐标和精度的统一调度（见 5.3）。

5.2 为什么要"Gaussian" phase estimation¶

普通的相位估计给出的估计值分布有比较重的尾巴和结构化的舍入误差；直接把内积值粗放进相位寄存器再估计，误差未必零均值。这里采用的技巧是：制备一个近 Gaussian 的 pointer 态，让待求的内积以平移/相位的形式编进 pointer，再做相位估计。这样得到的估计器近似是一个以真值为中心的 Gaussian 随机变量：

\[ \widehat y_i\approx y_i+\eta_i, \qquad \mathbb E[\eta_i]\approx0, \]

且方差 $\mathbb E[\eta_i^2]$ 可以通过加大相位估计的精度来调节（更精确的估计花更多查询）。近无偏性正是 4.3 节要求的第一条性质：逐轮独立的近零均值噪声在 robust power 分析下不会相干累积。这套构造常被称为 Gaussian phase estimation。

5.3 精度分配与复杂度¶

粗算一笔账作为基线：若对每个坐标用统一精度 $\sigma$，则输出向量的 $\ell_2$ 误差为

\[ \|\widehat y-y\|_2 \approx\sqrt{d}\,\sigma, \]

要求它不超过本轮预算 $\epsilon_{\rm rd}$，即 $\sigma=\epsilon_{\rm rd}/\sqrt d$。每个坐标花 $\widetilde O(1/\sigma)=\widetilde O(\sqrt d/\epsilon_{\rm rd})$ 次查询，$d$ 个坐标合计每轮

\[ d\cdot\widetilde O\!\left(\frac{\sqrt d}{\epsilon_{\rm rd}}\right) =\widetilde O\!\left(\frac{d^{3/2}}{\epsilon_{\rm rd}}\right) \]

次查询。也就是说，逐坐标、统一精度的量子 matvec 每轮约 $d^{3/2}$ 次查询（取 $\epsilon_{\rm rd}$ 为常数），已经优于经典一轮的 $d^2$；若再乘以迭代数并对最后几轮提高精度，总成本会滑向 $d^{3/2}\cdot(\text{高精度轮的开销})$，并不理想。

第一个算法的改进在于更精细的精度分配：

不同坐标分配不同精度——贡献大的坐标（$|x_j|$ 分布集中的行）给高精度，其余给低精度，使"总查询数 = $\sum_i\widetilde O(1/\sigma_i)$"在固定 $\ell_2$ 误差预算下最小化；
不同迭代轮次分配不同精度——早期轮次用很粗糙的估计（便宜），精度随收敛进程逐步提高，利用 4.3 节"旧误差被间隙洗掉"的观察。

把这两项调度做最优后，整个 robust power iteration 的总时间压到约

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

（精度 $\epsilon$ 与 gap 的因子另计）。注意 $7/4=1.75<2$：即便把全部 $d$ 个坐标都经典地写出来，总查询仍然低于经典模型的 $\Omega(d^2)$ 下界，这已经是严格的量子加速；但 $7/4$ 与下界 $3/2$ 之间还有缝隙，原因是逐坐标估计没有把"输出是一个量子态的中间形态"利用起来。下一个算法补上这一点。

6. 方法二：量子态 Matvec + 无偏纯态 Tomography¶

更快的算法把"相干 matvec"（4.1 节）与"良性读出"（4.3 节）拼在一起，避免逐坐标估计。一轮迭代的流程是：

相干 matvec：用 block-encoding $U_A$ 与 state preparation，以高成功振幅（配合振幅放大）制备 $$ |y\rangle\propto A|x\rangle, $$ 其中 $|x\rangle$ 是上一轮经典近似 $x$ 的相干编码；
无偏 tomography：对 $|y\rangle$ 做 time-efficient 的无偏纯态层析，输出一个随机的经典向量 $\widehat y$，它是 $y$ 的估计器；
无偏性与尾界：层析方案保证 $$ \mathbb E[\widehat y]\approx y, $$ 并且协方差/尾界受控（典型要求如 $\mathbb E|\widehat y-y|^2$ 有界、大偏差指数衰减），恰好满足 robust power 分析对噪声的要求；
归一化并进入下一轮：令 $x\leftarrow\widehat y/\|\widehat y\|$，回到第 1 步；轮次安排与精度调度沿用"早期粗糙、后期精细"的原则。

6.1 为什么这条路更快¶

与方法一对比，关键在于读出的组织方式。逐坐标估计为每个坐标独立地支付"相位估计的精度代价"，而纯态层析把 $d$ 个坐标作为一个整体来读：它从 $|y\rangle$ 的拷贝中提取全部坐标的信息，存在时间效率接近"每份拷贝摊到一个坐标的有效信息"的层析方案，使得在本算法所需的误差水平下，单轮读出成本可以压到接近线性（$d^{1+o(1)}$ 量级）而不是方法一那种 $d^{3/2}$ 每轮的形态。这里节省的正是方法一中"逐坐标重复支付精度开销"的部分。

6.2 为什么收敛：无偏噪声 + 间隙收缩¶

鲁棒性分析与 4.3 节一致，现在可以更具体一点。设第 $t$ 轮的读出噪声为 $e_t=\widehat y_t-y_t$，满足 $\mathbb E[e_t]\approx0$、各轮独立。把 $e_t$ 按特征基分解：$v_1$ 方向的分量只改变归一化（无害，只影响相位与长度），垂直于 $v_1$ 的分量才是角度误差。第 $t$ 轮注入的垂直误差，在之后的每一轮都被乘上因子 $r=|\lambda_2/\lambda_1|<1$；到第 $T$ 轮输出时，第 $t$ 轮噪声的残留为 $r^{T-t}e_t$。因此输出误差主要来自最后几轮：

\[ \Bigl\|\sum_{t\le T} r^{T-t}e_t\Bigr\| \;\lesssim\; \sum_{s\ge0}r^s\|e_{T-s}\| \;\approx\;\frac{\sigma_{\rm final}}{1-r}, \]

其中 $\sigma_{\rm final}$ 是最后几轮的噪声水平——这就是为什么 tomography 不必在每轮都做到最终精度 $\epsilon$：只要最后一两轮做到 $\sim\epsilon(1-r)$，更早轮次的粗误差已被 $r$ 的幂次压掉。而"无偏"保证上式中的随机和不会系统性地偏向某个方向：各轮的 $e_t$ 均值为零且独立，典型大小按平方根累计而非线性累计。若误差带有固定方向的 bias，上式中的随机和会变成确定性的相干累加，同样大小的逐轮噪声会造成大得多的最终偏差——这正是"unbiased"不可或缺的原因。

6.3 总复杂度¶

配合快速 state preparation（把经典 $x$ 相干编码）与 randomized coordinate recovery（把层析输出组织成满足无偏与尾界要求的经典估计器），在常数 gap、常数最终误差的设定下，整个迭代的总时间为

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

并且算法显式输出全部 $d$ 个坐标。与方法的复杂度相比：$d^{3/2+o(1)}<d^{7/4}<d^2$，第二个算法把方法一里逐坐标相位估计的冗余彻底消除，指数从 $7/4$ 降到 $3/2$。下一节将看到，$3/2$ 正好顶到量子下界，所以在 $d$ 的指数上已没有本质改进空间（剩下的 $o(1)$ 来自对数因子与精细的调度）。

7. 下界与 top-$q$ 子空间推广¶

7.1 经典下界 $\Omega(d^2)$¶

经典 entry-query 模型下，任何输出主特征向量好近似的算法都需要 $\Omega(d^2)$ 次查询。对抗论证的直觉是"草堆藏针"：对手构造一对矩阵，它们在绝大多数 entry 上相同，只在某一小片 entry（一个小秩扰动）上不同，而这个小秩扰动恰好决定主特征向量的方向。扰动可以藏在 $d^2$ 个 entry 的任意位置，经典算法不翻开几乎每个 entry 就无法排除"针藏在没读过的地方"的可能，于是最坏情况下需要 $\Omega(d^2)$ 次查询。这把 3.4 节的观察"每轮 matvec 已读遍输入"升级为模型级的下界：经典算法在查询意义下已经最优，不可能有渐近更快的经典算法。

7.2 量子下界 $\widetilde\Omega(d^{3/2})$¶

量子情形，同一个"藏针"矩阵对仍然可以用，但 Grover 搜索告诉我们：在 $d^2$ 个 entry 中找一个标记位置，量子只需 $O(d)$ 次查询——所以简单的搜索归约只给出 $\Omega(d)$，太弱。真正的下界 $\widetilde\Omega(d^{3/2})$ 来自更精细的量子 adversary 方法与通信复杂度归约：把某个已知需要 $\widetilde\Omega(d^{3/2})$ 通信/查询的问题编码进"求主特征向量"，使得任何 $T$ 查询的量子算法都能转回去解那个难题，从而 $T=\widetilde\Omega(d^{3/2})$。

这个下界有一个重要推论：不可能仅因输出 $d$ 个数就做到 $O(d)$ 次 entry 查询。尽管"写出 $d$ 个坐标"听上去只要 $d$ 步，查询复杂度的瓶颈不在写，而在为了确定这些坐标必须向 oracle 索取的信息量——这个量就是 $\widetilde\Omega(d^{3/2})$。于是第二个算法的 $d^{3/2+o(1)}$ 与下界在 $d$ 的指数上吻合，仅剩对数级的缝隙。

7.3 推广：输出 top-$q$ 特征子空间¶

同样的框架可以推广到求前 $q$ 个特征向量张成的子空间。思路是 deflation / block subspace iteration（块子空间迭代）：不再迭代单个向量，而是维护一个 $d\times q$ 的经典矩阵，其 $q$ 列保持（近似）正交归一，每轮对每列各做一次（量子加速的）近似 matvec，然后重新正交化。经典地这对应把 power method 换成子空间迭代；量子地，每列的 matvec 与读出沿用方法二的无偏 tomography 流程，$q$ 列的成本近似相加：

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

另含对相邻特征值间隙（第 $q$ 与第 $q+1$ 个特征值之间的 gap，它替代了 top gap 的角色）与 reorthogonalization（重新正交化）的依赖。当 $q$ 是常数时，这仍与单特征向量情形同阶。

8. 小例子：$2\times2$ 矩阵的完整计算¶

用一个可以手算到底的例子，把第 3 节的抽象推导和第 6 节的噪声讨论都演一遍。取

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

特征分解。 特征方程 $\det(A-\lambda I)=(2-\lambda)^2-1=0$ 给出 $\lambda_1=3$、$\lambda_2=1$。代入 $(A-\lambda I)v=0$：$\lambda_1=3$ 对应 $v_1=(1,1)/\sqrt2$（两分量相等）；$\lambda_2=1$ 对应 $v_2=(1,-1)/\sqrt2$（两分量相反）。相对间隙 $r=\lambda_2/\lambda_1=1/3$。

精确演化。 取初态 $x_0=(1,0)$。注意

\[ x_0=\frac{v_1+v_2}{\sqrt2}, \qquad\text{即 }c_1=c_2=\frac1{\sqrt2}. \]

（验证：$(v_1+v_2)/\sqrt2=\frac12(1+1,\,1-1)=(1,0)$。）于是

\[ A^t x_0 =\frac{1}{\sqrt2}\bigl(3^t v_1+1^t v_2\bigr) =\frac12\bigl(3^t+1,\;3^t-1\bigr), \]

第二步把 $v_1,v_2$ 的分量代进去合并：第一分量 $\frac{1}{\sqrt2}(3^t\cdot\frac{1}{\sqrt2}+1\cdot\frac{1}{\sqrt2})=\frac{3^t+1}{2}$，第二分量 $\frac{1}{\sqrt2}(3^t\cdot\frac{1}{\sqrt2}-1\cdot\frac{1}{\sqrt2})=\frac{3^t-1}{2}$。

逐轮归一化向量。 计算范数

\[ \|A^tx_0\|^2=\frac{(3^t+1)^2+(3^t-1)^2}{4}=\frac{2\cdot9^t+2}{4}=\frac{9^t+1}{2}, \]

所以

\[ x_t=\frac{(3^t+1,\;3^t-1)}{\sqrt{2(9^t+1)}}. \]

具体地：$t=1$ 时 $Ax_0=(2,1)$，$\|(2,1)\|=\sqrt5$，$x_1=(2,1)/\sqrt5$；$t=2$ 时 $A(2,1)=(5,4)$，$\|(5,4)\|=\sqrt{41}$，$x_2=(5,4)/\sqrt{41}$。与公式核对：$t=1$ 给出 $(3+1,3-1)/\sqrt{2(9+1)}=(4,2)/\sqrt{20}=(2,1)/\sqrt5$ ✓。

误差衰减。 与 $v_1$ 的内积为

\[ \langle v_1,x_t\rangle =\frac{(3^t+1)+(3^t-1)}{\sqrt2\cdot\sqrt{2(9^t+1)}} =\frac{3^t}{\sqrt{9^t+1}} =\frac{1}{\sqrt{1+9^{-t}}}. \]

因为两个向量都是单位向量，

\[ \min_{\omega=\pm1}\|x_t-\omega v_1\|^2 =2-2\langle v_1,x_t\rangle =2-\frac{2}{\sqrt{1+9^{-t}}}. \]

用泰勒展开 $1/\sqrt{1+u}=1-\frac u2+O(u^2)$（$u=9^{-t}$），得

\[ \min_\omega\|x_t-\omega v_1\|^2=9^{-t}+O(9^{-2t}) \quad\Longrightarrow\quad \min_\omega\|x_t-\omega v_1\|\approx 3^{-t}=\left(\frac13\right)^t. \]

这正是第 3 节误差界预言的 $r^t=(1/3)^t$ 衰减（此例中 $|c_1|=1/\sqrt2$，前置因子为 1），数值上完全吻合：$t=1$ 时误差平方 $2-6/\sqrt{10}\approx0.103$，$t=2$ 时 $2-18/\sqrt{82}\approx0.0125$，比值约 $1/9$，即误差本身每轮约除以 $3$。

噪声演示。 现在模拟"每轮 matvec 带噪声"的情形。设每轮归一化后注入范数不超过 $\sigma$ 的扰动。收缩因子 $r=1/3$：

若扰动是固定方向的 bias（每轮都往同一方向推 $\sigma$），残留偏差按几何级数累加，稳态约为 $\sigma(1+\frac13+\frac19+\cdots)=\frac32\sigma$——是单轮噪声的 $1.5$ 倍，且方向确定；
若扰动是逐轮独立、零均值的噪声，各轮残留 $r^s e_{t-s}$ 方向随机，典型大小按平方和开根号累计：$\sigma\sqrt{1+\frac19+\frac1{81}+\cdots}=\sigma\sqrt{9/8}\approx1.06\,\sigma$。

同样的逐轮噪声强度，bias 的稳态影响约为零均值噪声的 $\sqrt2$ 倍且方向相干——这个 $2\times2$ 的玩具计算已经显示出两者的定性差别；在高维、且 bias 被允许"对准当前最受伤的方向"（adversarial）时，差距会进一步放大。这就是算法要求估计器无偏的根本原因。

9. 小结¶

小结。

Power method 的收敛由特征值比值 $r=|\lambda_2/\lambda_1|$（即相对间隙）与初始重叠 $|c_1|$ 控制：误差 $\approx\frac{\sqrt{1-|c_1|^2}}{|c_1|}r^t$，随机初态下 $|c_1|\sim1/\sqrt d$，常数间隙时 $t=O(\log(d/\epsilon))$。
经典瓶颈在 matvec：稠密矩阵每轮 $d^2$ 次 entry 操作，且 $\Omega(d^2)$ 是经典 entry-query 下界，经典算法已无渐近改进空间。
量子态 matvec（block-encoding + 振幅放大）不等于经典特征向量输出；把每轮中间态经典化的 tomography 才是核心成本，朴素高精度读出会把复杂度退回 $d^2$ 量级。
破局靠两条原则：matvec 误差无偏（零均值、逐轮独立）比高精度更重要；旧误差被间隙收缩洗掉，故精度只需随迭代逐步提高。
方法一（逐坐标 Gaussian phase estimation + 精度分配）给出 $\widetilde O(d^{7/4})$；方法二（相干 matvec + 无偏纯态 tomography）给出 $d^{3/2+o(1)}$，匹配量子下界 $\widetilde\Omega(d^{3/2})$ 的指数。推广到 top-$q$ 子空间的成本为 $q\cdot d^{3/2+o(1)}$（另含相邻间隙与正交化开销）。

练习题¶

练习 1【问题设定与 gap promise】（→ 第 2 节）

基础：写出 entry oracle 的作用规则 $O_A|i,j,z\rangle=|i,j,\,z\oplus A_{ij}\rangle$ 与输出目标 $\min_{|\omega|=1}\|\widetilde v-\omega v_1\|_2\le\epsilon$，并解释为什么误差定义必须对相位 $\omega$ 取最小值。
进阶：取 $A=I$（$2\times2$ 单位阵）与 $A'=I+\sigma\,uu^{\mathsf T}$，其中 $u$ 为任意单位向量、$0<\sigma<1$。验证 $A'$ 的主特征向量恰是 $u$，而两个矩阵的每个 entry 至多相差 $\sigma$；据此说明间隙趋于 0 时主特征向量对矩阵元有多敏感，以及为什么任何算法的复杂度都必然带 $1/\Delta$ 因子。

提示：$uu^{\mathsf T}$ 的特征值是 $1$（沿 $u$）和 $0$（与之正交的方向）。

练习 2【power method 的谱分析与误差界】（→ 3.2 节）

基础：写出污染项 $w_t:=\sum_{j>1}c_j(\lambda_j/\lambda_1)^tv_j$ 的定义，并用特征基的正交归一性（Parseval 恒等式）证明 $\|w_t\|_2\le r^t\sqrt{1-|c_1|^2}$。
基础：（计算）对第 8 节的 $2\times2$ 例子，直接计算 $t=1,2$ 的归一化向量 $x_1,x_2$，并用 $\langle v_1,x_t\rangle=3^t/\sqrt{9^t+1}$ 验证误差以 $(1/3)^t$ 衰减；再算 $t=3$，确认误差约为 $t=2$ 时的 $1/3$。
进阶：（推导）补全 3.2 节：从谱展开 $A^tx_0=\sum_jc_j\lambda_j^tv_j$ 出发，严格证明 $\min_\omega\|x_t-\omega v_1\|_2\le\sqrt2\,\dfrac{r^t\sqrt{1-|c_1|^2}}{|c_1|-r^t\sqrt{1-|c_1|^2}}$（在分母为正的条件下），并指出每一步用了哪条不等式。

提示：取相位使 $\omega v_1$ 与 $x_t$ 同相后，$\min_\omega\|x_t-\omega v_1\|_2=2\sin(\theta_t/2)\le\sqrt2\,\sin\theta_t$。

练习 3【随机初态与迭代复杂度】（→ 3.4 节）

基础：设 $r=1/2$、$|c_1|=1/\sqrt d$，写出把误差降到 $\epsilon$ 所需的迭代轮数 $t$（用对数表示），并指出 $d$ 出现在哪里、为什么几乎不影响轮数。
进阶：（重叠）证明均匀随机单位向量 $x_0$ 在任一固定方向 $v_1$ 上满足 $\mathbb E|\langle v_1,x_0\rangle|^2=1/d$，由此说明随机初始化只给迭代数贡献一个 $\frac12\log d$ 量级的加项。
进阶：（间隙依赖）若相对间隙缩小为 $\delta=1/d$（即 $r\le1-1/d$），用 $-\log(1-\delta)\ge\delta$ 证明迭代数 $t=O(d\log(d/\epsilon))$，并讨论此时"量子加速"与"经典 $\Omega(d^2)$ 下界"的相对位置会发生什么变化。

提示：取一组包含 $v_1$ 的正交归一基，利用各坐标分布的对称性与 $\sum_j|c_j|^2=1$。

练习 4【相干 matvec 与读出瓶颈】（→ 4.2 节）

基础：说明"block-encoding + state preparation + 振幅放大"能近似实现哪个映射、每一轮交付的输出是什么形态；再写出朴素纯态 tomography 在 $\ell_2$ 误差 $\epsilon$ 下的成本量级。
进阶：解释 4.2 节"困难不在做 matvec，而在迭代与读出之间的接口"这句话：为什么中间的量子态必须先经典化才能进入下一轮？为什么"每一轮都做最终精度的高精度读出"会把总成本变成"轮数 × 每轮层析"，从而吃掉量子 matvec 省下的查询？

提示：下一轮的 state preparation 需要经典向量 $x$ 作输入；朴素层析的成本随精度按 $1/\epsilon^2$ 变贵。

练习 5【良性噪声与鲁棒迭代原则】（→ 4.3 节）

基础：设收缩因子 $r=1/3$、每轮噪声范数为 $\sigma$。分别计算固定方向 bias 的稳态累积系数 $\frac{1}{1-r}$ 与逐轮独立零均值噪声的典型累积系数 $\frac{1}{\sqrt{1-r^2}}$，并给出两者之比。
基础：用自己的话写出 4.3 节的两条算法设计原则，并说明各自针对的是哪类失败模式。
进阶：（噪声）设每轮噪声范数至多为 $\sigma$、收缩因子为 $r$。对最坏情形 bias 证明稳态误差上界 $\sigma/(1-r)$；再对逐轮独立零均值噪声，说明典型稳态误差为 $\sigma/\sqrt{1-r^2}$ 量级，并解释两者差异的来源。当 $r\to1$（小间隙）时两者如何发散？

提示：几何级数 $\sum_{s\ge0}r^s=\frac{1}{1-r}$；独立噪声各轮贡献按平方和累计，$\sum_{s\ge0}r^{2s}=\frac{1}{1-r^2}$。

练习 6【Gaussian phase estimation 与精度分配】（→ 5.3 节）

基础：写出把单个坐标 $y_i=(Ax)_i$ 估计到加性误差 $\sigma$ 所需的 entry 查询次数——经典 Monte Carlo 与量子求和各是多少？两者的加速比来自哪里？
基础：解释 5.2 节为什么要"Gaussian"：普通相位估计的估计误差为什么未必零均值，近 Gaussian 的 pointer 态如何把内积编进相位、得到以真值为中心的估计器。
进阶：（复杂度）采用 5.3 节的设定：逐坐标估计、每坐标加性误差 $\sigma$ 的量子成本为 $\widetilde O(1/\sigma)$。证明要求一轮 matvec 的 $\ell_2$ 误差不超过 $\epsilon_{\rm rd}$ 时，统一精度分配给出每轮 $\widetilde O(d^{3/2}/\epsilon_{\rm rd})$ 次查询；并解释为什么非统一的精度分配（按坐标、按轮次）能在此基础上进一步降低总成本。

提示：由 $\|\widehat y-y\|_2\approx\sqrt d\,\sigma$ 定出 $\sigma=\epsilon_{\rm rd}/\sqrt d$，再乘上 $d$ 个坐标。

练习 7【无偏纯态 tomography 与收敛分析】（→ 6.2 节）

基础：按顺序列出一轮迭代的四个步骤，并写出无偏 tomography 的输出 $\widehat y$ 需要满足的两条性质（期望与协方差/尾界）。
进阶：利用"第 $t$ 轮噪声到输出时的残留为 $r^{T-t}e_t$"论证：为什么 tomography 只需在最后一两轮做到 $\sim\epsilon(1-r)$ 的精度，更早轮次的粗误差去了哪里？再对比方法一，说明读出组织方式的差别如何把复杂度指数从 $7/4$ 降到 $3/2$。

提示：输出处的总误差 $\lesssim\sum_{s\ge0}r^s\|e_{T-s}\|\approx\sigma_{\rm final}/(1-r)$，主要由最后几轮决定。

练习 8【查询下界与最优性】（→ 7.1 节）

基础：复述经典下界的"草堆藏针"对抗论证，写出经典 $\Omega(d^2)$ 与量子 $\widetilde\Omega(d^{3/2})$ 两个下界，并判断两个算法（$\widetilde O(d^{7/4})$ 与 $d^{3/2+o(1)}$）各自距离下界还有多远。
进阶：解释为什么把"藏针矩阵对"直接交给 Grover 搜索只能得到 $\Omega(d)$ 的量子下界（在 $d^2$ 个 entry 中找一个标记位置需要多少次量子查询？），而 adversary/通信复杂度归约如何把下界加强到 $\widetilde\Omega(d^{3/2})$；再说明 top-$q$ 推广为什么付出 $q\cdot d^{3/2+o(1)}$ 的成本，额外依赖哪些量。

提示：$O(\sqrt{d^2})=O(d)$——Grover 省掉的是"找位置"的平方，而问题的难度在于确定方向所需的信息量。

参考文献¶

Zoo 编号 462：Chen、Gilyén 与 de Wolf, A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix.