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

给一个维数 \(N\) 可能指数大的稀疏实对称矩阵 \(A\)，我们只关心它的幂的一个对角元

\[ (A^m)_{jj}=\langle j|A^m|j\rangle. \]

这看起来像是矩阵计算里最小的局部问题——不读整张矩阵、不输出整行整列，只要一个数。但本文将看到：在适当的归一化口径下，这个"只算一个数"的问题精确刻画了量子计算的全部能力——它是 PromiseBQP-complete 的。一方面，量子计算机可以从基态 \(|j\rangle\) 的谱测度 (spectral measure) 中采样，把该对角元解释为这个测度的第 \(m\) 阶矩来估计；另一方面，Feynman clock 构造可以把任意量子电路的接受概率编码进某个稀疏矩阵的谱矩，因此任何能解该问题的经典算法都能模拟通用量子计算。

这个结果由 Janzing 与 Wocjan 于 2006 年证明（见文末参考文献，Zoo 编号 60）。它与本站字符串重写一节的结果互为表里：两者都把"局部转移规则生成的隐式稀疏矩阵"作为载体，把通用量子计算编码进高阶谱矩。

本课知识点

  1. 稀疏预言机与输入模型——能写出位置查询与取值查询的定义，列出 \(s\)、\(m\)、\(b\)、\(1/\epsilon\) 各自的 \(\operatorname{polylog}N\) 量级，并解释 \(N=2^n\) 指数大时矩阵为何只能隐式访问。

  2. 归一化与误差口径——能推导 \(|(A^m)_{jj}|\le b^m\)，把 \(\epsilon b^m\) 的误差口径换算为 \(\|H\|\le1\) 矩阵上的加性误差 \(\epsilon\)，并解释归一化为何是问题定义的核心而非技术细节。

  3. 路径展开与经典瓶颈——能证明路径展开恒等式并数出非零项上界 \(s^m\)，解释路径枚举、整体乘方、快速幂与 Monte Carlo 采样四条经典路线各自的失败原因与符号问题。

  4. 谱测度与矩公式——能推导 \(H^m\) 的谱分解与 \(\mu_m=\mathbb E_{\lambda\sim\nu_j}[\lambda^m]\)，验证 \(\nu_j\) 是概率测度，并由此证明 \(|\mu_m|\le1\)。

  5. 谱采样算法与误差预算——能按序写出谱采样的四步流程，证明幂函数的 \(m\)-Lipschitz 界，并由对分误差预算解出分辨率 \(\delta=O(\epsilon/m)\) 与样本数 \(R=O(1/\epsilon^2)\)。

  6. Block Encoding 与 QSVT 路线——能逐条核对 \(p(x)=x^m\) 的三个 QSVT 可实施性条件，并比较谱采样与"QSVT + Hadamard test + 振幅估计"两条路线的代价构成与 \(\epsilon\) 依赖。

  7. 输出边界与 polarization 恒等式——能解释量子算法为何不输出整个 \(A^m\)（\(\Omega(N^2)\) 下界），并推导把非对角元归约到对角元的 polarization 恒等式。

  8. Feynman clock 与 BQP 完备性——能验证 propagation matrix 的 Hermitian 性、稀疏性与 \(\|K\|\le2\)，解释奇数阶矩恒为零与接受概率进入谱矩的机制，并说明 PromiseBQP-complete 结论的 promise 保留条款。

1. 问题陈述与输入模型

1.1 稀疏矩阵预言机

设 \(N = 2^n\)，即矩阵的行（列）用 \(n\) 个比特索引。输入是一个实对称矩阵 \(A\in\mathbb R^{N\times N}\)，满足稀疏性假设：每行至多有

\[ s=\operatorname{polylog}N=\operatorname{poly}(n) \]

个非零矩阵元。由于 \(N\) 指数大，\(A\) 不可能以显式形式给出；我们通过 sparse oracle 访问它。预言机回答两类查询，每次查询的代价是 \(\operatorname{poly}(n)\)：

  1. 位置查询：给定行号 \(r\) 与序号 \(\ell\in\{1,\dots,s\}\)，返回第 \(r\) 行第 \(\ell\) 个非零元的列号 \(c\)；

  2. 取值查询：给定 \((r,c)\)，返回实数值 \(A_{r,c}\)。

这就是 Hamiltonian simulation 文献中的标准稀疏访问模型（参见量子模拟一章同款假设—— sparse Hamiltonian simulation 用的正是这样的预言机）。此外已知谱范数的上界

\[ \|A\|\le b, \]

其中 \(\|A\|=\max_r|\lambda_r(A)|\) 是算子范数，\(b=\operatorname{poly}(n)\)。

1.2 要估计什么：归一化是问题定义的核心

问题（稀疏矩阵幂对角元估计）. 给定上述稀疏预言机、行号 \(j\)、幂次

\[ m=\operatorname{polylog}N, \]

要求以加性误差

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

估计 \((A^m)_{jj}\)，即输出一个数 \(\widetilde\mu\)，使得 \(|\widetilde\mu-(A^m)_{jj}|\le\epsilon b^m\)。

为什么误差按 \(b^m\) 缩放？因为 \(b^m\) 是这个量的自然尺度。事实上，由算子范数的次可乘性（\(\|XY\|\le\|X\|\|Y\|\)，对 \(m\) 归纳得 \(\|A^m\|\le\|A\|^m\)）与算子范数的定义（\(|\langle j|M|j\rangle|\le\|M\|\)，因为单位矢量的像的范数不超过 \(\|M\|\)），

\[ \left|(A^m)_{jj}\right|=\left|\langle j|A^m|j\rangle\right|\le\|A^m\|\le\|A\|^m\le b^m. \]

也就是说，\((A^m)_{jj}\) 本身可以达到 \(b^m\) 量级。除以 \(b^m\) 之后，问题等价于估计

\[ \mu_m=\langle j|H^m|j\rangle,\qquad H:=A/b,\quad \|H\|\le 1, \]

到加性误差 \(\epsilon\)。下文一律在归一化矩阵 \(H\) 上工作，最后再把因子 \(b^m\) 乘回去。

这个归一化是问题定义的核心，而不是技术细节。 若改为要求"原值的绝对误差 \(1\)"，而 \(b^m\) 随 \(n\) 指数大，那么我们是在要求相对误差 \(b^{-m}\)——复杂度的口径完全不同，量子算法不再高效。本章（以及第 13 章其余各节）反复强调的原则在这里同样适用：一个量的可估计性永远要连同它的归一化一起陈述。

1.3 动机：谱矩在哪里出现

矩阵幂的对角元绝不是人为造出来的问题。下面三个例子说明它的来源：

  • 路径计数。若 \(A\) 是某个稀疏图的邻接矩阵，\((A^m)_{jj}\) 是从顶点 \(j\) 出发、恰好 \(m\) 步回到 \(j\) 的闭合路径条数（我们将在 §2.1 证明这一点）。更一般地，带权矩阵给出带权路径和。统计物理中的配分函数、组合学中的生成函数都涉及这类计数。

  • 谱测度与矩问题。数值线性代数中，估计大规模对称矩阵的谱密度（例如凝聚态物理中的态密度）的标准做法正是通过 \(\langle v|f(A)|v\rangle\) 型的量提取谱信息；取 \(f(x)=x^m\) 就是谱矩。

  • 量子计算自身。§7 将看到，任意量子电路的演化历史可以被写成一个稀疏 Hermitian 矩阵，其幂的对角元编码了电路的接受概率——这是 BQP-hardness 的来源。

2. 经典算法的瓶颈

在给出量子算法之前，先弄清楚经典算法卡在哪里。这能帮我们理解量子加速究竟来自哪一步。

2.1 路径展开：矩阵幂的组合含义

引理（路径展开恒等式）. 对任意矩阵 \(A\) 与任意正整数 \(m\)，

\[ (A^m)_{jj}=\sum_{i_1,\dots,i_{m-1}} A_{j,i_1}\,A_{i_1,i_2}\,\cdots\,A_{i_{m-1},j}. \]

若 \(A\) 是图 \(G\) 的邻接矩阵（\(A_{ik}=1\) 当且仅当 \((i,k)\) 是一条边），则 \((A^m)_{jj}\) 等于从 \(j\) 出发长度为 \(m\) 的闭合路径（closed walk）条数。

证明。\(m=1\) 时右端没有求和指标，就是 \(A_{jj}\) 本身。设公式对 \(m\) 成立，则由矩阵乘法的定义 \((XY)_{ik}=\sum_l X_{il}Y_{lk}\)，

\[ (A^{m+1})_{jj}=\sum_{i_1} A_{j,i_1}\,(A^m)_{i_1,j} =\sum_{i_1}A_{j,i_1}\sum_{i_2,\dots,i_m}A_{i_1,i_2}\cdots A_{i_m,j}, \]

把两个求和合并即得 \(m+1\) 的情形，归纳完成。对邻接矩阵，乘积 \(A_{j,i_1}A_{i_1,i_2}\cdots A_{i_{m-1},j}\) 等于 \(1\) 当且仅当 \((j,i_1,\dots,i_{m-1},j)\) 是一条合法的闭合路径（每条边都存在），否则为 \(0\)；求和就是数路径。Q.E.D.

这个恒等式给我们两个重要信息：

  • 非零项的数量。从 \(j\) 出发，每一步至多有 \(s\) 个非零元可选（稀疏性），所以长度为 \(m\) 的路径至多有 \(s^m\) 条，即求和中至多有 \(s^m\) 个非零项。

  • 与干涉的对应。量子力学中"振幅 = 路径振幅之和"的 Feynman 图像在这里完全精确：\((A^m)_{jj}\) 是所有闭合路径贡献的代数和。§7 的 Feynman clock 构造正是把量子电路的演化历史嵌入这些路径。

2.2 直接计算与快速幂为什么都不行

策略一：逐条枚举路径。 由 §2.1，用深度优先搜索枚举所有从 \(j\) 出发的长度 \(m\) 路径并累加贡献，代价是 \(O(s^m)\) 次预言机查询。代入问题的参数尺度：

\[ s^m=\bigl(\operatorname{polylog}N\bigr)^{\operatorname{polylog}N} =2^{\operatorname{polylog}N\cdot\log\operatorname{polylog}N}, \]

这是关于 \(n=\log N\) 的超多项式（quasi-polynomial 以上）增长。\(m\) 哪怕只是 \(n^2\)，\(s^m\) 也已经是 \(2^{\Theta(n^2\log n)}\)。路径枚举不可用。

策略二：把 \(A^m\) 整个算出来。 这更糟：\(A^m\) 通常是稠密 (dense) 的，有 \(\Theta(N^2)\) 个非零矩阵元，仅仅把输出写下来就需要 \(\Omega(N^2)\) 时间，而 \(N=2^n\)。

策略三：快速幂（repeated squaring）。 经典计算中，算数的 \(m\) 次幂只需 \(O(\log m)\) 次乘法。对矩阵同样可以做 \(A\to A^2\to A^4\to\cdots\)，只需 \(O(\log m)\) 次矩阵乘法。但这里有两个致命伤：

  1. 稀疏性在乘方后不保持（fill-in）。若 \(A\) 每行至多 \(s\) 个非零元，则 \((A^2)_{ik}=\sum_l A_{il}A_{lk}\) 中非零项出现在"存在共同邻居 \(l\)"的位置，每行至多 \(s^2\) 个；归纳地看，\(A^{2^k}\) 每行的非零元至多 \(s^{2^k}\) 个。平方 \(\log m\) 次之后上界已是 \(s^m\)——矩阵早已稠密，稀疏预言机的优势荡然无存。

  2. 维数不可承受。快速幂把乘法次数降到 \(O(\log m)\)，但每次乘法的对象是 \(N\times N\) 矩阵，\(N=2^n\)。即使最朴素的稠密乘法也是 \(\Theta(N^3)\)，任何已知乘法都不可能低于输出规模的 \(\Omega(N^2)\)。

结论：经典快速幂优化的是乘法次数，而我们的瓶颈是矩阵维数。两者正交。

策略四：Monte Carlo 采样路径。 若矩阵元全部非负（例如随机游走的转移矩阵），可以从 \(j\) 出发随机游走 \(m\) 步，用"回到 \(j\) 的频率"估计对角元——这正是 Markov chain Monte Carlo 的思想，经典上是可行的。但一般的实对称矩阵有正有负，路径贡献带符号：此时估计量是大量正负数相消后的小差值，方差与所求量的比值可以指数大——这就是著名的符号问题 (sign problem)。量子算法的相干干涉恰好擅长处理这种带符号的求和；这也是 BQP-hardness 结果（§7）告诉我们"一般情形经典难"并不矛盾于"非负特例经典易"的原因。

3. 谱测度：把对角元看成矩

量子算法的第一步不是线路，而是一个重新表述：把 \(\mu_m\) 解释为某个概率分布的矩。这一步是纯粹的经典数学。

3.1 从谱分解到矩公式

\(H\) 是实对称矩阵，由谱定理它有完备的正交归一特征矢量基：

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

其中特征值的范围来自 \(\|H\|\le 1\)（§1.2 的归一化）。

第一步：\(H\) 的幂的谱分解。 我们证明

\[ H^m=\sum_r\lambda_r^m\,|u_r\rangle\langle u_r|. \]

\(m=1\) 时就是谱分解本身。设上式对 \(m\) 成立，则

\[ H^{m+1}=H\cdot H^m =\left(\sum_s\lambda_s|u_s\rangle\langle u_s|\right)\left(\sum_r\lambda_r^m|u_r\rangle\langle u_r|\right) =\sum_{s,r}\lambda_s\lambda_r^m\,|u_s\rangle\langle u_s|u_r\rangle\langle u_r|. \]

由正交归一性 \(\langle u_s|u_r\rangle=\delta_{sr}\)，双重求和退化为 \(s=r\) 的单重求和，系数为 \(\lambda_r\cdot\lambda_r^m=\lambda_r^{m+1}\)，归纳完成。这一步只用到了"投影算子 \(|u_r\rangle\langle u_r|\) 互相正交"——同一个特征矢量基同时对角化 \(H\) 的所有幂。

第二步：夹在 \(|j\rangle\) 之间。 两边取对角元：

\[ \mu_m=\langle j|H^m|j\rangle =\sum_r\lambda_r^m\,\langle j|u_r\rangle\langle u_r|j\rangle =\sum_r|\langle u_r|j\rangle|^2\,\lambda_r^m, \]

最后一步用了 \(\langle j|u_r\rangle=\overline{\langle u_r|j\rangle}\)（内积的共轭对称性），故两者的乘积是模方。

3.2 谱测度是概率分布

定义

\[ p_r:=|\langle u_r|j\rangle|^2,\qquad \nu_j:=\sum_r p_r\,\delta_{\lambda_r}, \]

其中 \(\delta_{\lambda}\) 是在点 \(\lambda\) 处的 Dirac 测度。称 \(\nu_j\) 为 \(H\) 在基态 \(|j\rangle\) 上看到的谱测度。它确实是概率测度：

  • 非负性：\(p_r=|\langle u_r|j\rangle|^2\ge 0\)；

  • 归一性：由完备性关系 \(\sum_r|u_r\rangle\langle u_r|=I\)，

\[ \sum_r p_r=\sum_r\langle j|u_r\rangle\langle u_r|j\rangle =\langle j|\left(\sum_r|u_r\rangle\langle u_r|\right)|j\rangle =\langle j|j\rangle=1. \]

（这就是 Parseval 恒等式：\(|j\rangle\) 在任何正交归一基下展开的系数模方和等于它的范数平方。）

于是 §3.1 的公式可以写成期望的形式：

\[ \boxed{\;\mu_m=\mathbb E_{\lambda\sim\nu_j}\left[\lambda^m\right]\;} \]

即 \(\mu_m\) 是谱测度 \(\nu_j\) 的第 \(m\) 阶矩。记号 \(\lambda\sim\nu_j\) 表示"以概率 \(p_r\) 取值 \(\lambda_r\)"的随机变量。

这个表述立即解释了一些基本事实。例如 \(|\mu_m|\le 1\)：由三角不等式与 \(|\lambda_r|\le 1\)，

\[ |\mu_m|\le\sum_r p_r\,|\lambda_r|^m\le\sum_r p_r=1, \]

与 §1.2 中 \(|(A^m)_{jj}|\le b^m\) 的归一化版本一致（换回原矩阵就是乘以 \(b^m\)）。

3.3 直觉：局部谱信息

谱测度 \(\nu_j\) 回答的问题是："基态 \(|j\rangle\) 坐在 \(H\) 的哪些特征方向上，各坐多重？" 把 \(|j\rangle\) 在特征基下展开，\(|j\rangle=\sum_r\langle u_r|j\rangle\,|u_r\rangle\)，谱测度记录的正是各分量的权重与对应的特征值——但不记录相位与方向信息。

这个观察解释了为什么这个问题天然地适合量子计算机。相位估计（ch03）的工作方式恰恰是：对 \(e^{iHt}\)、输入态 \(|j\rangle\) 做测量，输出以概率 \(p_r=|\langle u_r|j\rangle|^2\) 抽到特征值 \(\lambda_r\) 的估计——也就是说，相位估计天然地从谱测度 \(\nu_j\) 中采样。经典算法若不读取指数多的矩阵结构，很难获得同一个局部谱测度的样本：算出 \(p_r\) 需要知道特征矢量，而对角化一个 \(2^n\) 维矩阵无从谈起。

值得强调：单个矩 \(\mu_m\) 只是谱测度的一个线性泛函，远不能确定整个测度。我们也不需要整个测度——这正是问题"只问一个数"的省力之处，也是它最终落入 BQP 而非更难复杂类的原因。

4. 量子算法一：谱采样

4.1 算法流程

第一个实现把 §3 的概率解释直接变成采样算法：

  1. 制备 \(|j\rangle\)（就是一个计算基态，\(n\) 个比特的制备代价 \(O(n)\)）；

  2. 相位估计：对酉算子 \(e^{iHt}\) 与输入 \(|j\rangle\) 运行相位估计（ch03），得到某个特征值的估计 \(\widetilde\lambda\)。由相位估计的分析，输出 \(\widetilde\lambda_r\) 的概率是 \(p_r=|\langle u_r|j\rangle|^2\)，即恰好从 \(\nu_j\) 采样；演化算子 \(e^{iHt}\) 本身由 sparse Hamiltonian simulation 实现（稀疏预言机 + Trotter 化或更优方法，见 ch05），其代价关于 \(s\)、\(t\)、\(\log N\) 是多项式；

  3. 经典后处理：计算 \(\widetilde\lambda^m\in[-1,1]\)；

  4. 重复平均：独立重复 \(R\) 次，输出样本均值 \(\frac{1}{R}\sum_i\widetilde\lambda_i^m\)。

由期望的定义，单次输出的期望是 \(\mathbb E_{\nu_j}[\lambda^m]=\mu_m\)（相差一个由估计精度造成的系统误差，见下），所以样本均值确实收敛到目标。剩下的问题是：特征值需要多精确？样本需要多少个？ 这是两个独立的误差来源，需要分别控制再做预算平衡。

4.2 关键引理：幂函数的 Lipschitz 常数

系统误差来自相位估计的分辨率：我们拿到的是 \(\widetilde\lambda\approx\lambda\)，但代入的是 \(m\) 次幂。误差如何放大？

引理. 对任意 \(|x|,|y|\le 1\) 与正整数 \(m\)，

\[ |x^m-y^m|\le m\,|x-y|. \]

证明。用有限几何级数的因式分解

\[ x^m-y^m=(x-y)\sum_{k=0}^{m-1}x^{m-1-k}y^{k}, \]

这可以通过把右端展开验证：求和式乘以 \((x-y)\) 后是一个错位相消（telescoping）的和，\(\sum_k(x^{m-k}y^k-x^{m-1-k}y^{k+1})=x^m-y^m\)。右端的和共有 \(m\) 项，每项满足 \(|x^{m-1-k}y^k|=|x|^{m-1-k}|y|^k\le 1\)（因为 \(|x|,|y|\le 1\)）。由三角不等式，

\[ |x^m-y^m|\le |x-y|\cdot\sum_{k=0}^{m-1}1=m|x-y|. \]

Q.E.D.

注意条件 \(|x|,|y|\le 1\) 必不可少：若 \(|x|>1\)，因子 \(|x|^{m-1-k}\) 会随 \(m\) 指数放大。这正是 §1.2 把矩阵归一化到 \(\|H\|\le 1\) 的又一个原因——归一化把幂函数变成了 \(m\)-Lipschitz 函数，特征值误差最多被放大 \(m\) 倍，而 \(m=\operatorname{polylog}N\) 是可承受的。

4.3 误差预算与参数平衡

总误差有两个来源，我们要求它们各自不超过 \(\epsilon/2\)，从而总和不超过 \(\epsilon\)。

系统误差（分辨率）。设相位估计给出的特征值误差为 \(|\widetilde\lambda-\lambda|\le\delta\)。由引理，每次采样的偏差满足 \(|\widetilde\lambda^m-\lambda^m|\le m\delta\)。这个偏差是系统的：它不会在平均中抵消，但因为每次采样都受同一个界控制，均值也受它控制：

\[ \left|\mathbb E[\widetilde\lambda^m]-\mathbb E[\lambda^m]\right| \le\mathbb E\left|\widetilde\lambda^m-\lambda^m\right| \le m\delta, \]

其中第一步是期望的三角不等式（Jensen 不等式的特例）。要求 \(m\delta\le\epsilon/2\)，解出所需分辨率

\[ \delta=O\!\left(\frac{\epsilon}{m}\right). \]

相位估计要把特征值分辨到 \(\delta\)，需要的演化时间是 \(t=O(1/\delta)=O(m/\epsilon)\)（相位估计的标准标度：精度与时间成反比，见 ch03）。

统计误差（采样）。每个样本 \(X_i=\widetilde\lambda_i^m\) 满足 \(|X_i|\le 1\)，故方差 \(\operatorname{Var}(X_i)\le\mathbb E[X_i^2]\le 1\)。\(R\) 个独立样本的均值方差为 \(\operatorname{Var}/R\le 1/R\)。由 Chebyshev 不等式，

\[ \Pr\left[\left|\tfrac{1}{R}\textstyle\sum_i X_i-\mathbb E[X]\right|\ge\tfrac{\epsilon}{2}\right] \le\frac{1/R}{(\epsilon/2)^2}=\frac{4}{R\epsilon^2}. \]

要让失败概率为常数（例如 \(1/3\)），取

\[ R=O\!\left(\frac{1}{\epsilon^2}\right) \]

个样本即可。这就是普通的 Monte Carlo 标度：\([-1,1]\) 上有界随机变量的均值估计，代价 \(O(1/\epsilon^2)\)。

平衡的结果。把两部分合起来：\(R=O(1/\epsilon^2)\) 次独立重复，每次的 Hamiltonian simulation 时间为 \(t=O(m/\epsilon)\)，每次模拟的线路代价关于 \(s\)、\(\log N\) 与 \(t\) 为多项式。总代价

\[ \underbrace{O\!\left(\frac{1}{\epsilon^2}\right)}_{\text{样本数}} \times \underbrace{\operatorname{poly}\!\left(s,\,\log N,\,\frac{m}{\epsilon}\right)}_{\text{单次模拟}} =\operatorname{poly}\!\left(s,\,m,\,\frac{1}{\epsilon},\,\log N\right). \]

代入问题的参数尺度 \(s,m,1/\epsilon=\operatorname{polylog}N=\operatorname{poly}(n)\)，总代价是 \(\operatorname{poly}(n)\)——该问题属于 PromiseBQP。注意这里的参数平衡是标准的"对分误差预算"：系统误差与统计误差各分到 \(\epsilon/2\)，再分别反解出分辨率 \(\delta\) 与样本数 \(R\)；不存在需要联立求解的隐式平衡。

4.4 复杂度表达式中每个因子的来源

把总代价拆开，逐项对照来源：

  • 因子 \(m\)：来自引理中幂函数的 Lipschitz 常数——幂次越高，特征值需要分辨得越细，演化时间越长；

  • 因子 \(1/\epsilon^2\)：Monte Carlo 平均的统计涨落，有界随机变量均值估计的通用代价；

  • 因子 \(s\) 与 \(\log N\)：sparse Hamiltonian simulation 每一步访问预言机的代价，以及 \(n=\log N\) 个系统比特上的基本门操作；

  • 隐含的 \(\log(1/\delta_{\mathrm{fail}})\)：若要求成功概率 \(1-\delta_{\mathrm{fail}}\)，Chebyshev 换成 Hoeffding 不等式（样本有界时可用）会引入对数因子，标准的成功概率放大技术。

5. 量子算法二：Block Encoding 与 QSVT

第二个实现更贴近 ch05 的语言，也更直接地暴露"归一化"与"次数"这两个关键参数。

5.1 为什么 \(p(x)=x^m\) 是合法多项式

由稀疏预言机可以构造 \(H\) 的 block encoding（标准构造，见 block-encoding 教程）：一个作用在系统加少量辅助比特上的酉算子 \(U_H\)，其左上角块就是 \(H\)（相差一个已知的归一化常数，构造时吸收进误差预算）。

回忆 QSVT 对多项式 \(p\) 的三个可实施性条件（ch05）：(i) \(p\) 的次数为 \(d\)；(ii) \(p\) 有确定的奇偶性（奇或偶）；(iii) 在 \([-1,1]\) 上 \(|p(x)|\le 1\)。逐条核对 \(p(x)=x^m\)：

  • 次数为 \(m\)；

  • 奇偶性：\((-x)^m=(-1)^mx^m\)，奇偶与 \(m\) 一致，确定；

  • 有界性：\(|x|\le 1\) 时 \(|x^m|=|x|^m\le 1\)。

三条都满足——而且条件 (iii) 恰好又是 \(\|H\|\le 1\) 这个归一化在起作用。于是 QSVT 给出 \(H^m\) 的 block encoding，其代价是 \(m\) 次对 \(U_H\) 及其逆的调用（QSVT 的查询数等于多项式次数）。在 QSVT 出现之前，原论文的表述是"测量 \(A\) 并估计 spectral moment"（即 §4 的谱采样路线）；两种表述等价，但 block-encoding 语言把 normalization（块编码的比例因子）与 degree（多项式次数 = 查询次数）显示在账面上。

5.2 从块编码到 Hadamard test

有了 \(H^m\) 的 block encoding \(U_{H^m}\)，估计 \(\langle j|H^m|j\rangle\) 是标准的 Hadamard test：用控制比特叠加地施加 \(U_{H^m}\)，测量控制比特得到 \(\operatorname{Re}\langle j|H^m|j\rangle\)（本问题中矩阵为实，虚部为零，一次 Hadamard test 即可）。块编码的比例因子是已知常数，除以它即得 \(\mu_m\) 的估计。

Hadamard test 的单次输出是 \(\pm 1\) 随机比特，均值估计同样需要 \(O(1/\epsilon^2)\) 次重复；但这里可以做得更好：把"控制比特为 \(+1\)"视为好事件做振幅估计 (amplitude estimation)（ch03，相位估计的又一应用），把精度代价从 \(O(1/\epsilon^2)\) 降到 \(O(1/\epsilon)\)。

5.3 复杂度对比

\[ \underbrace{O(m)}_{\text{QSVT 查询}} \times \underbrace{\operatorname{poly}(s,\log N)}_{\text{块编码代价}} \times \underbrace{O\!\left(\frac{1}{\epsilon}\right)}_{\text{振幅估计}} =\operatorname{poly}\!\left(s,\,m,\,\frac{1}{\epsilon},\,\log N\right). \]

与 §4 的谱采样相比，\(\epsilon\) 的依赖从 \(1/\epsilon^3\)（样本数 \(1/\epsilon^2\) 乘以单次模拟 \(m/\epsilon\)）改进到接近 \(1/\epsilon\)，代价是动用了更重的机制（块编码、QSVT、振幅估计）。两条路线在参数尺度 \(\operatorname{polylog}N\) 下都是 \(\operatorname{poly}(n)\)，所以 BQP 成员资格的结论相同。

6. 为什么不是"快速输出 \(A^m\)"

6.1 输出本身就太大

值得把 §2 的结论再强调一遍，因为它划定了这类算法的边界：量子算法不输出 \(A^m\)，也不输出它的某一行。\(A^m\) 通常稠密，有 \(\Theta(N^2)\) 个矩阵元；输出它的任何经典表示都至少需要 \(\Omega(N^2)\) 时间。量子算法回答的只是"一个矩阵元"或更一般的少量线性泛函 \(\langle\psi|A^m|\varphi\rangle\)。把问题理解成"快速计算矩阵幂"会得到错误的复杂度预期；正确的理解是"从局部稀疏预言机直接访问谱函数的值，避免物化任何中间矩阵"。

同样的边界条件也适用于读者熟悉的其他算法：HHL 不输出解向量本身，只输出关于解的测量统计；量子相位估计不输出整个谱，只输出被采样到的那个特征值。

6.2 非对角元：polarization 恒等式

对角元算法其实够用于所有矩阵元。对非对角元，用 polarization 恒等式把问题归约到对角元。给定 \(i\neq j\)，定义叠加态（这里的 \(|+\rangle\) 依赖于 \(i,j\)，是临时记号，不要与 Hadamard 基混淆）

\[ |+\rangle:=\frac{|i\rangle+|j\rangle}{\sqrt2}. \]

对实对称矩阵 \(B\)（例如 \(B=H^m\)），有恒等式

\[ \langle i|B|j\rangle =\langle +|B|+\rangle -\frac12\langle i|B|i\rangle -\frac12\langle j|B|j\rangle. \]

验证。把 \(|+\rangle\) 的定义代入并展开（四个交叉项）：

\[ \langle +|B|+\rangle =\frac12\left(\langle i|B|i\rangle+\langle i|B|j\rangle+\langle j|B|i\rangle+\langle j|B|j\rangle\right). \]

因为 \(B\) 实对称，\(\langle j|B|i\rangle=\langle i|B|j\rangle\)（实对称的内积 \(\langle j|B|i\rangle=(B^T)_{ij}=B_{ij}\)，就是同一个数），两个交叉项合并：

\[ \langle +|B|+\rangle =\frac12\langle i|B|i\rangle+\frac12\langle j|B|j\rangle+\langle i|B|j\rangle. \]

把对角项移到左端即得恒等式。Q.E.D.

右端三项都是"某个易制备态上的对角元"：\(|i\rangle,|j\rangle\) 是计算基态，\(|+\rangle\) 只需对 \(i,j\) 的地址比特做一次受控叠加即可制备。因此对角元算法的任何实现都自动覆盖全部矩阵元，代价至多是三倍。注意这个归约依赖 \(B\) 实对称；一般 Hermitian 情形需要额外的 \(i\) 相位版本区分实部与虚部（留作习题）。

7. PromiseBQP-hardness：Feynman clock

现在转向反方向：为什么这个问题难。我们将看到任意 BQP 计算的接受概率可以被编码成某个稀疏 Hermitian 矩阵的谱矩，因此该估计问题是 PromiseBQP-hard 的；结合 §4–§5 的成员资格，它是 PromiseBQP-complete 的。

构造的思想可以追溯到 Feynman 的 clock 寄存器与 Kitaev 的 history state：给量子电路配一个"时钟"，让矩阵的幂把演化历史当作路径来数。

7.1 propagation matrix 的构造与基本性质

给定作用在 \(n\) 个比特上的量子电路

\[ U=U_T\cdots U_1,\qquad T=\operatorname{poly}(n), \]

引入时钟寄存器（维数 \(T+1\)，基态 \(|0\rangle,\dots,|T\rangle\)），在"时钟 \(\otimes\) 数据"空间上定义 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). \]

逐项理解：第一项把时钟从 \(t\) 拨到 \(t+1\)，同时在数据寄存器上施加第 \(t+1\) 个门；第二项是它的逆操作（时钟回拨、施加逆门）。\(K\) 有三个直接可验证的性质。

Hermitian 性。对和式中的每一项取伴随：

\[ \left(|t+1\rangle\langle t|\otimes U_{t+1}\right)^\dagger =|t\rangle\langle t+1|\otimes U_{t+1}^\dagger, \]

恰好是和式中的另一项。所以 \(K^\dagger=K\)，它有实谱，谱矩语言适用。

稀疏性。固定基态 \(|t\rangle|x\rangle\)（\(x\) 是数据的计算基态），

\[ K\,|t\rangle|x\rangle =|t+1\rangle\otimes U_{t+1}|x\rangle+|t-1\rangle\otimes U_{t}^\dagger|x\rangle \]

（边界处只有一项）。每个时钟位形只连接前后两步；而一个局部门（一至两个比特）把计算基态映到至多常数个基态（例如两比特门至多 \(4\) 个）。所以 \(K\) 的每列只有 \(O(1)\) 个非零元，且非零元就是门的矩阵元——位置与取值都可以从电路描述在 \(\operatorname{poly}(n)\) 时间内算出，即稀疏预言机可以有效实现。

范数有界。记"前进部分"

\[ W:=\sum_{t=0}^{T-1}|t+1\rangle\langle t|\otimes U_{t+1}, \]

则 \(K=W+W^\dagger\)。计算

\[ W^\dagger W =\sum_{t,t'}\left(|t'\rangle\langle t'+1|\otimes U_{t'+1}^\dagger\right)\left(|t+1\rangle\langle t|\otimes U_{t+1}\right) =\sum_{t}|t\rangle\langle t|\otimes U_{t+1}^\dagger U_{t+1}, \]

其中第二个等号用了时钟基的正交性 \(\langle t'+1|t+1\rangle=\delta_{t't}\)。由 \(U_{t+1}^\dagger U_{t+1}=I\)，\(W^\dagger W\) 是一个投影算子（向时钟 \(t\le T-1\) 子空间的投影），故 \(\|W\|=1\)（\(W\) 是部分等距）。于是

\[ \|K\|\le\|W\|+\|W^\dagger\|=2, \]

即归一化常数 \(b\le 2\)，与 \(n\) 无关。

7.2 \(K^m\) 的闭合路径展开

取时钟为 \(0\)、数据为某个计算基态 \(x\) 的联合基态 \(|j\rangle=|0\rangle|x\rangle\)，考察 \(\langle j|K^m|j\rangle\)。由 §2.1 的路径展开恒等式（把基态写成 \((t_i,x_i)\) 对），

\[\begin{split} \langle 0,x|K^m|0,x\rangle =\sum_{\substack{t_0=\cdots=t_m=0\\ x_0=x_m=x}} \prod_{i=0}^{m-1}\langle t_{i+1},x_{i+1}|K|t_i,x_i\rangle. \end{split}\]

由 §7.1，因子 \(\langle t_{i+1},x_{i+1}|K|t_i,x_i\rangle\) 非零仅当 \(|t_{i+1}-t_i|=1\)：时钟序列必须是一条在线段 \(\{0,1,\dots,T\}\) 上、每步走一格的路径。这条路径从 \(0\) 出发又回到 \(0\)，所以前进与后退的步数必须相等，\(m\) 必为偶数；奇数阶矩恒为零——这与对称谱 \(\nu_j(\lambda)=\nu_j(-\lambda)\) 的图像一致。

每条时钟路径对应一个数据寄存器上的算子乘积：前进经过 \(t\to t+1\) 贡献 \(U_{t+1}\)，后退经过 \(t+1\to t\) 贡献 \(U_{t+1}^\dagger\)。对中间数据基态 \(x_1,\dots,x_{m-1}\) 求和，由路径展开恒等式，恰好拼出算子乘积的对角元：

\[ \langle 0,x|K^m|0,x\rangle =\sum_{\text{闭合时钟路径 }(t_0,\dots,t_m)} \langle x|\,V_{t_{m-1}\to t_m}\cdots V_{t_0\to t_1}\,|x\rangle, \qquad V_{t\to t+1}=U_{t+1},\quad V_{t+1\to t}=U_{t+1}^\dagger. \]

例如，"单调走到 \(T\) 再走回来"的 excursion（要求 \(m\ge 2T\)）贡献

\[ \langle x|\,U_1^\dagger U_2^\dagger\cdots U_T^\dagger\cdot U_T\cdots U_2U_1\,|x\rangle=1, \]

即这类路径只贡献平凡的计数。这说明裸的 \(K\) 还不够：有用的信号必须来自被门振幅非平凡加权的闭合路径，其干涉权重包含电路各门的矩阵元。

7.3 接受概率如何进入谱矩

原论文通过三个补充构造让非平凡信号分离出来：

  • 输入 flag：在时钟起点附近加入标志位与投影项，强制参与求和的路径从合法初态（例如数据寄存器为 \(|0^n\rangle\)）出发，排除垃圾历史；

  • 输出 gadget：在时钟终点处放置与接受输出位耦合的结构，使穿过终点的路径带上正比于电路接受振幅的权重；

  • padding（恒等步）：在电路末端拼接若干恒等"门"，延长时钟线段，使得可以选择一个 \(\operatorname{poly}(n)\) 大小的 \(m\)，让含信号的路径族恰好被第 \(m\) 阶矩分离出来。

最终的结论是：对任意 BQP 语言与任意输入，可以构造（\(\operatorname{poly}(n)\) 时间内构造）一个稀疏 Hermitian 矩阵与一个基态 \(|j\rangle\)，使得电路接受时 \(\langle j|K^m|j\rangle\) 落在一个区间、拒绝时落在与之不相交的另一区间，两区间之间隔着逆多项式（在归一化口径下逆多对数）的 gap。于是，任何能以 \(\epsilon b^m\) 加性误差估计稀疏矩阵幂对角元的算法，都能判定任意 BQP 语言——PromiseBQP-hardness 得证。

精确的 gadget 构造技术性较强，超出本教程范围；这里的要点是机制：矩阵幂把演化历史展开成闭合路径的和，路径的代数干涉权重里藏着门振幅，而 flag 与 padding 负责把"完整穿过计算"的路径从平凡计数中挑出来。 这与 §2.1 路径展开恒等式给出的 Feynman 图像是同一枚硬币的两面。

还有一个耐人寻味的细节：通过把每个门替换为只含 \(\pm 1\) 矩阵元的小 gadget（门的"离散化"），构造甚至可以把矩阵元限制为 \(-1,0,1\)。这说明该问题的困难不来自高精度输入数值——即使矩阵元粗糙到只有三个取值，问题依然 BQP-hard；困难完全来自隐式图的组合结构与相位干涉。

7.4 保留条款

  • 结论针对的是 promise problem：gap（接受/拒绝两区间的分离）是输入承诺的一部分。没有这个 gap，"矩落在哪个区间"本身不是一个良定义的判定问题。

  • 复杂度口径是 §1.2 的归一化口径：误差 \(\epsilon b^m\)、\(1/\epsilon=\operatorname{polylog}N\)。改成绝对误差或相对误差，结论不再成立。

  • "稀疏"与"实对称"两个条件都在构造中起到实质作用：稀疏性保证预言机高效、保证量子算法一端的多项式代价；对称（Hermitian）性保证谱矩语言与谱采样成立。

8. 与字符串重写的统一

字符串重写一节考虑的问题看似完全不同：按局部替换规则把字符串 \(s\) 改成 \(t\)，问"恰好 \(m\) 步的重写序列数"之差的符号。但那里的重写图邻接矩阵同样是稀疏 Hermitian 的，重写路径数同样是其幂的矩阵元（那里用的是 §2.1 的路径展开恒等式）。两个 BQP-complete 结果共享同一条流水线：

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

差别只在符号的来源：矩阵幂问题允许一般的正负矩阵元，符号直接来自权重；字符串重写中只有非负的路径计数，符号靠"两个目标路径数之差"人为制造。对应的 Feynman clock / propagation Hamiltonian 构造在两边几乎逐字相同。把两节对照阅读，可以看到"局部规则 \(\Rightarrow\) 隐式稀疏矩阵 \(\Rightarrow\) 谱矩"是第 13 章反复出现的范式。

9. 两个小例子

9.1 Pauli \(X\)：三种算法互相验证

取

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

这里 \(N=2\)、\(s=1\)、\(\|H\|=1\)。我们用三种方法计算 \(\mu_m=\langle0|H^m|0\rangle\)。

方法一：直接乘方。计算 \(X^2=\begin{pmatrix}0&1\\1&0\end{pmatrix}\begin{pmatrix}0&1\\1&0\end{pmatrix}=\begin{pmatrix}1&0\\0&1\end{pmatrix}=I\)。于是

\[ H^{2r}=(X^2)^r=I,\qquad H^{2r+1}=X\cdot X^{2r}=X, \]

故

\[\begin{split} \langle0|H^m|0\rangle= \begin{cases}\langle0|I|0\rangle=1,&m\text{ 偶},\\[2pt]\langle0|X|0\rangle=0,&m\text{ 奇}.\end{cases} \end{split}\]

方法二：谱测度。\(X\) 的特征分解为 \(X=|+\rangle\langle+|-|-\rangle\langle-|\)，特征值 \(\lambda_\pm=\pm1\)，特征矢量 \(|\pm\rangle=(|0\rangle\pm|1\rangle)/\sqrt2\)。权重

\[ p_+=|\langle+|0\rangle|^2=\frac12,\qquad p_-=|\langle-|0\rangle|^2=\frac12, \]

即谱测度在 \(\lambda=\pm1\) 上各有质量 \(1/2\)。于是

\[\begin{split} \mu_m=\frac12\cdot 1^m+\frac12\cdot(-1)^m=\frac{1+(-1)^m}{2} =\begin{cases}1,&m\text{ 偶},\\0,&m\text{ 奇}.\end{cases} \end{split}\]

方法三：路径计数。把 \(X\) 看成两个顶点、两条平行边（或一条无向边）的图的邻接矩阵：从 \(0\) 出发每步只能走到 \(1\)、再走回来，路径被唯一决定。\(m\) 为奇数时不可能回到 \(0\)（零条闭合路径）；\(m\) 为偶数时恰有一条（来回交替）。与方法一、二一致。

三种视角——算子代数、谱测度、组合路径——给出同一个答案。这个例子也验证了一般理论：谱测度关于 \(0\) 对称（\(\pm1\) 等权），所以奇数阶矩为零，与 §7.2 中"奇数阶矩恒零"的时钟奇偶性论证同源。

9.2 三顶点路径图：归一化的作用

取三个顶点的路径图的邻接矩阵，\(j\) 为中间顶点：

\[\begin{split} A=\begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix},\qquad |j\rangle=(0,1,0)^T. \end{split}\]

路径计数。从中间顶点出发走两步：先到左端再回来，或先到右端再回来，共 \(2\) 条闭合路径，故 \((A^2)_{jj}=2\)。走四步时，每条两步路径可以继续分裂：逐步数下去得 \((A^4)_{jj}=4\)（先左/右、回中、再左/右、回中，共 \(2\times2=4\) 条）。

谱方法验证。\(A\) 的特征值为 \(\sqrt2,0,-\sqrt2\)（特征方程 \(\det(\lambda I-A)=\lambda(\lambda^2-2)=0\)：展开行列式，\(\lambda^3-\lambda-\lambda=\lambda^3-2\lambda\)）。对应 \(\lambda=\pm\sqrt2\) 的归一化特征矢量为 \(\frac12(1,\pm\sqrt2,1)^T\)，与 \(|j\rangle\) 的内积为 \(\pm\sqrt2/2\)，权重各为 \(1/2\)；\(\lambda=0\) 的特征矢量权重为 \(0\)。于是

\[\begin{split} \mu_m=\frac12(\sqrt2)^m+\frac12(-\sqrt2)^m =\begin{cases}2^{m/2},&m\text{ 偶},\\0,&m\text{ 奇},\end{cases} \end{split}\]

与路径计数一致（\(m=2\) 得 \(2\)，\(m=4\) 得 \(4\)）。

归一化。这里 \(\|A\|=\sqrt2>1\)，所以矩随 \(m\) 增长：\(\mu_m=\|A\|^m\)（\(m\) 偶）。算法运行时必须先归一化 \(H=A/\sqrt2\)，此时 \(\langle j|H^2|j\rangle=1\)，落在 \([-1,1]\) 内，谱采样与 QSVT 的有界性条件才成立；最后把答案乘回 \((\sqrt2)^m=b^m\)。这个小例子把 §1.2 的抽象口径落到了具体数字上：\(b^m\) 不是人为的缩放，而是这个量真实的增长尺度。

10. 本课小结

  • 稀疏矩阵幂的对角元 \(\langle j|H^m|j\rangle\) 是基态 \(|j\rangle\) 的谱测度 \(\nu_j=\sum_r|\langle u_r|j\rangle|^2\delta_{\lambda_r}\) 的第 \(m\) 阶矩；它同时是从 \(j\) 出发长度 \(m\) 的带权闭合路径之和。

  • 量子算法有两条等价路线：谱采样（sparse Hamiltonian simulation + 相位估计 + Monte Carlo，代价 \(\operatorname{poly}(s,m,1/\epsilon,\log N)\)）与 block encoding / QSVT（次数 \(m\) 的多项式变换 + Hadamard test / 振幅估计）。归一化 \(\|H\|\le1\) 同时保证幂函数的 \(m\)-Lipschitz 性与 QSVT 多项式的有界性。

  • 算法不输出稠密的 \(A^m\)，只回答单个矩阵元或少量线性泛函；误差口径是 \(\epsilon b^m\)，归一化是问题定义的核心。

  • Feynman clock 把任意量子电路编码为稀疏 Hermitian propagation matrix，其幂的对角元把演化历史展开成闭合路径的干涉求和；配合 flag 与 padding，接受/拒绝电路给出落在不相交区间的矩，从而该 promise problem 是 PromiseBQP-complete 的。

  • 与字符串重写问题共享"局部规则 \(\to\) 隐式稀疏矩阵 \(\to\) 高阶谱矩"的范式。

练习题

练习 1【稀疏预言机与输入模型】（→ 1.1 节）

  1. 基础：写出稀疏预言机回答的两类查询——位置查询与取值查询——各自的输入与输出，并说明 \(s\)、\(m\)、\(b\)、\(1/\epsilon\) 各应是什么量级（用 \(n=\log N\) 表示）。

  2. 进阶：设 \(A\) 的所有非零矩阵元的绝对值不超过 \(a\)。证明 \(\|A\|\le s\cdot a\)，并说明这个上界与 \(b=\operatorname{poly}(n)\) 的假设相容。

提示：实对称矩阵的算子范数不超过其最大绝对行和，而每行至多 \(s\) 个非零元。

练习 2【归一化与误差口径】（→ 1.2 节）

  1. 基础：补全 \(|(A^m)_{jj}|\le\|A^m\|\le\|A\|^m\le b^m\) 每一步的理由（算子范数的次可乘性与 \(|\langle j|M|j\rangle|\le\|M\|\)），并解释 \(b^m\) 为什么是这个量的自然尺度。

  2. 进阶：本题要求把参数对应关系讲清楚。(a) 设 \(N=2^n\)、\(m=\operatorname{poly}(n)\)、\(1/\epsilon=\operatorname{poly}(n)\)、\(s=\operatorname{poly}(n)\)，说明谱采样算法的总代价是 \(\operatorname{poly}(n)\)，逐因子对应。(b) 设 \(b\) 为大于 \(1\) 的常数（例如 \(b=2\)），则 \(b^m=2^{\operatorname{poly}(n)}\) 指数大；此时若把误差要求从 \(\epsilon b^m\) 改为原值的绝对误差 \(1\)，相当于要求归一化量 \(\mu_m\) 的误差达到 \(b^{-m}\)。说明谱采样算法的代价如何变化，为什么 §1.2 说"复杂度口径完全不同"。

提示：(b) 中把绝对误差 \(1\) 除以自然尺度 \(b^m\)，看它对 \(\mu_m\) 要求的加性误差是多少。

练习 3【路径展开与经典瓶颈】（→ 2.1 节）

  1. 基础：把路径展开恒等式用于 §9.2 的三顶点路径图（\(j\) 为中间顶点）：逐项写出 \(m=2\) 的求和并算出 \((A^2)_{jj}\)，再说明"从 \(j\) 出发长度为 \(m\) 的路径至多 \(s^m\) 条"的理由。

  2. 进阶：解释为什么矩阵元全部非负时 Monte Carlo 路径采样经典可行，而一般实对称矩阵会出现符号问题；并结合 §7 的 BQP-hardness 说明"非负特例经典易"与"一般情形 BQP-complete"为何并不矛盾。

提示：比较"估计量与所求量同量级"与"估计量是大量正负贡献相消后的小差值"两种情形的方差。

练习 4【谱测度与矩公式】（→ 3.1 节）

  1. 基础：验证谱测度的归一性 \(\sum_r p_r=1\)（完备性关系），并对 §9.1 的 \(H=X\)、\(|j\rangle=|0\rangle\) 写出 \(\nu_j\)，计算 \(\mu_2\) 与 \(\mu_3\)。

  2. 基础：对 §9.2 的三顶点路径图，用路径计数直接数出 \((A^6)_{jj}\)，再用谱测度公式 \(\mu_m=\frac12(\sqrt2)^m+\frac12(-\sqrt2)^m\) 核对。中间顶点的谱测度为什么不含 \(\lambda=0\) 的成分？

  3. 进阶：设 \(H=\sum_r\lambda_r|u_r\rangle\langle u_r|\) 是 \(\|H\|\le1\) 的 Hermitian 矩阵的谱分解。证明 \(H^m=\sum_r\lambda_r^m|u_r\rangle\langle u_r|\)，并由此推导 \(\mu_m=\sum_r|\langle u_r|j\rangle|^2\lambda_r^m\)。说明证明中哪一步用到了特征矢量的正交归一性。

提示：\(\lambda=0\) 对应的特征矢量与 \(|j\rangle\) 正交；谱分解推导的关键是 \(\langle u_s|u_r\rangle=\delta_{sr}\)。

练习 5【谱采样算法与误差预算】（→ 4.1 节）

  1. 基础：按顺序写出谱采样算法的四个步骤，并解释相位估计的输出分布为什么恰好是 \(p_r=|\langle u_r|j\rangle|^2\)。

  2. 基础：取 \(\epsilon=0.1\)、\(m=100\)。按正文的对分预算，相位估计需把特征值分辨到多细（\(\delta\)）？要使 Chebyshev 失败概率不超过 \(1/3\) 需要多少独立样本 \(R\)？单次演化时间 \(t\) 是什么量级？

  3. 进阶：证明对 \(|x|,|y|\le1\) 有 \(|x^m-y^m|\le m|x-y|\)（提示：因式分解 \(x^m-y^m\)）。给出一个 \(|x|>1\) 时该界失效的例子，并解释这与"先把 \(A\) 归一化到 \(\|H\|\le1\)"之间的关系。

提示：取 \(x=2\)、\(y=1\)，观察 \(|x^m-y^m|/|x-y|\) 随 \(m\) 的增长。

练习 6【Block Encoding 与 QSVT 路线】（→ 5.1 节）

  1. 基础：逐条核对 \(p(x)=x^m\) 的三个 QSVT 可实施性条件（次数、奇偶性、\([-1,1]\) 上有界），并指出哪一条用到了归一化 \(\|H\|\le1\)。

  2. 进阶：把谱采样路线的 \(\epsilon\) 依赖 \(1/\epsilon^3\) 拆成两个因子并说明各自来源；再解释振幅估计如何把它改进到接近 \(1/\epsilon\)，以及两条路线的 BQP 成员资格结论为什么相同。

提示：\(1/\epsilon^2\) 来自 Monte Carlo 均值的统计涨落，\(m/\epsilon\) 来自相位估计的演化时间；振幅估计用相位估计替换 Monte Carlo。

练习 7【输出边界与 polarization 恒等式】（→ 6.1 节）

  1. 基础：解释为什么量子算法既不输出 \(A^m\) 也不输出它的某一行，输出下界 \(\Omega(N^2)\) 从哪里来；再从 §6.1 举出两个"只输出测量统计而非对象本身"的其他算法例子。

  2. 进阶：展开 \(\langle+|B|+\rangle\) 验证 §6.2 的恒等式，并指出"实对称"用在了哪一步。若 \(B\) 只是 Hermitian（允许复矩阵元），写出用 \(|+\rangle=(|i\rangle+|j\rangle)/\sqrt2\) 与 \(|{+i}\rangle=(|i\rangle+i|j\rangle)/\sqrt2\) 分别恢复 \(\operatorname{Re}\langle i|B|j\rangle\) 与 \(\operatorname{Im}\langle i|B|j\rangle\) 的恒等式。

提示：两个展开式的对角项 \(\frac12\langle i|B|i\rangle+\frac12\langle j|B|j\rangle\) 相同，差别只在交叉项前的系数是 \(1\) 还是 \(\pm i\)。

练习 8【Feynman clock 与 BQP 完备性】（→ 7.1 节）

  1. 基础：写出 propagation matrix \(K\) 的定义式，逐项说明每个求和项对时钟寄存器与数据寄存器分别做什么，并验证 \(K^\dagger=K\)。

  2. 进阶：证明 §7.2 的断言：对时钟基态 \(|j\rangle=|0\rangle|x\rangle\)，当 \(m\) 为奇数时 \(\langle j|K^m|j\rangle=0\)。进一步证明 \(\|K\|\le2\)（提示：把 \(K\) 写成 \(W+W^\dagger\) 并计算 \(W^\dagger W\)）。

  3. 进阶：解释输入 flag、输出 gadget 与 padding 三个补充构造各自解决的问题，并说明为什么最终结论必须陈述为 promise problem；再对照 §8，指出矩阵幂与字符串重写两个 BQP-complete 结果共享的同一条流水线，以及两者符号来源的差别。

提示：闭合时钟路径的前进步数与后退步数相等；流水线是"局部规则 \(\to\) 隐式稀疏矩阵 \(\to\) 高阶谱矩"。

参考文献