# 有效电阻量子算法：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 复杂度。

## 参考文献

- 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).