有效电阻量子算法：Laplacian 线性系统、量子行走与 Span Witness

把加权图看成电阻网络，在 \(s\) 注入 1 单位电流、从 \(t\) 抽出，所需电压差就是有效电阻 \(R_{st}\)。它既是 Laplacian 伪逆的二次型，也是最小能量单位流；因此可由量子线性系统、随机行走谱和 span-program witness 三条路线估计。指数级 \(\log n\) 依赖只在图稀疏、条件良好且只输出少量标量时成立。

1. Laplacian 与电路方程

给每条无向边 \(e\) 电阻 \(r_e>0\)、conductance

\[ w_e=1/r_e. \]

任选边方向，令 incidence matrix \(B\) 的第 \(e\) 行在尾点为 \(+1\)、头点为 \(-1\)。加权 Laplacian

\[ L=B^TWB, \qquad W=\operatorname{diag}(w_e). \]

注入向量

\[ b=e_s-e_t \]

满足坐标和 0，位于 \(L\) 的像空间。节点电势 \(v\)（差一个全局常数）解

\[ Lv=b. \]

有效电阻为

\[ R_{st}=v_s-v_t =b^TL^+b, \]

其中 \(L^+\) 是 Moore--Penrose 伪逆。

2. Thomson 原理：电阻是最小流能量

边流 \(j\in\mathbb R^E\) 若满足

\[ B^Tj=b \]

就是从 \(s\) 到 \(t\) 的单位流。耗散能

\[ \mathcal E(j)= \sum_er_ej_e^2 =j^TW^{-1}j. \]

Lagrange multiplier 最小化给

\[ j^*=WBv,\qquad Lv=b, \]

并有

\[ R_{st}=min_{B^Tj=b}\mathcal E(j). \]

这个变分式把图连通性、流 witness 与电阻统一：若 \(s,t\) 不连通，不存在单位流，有效电阻视为无穷；若有许多并行路径，能量下降。

3. 量子线性系统路线

对最大度 \(d\) 的稀疏图，邻接/权值 oracle 可实现 normalized Laplacian

\[ \mathcal L=D^{-1/2}LD^{-1/2} \]

的 sparse block encoding。准备归一化源项 \(|b\rangle\)，量子线性系统算法近似制备

\[ |v\rangle \propto L^+|b\rangle. \]

再用 Hadamard/amplitude estimation 估计

\[ \langle b|L^+|b\rangle \]

及解态归一化，恢复 \(R_{st}\)。类似测量可估计某节点电压、某边电流与总耗散功率。

复杂度可写成

\[ \operatorname{poly} (d,c,\log n,1/\lambda,1/\epsilon), \]

其中 \(c=w_{\max}/w_{\min}\)（或电阻比），\(\lambda\) 是 normalized Laplacian 最小非零本征值，\(\epsilon\) 是相对/加性精度。\(1/\lambda\) 是条件数来源；论文还证明其多项式依赖在该模型中不能完全去掉。

4. 量子行走路线

由 conductance 定义随机游走

\[ P_{uv}=w_{uv}/d_u. \]

其 discriminant 与 \(I-\mathcal L\) 相似，Szegedy walk 的本征相位编码 Laplacian 本征值。源汇相关的 commute/hitting 结构与 effective resistance 满足经典关系，例如无权连通图中

\[ \operatorname{Commute}(s,t)=2mR_{st}. \]

量子相位估计对源汇初态的谱测量可估计相应 Green's function/电阻，而无需输出整个电势向量。与线性系统路线一样，小谱隙导致长相位分辨时间。

两条路线使用不同中间态和 oracle，但最终都在估计 Laplacian 逆谱权重

\[ R_{st}=\sum_{j\ge2} \frac{|\langle u_j,b\rangle|^2}{\lambda_j}. \]

5. Span program witness size 路线

为每条存在边 \(e=(u,v)\) 提供输入向量

\[ |a_e\rangle =\sqrt{w_e}(|u\rangle-|v\rangle), \]

目标为 \(|\tau\rangle=|s\rangle-|t\rangle\)。若 \(s,t\) 连通，正 witness 系数对应边流。条件

\[ \sum_e c_e|a_e\rangle=|\tau\rangle \]

等价流守恒，最小 witness norm

\[ \sum_ec_e^2 \]

按缩放正好等于 \(R_{st}\)。因此有效电阻就是 connectivity span program 的正 witness size。

Approximate span program 不只判断 target 是否在 span，而用相位检测估计 witness size。邻接矩阵查询模型中得到

\[ \widetilde O\!\left( \frac{n\sqrt{R_{st}}}{\epsilon^{3/2}} \right) \]

时间；若已知谱隙下界 \(\mu\le\lambda_2\)，相位 gap 分析改善为

\[ \widetilde O\!\left( \frac n\epsilon \sqrt{R_{st}/\mu} \right), \]

并只需 \(O(\log n)\) 工作空间。

6. 何时才有指数优势

若

\[ d,c,1/\lambda,1/\epsilon =\operatorname{polylog}(n), \]

且输入/源项 oracle 可高效相干实现，线性系统/行走算法对 \(n\) 只有 polylog 依赖；已知经典算法通常至少要处理多项式多图数据，形成潜在指数差距。

反例是长度 \(n\) 的路径：

\[ R_{st}=n-1,\qquad \lambda_2=\Theta(1/n^2). \]

条件数因子消除所有 polylog 优势。另一个限制是输出：算法估计一个或少数电量；若要打印所有 \(n\) 个电势和 \(m\) 条电流，输出规模本身线性。

7. 小例子

串联 \(L\) 条单位电阻：唯一单位流每边为 1，

\[ R=L. \]

两条长度 \(L\) 的独立并行路径各电阻 \(L\)，并联后

\[ R=(L^{-1}+L^{-1})^{-1}=L/2. \]

Thomson 视角中最优流各走 \(1/2\)，能量

\[ 2\cdot L(1/2)^2=L/2. \]

8. 小结与习题

  • \(R_{st}=b^TL^+b\)，也是单位流最小耗散能。

  • QLSA 制备电势解态，量子行走估计 Laplacian 谱，span program 估计流 witness。

  • 稀疏度、权重比、谱隙与精度共同决定复杂度；只写 \(\log n\) 会误导。

  • 指数优势适用于少量标量输出和条件良好图，不适用于路径等小谱隙实例。

  1. 用 Lagrange multiplier 推导 Thomson 原理。

  2. 计算三角形三条单位电阻中任意两点的有效电阻。

  3. 推导 Laplacian 谱展开的 \(R_{st}\) 公式。

  4. 解释路径图的谱隙如何破坏 polylog 复杂度。

参考文献