字符串重写量子算法

字符串重写是一个纯组合的过程：给定一组固定的局部替换规则，把一个字符串一步步改写成另一个字符串。如果规则是对称的（每一步都可以反向执行），那么所有长度为 $L$ 的字符串构成一张巨大的无向图的顶点，一次局部替换就是一条边，而”恰好用 $m$ 步从 $s$ 改写到 $t$ 的方案数”恰好是邻接矩阵 $A$ 的幂 $A^m$ 的一个矩阵元。Janzing 与 Wocjan（Zoo 编号 59）证明：估计两个这样的路径计数之差的归一化符号，是一个 PromiseBQP-complete 的问题——量子计算机用多项式资源就能完成，而它能解出整个 BQP 中的任何问题。

这个结果是理解”量子优势从哪里来”的一个极好样本。困难不在于单次重写有多复杂（每步只是查一张常数大小的规则表），而在于状态空间是指数大的：$|\Sigma {|}^L$ 个字符串谁也无法枚举。量子算法从不逐条数路径，而是把路径计数变成振幅，让两个目标振幅相干相减，再把这个差值编码进一次测量的偏置里。反过来，任意量子电路的 Feynman 路径积分展开又可以被”编译”成一组局部重写规则，于是估计路径数之差必然和通用量子计算一样难。本词条按以下顺序展开：先给出问题的精确定义和承诺条件；再把组合对象翻译成稀疏矩阵的幂；然后分析经典算法的瓶颈；接着给出完整的量子算法与复杂度账目；再证明 BQP-hardness；最后讨论它与经典随机游走 mixing 问题的关系，并用一个可以完全手算的小例子收尾。

1. 问题的精确定义

1.1 重写系统与重写序列

固定一个有限字母表 $\Sigma$（例如 $\Sigma =\{0,1\}$）和一个有限的局部重写规则集合 $R$，每条规则形如

$$u\leftrightarrow v,u,v\in {\Sigma }^{O(1)},$$

即 $u$ 和 $v$ 都是长度不超过某个常数的子串，并且规则是对称的：凡是能把 $u$ 换成 $v$ 的地方，也允许把 $v$ 换回 $u$。这个对称性假设是后文一切结构（无向图、Hermitian 矩阵、可逆演化）的根源，第 5 节的电路编码也必须费尽心思保持它。

现在给定三个长度均为 $L$ 的字符串 $s,t,t^{\prime }\in {\Sigma }^L$。一步重写是指：选定字符串中的某个位置，若该处子串与某条规则的 $u$（或 $v$）匹配，就把它替换成 $v$（或 $u$）。一个恰好 $m$ 步的重写序列是一串字符串

$$a=x_0\to x_1\to \cdots \to x_m=b,$$

其中每个箭头都是一步合法重写。注意序列是有顺序的：即使最终到达同一个 $b$，中间经过的字符串不同就算不同的序列。我们记

$$N_m(a\to b):=\#\{\text{恰好 }m\text{ 步从 }a\text{ 到 }b\text{ 的重写序列}\}.$$

1.2 计数差问题与承诺

问题（路径数之差的符号）。 判断

$$\Delta (m):=N_m(s\to t)-N_m(s\to t^{\prime })$$

是正还是负。也就是说：从 $s$ 出发走 $m$ 步，到达 $t$ 的方案多，还是到达 $t^{\prime }$ 的方案多？

参数取 $m=\mathrm{polylog}L$，即步数远小于字符串长度（相对于隐式图的大小 $|\Sigma {|}^L$，这是多重对数之外的”多项式对数”尺度）。问题是承诺问题 (promise problem)：输入保证满足以下两条，算法只需在满足承诺的输入上给出正确答案。

• Gap 承诺：存在常数 $c$ 与逆多对数 $ϵ$（即 $1/ϵ=\mathrm{polylog}L$），使得

$$|\Delta (m)|\ge ϵc^m.$$

• 增长/度上界：重写系统的最大度与路径增长有适当的界，保证任何相关的路径数都不超过 $c^m$ 的尺度；换言之 $c^m$ 是这类计数的”自然量纲”。

把两条合起来读：$c^m$ 是单个路径计数的典型上界，而承诺要求两个计数之差至少占这个量纲的 $ϵ$ 分之一。量子算法的任务是估计归一化量 $\Delta (m)/c^m$ 到加性误差 $O(ϵ)$——承诺保证这个归一化量要么 $\ge ϵ$、要么 $\le -ϵ$，远离零点，所以符号判决是稳定的。

1.3 为什么承诺必不可少

如果没有 gap 承诺，这个问题可能量子计算机也无能为力。设想 $N_m(s\to t)$ 与 $N_m(s\to t^{\prime })$ 都是 $c^m$ 量级的巨大整数，但只相差 $1$。此时要判断符号，等价于以绝对误差小于 $1$ 的精度估计一个 $c^m$ 量级的整数，即相对精度 $c^{-m}$——指数精细。无论量子还是经典，任何”估计到加性误差 $\delta \cdot c^m$“的方法都需要 $\delta \sim c^{-m}$，代价随 $m$ 指数增长。精确判定两个大计数谁大，带有 #P 类计数问题的味道，没有理由相信它属于 BQP。承诺把问题裁到”量子可加性估计刚好够用”的尺度上：这就是 PromiseBQP-complete 而不是 BQP-complete 的原因，也是本词条反复强调的口径——归一化和误差尺度是问题定义的一部分。

2. 重写图：从组合计数到矩阵幂

2.1 隐式图与稀疏性

定义重写图 (rewrite graph) $G_R$：顶点集是全部 ${\Sigma }^L$（共 $|\Sigma {|}^L$ 个字符串），两个顶点相邻当且仅当它们可以经一步重写互相得到。由于规则对称，邻接关系是对称的，$G_R$ 是无向图，其邻接矩阵 $A$ 是实对称矩阵。

这张图有两个决定性特征。

第一，它是指数大但隐式给出的：顶点有 $|\Sigma {|}^L$ 个，但每个顶点只需 $L\lceil \log |\Sigma |\rceil$ 位就能写下，任何具体顶点都可以用多项式空间存储。

第二，它是稀疏且可有效探测的。一个长度为 $L$ 的字符串上，一步重写的全部可能性由”用哪条规则、作用在哪个位置”决定：规则数是常数，位置数是 $O(L)$，所以每个字符串只有

$$O(L)$$

个候选邻居。也就是说 $G_R$ 的最大度是 $O(L)$，相对于 $|\Sigma {|}^L$ 个顶点是极度稀疏的。更进一步，给定一个字符串和一个邻居索引（规则编号 + 作用位置），我们可以在

$$\mathrm{polylog}|{\Sigma }^L|=\mathrm{poly}(L)$$

次位操作内算出该邻居：查规则表是常数时间，定位和替换子串是 $O(L)$ 量级的字符串操作。这正是”稀疏矩阵有效可寻址”的输入模型，也是第 4 节 block encoding 能够构造的前提。

2.2 Walk-count 恒等式

矩阵幂与路径计数之间有一条教科书级的恒等式，它是整个问题的桥梁。

Lemma 1（walk-count identity）. 对任意顶点 $a,b$ 与整数 $m\ge 0$，

$$(A^m{)}_{ab}=N_m(a\to b),$$

即邻接矩阵的 $m$ 次幂的 $(a,b)$ 元，恰好等于从 $a$ 到 $b$ 长度恰为 $m$ 的行走（walk）条数。

证明。 对 $m$ 做归纳。$m=0$ 时 $A^0=I$，$(I{)}_{ab}={\delta }_{ab}$；长度 $0$ 的行走只有”停在原地”一条，当且仅当 $a=b$，两边一致。

设等式对 $m$ 成立。由矩阵乘法的定义，

$$(A^{m+1}{)}_{ab}=\sum _{x\in {\Sigma }^L}(A^m{)}_{ax}{A}_{xb}.$$

由归纳假设，$(A^m{)}_{ax}$ 是从 $a$ 到 $x$ 的 $m$ 步行走数；$A_{xb}\in \{0,1\}$ 表示 $x$ 与 $b$ 是否相邻。一条从 $a$ 到 $b$ 的 $m+1$ 步行走，删去最后一步后唯一地分解为”一条从 $a$ 到某个 $x$ 的 $m$ 步行走”加上”一条 $x\to b$ 的边”，而这个分解是可逆的（给定 $m+1$ 步行走，取倒数第二个顶点为 $x$）。因此对 $x$ 求和正好不重不漏地数出所有 $m+1$ 步行走。Q.E.D.

证明里唯一用到图结构的地方就是”最后一步 + 前 $m$ 步”的双射分解，这也是所有路径计数恒等式的共同原型。

2.3 把 $\Delta (m)$ 写成单个矩阵元

由 Lemma 1，

$$\Delta (m)=⟨t|A^m|s⟩-⟨t^{\prime }|A^m|s⟩=(⟨t|-⟨t^{\prime }|)A^m|s⟩.$$

第一步是把两个计数各写成一个矩阵元（这要求 $t\ne t^{\prime }$，且 $|s⟩,|t⟩,|t^{\prime }⟩$ 是计算基矢）；第二步是内积对 bra 的线性性。定义归一化态

$$|{\tau }_{-}⟩=\frac{|t⟩-|t^{\prime }⟩}{\sqrt{2}},$$

则 $⟨{\tau }_{-}|=(⟨t|-⟨t^{\prime }|)/\sqrt{2}$，于是

$$\frac{\Delta (m)}{\sqrt{2}}=⟨{\tau }_{-}|A^m|s⟩.$$

这一步是整个算法的”点题”之处：两个整数的差，被写成了一个量子矩阵元。经典世界里要分别估计 $N_m(s\to t)$ 与 $N_m(s\to t^{\prime })$ 再相减，两个大数相减会把相对误差放大到无法接受；量子世界里，差值本身以振幅的形式存在，可以一次性地、相干地测出来。第 4 节的全部工作就是把这个矩阵元变成可测量的量。

3. 经典算法能做到什么

在进入量子算法之前，先看清经典方法的瓶颈在哪里，这样后面的复杂度账目才有对照。

3.1 枚举与动态规划

最直接的算法是枚举：从 $s$ 出发做宽度优先的逐步展开，记录每个字符串在第 $m$ 层的出现次数。第 $j$ 层至多有 $d^j$ 个（带重数的）节点，其中 $d=O(L)$ 是最大度，因此总工作量是

$$\Theta \left(\sum _{j=0}^m{d}^j\right)=\Theta (d^m)=\Theta (c^m)$$

量级的操作（合并相同字符串不改变指数 scaling）。代入参数范围 $m=\mathrm{polylog}L$，代价 $c^m=\exp (O(m))$ 是超多项式的（准多项式量级）。瓶颈的本质：路径数是指数大的整数，而枚举法把每条路径都付了一次钱。动态规划（按字符串存计数）在空间上同样爆炸——中间层可能激活指数多个不同字符串。

3.2 随机采样为什么也不够

一个自然的想法是 Monte Carlo：从 $s$ 出发随机走 $m$ 步（每步均匀选取一个合法重写），统计落到 $t$ 与 $t^{\prime }$ 的频率之差。这相当于估计归一化量 $p_t-p_{t^{\prime }}$，其中 $p_t$ 是随机行走在第 $m$ 步击中 $t$ 的概率。单次试验给出取值 $\{+1,0,-1\}$ 的无偏估计，方差 $O(1)$，所以要分辨一个 $ϵ$ 量级的差需要 $O(1/{ϵ}^2)$ 个样本——这部分看起来还行。

真正的障碍有两个。其一，随机行走不均匀：每个顶点的合法重写数不同，行走分布是未知且难以修正的，频率之差一般不等于我们需要的计数之差 $\Delta (m)/c^m$；要把它校正成均匀路径计数，需要知道每个顶点的精确度并做重要性重加权，权重本身又是难算的量。其二，也是更根本的：这个问题是 PromiseBQP-complete 的（第 5 节），如果存在多项式时间的经典（随机）算法，就意味着 $\mathrm{BQP}\subseteq \mathrm{BPP}$，即通用量子计算可以被经典高效模拟。这与现有的复杂性信念直接冲突。所以”经典做不到”不是某个具体算法的失败，而是问题本身的计算地位。

3.3 小结

• 枚举代价 $\Theta (c^m)$：把路径逐条付钱，超多项式。
• 朴素采样估计的不是目标量；即使修正了，BQP-hardness 也排除了经典多项式算法存在的可能（在标准复杂性假设下）。
• 唯一剩下的出路是：不数路径，直接合成”路径数之差”这个量。这正是量子算法做的事。

4. 量子算法：估计归一化矩阵元

算法的主线只有一句：构造 $A/c$ 的 block encoding，用多项式变换把 $A/c$ 变成 $(A/c{)}^m$，再用 Hadamard test 测出 $⟨{\tau }_{-}|(A/c{)}^m|s⟩=\Delta (m)/(\sqrt{2}{c}^m)$。下面逐块展开。

4.1 归一化：为什么 $\Vert A/c\Vert \le 1$

Block encoding 与多项式变换都要求算子的谱范数不超过 $1$。对邻接矩阵，最大度给出天然的归一化常数。

Lemma 2. 设图的最大度为 $d_{\max }$，则其邻接矩阵满足 $\Vert A\Vert \le d_{\max }$。

证明。 用 Gershgorin 圆盘定理：$A$ 的每个特征值都落在某个圆盘 $|\lambda -A_{ii}|\le {\sum }_{j\ne i}|A_{ij}|$ 内。邻接矩阵对角元为 $0$，第 $i$ 行的绝对值和就是顶点 $i$ 的度，不超过 $d_{\max }$，故 $|\lambda |\le d_{\max }$ 对所有特征值成立；对称矩阵的谱范数等于特征值绝对值的最大值，所以 $\Vert A\Vert \le d_{\max }$。Q.E.D.

由增长/度上界承诺，取 $c$ 为不小于最大度的常数量级（结合规则结构给出的路径增长界），就有

$$\Vert \frac{A}{c}\Vert \le 1.$$

这个归一化同时决定了读出量的量纲：我们最终测的是 $\Delta (m)/c^m$，而承诺正是相对于这个量纲给出 gap 的——归一化常数 $c$ 在问题定义与算法两端是同一个数，这不是巧合，而是问题设计的一部分。

4.2 稀疏矩阵的 block encoding

回忆稀疏矩阵输入模型（参见本词条量子游走与 Hamiltonian 模拟章节）：一个 $s$-稀疏 Hermitian 矩阵 $H$（每行至多 $s$ 个非零元）若配备两个预言机——$O_{\mathrm{pos}}$：给定行指标 $a$ 与 $j\in [s]$，返回第 $j$ 个非零元的列指标；$O_{\mathrm{val}}$：给定 $(a,b)$ 返回矩阵元——则存在 $\Vert H\Vert \le 1$ 情形下的 block encoding，即一个作用在系统加 $a$ 个辅助比特上的酉 $U_H$，满足

$$(⟨0^a|\otimes I\left)U_H\right(|0^a⟩\otimes I)=H,$$

其电路代价是 $O(s)$ 次预言机调用加 $\mathrm{poly}(s,\log N)$ 个基本门。

对我们的问题，$H=A/c$，$N=|\Sigma {|}^L$，$s=O(L)$。§2.1 已经验证了预言机可以有效实现：$O_{\mathrm{pos}}$ 就是”给定字符串与邻居索引，枚举（规则， 位置）对”，$\mathrm{poly}(L)$ 次位操作；$O_{\mathrm{val}}$ 返回 $1/c$ 或 $0$，同样简单。因此 $A/c$ 的 block encoding 的每次调用代价是 $\mathrm{poly}(L)$——对图的规模 $N$ 而言是 $\mathrm{polylog}N$。这就是”隐式指数大图”范式成立的技术核心：图大到不能写下，但局部结构简单到可以按需查询。

4.3 用特征值变换实现 $(A/c{)}^m$

由于 $A/c$ 是 Hermitian 的且 $\Vert A/c\Vert \le 1$，我们可以对它做量子特征值变换（quantum eigenvalue transformation；更一般的框架是 QSVT，参见 QSP/QSVT 章节）：对任意有界多项式 $p$（满足奇偶性与 $|p(x)|\le 1$ 的约束），存在电路把 block encoding 的每个特征块从 $\lambda$ 变成 $p(\lambda )$，调用 block encoding 的次数等于多项式的次数。

取

$$p(x)=x^m.$$

它满足 $|x^m|\le 1$（因为 $|x|\le 1$）且次数为 $m$，可以直接实现，不需要任何多项式逼近——这是本问题在 QSVT 应用里格外干净的地方：不像矩阵求逆或指数函数那样要讨论 Chebyshev 截断误差，这里的多项式就是目标函数本身，唯一的误差来源是后面的统计采样。变换结果是一个酉 $W$，其顶左块为

$$B={\left(\frac{A}{c}\right)}^m=\frac{A^m}{c^m}.$$

调用 $A/c$ 的 block encoding 共 $m$ 次。

需要说明的是，这是用现代语言（block encoding + QSVT）重述的算法；原论文（Janzing–Wocjan 2007）用的是等价的谱测量/随机行走构造：把 $A$ 归一化后视为演化算子，对 $|s⟩$ 做适当时间的演化与测量，从测量统计中读出矩阵元。两条路线的资源 scaling 相同，QSVT 版本的优点是模块化——归一化、多项式、读出三件事各自独立。

4.4 Hadamard test：把矩阵元变成测量偏置

剩下的一步是估计实数

$$⟨{\tau }_{-}|B|s⟩=\frac{\Delta (m)}{\sqrt{2}{c}^m}.$$

注意它是实数：$A$ 是实对称矩阵，$A^m$ 亦然，而 $|s⟩,|{\tau }_{-}⟩$ 都是实振幅的计算基矢组合。

态制备。 我们需要叠加态

$$|\Phi ⟩=\frac{|0⟩|s⟩+|1⟩|{\tau }_{-}⟩}{\sqrt{2}}.$$

因为 $s,t,t^{\prime }$ 都是显式给定的字符串，制备电路是完全初等的：把控制比特置于 $|+⟩$，以控制比特为条件把系统从 $|0\cdots 0⟩$ 写成 $|s⟩$ 或 $|{\tau }_{-}⟩$；后者又只是”写入 $t$ 或 $t^{\prime }$，并对两串第一位不同的位置施加一个受控的符号翻转”。代价 $O(L)$ 个门。

可观测量。 对联合酉算子 $X\otimes W$（$X$ 是控制比特上的 Pauli-$X$，$W$ 是 §4.3 的酉）计算期望值：

$$⟨\Phi |X\otimes W|\Phi ⟩=\frac{1}{2}(⟨s|W|{\tau }_{-}⟩+⟨{\tau }_{-}|W|s⟩)=\mathrm{Re}⟨{\tau }_{-}|W|s⟩.$$

第一个等号是直接把 $X\otimes W$ 作用在 $|\Phi ⟩$ 上（$X$ 交换两个控制分支）再与 $⟨\Phi |$ 作内积，交叉项因为控制比特正交而消失；第二个等号是因为两项互为复共轭（$W$ 固定时 $⟨s|W|{\tau }_{-}⟩=\overline{⟨{\tau }_{-}|W|s⟩}$）。再代入 $W$ 的 block encoding 结构：$|s⟩,|{\tau }_{-}⟩$ 都躺在辅助比特为 $|0^a⟩$ 的顶块子空间里，$W$ 在该子空间上的有效作用就是 $B$，所以

$$\mathrm{Re}⟨{\tau }_{-}|W|s⟩=⟨{\tau }_{-}|B|s⟩=\frac{\Delta (m)}{\sqrt{2}{c}^m}.$$

$X\otimes W$ 是酉的，其期望值可以用标准的 Hadamard test 测量：再加一个测量辅助比特，做 $H$——受控-$(X\otimes W)$——$H$，测得 $0$ 与 $1$ 的概率差正好是该期望值。受控-$X$ 是一个 CNOT，受控-$W$ 与原 $W$ 同阶代价。

4.5 误差预算与符号判决

由 gap 承诺 $|\Delta (m)|\ge ϵc^m$，归一化目标量满足

$$\left|\frac{\Delta (m)}{\sqrt{2}{c}^m}\right|\ge \frac{ϵ}{\sqrt{2}}.$$

所以只要把期望值估到加性误差严格小于 $ϵ/\sqrt{2}$（取 $ϵ/2$ 量级即可），输出符号就是正确的。Hadamard test 每运行一次给出一个 $\pm 1$ 的随机位，其均值就是目标期望值；由 Hoeffding 不等式，$k$ 次独立重复把加性误差压到 $O(1/\sqrt{k})$，取

$$k=O\left(\frac{1}{{ϵ}^2}\right)$$

即以常数概率得到正确符号（再重复取多数可以把成功概率推到 $1-\delta$，代价乘 $O(\log \frac{1}{\delta })$）。若改用振幅估计代替逐次采样，可把 $1/ϵ$ 依赖从平方降到线性，但在本问题的参数范围（$1/ϵ$ 只是逆多对数）里这不是重点。

至此我们看到承诺如何被精确消费：gap 决定所需精度，精度决定采样数，采样数落在 $\mathrm{polylog}L$ 量级，算法因此是高效的。同时注意算法从不枚举 $c^m$ 条路径中的任何一条——$N_m(s\to t)$ 与 $N_m(s\to t^{\prime })$ 这两个天文数字自始至终没有单独出现过，出现的只有它们相干相减后的振幅。

4.6 复杂度逐项分析

把各环节的资源乘起来，并对照问题参数解释每个因子的来源：

• 寄存器规模：$\log N=L\log |\Sigma |$ 个系统比特加 $O(1)$ 个辅助比特，即 $O(L)$ 个比特——输入字符串本身就占 $L$ 位，这是下限。
• 单次 block encoding 调用：$\mathrm{poly}(L)$ 个门。因子来源：稀疏度 $s=O(L)$（规则 × 位置），加上邻居计算的 $\mathrm{poly}(L)$ 位操作。
• QSVT 实现 $(A/c{)}^m$：调用 block encoding $m$ 次，多项式次数就是 $m$ 本身，无逼近开销。总计 $m\cdot \mathrm{poly}(L)$。
• 读出：Hadamard test 每次运行调用一次受控-$W$，重复 $O(1/{ϵ}^2)$ 次（或振幅估计 $O(1/ϵ)$）。
• 总门数：

$$m\cdot \mathrm{poly}(L)\cdot O\left(\frac{1}{{ϵ}^2}\right).$$

在承诺的参数范围 $m=\mathrm{polylog}L$、$1/ϵ=\mathrm{polylog}L$ 下，总量是 $\mathrm{poly}(L)$——对输入长度是多项式，对图的大小 $N=|\Sigma {|}^L$ 是 polylogarithmic。因此该承诺问题属于 PromiseBQP。与 §3 的对照：经典枚举付 $\Theta (c^m)$，量子算法付 $\mathrm{poly}(L)$；加速的来源不是某个单项技巧，而是”隐式稀疏结构（稀疏预言机廉价）+ 振幅相消（差值一次测出）+ 多项式变换（幂运算只花 $m$ 次调用）“三者的组合。

5. 为什么 BQP-hard：把量子电路编成字符串

上一节说明问题”量子可解”。这一节说明它”量子最难”：任何 BQP 语言都能归约到它。方向与直觉相反——我们不是用重写系统去模拟某个具体组合问题，而是用它模拟任意量子电路。

5.1 Feynman 时钟与 history state

设任意量子电路

$$U=U_T\cdots U_1$$

作用在 $n$ 个比特上，门取自某个有限通用门集。Feynman–Kitaev 构造引入一个时钟 (clock) 寄存器记录计算进行到哪一步，并定义history state

$$|\eta ⟩=\frac{1}{\sqrt{T+1}}\sum _{j=0}^T|j⟩\otimes U_j\cdots U_1|x⟩,$$

即把计算的全部历史——第 $j$ 步时的中间态——叠加起来。支持这个叠加的”历史图”是一个层状结构：第 $j$ 层有 $2^n$ 个顶点（所有计算基矢），第 $j$ 层的顶点 $y$ 与第 $j+1$ 层的顶点 $z$ 之间有一条权重为 $⟨z|U_{j+1}|y⟩$ 的边。

5.2 传播 Hamiltonian 的路径解释

让历史”流动”起来的是 Feynman propagation Hamiltonian

$$H_{\mathrm{prop}}=\sum _{j=0}^{T-1}(|j+1⟩⟨j|\otimes U_{j+1}+\text{h.c.}),$$

其中 h.c. 表示前一项的 Hermitian 共轭，保证 $H_{\mathrm{prop}}$ 是 Hermitian 的。它的非零矩阵元恰好是

$$⟨j+1,z|H_{\mathrm{prop}}|j,y⟩=⟨z|U_{j+1}|y⟩,$$

即历史图的边权。把 $H_{\mathrm{prop}}$ 看作带权邻接矩阵并对它取幂，矩阵元按 walk-count 恒等式的带权版本展开：

$$⟨T,z|H_{\mathrm{prop}}^m|0,y⟩=\sum _{\text{长度 }m\text{ 的历史路径}}\prod _{\text{沿路径的边}}⟨\cdot |U_j|\cdot ⟩.$$

当时钟从 $0$ 单调走到 $T$ 且各层恰好经过一次时，右边的乘积正是 Feynman 路径积分的一条轨道 $⟨z|U_T\cdots U_1|y⟩$ 的一个加项。电路的振幅 = 历史路径的带权和——这就是要把电路编码进重写的全部理由。

5.3 字符串编码与门 gadget

重写系统版本把上述结构离散化、无权重化。字符串按功能分区：

• 数据符号 (data symbols)：一段长度 $n$ 的区间，表示计算比特的当前取值；
• 时钟/头符号 (clock/head symbols)：标记当前进行到哪一道门，相当于 Feynman 时钟的”读写头”；
• 辅助符号：记录门 gadget 内部的中间状态与符号信息（见下）。

每一条局部重写规则负责把时钟向前推进一步，同时实施相应门的离散路径 gadget：对通用门集中每个门的每个非零矩阵元，设计一小段固定长度的局部替换序列，使得”选哪条 gadget 路径”恰好对应”选该门的哪个矩阵元”。为了让每条 gadget 路径的权重变成纯粹的 $\pm 1$（从而能被计数而不是加权求和），取门集为 Hadamard + Toffoli 这类矩阵元只有 $\pm 1/\sqrt{2}$、$\pm 1$ 等简单值的实门集（实量子计算与复量子计算在 BQP 意义下等价），把所有 $1/\sqrt{2}$ 因子收集起来吸收进归一化常数 $c$；剩下的正负号记录在辅助符号里随路径传播。由于每条规则都要可逆（§1 的对称性要求），gadget 内部也按可逆方式设计：每一步替换都由局部上下文唯一决定，逆规则就是按相反顺序撤销。这正是 $H_{\mathrm{prop}}$ 的局部字符串版本。

5.4 符号的归宿：$t$ 与 $t^{\prime }$ 的分流

最微妙的一步是：路径计数 $N_m$ 是非负整数，而电路振幅有正有负，带符号的和怎么变成两个无符号计数的差？答案是把符号信息路由到终点。当所有 $T$ 道门走完、计算停止时， gadget 把时钟引导到一个收尾阶段：读取数据区的输出比特（accept 或 reject）与辅助区记录的路径符号（$+$ 或 $-$），然后沿一条公共的”传送带”走向两个最终字符串之一——

• 终点 $t$：收集（accept, $+$）与（reject, $-$）两类历史路径；
• 终点 $t^{\prime }$：收集（accept, $-$）与（reject, $+$）两类历史路径。

设 $p_{\mathrm{acc}},p_{\mathrm{rej}}$ 是电路的接受与拒绝概率（以 $|\cdot {|}^2$ 归一、公共权重因子已提出），于是

$$N_m(s\to t)-N_m(s\to t^{\prime })\propto \sum _{\text{accept 路径}}(\text{符号})-\sum _{\text{reject 路径}}(\text{符号})\propto p_{\mathrm{acc}}-p_{\mathrm{rej}},$$

即 $\Delta (m)$ 与电路的接受偏差 (acceptance bias) 同号：这正是”两个终点分别收集 accept/reject 分支的带符号路径贡献”的实现方式。符号本身从不被”数成负数”，而是通过终点身份贡献到差式的正确一侧。

5.5 Padding、步数 $m$ 的选择与 gap

还差两个收尾条件。第一，所有历史路径必须有相同的总长度 $m$：在计算结束前后插入恒等的”等待”步（padding），让提前走完 gadget 的路径在原地附近踱步到统一步数；这样”恰好 $m$ 步到达 $t$“才能精确对应”完整执行了电路并收尾”。第二，BQP 的承诺是 $p_{\mathrm{acc}}-p_{\mathrm{rej}}\ge$ 逆多项式（必要时先做多数放大），经归一化后 $\Delta (m)/c^m$ 保持同样的符号与逆多项式量级的 gap，落进 §1 的承诺范围。字符串长度 $L$ 取电路规模的某个多项式（足够写下数据区、时钟与 gadget 工作区），相对于图的大小 $|\Sigma {|}^L$ 这些参数都在 polylog 口径之内。

合起来：任何 BQP 语言的判定电路都能编译成一个重写实例，其 $\Delta (m)$ 的符号就是该实例的答案是/否。所以一个能解 §1 承诺问题的算法就能判定任意 BQP 语言——问题是 BQP-hard 的；结合 §4 的成员性，它是 PromiseBQP-complete 的。

6. 与经典随机游走 mixing 的联系

同一个数学对象换一个归一化口径，就得到一族相关的问题。把 $A$ 归一化为随机矩阵 $P$（例如 $P=A/d_{\max }$，或对不规则度做标准的 lazy walk 修正），则 $(P^m{)}_{ab}$ 不再是路径计数，而是随机游走从 $a$ 出发第 $m$ 步位于 $b$ 的概率。Janzing 与 Wocjan（Zoo 编号 58）还构造了关于稀疏图经典随机游走 mixing 性质及相关统计量的 BQP-complete 承诺问题：例如判断某个稀疏隐式图上的随机行走在给定步数后是”接近混合”还是”远离混合”，或对转移概率的某些组合做符号判断。

这两个结果共享同一个范式，值得明确点出：困难不来自单步转移——每步只是查规则表、改写 $O(1)$ 个符号，经典上轻而易举；困难来自隐式的指数大状态图与高阶谱矩。无论是 $(A^m{)}_{ab}$（计数口径）还是 $(P^m{)}_{ab}$（概率口径），回答关于 $m$ 步全局行为的问题都等价于探测 $A$ 的谱测度的第 $m$ 阶矩，而量子算法——稀疏模拟、相位估计、QSVT——恰好是处理稀疏 Hermitian 矩阵谱性质的通用机器。“稀疏矩阵幂”教程讲的正是同一范式的另一个实例，可以对照阅读。

7. 小例子：交换规则的完整计算

原文给出的最小例子是单条规则

$$01\leftrightarrow 10,$$

它只交换相邻两个不同的比特。注意这条规则保持字符串的 Hamming 重量（$1$ 的个数），所以重写图按重量分层、各层互不连通。这一节把长度 $L=3$ 的情形彻底算清楚。

7.1 重写图

长度 $3$ 的二元串共 $8$ 个，按重量分层：

• 重量 $0$：$\{000\}$，孤立点（没有可交换的位置）；
• 重量 $3$：$\{111\}$，孤立点；
• 重量 $1$：$\{001,010,100\}$，唯一的 $1$ 可以左右移动，构成一条三点路径 $001-010-100$；
• 重量 $2$：$\{011,101,110\}$，同理构成路径 $011-101-110$。

每个字符串至多有 $2$ 个邻居（两个相邻位置），最大度 $d_{\max }=2$，故可取 $c=2$。

7.2 矩阵幂与 $\Delta (m)$

在重量 $1$ 的连通分量上，按基 $(001,010,100)$ 写邻接矩阵并逐次取幂：

$$A=\left(\begin{array}{ccc}0& 1& 0\\ 1& 0& 1\\ 0& 1& 0\end{array}\right),A^2=\left(\begin{array}{ccc}1& 0& 1\\ 0& 2& 0\\ 1& 0& 1\end{array}\right),A^3=\left(\begin{array}{ccc}0& 2& 0\\ 2& 0& 2\\ 0& 2& 0\end{array}\right).$$

每个矩阵元都可以用 Lemma 1 逐条路径核对。例如 $(A^2{)}_{001,100}=1$ 对应唯一的两步序列

$$001\to 010\to 100;$$

$(A^2{)}_{001,001}=1$ 对应折返路径 $001\to 010\to 001$；$(A^2{)}_{010,010}=2$ 对应 $010\to 001\to 010$ 与 $010\to 100\to 010$ 两条；$(A^2{)}_{001,010}=0$ 因为该图是二分图，偶数步必回到出发一侧。$(A^3{)}_{001,010}=2$ 对应 $001\to 010\to 001\to 010$ 和 $001\to 010\to 100\to 010$；$(A^3{)}_{001,100}=0$ 同样由奇偶性排除。

现在取 $s=001$，$t=100$，$t^{\prime }=010$，算出两种步数下的承诺量：

$$\Delta (2)=N_2(s\to t)-N_2(s\to t^{\prime })=1-0=1,\frac{\Delta (2)}{c^2}=\frac{1}{4}>0;$$ $$\Delta (3)=0-2=-2,\frac{\Delta (3)}{c^3}=-\frac{2}{8}=-\frac{1}{4}<0.$$

同一组 $(s,t,t^{\prime })$，仅仅把步数从 $2$ 改成 $3$，答案的符号就翻转了。这说明 $m$ 必须作为输入的一部分被明确给出——“从 $s$ 到 $t$ 还是到 $t^{\prime }$ 更容易”这个问题本身在步数不确定时没有意义。

7.3 两点讨论

第一，归一化常数的松紧。$A$（重量 $1$ 分量）的特征值是 $\pm \sqrt{2}$ 与 $0$，谱范数 $\sqrt{2}$，小于我们按 Lemma 2 取的 $c=d_{\max }=2$。一般图上 $\Vert A\Vert$ 可以等于 $d_{\max }$（正则图），所以 $c=d_{\max }$ 是安全而普适的选择；本例说明它不必是紧的。

第二，这个玩具规则与真实构造的距离。这里的路径计数可以直接手算，没有任何量子难度；真正的 BQP-hard 规则集包含时钟符号和门 gadget——每条路径携带从电路矩阵元继承来的符号，终点分流把接受偏差翻译成计数差。玩具例子的价值在于把 Lemma 1、归一化与 $\Delta$ 的符号判决这些机制演算一遍，而这些机制在真实构造里逐项原样保留。

8. 小结与习题

• 对称的局部重写规则定义一张稀疏、可有效探测的无向隐式图 $G_R$；恰好 $m$ 步的重写序列数等于邻接矩阵幂的矩阵元 $(A^m{)}_{ab}$（walk-count identity）。
• 量子算法把路径数之差写成单个矩阵元 $\Delta /\sqrt{2}=⟨{\tau }_{-}|A^m|s⟩$，经归一化 $\Vert A/c\Vert \le 1$、block encoding、多项式 $x^m$ 的 QSVT 与 Hadamard test，以 $\mathrm{poly}(L)$ 资源读出 $\Delta (m)/c^m$ 的符号；gap 承诺 $|\Delta |\ge ϵc^m$ 是效率的支点。
• 算法从不枚举 $c^m$ 条路径；符号来自两个目标振幅的相干相减。多项式就是 $x^m$ 本身，无逼近误差，唯一误差源是采样。
• Feynman 时钟把任意量子电路的传播 Hamiltonian 编成局部字符串重写；gadget 路径对应门矩阵元，符号经终点分流进入计数差，padding 统一步长——因此该承诺问题是 PromiseBQP-complete 的。
• 同一范式覆盖经典随机游走 mixing 的承诺问题（Zoo 58）与稀疏矩阵幂的估计：难度来自隐式指数状态图与高阶谱矩，而非单步转移。

习题

1. （walk-count 恒等式）补全 Lemma 1 的归纳证明中 $m=1$ 的基例，并说明”删去最后一步”的分解为什么对 walk（允许重复经过顶点）仍然成立。如果把问题改成”简单路径”（不允许重复顶点），同样的矩阵恒等式还成立吗？为什么？
2. （对称性的作用）说明规则的对称性 $u\leftrightarrow v$ 为什么使 $A$ 成为 Hermitian（实对称）矩阵。若规则只允许单向替换 $u\to v$，§2–§4 的链条分别在哪一步断裂？（提示：检查 $G_R$ 的方向性、$A$ 的对称性、block encoding 与 $x^m$ 变换的可行性。）
3. （度界与归一化）用 Gershgorin 定理证明 Lemma 2：$\Vert A\Vert \le d_{\max }$。再给出一个 $\Vert A\Vert =d_{\max }$ 取等的图类，说明 $c=d_{\max }$ 一般不能系统性改进。
4. （没有 gap 会怎样）设 $N_m(s\to t),N_m(s\to t^{\prime })$ 都是 $c^m$ 量级但只差 $1$。写出此时判定符号所需的归一化精度，并据此说明 Hadamard test 路线的采样数如何随 $m$ 增长。这解释了为什么 §1 说”没有 gap 时该问题不一定属于 BQP”。
5. （手算）对 §7 中重量 $2$ 的连通分量 $\{011,101,110\}$ 写出邻接矩阵，计算 $A^2$，并取 $s=011$，$t=110$，$t^{\prime }=101$ 计算 $\Delta (2)$ 与 $\Delta (3)$ 及其符号。
6. （Hadamard test 的账目）验证 §4.4 的恒等式 $⟨\Phi |X\otimes W|\Phi ⟩=\mathrm{Re}⟨{\tau }_{-}|W|s⟩$（逐项展开，指出交叉项消失的原因）。再用 Hoeffding 不等式推导：要把期望值估到加性误差 $ϵ/2$、失败概率不超过 $\delta$，需要多少次重复。

参考文献

• Zoo 编号 59：Dominik Janzing 与 Pawel Wocjan, A PromiseBQP-Complete String Rewriting Problem.
• Zoo 编号 58：同作者关于稀疏图经典随机游走 mixing properties 的 BQP-complete 问题。

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch13-topology-statistical-physics/string-rewriting
• 内容遵循 CC BY-NC-SA 4.0 许可协议