# 有效电阻量子算法：Laplacian 线性系统、量子行走与 Span Witness 把一个加权图看成一个电阻网络：每条边是一只电阻，在顶点 $s$ 注入 1 单位电流、从顶点 $t$ 抽出，网络两端所需的电压差就定义为 $s$ 与 $t$ 之间的**有效电阻 (effective resistance)** $R_{st}$。这个看似纯粹的电学量其实同时有三个身份：它是图 Laplacian 伪逆的一个二次型 $b^TL^+b$，是所有单位流中耗散能量的最小值（Thomson 原理），也是衡量两点之间"连通程度"的一个谱量。三个身份恰好对应三条量子算法路线：量子线性系统算法（HHL 类）、量子行走相位估计、以及 span program 的 witness size 估计。 本课的目标是把这三条路线逐一讲透。我们会看到：有效电阻的量子算法可以做到对顶点数 $n$ 只有 $\operatorname{polylog}(n)$ 的依赖，但这个"指数级优势"有严格的前提——图要稀疏、权重要均匀、谱隙不能太小，而且我们只输出一个标量（电阻值），而不是全部 $n$ 个节点电势。脱离这些前提谈 $\log n$ 是误导性的，本课第 8 节专门讨论这些保留条款。 *前置阅读：[相位估计](../ch03-algo-basics/phase-estimation.md)、[HHL 算法](../ch06-scientific-computing/hhl-algorithm-tutorial.md)、[量子行走](../ch06-scientific-computing/quantum-walk-tutorial.md)、[块编码](../ch05-hamiltonian-qsp/block-encoding-tutorial.md)。本章[邻接矩阵模型](adjacency-matrix-properties.md)一节建立的查询复杂度口径也会被用到。* :::{admonition} 本课知识点 :class: tip 1. **[有效电阻的物理意义](#resistance-physical-origin)**——能写出有效电阻的电路定义，解释它为何度量两点间路径的"总带宽"，并写出它与通勤时间的恒等式 $\operatorname{Commute}(s,t) = 2mR_{st}$。 2. **[Laplacian、电路方程与伪逆二次型](#laplacian-circuit-equation)**——能用关联矩阵构造 $L = B^TWB$ 并证明其半正定、写出连通图的核空间，再从 Ohm 定律与 Kirchhoff 电流定律推导 $Lv = b$ 与 $R_{st} = b^TL^+b$。 3. **[Thomson 原理](#thomson-principle)**——能写出单位流与耗散能的定义，用正交性论证证明 $R_{st} = \min_{B^Tj=b}\mathcal{E}(j)$，并由此推出 Rayleigh 单调性。 4. **[谱展开：逆谱权重](#spectral-expansion)**——能推导 $R_{st} = \sum_{j\ge2}|\langle u_j,b\rangle|^2/\lambda_j$，解释电阻为何由谱的低端主导，以及谱隙进入复杂度的原因。 5. **[量子线性系统路线](#qlsa-route)**——能把 $R_{st} = \langle b|L^+|b\rangle$ 拆成"制备解态 + 振幅与内积估计"两步，解释归一化 Laplacian 块编码的必要性，并逐项说明复杂度 $\operatorname{poly}(d, c, \log n, 1/\lambda, 1/\epsilon)$ 中每个因子的来源。 6. **[量子行走路线](#quantum-walk-route)**——能证明 $\mathcal{D}(P) = I - \mathcal{L}$，由 $\cos\theta_j = 1-\lambda_j$ 推出 $\theta_j \approx \sqrt{2\lambda_j}$，并比较经典混合时间与量子相位估计时间的谱隙依赖。 7. **[Span program 与 witness size](#span-program-route)**——能构造输入向量 $|a_e\rangle = \sqrt{w_e}(|u\rangle - |v\rangle)$，证明正 witness 与单位流一一对应、最小 witness size 等于 $R_{st}$，并比较 approximate span program 的两个复杂度界。 8. **[指数优势的条件与失效场景](#quantum-advantage-conditions)**——能列出 polylog 优势成立的全部前提，用路径图 $\lambda_2 = \Theta(1/n^2)$ 解释谱隙如何单独摧毁优势，并说明"只输出少量标量"这一输出限制。 ::: ## 1. 问题背景：从哪里来，为什么重要 (resistance-physical-origin)= ### 1.1 物理起源 有效电阻的概念来自 19 世纪的电路理论。Kirchhoff 在 1847 年给出了电路的两条基本定律（电流守恒与电压环路定律），Thomson（即 Lord Kelvin）随后指出：真实电流分布有一个变分刻画——在所有满足守恒约束的电流分布中，真实分布使总焦耳热最小。这个变分原理（第 3 节的 Thomson 原理）把"电学量"变成了纯粹的"图上的优化问题"，从此有效电阻脱离了物理语境，成为图论对象。 为什么图论学家关心它？因为 $R_{st}$ 是两点之间连通性的一个精细度量： - 若 $s$、$t$ 不连通，不存在从 $s$ 到 $t$ 的电流通道，定义 $R_{st} = +\infty$； - 若两点之间只有一条长路径（瓶颈），电阻随路径长度线性增长； - 若两点之间有许多条独立的并行路径，电流被分流，电阻显著下降。 因此 $R_{st}$ 比"是否连通""最短路径多长"都包含更多信息，它度量的是两点之间路径的**总带宽**。这一直觉在随机游走理论中得到严格化：无权连通图中两点间的**通勤时间 (commute time)**——从 $s$ 出发随机游走到 $t$ 再返回 $s$ 的期望步数——恰好等于 $2mR_{st}$（$m$ 为边数），这是随机游走理论中的经典恒等式，第 6 节会用到它。有效电阻还出现在图稀疏化（按有效电阻采样边可以保持图的谱结构）、聚类与谱图论中。 ### 1.2 经典算法能做什么，瓶颈在哪 计算 $R_{st}$ 归约为求解 Laplacian 线性系统 $Lv = b$（第 2 节推导）。经典算法经过几十年发展已经相当快：共轭梯度类迭代法大约需要 $O(m\sqrt{\kappa})$ 次算术运算（$\kappa$ 为条件数），而 Spielman–Teng 开创的 Laplacian 专用求解器可以做到近线性时间 $\widetilde O(m\,\operatorname{polylog}(1/\epsilon))$。也就是说，**经典算法并没有指数级的困难**——量子算法若想取得指数优势，必须换一种比较方式。 换的方式是改变输入输出模型。量子算法假设： - 图通过 oracle（邻接矩阵查询或邻接表/权重查询）相干访问，不需要把整张 $\Theta(n^2)$ 规模的图读入内存； - 输出不是 $n$ 维电压向量 $v$，而是单个标量 $R_{st}$（或少量几个电学量）。 在这个模型下，经典算法通常至少要处理与图规模多项式相关的数据量，而量子算法有机会做到 $\operatorname{poly}(d, c, \log n, 1/\lambda, 1/\epsilon)$——对 $n$ 只有多对数依赖。历史上这条线索由 Harrow–Hassidim–Lloyd 的量子线性系统算法（Zoo 编号 104）开启，Guoming Wang（Zoo 编号 210）把它专门化到电阻网络并分析了复杂度的各个因子，Ito 与 Jeffery（Zoo 编号 280）则用 approximate span program 给出了查询/时间复杂度不同的另一条路线，还附带 $O(\log n)$ 的工作空间优势。本课逐一展开这三条路线，并在第 8 节讨论"指数优势何时成立、何时失效"。 ## 2. Laplacian 与电路方程 本节把物理问题翻译成线性代数。所有后面三条量子路线，最终都在估计同一个线性代数对象。 (laplacian-circuit-equation)= ### 2.1 图、电导与关联矩阵 设无向加权图 $G = (V, E)$，$|V| = n$，$|E| = m$。给每条边 $e$ 一个正电阻 $r_e > 0$，其倒数称为**电导 (conductance)** $$ w_e = \frac{1}{r_e}. $$ 无向边没有天然方向，但写方程时需要给每条边**任选一个定向**：定向只影响中间记号的符号，不影响任何物理量（下面会看到 Laplacian $L$ 本身与定向无关）。对定向边 $e = (u, v)$，我们称 $u$ 为尾点、$v$ 为头点。定义**关联矩阵 (incidence matrix)** $B \in \mathbb{R}^{E \times V}$：第 $e = (u,v)$ 行在尾点 $u$ 处取 $+1$、头点 $v$ 处取 $-1$，其余为零，即 $$ B_{e,x} = \begin{cases} +1, & x = u,\\ -1, & x = v,\\ 0, & \text{其他}. \end{cases} $$ $B$ 的作用是把"节点上的量"变成"边上的差"：对任意节点向量 $x \in \mathbb{R}^V$（比如电势）， $$ (Bx)_e = x_u - x_v, $$ 即边 $e$ 两端的势差。反过来，$B^T$ 把"边上的量"（比如边流 $j \in \mathbb{R}^E$）聚合成节点上的净流出： $$ (B^T j)_x = \sum_{e:\,x\text{ 是尾点}} j_e - \sum_{e:\,x\text{ 是头点}} j_e. $$ 令 $W = \operatorname{diag}(w_e)$ 为电导的对角矩阵，定义**加权 Laplacian** $$ L = B^T W B. $$ 展开矩阵元可以看到 $L$ 的显式形式（这同时说明 $L$ 与定向无关：把某条边反向，$B$ 的对应行变号，$B^TWB$ 不变）：对角元 $L_{uu} = \sum_{e \ni u} w_e$（记为加权度 $d_u$），非对角元 $L_{uv} = -w_{uv}$（$u \neq v$ 有边时），其余为零。 $L$ 的两个性质是后文一切推导的基础： - **半正定性**：对任意 $x \in \mathbb{R}^V$， $$ x^T L x = x^T B^T W B x = \sum_{e=(u,v)} w_e\,(x_u - x_v)^2 \ge 0, $$ 第一步代入 $L$ 的定义，第二步把 $(Bx)_e = x_u - x_v$ 按边求和。右边是平方的非负加权和，故 $L \succeq 0$。 - **核空间**：上式取零当且仅当每条边两端 $x_u = x_v$，即 $x$ 在每个连通分量上取常值。特别地，连通图的核空间为 $\ker L = \operatorname{span}\{\mathbf{1}\}$，其中 $\mathbf{1} = (1,1,\ldots,1)^T$，零本征值一重。 ### 2.2 Kirchhoff 定律与方程 $Lv = b$ 现在在 $s$ 注入 1 单位电流、从 $t$ 抽出。外部注入用节点向量 $$ b = e_s - e_t $$ 表示（$e_x$ 是第 $x$ 个标准基矢），即 $b_s = +1$、$b_t = -1$、其余为零。注意 $b$ 的坐标和为零——"注入多少就抽出多少"，这一点马上会起关键作用。 电路由两条定律支配： - **Ohm 定律**：边 $e = (u,v)$ 上的电流正比于两端势差，$j_e = \frac{v_u - v_v}{r_e} = w_e(v_u - v_v)$。写成向量形式（用 2.1 节 $(Bv)_e = v_u - v_v$）： $$ j = WBv. $$ - **Kirchhoff 电流定律 (KCL)**：每个内部节点流入等于流出；在 $s$ 净流出恰为注入的 $1$，在 $t$ 净流入 $1$。净流出向量由 $B^Tj$ 给出（2.1 节），故约束是 $$ B^T j = b. $$ 把 Ohm 定律代入 KCL，消去 $j$： $$ B^T(WBv) = b \quad\Longleftrightarrow\quad Lv = b. $$ 于是**节点电势 $v$ 是 Laplacian 线性系统 $Lv = b$ 的解**。 这个方程有两个细节必须交代。第一，$L$ 不可逆（核空间非空），方程何时有解？有解当且仅当 $b$ 落在 $L$ 的像空间，而实对称矩阵的像空间是核空间的正交补，所以需要 $b \perp \ker L$。对连通图这要求 $b \perp \mathbf{1}$，即 $b$ 坐标和为零——这正是上面强调的"注入等于抽出"。第二，解不唯一：若 $v$ 是解，则 $v + c\mathbf{1}$ 也是解（$\mathbf{1} \in \ker L$）。物理上这对应"电势只有相对意义，零点可以任取"；所有可观测的势差 $v_s - v_t$ 都是确定的。 ### 2.3 伪逆与二次型 $R_{st} = b^TL^+b$ **有效电阻**定义为维持 1 单位电流所需的电压差： $$ R_{st} = v_s - v_t. $$ 为了把它写成闭式，引入 **Moore–Penrose 伪逆 (pseudo-inverse)** $L^+$：它在 $\ker L$ 上取零，在 $\ker L$ 的正交补上取通常的逆。由于 $b \perp \ker L$， $$ v := L^+ b $$ 是 $Lv = b$ 的一个合法解（验证：$LL^+$ 是向 $\ker L$ 正交补的投影，而 $b$ 在该正交补内，故 $Lv = LL^+b = b$）。通解为 $v + c\mathbf{1}$。现在计算电阻： $$ R_{st} = v_s - v_t = (e_s - e_t)^T v = b^T(L^+ b + c\mathbf{1}) = b^T L^+ b, $$ 最后一步用了 $b^T\mathbf{1} = 0$（$b$ 坐标和为零）——任意常数势自动消去，结果与解的选取无关。 我们把第一个核心结论框出来： $$ R_{st} = b^T L^+ b,\qquad b = e_s - e_t. $$ 这个恒等式是量子线性系统路线（第 5 节）的直接出发点：$R_{st}$ 是"一个二次型"，而二次型正是"制备态 + 估计内积"类量子原始操作擅长估计的对象。 **物理一致性检查**：$b^TL^+b$ 还等于网络的总耗散功率。事实上 $$ b^T v = v^T L v = v^T B^TWB\, v = \sum_e w_e(v_u - v_v)^2 = \sum_e \frac{j_e^2}{w_e} = \sum_e r_e j_e^2, $$ 其中第二步代入 $Lv = b$ 的转置（$L$ 对称，$b^Tv = v^Tb = v^TLv$），第四步用 Ohm 定律 $j_e = w_e(v_u - v_v)$。注入 1 单位电流、端电压为 $R_{st}$，功率 $= I \cdot V = R_{st}$，与焦耳热 $\sum_e r_e j_e^2$ 一致。这个能量视角在下一节成为独立的变分原理。 ## 3. Thomson 原理：电阻是最小流能量 上一节从"真实电流"（Ohm 定律 + KCL 的解）出发得到电阻。Thomson 原理反过来了：它完全不提 Ohm 定律，宣称**在所有满足电流守恒的单位流中，真实流恰好是耗散能量最小的那个**，且最小能量就是 $R_{st}$。这个变分刻画是 span program 路线（第 7 节）的桥梁。 (thomson-principle)= ### 3.1 单位流与耗散能 边流向量 $j \in \mathbb{R}^E$ 若满足 $$ B^T j = b, $$ 就称为从 $s$ 到 $t$ 的**单位流 (unit flow)**：由 2.1 节，这正是"内部节点守恒、$s$ 净流出 1、$t$ 净流入 1"。注意单位流只要求守恒，**不要求**满足 Ohm 定律——比如可以让电流绕远路走，只要账面上守恒。定义流的**耗散能** $$ \mathcal{E}(j) = \sum_e r_e j_e^2 = j^T W^{-1} j, $$ 等号用了 $r_e = 1/w_e$ 即 $W^{-1} = \operatorname{diag}(r_e)$。 **Thomson 原理**断言： $$ R_{st} = \min_{j:\,B^Tj = b} \mathcal{E}(j), $$ 且最小值在 Ohm 流 $j^* = WBv$（$Lv = b$）处取到。 ### 3.2 证明：正交性论证 证明分两步：先验证 $j^*$ 可行，再证明任何可行流的能量都不小于 $\mathcal{E}(j^*)$。 第一步，可行性。$B^Tj^* = B^TWBv = Lv = b$，故 $j^*$ 是单位流。其能量（2.3 节末已算过）： $$ \mathcal{E}(j^*) = (WBv)^TW^{-1}(WBv) = v^TB^TWBv = v^TLv = b^TL^+b = R_{st}, $$ 第一步展开定义，第二步用 $W^TW^{-1}W = W$ 与 $L = B^TWB$，第三步用 $Lv = b$ 与 $v^Tb = b^TL^+b$（$L^+$ 对称）。 第二步，最优性。任取可行流 $j$，记差流 $\delta = j - j^*$。$j$ 与 $j^*$ 都满足 $B^T(\cdot) = b$，相减得 $$ B^T\delta = 0, $$ 即 $\delta$ 是一个**环流 (circulation)**：在每个节点净流入为零。展开能量（$\mathcal{E}$ 是二次型）： $$ \mathcal{E}(j) = \mathcal{E}(j^* + \delta) = \mathcal{E}(j^*) + 2\,\delta^T W^{-1} j^* + \mathcal{E}(\delta). $$ 关键在于交叉项为零： $$ \delta^T W^{-1} j^* = \delta^T W^{-1} W B v = \delta^T B v = (B^T\delta)^T v = 0, $$ 依次代入 $j^* = WBv$、化简 $W^{-1}W = I$、转置，最后用环流条件 $B^T\delta = 0$。物理含义：**环流与 Ohm 流在能量内积下正交**——绕圈的流不携带净电流，也不与真实流交换能量。因此 $$ \mathcal{E}(j) = \mathcal{E}(j^*) + \mathcal{E}(\delta) \ge \mathcal{E}(j^*) = R_{st}, $$ 等号当且仅当 $\delta = 0$（$\mathcal{E}(\delta) = \sum_e r_e\delta_e^2$ 且 $r_e > 0$）。Q.E.D. ### 3.3 用 Lagrange 乘子再看一遍 正交性论证简洁，但"最小值点是 Ohm 流"这件事也可以用标准的约束优化语言重述，二者互为印证。构造 Lagrange 函数（约束 $B^Tj = b$ 共 $n$ 个等式，乘子记为向量 $2v$——因子 2 是为了后面式子干净）： $$ \mathcal{L}(j, v) = j^TW^{-1}j - 2v^T(B^Tj - b). $$ 对 $j$ 求梯度并置零： $$ \nabla_j \mathcal{L} = 2W^{-1}j - 2Bv = 0 \quad\Longrightarrow\quad j = WBv. $$ 代回约束 $B^Tj = b$ 得 $B^TWBv = Lv = b$。于是 Lagrange 乘子 $v$ 恰好就是电势——这是一个一般现象的实例：**流网络上的对偶变量就是节点势**。驻点条件自动给出 Ohm 定律，可行性给出 KCL，变分原理与电路定律完全等价。 ### 3.4 推论：Rayleigh 单调性 Thomson 原理立刻给出一个定性结论：**增大任何一条边的电阻（或删除一条边），任意两点间的有效电阻不降**。原因是删除边等价于把可行流集合缩小（强迫该边流量为零），约束变多，最小值只能变大或不变；增大 $r_e$ 则直接增大目标函数。这与直觉一致：砍掉路径只会让两点"更不连通"。第 8 节讨论量子算法失效的实例时，这个单调性背后的"瓶颈路径"直觉会再次出现。 (spectral-expansion)= ## 4. 谱展开：电阻的本征值表达 第 2 节把 $R_{st}$ 写成伪逆二次型，第 3 节写成最小能量。第三种写法按 $L$ 的本征向量展开，它是量子行走路线（第 6 节）的出发点，也解释了"谱隙"这个参数为什么进入所有复杂度。 设图连通，$L$ 的谱分解为 $$ L = \sum_{j=1}^{n} \lambda_j\, u_j u_j^T,\qquad 0 = \lambda_1 < \lambda_2 \le \cdots \le \lambda_n, $$ 其中 $u_1 = \mathbf{1}/\sqrt{n}$ 是零本征值的归一化本征向量（2.1 节：连通图零本征值一重）。伪逆按定义在核上取零、在正交补上取逆，因此其谱分解为 $$ L^+ = \sum_{j=2}^{n} \frac{1}{\lambda_j}\, u_j u_j^T. $$ 代入 $R_{st} = b^TL^+b$： $$ R_{st} = \sum_{j=2}^{n} \frac{|\langle u_j, b\rangle|^2}{\lambda_j}. $$ 逐项读懂这个式子： - $|\langle u_j, b\rangle|^2$ 是注入向量 $b$ 在第 $j$ 个本征方向上的权重（注意 $\sum_j |\langle u_j,b\rangle|^2 = \|b\|^2 = 2$）； - 每个方向被 $\lambda_j$ "打折"：大的本征值（图上"高频振荡"的模式）贡献小，小的本征值（"平缓变化"的模式）贡献大； - 特别地，若 $b$ 的权重集中在小本征值方向上，电阻就大。极端情形是路径图（第 8 节）：$\lambda_2 = \Theta(1/n^2)$ 极小，而端点注入 $b = e_s - e_t$ 与 $u_2$ 有常数量级的重叠，仅 $j=2$ 一项就贡献 $\Theta(n^2) \cdot \Theta(1) = \Theta(n^2)$ 量级的……等等，这与 $R_{st} = n-1$ 似乎矛盾？ 这里需要小心，它正好是一个展示"谱式如何逐项核算"的机会：对路径图，$u_2$ 近似为缓变的余弦波形，端点处取值约为 $\pm\sqrt{2/n}$ 量级，故 $|\langle u_2, b\rangle|^2 = \Theta(1/n)$，贡献为 $\Theta(1/n)/\Theta(1/n^2) = \Theta(n)$，与 $R_{st} = n - 1$ 同阶，并不矛盾。这个核算也说明了本节的核心信息：**电阻的大小由谱的低端（小 $\lambda_j$）主导**。任何想通过"分辨谱"来估计电阻的算法（第 6 节），其分辨精度必须达到最小相关本征值的量级——这就是谱隙 $\lambda_2$（或其下界）进入复杂度的原因。 ## 5. 路线一：量子线性系统 (qlsa-route)= ### 5.1 思路 第 2 节给出 $R_{st} = b^TL^+b$。把它拆成两步，每一步都对应一个标准量子原始操作： 1. **制备解态**：用 HHL 类量子线性系统算法（本站第 6 章）近似制备 $$ |v\rangle \propto L^+|b\rangle, $$ 其中 $|b\rangle = (|s\rangle - |t\rangle)/\sqrt{2}$ 是归一化的注入向量（用本站第 7 章的态制备方法，$O(1)$ 深度即可制备）。 2. **估计二次型**：设 $|v\rangle = L^+|b\rangle/\|L^+|b\rangle\|$，则 $$ R_{st} = \langle b|L^+|b\rangle = \|L^+|b\rangle\|\cdot\langle b|v\rangle. $$ 两个因子分别估计：QLSA 制备 $|v\rangle$ 的成功振幅正比于 $\|L^+|b\rangle\|/\kappa$（$\kappa$ 为条件数），用振幅估计（本站第 3 章）读出它即得范数因子；$\langle b|v\rangle$ 是已知态 $|b\rangle$ 与已制备态 $|v\rangle$ 的内积，用 Hadamard 检验或交换检验估计。两者相乘恢复 $R_{st}$。同样的测量框架稍作改动，可以估计某个节点的电压（换成 $\langle e_x|v\rangle$）、某条边的电流（换成相邻节点势差）与总耗散功率——这些都是"少量标量输出"。 ### 5.2 归一化 Laplacian 与块编码 直接对 $L$ 做块编码有一个技术障碍：块编码要求算子范数有已知的上界作归一化，而 $L$ 的范数随加权度增长，不同顶点差异悬殊。标准处理是改用**归一化 Laplacian** $$ \mathcal{L} = D^{-1/2} L D^{-1/2},\qquad D = \operatorname{diag}(d_u),\quad d_u = \sum_v w_{uv}. $$ $\mathcal{L}$ 的矩阵元为 $\mathcal{L}_{uu} = 1$、$\mathcal{L}_{uv} = -w_{uv}/\sqrt{d_ud_v}$；由与 2.1 节类似的恒等式 $x^T\mathcal{L}x = \sum_{e=(u,v)}w_e\,(x_u/\sqrt{d_u} - x_v/\sqrt{d_v})^2$ 可以证明其本征值全部落在 $[0, 2]$ 内，与图的规模、权重绝对值无关——范数被"归一化"掉了。电阻信息仍然完整保留在 $\mathcal{L}$ 的谱中（只是源项和读出方式需要相应地按 $D^{-1/2}$ 缩放）。 对最大（加权）度为 $d$ 的稀疏图，$\mathcal{L}$ 是 $d$-稀疏矩阵：每行至多 $d$ 个非零元，且可以通过邻接/权重 oracle（给定顶点，查询其第 $k$ 个邻居及边权）相干定位。按本站第 5 章的稀疏矩阵块编码构造，这些 oracle 足以实现 $\mathcal{L}$ 的块编码，单次成本随 $d$ 多项式增长、随 $n$ 至多对数增长。这正是复杂度表达式中因子 $d$ 与 $\log n$ 的来源。 ### 5.3 复杂度：逐项因子分析 Wang（Zoo 编号 210）给出的总复杂度可以写成 $$ \operatorname{poly}\!\left(d,\; c,\; \log n,\; \frac{1}{\lambda},\; \frac{1}{\epsilon}\right), $$ 其中各因子的来源如下： - $d$：最大加权度，即稀疏度。它决定块编码 $\mathcal{L}$ 的 oracle 调用与门开销——每行的非零元越多，相干寻址越贵。 - $c = w_{\max}/w_{\min}$（等价地可用电阻比）：权重范围的宽度。权重过于悬殊时，归一化后小权重边对应的矩阵元被压到接近零，块编码与相位分辨的有效精度被摊薄，成本随之上升。这个因子提醒我们："稀疏"之外还需要"权重均匀"。 - $\log n$：寄存器规模与相干寻址的基本开销。这是"指数优势"的载体——整个算法只用 $O(\log n)$ 个量子比特表示 $n$ 个顶点的图。 - $1/\lambda$：$\lambda$ 是归一化 Laplacian 的**最小非零本征值**。因为 $\mathcal{L}$ 的谱落在 $[0,2]$，条件数为 $\kappa = \lambda_{\max}/\lambda \le 2/\lambda$，所以 $1/\lambda$ 就是条件数来源：QLSA 的开销随 $\kappa$ 多项式增长（相位估计需要分辨到精度 $\lambda$，演化时间正比于 $1/\lambda$）。 - $1/\epsilon$：输出精度。振幅估计把二次型估到相对/加性精度 $\epsilon$ 需要 $\Theta(1/\epsilon)$ 量级的重复，这一因子在"只输出标量"的读出阶段不可避免。 **保留条款（重要）**：上述表达式中的多项式度依赖具体模型假设——oracle 的形式、权重编码的精度、以及对谱隙的处理方式。特别地，Wang 的论文同时给出了查询下界，证明在该 oracle 模型下对 $1/\lambda$（等价地，对图规模通过谱隙传导）的多项式依赖**不能完全去掉**：存在图族使得任何量子算法都必须付出随谱隙倒数多项式增长的查询数。换句话说，$1/\lambda$ 不是分析技术不够好留下的 artifact，而是问题的内禀硬度。第 8 节的路径图就是这个下界起作用的实例。 ## 6. 路线二：量子行走 (quantum-walk-route)= ### 6.1 随机游走与 discriminant 第二条路线换一个角度：不求解线性系统，而是"听"图的谱。由电导定义图上的随机游走：在顶点 $u$ 处，沿边 $(u,v)$ 走出去的概率正比于该边电导， $$ P_{uv} = \frac{w_{uv}}{d_u},\qquad d_u = \sum_{v} w_{uv}, $$ 即 $P = D^{-1}A_w$（$A_w$ 为加权邻接矩阵）。$P$ 一般不对称（$P_{uv} \neq P_{vu}$），但它与对称矩阵**相似**——这正是量子化处理的前提。定义 **discriminant** $$ \mathcal{D}(P) = D^{1/2} P D^{-1/2} = D^{-1/2} A_w D^{-1/2}. $$ 第一个等号是定义（相似变换，故 $\mathcal{D}(P)$ 与 $P$ 本征值全同），第二个等号代入 $P = D^{-1}A_w$：$D^{1/2}D^{-1}A_wD^{-1/2} = D^{-1/2}A_wD^{-1/2}$。右边是对称矩阵，矩阵元为 $w_{uv}/\sqrt{d_ud_v}$。与 5.2 节归一化 Laplacian 的矩阵元对比，立即得到关键恒等式 $$ \mathcal{D}(P) = I - \mathcal{L}. $$ 所以随机游走的谱与 Laplacian 的谱互为镜像：$\mathcal{D}(P)$ 的本征值是 $1 - \lambda_j(\mathcal{L})$，本征向量相同。谱隙 $\lambda_2$ 恰好是随机游走的混合速率——谱完全统一了。 ### 6.2 Szegedy 行走：把谱变成相位 经典随机游走不是酉演化，不能直接上量子计算机。Szegedy 的构造（本站第 6 章量子行走一节）把 $P$ 提升为双倍空间上的酉算子 $W(P)$，其谱由 discriminant 完全决定：对 $\mathcal{D}(P)$ 的每个本征值 $\nu_j = 1 - \lambda_j$（对应本征向量 $\tilde u_j$），$W(P)$ 有一对共轭本征相位 $$ e^{\pm i\theta_j},\qquad \cos\theta_j = \nu_j = 1 - \lambda_j. $$ **小本征值对应小相位**：当 $\lambda_j \ll 1$ 时，由 $1 - \cos\theta_j = \lambda_j$ 与 $1 - \cos\theta \approx \theta^2/2$ 得 $$ \theta_j \approx \sqrt{2\lambda_j}. $$ 这就是量子行走带来平方加速的机制：经典侧，分辨谱隙 $\lambda$ 需要混合时间 $\Theta(1/\lambda)$ 步；量子侧，相位估计要分辨相位 $\theta \approx \sqrt{2\lambda}$，只需演化时间 $\Theta(1/\theta) = \Theta(1/\sqrt{\lambda})$。注意代价的依存关系没有变：**小谱隙仍然意味着长的相位分辨时间**——平方根改善的是依赖的幂次，而不是消掉了依赖。 ### 6.3 从谱测量到电阻 如何用电阻？由第 4 节的谱展开， $$ R_{st} = \sum_{j\ge 2} \frac{|\langle u_j, b\rangle|^2}{\lambda_j} $$ 是"$b$ 的谱测度下函数 $1/\lambda$ 的期望"。量子行走路线正是按这个结构操作： 1. 制备与源汇相关的初态（本质上是归一化的 $|s\rangle - |t\rangle$ 提升到行走空间）； 2. 对该初态做 Szegedy 行走的相位估计：以概率 $|\langle u_j, b\rangle|^2/\|b\|^2$ 采样到本征相位 $\pm\theta_j$，即对谱进行测量； 3. 结合受控旋转与振幅估计，把谱测度下的 $1/\lambda_j$（由 $\theta_j$ 经 $1-\cos\theta_j = \lambda_j$ 换算）加权平均，得到相应的 **Green's function**——即 $R_{st}$。 整个过程只输出一个标量，**无需输出整个电势向量**——这是它相对"制备 $|v\rangle$ 再逐坐标读取"的朴素方案的根本优势。同理， commute/hitting 结构也可由此估计：无权连通图中的经典恒等式 $$ \operatorname{Commute}(s,t) = 2mR_{st} $$ （通勤时间 $=$ 从 $s$ 到 $t$ 的期望 hitting time 加上返程）说明 hitting time 类量与有效电阻只差一个全局因子 $2m$，凡是能估一个就能估另一个。 ### 6.4 两条路线的统一 值得停下来回看：线性系统路线估计 $b^TL^+b$，行走路线估计谱测度下的 $\sum_j |\langle u_j,b\rangle|^2/\lambda_j$——按第 4 节，这两个表达式**就是同一个数**的两种写法。两条路线使用不同的中间态（解态 $|v\rangle$ vs. 谱采样）和不同的 oracle 包装（块编码 vs. Szegedy 行走），但最终都在估计 **Laplacian 逆谱权重**。区别在工程层面：行走路线天然带平方根级的谱隙依赖改善，且相位估计框架对"只估标量"的任务更直接。 ## 7. 路线三：Span program 与 witness size (span-program-route)= ### 7.1 从流到 witness 第三条路线把 Thomson 原理"量子化"。为每条（任选定向的）边 $e = (u,v)$ 准备输入向量 $$ |a_e\rangle = \sqrt{w_e}\,(|u\rangle - |v\rangle), $$ 目标向量取 $$ |\tau\rangle = |s\rangle - |t\rangle. $$ 一个 **span program** 问的是：$|\tau\rangle$ 是否在 $\{|a_e\rangle\}$ 的张成空间内？这里我们关心更精细的量：**正 witness**——一组系数 $c_e$，满足 $$ \sum_e c_e\,|a_e\rangle = |\tau\rangle, $$ 且其 **witness size** 定义为 $\sum_e c_e^2$。 先看 witness 条件的含义。把 $|a_e\rangle$ 的定义代入，比较每个顶点 $x$ 的系数： $$ \sum_{e:\,x\text{ 是尾点}} c_e\sqrt{w_e} \;-\; \sum_{e:\,x\text{ 是头点}} c_e\sqrt{w_e} \;=\; b_x. $$ 与 2.1 节 $B^T$ 的作用对比：令 $j_e = c_e\sqrt{w_e}$（带符号，负号表示逆着定向流），上式正是 $B^Tj = b$。所以 **witness 与单位流一一对应**： $$ \{c_e\} \text{ 是 witness} \quad\Longleftrightarrow\quad j_e = c_e\sqrt{w_e} \text{ 是单位流}. $$ 特别地，$s$、$t$ 连通时 witness 存在（沿任一条 $s$–$t$ 路径送流即可）；不连通时不存在，这与"电阻视为无穷"一致。 ### 7.2 Witness size 恰好等于有效电阻 在这个对应下计算 witness size： $$ \sum_e c_e^2 = \sum_e \frac{j_e^2}{w_e} = \sum_e r_e j_e^2 = \mathcal{E}(j), $$ 第一步代入 $c_e = j_e/\sqrt{w_e}$，第二步用 $1/w_e = r_e$，第三步是 3.1 节耗散能的定义。对所有 witness 取最小，等价于对所有单位流取能量最小，由 Thomson 原理（第 3 节）： $$ \min_{\text{witness } c} \sum_e c_e^2 = \min_{B^Tj = b} \mathcal{E}(j) = R_{st}. $$ **结论：有效电阻就是 connectivity span program 的正 witness size**——$\sqrt{w_e}$ 这个缩放正是为此设计的（它把电导换算成电阻加权）。第 3 节的变分原理在这里兑现为一条算法路线：**估计电阻 $=$ 估计 span program 的 witness size**。 ### 7.3 Approximate span program：从"判断"到"估计" 标准 span program 算法（如连通性判定）只回答"target 是否在 span 内"，输出一个比特。Ito 与 Jeffery 的 **approximate span program**（Zoo 编号 280）把这个框架升级为估计问题：通过相位检测（phase estimation 在 span program 算子上的版本）估计 witness size 本身，相对误差 $\epsilon$。在**邻接矩阵查询模型**下（见本章邻接矩阵一节），估计 $R_{st}$ 的时间复杂度为 $$ \widetilde{O}\!\left(\frac{n\sqrt{R_{st}}}{\epsilon^{3/2}}\right). $$ 逐项读懂各因子： - $n$：邻接矩阵模型的输入规模尺度——实现 span program 算子的一步涉及对顶点指标的相干处理，成本随顶点数（而非边数）增长，这是该模型的口径； - $\sqrt{R_{st}}$：witness size 的平方根。这是 span program 算法的标志性量子加速：经典地"读出一个大小为 $W$ 的 witness"需要 $\Omega(W)$，量子算法只需 $O(\sqrt{W})$ 尺度；这里 $W = R_{st}$； - $\epsilon^{-3/2}$：approximate span program 的误差—相位间隙权衡。直接分析中精度与相位分辨两个来源的误差叠加，给出 $3/2$ 的幂次。 若额外已知谱隙下界 $\mu \le \lambda_2$，改进的相位间隙分析把精度依赖优化为 $$ \widetilde{O}\!\left(\frac{n}{\epsilon}\sqrt{\frac{R_{st}}{\mu}}\right), $$ 并且整个算法只需 $O(\log n)$ 的工作空间——这是三条路线中空间效率最高的。 两个界何时谁更优？比较 $\epsilon$ 依赖：第二个界的 $\epsilon^{-1}$ 优于第一个界的 $\epsilon^{-3/2}$；但它多付了 $\mu^{-1/2}$。具体地， $$ \frac{n}{\epsilon}\sqrt{\frac{R_{st}}{\mu}} \;<\; \frac{n\sqrt{R_{st}}}{\epsilon^{3/2}} \quad\Longleftrightarrow\quad \frac{1}{\sqrt{\mu}} < \frac{1}{\sqrt{\epsilon}} \quad\Longleftrightarrow\quad \mu > \epsilon. $$ （第一步约去公因子 $n\sqrt{R_{st}}$ 并比较剩余部分，第二步两边平方取倒数。）所以：**只要谱隙下界不比目标精度还小，第二个界就占优**。两个界是同一算法在不同已知信息下的分析，实践中按可获得的 $\mu$ 选择。 另一个一致性检查：无权图中 $R_{st}$ 至多为直径（串联不等式，见第 9 节），故 $R_{st} \le n - 1$。代入第一个界，最坏情况为 $\widetilde{O}(n^{3/2}/\epsilon^{3/2})$，与连通性判定的 $\Theta(n^{3/2})$ 查询复杂度（本章邻接矩阵一节）相容——估计比判定多付精度因子，判定对应 $\epsilon$ 取常数的特例。 ## 8. 何时才有指数优势 现在把散落的保留条款集中起来，回答最重要的问题：什么时候上述算法真正带来相对经典方法的指数优势？ (quantum-advantage-conditions)= ### 8.1 充分条件 若同时满足 - **稀疏**：$d = \operatorname{polylog}(n)$； - **权重均匀**：$c = w_{\max}/w_{\min} = \operatorname{polylog}(n)$； - **谱隙良好**：$1/\lambda = \operatorname{polylog}(n)$（$\lambda$ 为归一化 Laplacian 最小非零本征值）； - **精度温和**：$1/\epsilon = \operatorname{polylog}(n)$； - **输入可相干访问**：邻接/权重 oracle 与源项 $|b\rangle$ 的制备都可高效相干实现， 则第 5、6 节的线性系统/行走算法总成本为 $\operatorname{polylog}(n)$——对顶点数只有多对数依赖。而已知经典算法通常至少要处理与图规模多项式相关的数据量（哪怕近线性的 Laplacian 求解器也要 $\widetilde\Theta(m)$），于是形成**潜在的指数差距**。注意"潜在"二字：这个比较的前提是 oracle 模型——如果任务要求显式读入整张邻接表，输入成本本身就把量子优势吞掉了。 ### 8.2 反例：路径图 所有条件里最容易被忽视、也最致命的是谱隙。考虑 $n$ 个顶点的**路径图**（$s$、$t$ 为两端）： $$ R_{st} = n - 1,\qquad \lambda_2 = \Theta\!\left(\frac{1}{n^2}\right). $$ 第一个式子是串联电阻求和（第 9 节例 1）；第二个式子是路径图 Laplacian 谱的经典结果（本征值 $2 - 2\cos\frac{k\pi}{n}$，$k = 1, \ldots, n-1$；最小非零者对应 $k=1$，由 $1-\cos x \approx x^2/2$ 得 $\lambda_2 \approx \pi^2/n^2$）。于是条件数因子 $$ \frac{1}{\lambda} = \Theta(n^2) $$ 是 $n$ 的多项式而非多对数——**仅此一项就消除了全部 polylog 优势**，线性系统路线在该实例上退化到多项式时间。物理图像与 1.1 节呼应：长路径是连通性的"瓶颈"，电阻大、谱隙小、量子算法慢，三者是同一件事的不同侧面。span program 路线同样不能幸免：取 $\mu \approx \lambda_2$，第二个界中的 $\sqrt{R_{st}/\mu} \approx \sqrt{n \cdot n^2} = n^{3/2}$，优势同样消失。 ### 8.3 输出规模的限制 最后一个限制与谱无关，与"要算什么"有关：上述所有算法估计的是**一个或少数几个标量**（电阻、某点电压、某边电流、耗散功率）。如果任务改为"打印全部 $n$ 个节点电势和全部 $m$ 条边电流"，输出本身就有 $\Theta(n + m)$ 个经典数，无论中间过程多快，总时间下界都是线性的。量子加速适用于"大图、少问"的场景，不适用于"大图、全要"的场景。 ## 9. 小例子 ### 9.1 例 1：$L$ 只单位电阻串联 $s$ 与 $t$ 之间是一条长度 $L$ 的路径，每条边电阻 $1$。用 Thomson 原理：单位流的可行集只有一个元素——守恒约束强迫每条边的流量都是 $1$（路径没有分叉，流量无处可去）。于是 $$ R_{st} = \mathcal{E}(j) = \sum_{e=1}^{L} 1 \cdot 1^2 = L. $$ 用电路方程验证：$Lv = b$ 的解为电势沿线性下降，$v_k = v_s - k$（第 $k$ 个中间节点；每条边流 $j_e = w_e(v_{k-1} - v_k) = 1 \cdot 1 = 1$，与上面的流一致），故 $R_{st} = v_s - v_t = L$。这就是欧姆定律的串联公式。谱视角（第 4 节）也一致：路径图 $\lambda_2 = \Theta(1/L^2)$，谱式由低端主导，给出 $\Theta(L)$。 ### 9.2 例 2：两条长度 $L$ 的路径并联 $s$、$t$ 之间有两条内部不相交的路径，各由 $L$ 只单位电阻串联而成（每条路径电阻 $L$）。 *方法一：并联公式。* 两条路径各自等效为电阻 $L$（例 1），并联电导相加： $$ R_{st} = \left(L^{-1} + L^{-1}\right)^{-1} = \frac{L}{2}. $$ *方法二：Thomson 原理。* 设第一条路径载流 $x$，则第二条载流 $1 - x$（$s$ 处守恒）。总能量 $$ \mathcal{E}(x) = \underbrace{L \cdot x^2}_{\text{路径一}} + \underbrace{L \cdot (1-x)^2}_{\text{路径二}}. $$ 对 $x$ 求导：$\mathcal{E}'(x) = 2Lx - 2L(1-x) = 2L(2x - 1) = 0$ 给出 $x = 1/2$（$\mathcal{E}'' = 4L > 0$，确为最小）。即**最优流均分两路**——两条路径电阻相同，对称分流。代回： $$ R_{st} = \mathcal{E}\!\left(\tfrac12\right) = 2 \cdot L \cdot \left(\tfrac12\right)^2 = \frac{L}{2}. $$ 两种方法一致。物理信息：并联使电阻减半——第 1.1 节"并行路径降低电阻"的定量版；这也是 span program 视角下 witness size 随并行度缩小的最小例子。 ## 10. 小结 - 有效电阻的三重身份：$R_{st} = b^TL^+b$（伪逆二次型）$= \min_{B^Tj=b}\sum_e r_ej_e^2$（Thomson 原理，最小耗散能）$= \sum_{j\ge2}|\langle u_j,b\rangle|^2/\lambda_j$（逆谱权重）。三条量子路线分别估计其中一个表达。 - 线性系统路线：QLSA 制备电势解态 $|v\rangle \propto L^+|b\rangle$，再用振幅估计与内积估计读出二次型；复杂度 $\operatorname{poly}(d, c, \log n, 1/\lambda, 1/\epsilon)$，且对 $1/\lambda$ 的多项式依赖有下界支撑，不能完全去掉。 - 行走路线：discriminant $= I - \mathcal{L}$，Szegedy 相位 $\theta_j \approx \sqrt{2\lambda_j}$，相位估计对源汇初态做谱测量、估计 Green's function；谱隙依赖取平方根但仍不可去。 - Span program 路线：$\sqrt{w_e}(|u\rangle - |v\rangle)$ 为输入向量时，正 witness 即单位流，witness size $= R_{st}$；approximate span program 给出 $\widetilde O(n\sqrt{R_{st}}/\epsilon^{3/2})$，已知谱隙下界 $\mu$ 时改善为 $\widetilde O((n/\epsilon)\sqrt{R_{st}/\mu})$ 且只需 $O(\log n)$ 空间。 - 指数优势只在 $d, c, 1/\lambda, 1/\epsilon = \operatorname{polylog}(n)$、oracle 相干访问、少量标量输出同时成立时出现；路径图（$\lambda_2 = \Theta(1/n^2)$）与"全量输出"是两类典型失效场景。只写 $\log n$ 会误导。 ## 练习题 **练习 1【有效电阻的物理意义】**（→ [1.1 节](#resistance-physical-origin)） 1. 基础：写出有效电阻的电路定义（在 $s$ 注入 1 单位电流、从 $t$ 抽出时两端的电压差），并用"电流被并行路径分流"解释为什么两点间的独立并行路径越多，$R_{st}$ 越小。 2. 进阶：（通勤时间恒等式）对练习 3 第 2 题的三角形（$R_{st} = 2/3$），直接按定义计算 hitting time $H_{st}$，验证 $\operatorname{Commute}(s,t) = H_{st} + H_{ts} = 2mR_{st}$（$m = 3$）。 > 提示：设 $H = H_{st}$，对第一步走向分类（以 $\frac12$ 概率一步到 $t$、以 $\frac12$ 概率到第三点），利用对称性列方程。 **练习 2【Laplacian、电路方程与伪逆二次型】**（→ [2.1 节](#laplacian-circuit-equation)） 1. 基础：对三个顶点 $s$–$u$–$t$、两条电导均为 $1$ 的边组成的路径图，写出 $B$、$W$、$L$ 与 $b = e_s - e_t$，验证 $L = B^TWB$ 的矩阵元（对角元为加权度、非对角元为 $-w_{uv}$），解 $Lv = b$ 并计算 $R_{st} = v_s - v_t = b^TL^+b$。 2. 进阶：证明连通图上 $Lv = b$ 可解当且仅当 $b \perp \mathbf{1}$（即坐标和为零），并说明虽然解不唯一（通解为 $L^+b + c\mathbf{1}$），$R_{st} = b^TL^+b$ 却与解的选取无关。 > 提示：实对称矩阵的像空间是核空间的正交补；常数势的贡献被 $b^T\mathbf{1} = 0$ 消去。 **练习 3【Thomson 原理】**（→ [3.1 节](#thomson-principle)） 1. 基础：写出单位流（$B^Tj = b$）与耗散能 $\mathcal{E}(j) = \sum_e r_ej_e^2$ 的定义，并说明为什么第 9.1 节长度 $L$ 的串联路径上可行流唯一、从而 $R_{st} = L$。 2. 进阶：（三角形）三个顶点两两相连，三条边均为单位电阻。任选两个顶点作为 $s$、$t$，分别用 (a) 串并联公式与 (b) Thomson 原理（对两条可行通道的流分配做优化）计算 $R_{st}$，验证二者都给出 $2/3$。 3. 进阶：（变分原理的细节）对第 9.2 节的并联例子，用 3.3 节的 Lagrange 乘子法显式写出 $\mathcal{L}(j, v)$，验证驻点条件给出的流正是 $x = 1/2$、乘子 $v$ 给出两端电势差 $L/2$。 > 提示：三角形中设直连边与二边通道分别载流 $x$ 与 $1-x$，对 $x^2 + 2(1-x)^2$ 求导；并联例子同理对 $Lx^2 + L(1-x)^2$ 求导。 **练习 4【谱展开：逆谱权重】**（→ [第 4 节](#spectral-expansion)） 1. 基础：对两个顶点、一条电导为 $1$ 的边组成的图，求 $L$ 的谱分解（$u_2$ 与 $\lambda_2$），代入 $R_{st} = \sum_{j\ge2}\frac{|\langle u_j,b\rangle|^2}{\lambda_j}$ 计算电阻，并与 $b^TL^+b$ 对照。 2. 进阶：（谱展开）从 $L$ 的谱定理出发，完整推导 $R_{st} = \sum_{j\ge2}|\langle u_j,b\rangle|^2/\lambda_j$，并说明 $b \perp u_1$ 这一步用在了哪里、为什么对加权图依然成立。 > 提示：把 $b$ 按本征基展开后代入 $b^TL^+b$，伪逆在 $\lambda_1 = 0$ 的分量上取零。 **练习 5【量子线性系统路线】**（→ [5.1 节](#qlsa-route)） 1. 基础：写出把 $R_{st} = \langle b|L^+|b\rangle$ 分解为 $\|L^+|b\rangle\|\cdot\langle b|v\rangle$ 的两步估计方案，并注明每一步使用的量子原始操作（QLSA、振幅估计、Hadamard 检验或交换检验）。 2. 进阶：解释 5.2 节为什么必须改用归一化 Laplacian $\mathcal{L} = D^{-1/2}LD^{-1/2}$ 才能块编码，并逐项说明 5.3 节复杂度 $\operatorname{poly}(d, c, \log n, 1/\lambda, 1/\epsilon)$ 中各因子的来源，以及 $1/\lambda$ 为何有查询下界支撑、不能去掉。 > 提示：块编码需要已知的范数上界，而 $\mathcal{L}$ 的谱落在 $[0,2]$；条件数 $\kappa \le 2/\lambda$。 **练习 6【量子行走路线】**（→ [6.1 节](#quantum-walk-route)） 1. 基础：从 $P = D^{-1}A_w$ 出发验证 $\mathcal{D}(P) = D^{-1/2}A_wD^{-1/2} = I - \mathcal{L}$，并说明随机游走的谱与归一化 Laplacian 的谱为何互为镜像。 2. 进阶：由 $\cos\theta_j = 1-\lambda_j$ 证明小本征值时 $\theta_j \approx \sqrt{2\lambda_j}$，比较经典混合时间 $\Theta(1/\lambda)$ 与量子相位估计时间 $\Theta(1/\sqrt{\lambda})$，说明平方根改善为什么没有消去谱隙依赖；再简述 6.3 节如何由谱采样得到 $R_{st}$（Green's function）而无需输出整个电势向量。 > 提示：用 $1-\cos\theta \approx \theta^2/2$；相位估计要分辨的是 $\theta$ 本身而非 $\lambda$。 **练习 7【Span program 与 witness size】**（→ [7.1 节](#span-program-route)） 1. 基础：对两个顶点、一条电导为 $w$ 的边，写出输入向量 $|a_e\rangle$ 与目标向量 $|\tau\rangle$，求出 witness 系数 $c_e$，并验证 witness size $\sum_e c_e^2 = 1/w = R_{st}$。 2. 进阶：（witness 核算）对第 9.1 节长度 $L$ 的串联路径，写出第 7 节 span program 的输入向量与一组 witness 系数 $c_e$，验证守恒条件 $\sum_e c_e|a_e\rangle = |\tau\rangle$ 成立且 witness size $\sum_e c_e^2 = L = R_{st}$；再说明为什么这组 witness 是唯一可行的。 > 提示：串联路径上守恒迫使每条边载流 $1$，故 $c_e = j_e/\sqrt{w_e} = 1$。 **练习 8【指数优势的条件与失效场景】**（→ [8.1 节](#quantum-advantage-conditions)） 1. 基础：列出 8.1 节 polylog 优势成立的五个前提（稀疏、权重均匀、谱隙良好、精度温和、输入可相干访问），并各用一句话指出违反它时复杂度表达式中哪个因子恶化。 2. 进阶：（路径图与谱隙）已知路径图 Laplacian 本征值为 $2 - 2\cos\frac{k\pi}{n}$，$k = 0, 1, \ldots, n-1$。用 $1 - \cos x = x^2/2 + O(x^4)$ 推导 $\lambda_2 = \Theta(1/n^2)$，并逐项代入第 5.3 节的复杂度表达式，解释路径图的谱隙如何破坏 polylog 复杂度。 3. 进阶：解释为什么"打印全部 $n$ 个节点电势与 $m$ 条边电流"的任务无论中间过程多快都没有亚线性总时间，并说明这属于 8.3 节的哪一类限制。 > 提示：最小非零本征值对应 $k=1$，把 $\frac{\pi}{n}$ 代入 $x^2/2$；输出规模本身给出 $\Theta(n+m)$ 下界。 ## 参考文献 - Zoo 编号 210：Guoming Wang, [Efficient Quantum Algorithms for Analyzing Large Sparse Electrical Networks](https://arxiv.org/abs/1311.1851). - Zoo 编号 104：Harrow--Hassidim--Lloyd 量子线性系统算法。 - Zoo 编号 280：Tsuyoshi Ito 与 Stacey Jeffery, [Approximate Span Programs](https://arxiv.org/abs/1507.00432).