# 字符串重写量子算法：隐式图路径计数与 PromiseBQP 完备性 字符串重写是一个纯组合的过程：给定一组固定的局部替换规则，把一个字符串一步步改写成另一个字符串。如果规则是对称的（每一步都可以反向执行），那么所有长度为 $L$ 的字符串构成一张巨大的无向图的顶点，一次局部替换就是一条边，而"恰好用 $m$ 步从 $s$ 改写到 $t$ 的方案数"恰好是邻接矩阵 $A$ 的幂 $A^m$ 的一个矩阵元。Janzing 与 Wocjan（Zoo 编号 59）证明：估计两个这样的路径计数之**差**的归一化符号，是一个 PromiseBQP-complete 的问题——量子计算机用多项式资源就能完成，而它能解出整个 BQP 中的任何问题。 这个结果是理解"量子优势从哪里来"的一个极好样本。困难不在于单次重写有多复杂（每步只是查一张常数大小的规则表），而在于状态空间是指数大的：$|\Sigma|^L$ 个字符串谁也无法枚举。量子算法从不逐条数路径，而是把路径计数变成振幅，让两个目标振幅**相干相减**，再把这个差值编码进一次测量的偏置里。反过来，任意量子电路的 Feynman 路径积分展开又可以被"编译"成一组局部重写规则，于是估计路径数之差必然和通用量子计算一样难。本文按以下顺序展开：先给出问题的精确定义和承诺条件；再把组合对象翻译成稀疏矩阵的幂；然后分析经典算法的瓶颈；接着给出完整的量子算法与复杂度账目；再证明 BQP-hardness；最后讨论它与经典随机游走 mixing 问题的关系，并用一个可以完全手算的小例子收尾。 :::{admonition} 本课知识点 :class: tip 1. **[计数差问题与承诺](#counting-difference-promise)**——能写出对称局部重写规则、$m$ 步重写序列与计数 $N_m(a\to b)$、$\Delta(m)$ 的定义，陈述 gap 承诺 $|\Delta(m)|\ge\epsilon c^m$，并解释没有 gap 时判定符号为何需要指数精度。 2. **[隐式重写图与稀疏性](#implicit-rewrite-graph)**——能说明重写图 $G_R$ 为何有 $|\Sigma|^L$ 个顶点而最大度只有 $O(L)$，以及给定字符串与邻居索引时为何只需 $\operatorname{poly}(L)$ 次位操作即可算出邻居。 3. **[walk-count 恒等式与矩阵元表示](#walk-count-identity)**——能用归纳法证明 $(A^m)_{ab}=N_m(a\to b)$，并把 $\Delta(m)/\sqrt2$ 写成单个矩阵元 $\langle\tau_-|A^m|s\rangle$。 4. **[经典算法的瓶颈](#classical-bottleneck)**——能推导枚举算法 $\Theta(c^m)$ 的工作量，并从"估计的不是目标量"与 BQP-hardness 两方面说明随机采样为何不能判定 $\Delta(m)$ 的符号。 5. **[归一化与稀疏 block encoding](#normalization-block-encoding)**——能用 Gershgorin 定理证明 $\|A/c\|\le1$，并解释 $O_{\rm pos}$、$O_{\rm val}$ 两类预言机如何给出 $A/c$ 的 block encoding。 6. **[幂变换与 Hadamard test](#power-hadamard-test)**——能解释 $p(x)=x^m$ 的 QSVT 实现为何无需多项式逼近，推导 $\langle\Phi|X\otimes W|\Phi\rangle=\Delta(m)/(\sqrt2\,c^m)$，并算出采样数与总门数。 7. **[从量子电路到重写规则](#circuit-to-rewriting)**——能解释 history state、传播 Hamiltonian 的路径解释、门 gadget 与符号分流，并说明 padding 与多数放大如何兑现 gap 承诺。 8. **[交换规则手算例子](#swap-rule-example)**——能在 $L=3$ 的交换规则重写图上手算 $A^2$、$A^3$ 与 $\Delta(m)$，并解释步数 $m$ 改变时符号翻转的原因。 ::: ## 1. 问题的精确定义 ### 1.1 重写系统与重写序列 固定一个有限字母表 $\Sigma$（例如 $\Sigma=\{0,1\}$）和一个有限的**局部重写规则**集合 $R$，每条规则形如 $$ u\leftrightarrow v,\qquad u,v\in\Sigma^{O(1)}, $$ 即 $u$ 和 $v$ 都是长度不超过某个常数的子串，并且规则是**对称**的：凡是能把 $u$ 换成 $v$ 的地方，也允许把 $v$ 换回 $u$。这个对称性假设是后文一切结构（无向图、Hermitian 矩阵、可逆演化）的根源，第 5 节的电路编码也必须费尽心思保持它。 现在给定三个长度均为 $L$ 的字符串 $s,t,t'\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{ 的重写序列}\}. $$ (counting-difference-promise)= ### 1.2 计数差问题与承诺 **问题（路径数之差的符号）。** 判断 $$ \Delta(m):=N_m(s\to t)-N_m(s\to t') $$ 是正还是负。也就是说：从 $s$ 出发走 $m$ 步，到达 $t$ 的方案多，还是到达 $t'$ 的方案多？ 参数取 $m=\operatorname{polylog}L$，即步数远小于字符串长度（相对于隐式图的大小 $|\Sigma|^L$，这是多重对数之外的"多项式对数"尺度）。问题是**承诺问题 (promise problem)**：输入保证满足以下两条，算法只需在满足承诺的输入上给出正确答案。 - **Gap 承诺**：存在常数 $c$ 与逆多对数 $\epsilon$（即 $1/\epsilon=\operatorname{polylog}L$），使得 $$ |\Delta(m)|\ge\epsilon\,c^m. $$ - **增长/度上界**：重写系统的最大度与路径增长有适当的界，保证任何相关的路径数都不超过 $c^m$ 的尺度；换言之 $c^m$ 是这类计数的"自然量纲"。 把两条合起来读：$c^m$ 是单个路径计数的典型上界，而承诺要求两个计数之差至少占这个量纲的 $\epsilon$ 分之一。量子算法的任务是估计**归一化量** $\Delta(m)/c^m$ 到加性误差 $O(\epsilon)$——承诺保证这个归一化量要么 $\ge\epsilon$、要么 $\le-\epsilon$，远离零点，所以符号判决是稳定的。 ### 1.3 为什么承诺必不可少 如果没有 gap 承诺，这个问题可能量子计算机也无能为力。设想 $N_m(s\to t)$ 与 $N_m(s\to t')$ 都是 $c^m$ 量级的巨大整数，但只相差 $1$。此时要判断符号，等价于以绝对误差小于 $1$ 的精度估计一个 $c^m$ 量级的整数，即相对精度 $c^{-m}$——指数精细。无论量子还是经典，任何"估计到加性误差 $\delta\cdot c^m$"的方法都需要 $\delta\sim c^{-m}$，代价随 $m$ 指数增长。精确判定两个大计数谁大，带有 \#P 类计数问题的味道，没有理由相信它属于 BQP。承诺把问题裁到"量子可加性估计刚好够用"的尺度上：这就是 PromiseBQP-complete 而不是 BQP-complete 的原因，也是本章反复强调的口径——**归一化和误差尺度是问题定义的一部分**。 ## 2. 重写图：从组合计数到矩阵幂 (implicit-rewrite-graph)= ### 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$ 个顶点是极度稀疏的。更进一步，给定一个字符串和一个邻居索引（规则编号 + 作用位置），我们可以在 $$ \operatorname{polylog}|\Sigma^L|=\operatorname{poly}(L) $$ 次位操作内算出该邻居：查规则表是常数时间，定位和替换子串是 $O(L)$ 量级的字符串操作。这正是"稀疏矩阵有效可寻址"的输入模型，也是第 4 节 block encoding 能够构造的前提。 (walk-count-identity)= ### 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) =\langle t|A^m|s\rangle-\langle t'|A^m|s\rangle =\bigl(\langle t|-\langle t'|\bigr)A^m|s\rangle. $$ 第一步是把两个计数各写成一个矩阵元（这要求 $t\ne t'$，且 $|s\rangle,|t\rangle,|t'\rangle$ 是计算基矢）；第二步是内积对 bra 的线性性。定义归一化态 $$ |\tau_-\rangle=\frac{|t\rangle-|t'\rangle}{\sqrt2}, $$ 则 $\langle\tau_-|=(\langle t|-\langle t'|)/\sqrt2$，于是 $$ \frac{\Delta(m)}{\sqrt2}=\langle\tau_-|A^m|s\rangle. $$ 这一步是整个算法的"点题"之处：两个整数的差，被写成了**一个**量子矩阵元。经典世界里要分别估计 $N_m(s\to t)$ 与 $N_m(s\to t')$ 再相减，两个大数相减会把相对误差放大到无法接受；量子世界里，差值本身以振幅的形式存在，可以一次性地、相干地测出来。第 4 节的全部工作就是把这个矩阵元变成可测量的量。 ## 3. 经典算法能做到什么 在进入量子算法之前，先看清经典方法的瓶颈在哪里，这样后面的复杂度账目才有对照。 (classical-bottleneck)= ### 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=\operatorname{polylog}L$，代价 $c^m=\exp(O(m))$ 是超多项式的（准多项式量级）。瓶颈的本质：**路径数是指数大的整数，而枚举法把每条路径都付了一次钱**。动态规划（按字符串存计数）在空间上同样爆炸——中间层可能激活指数多个不同字符串。 ### 3.2 随机采样为什么也不够 一个自然的想法是 Monte Carlo：从 $s$ 出发随机走 $m$ 步（每步均匀选取一个合法重写），统计落到 $t$ 与 $t'$ 的频率之差。这相当于估计归一化量 $p_t-p_{t'}$，其中 $p_t$ 是随机行走在第 $m$ 步击中 $t$ 的概率。单次试验给出取值 $\{+1,0,-1\}$ 的无偏估计，方差 $O(1)$，所以要分辨一个 $\epsilon$ 量级的差需要 $O(1/\epsilon^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 测出 $\langle\tau_-|(A/c)^m|s\rangle=\Delta(m)/(\sqrt2\,c^m)$。下面逐块展开。 (normalization-block-encoding)= ### 4.1 归一化：为什么 $\|A/c\|\le1$ Block encoding 与多项式变换都要求算子的谱范数不超过 $1$。对邻接矩阵，最大度给出天然的归一化常数。 **Lemma 2.** 设图的最大度为 $d_{\max}$，则其邻接矩阵满足 $\|A\|\le d_{\max}$。 **证明。** 用 Gershgorin 圆盘定理：$A$ 的每个特征值都落在某个圆盘 $| \lambda - A_{ii}|\le\sum_{j\ne i}|A_{ij}|$ 内。邻接矩阵对角元为 $0$，第 $i$ 行的绝对值和就是顶点 $i$ 的度，不超过 $d_{\max}$，故 $|\lambda|\le d_{\max}$ 对所有特征值成立；对称矩阵的谱范数等于特征值绝对值的最大值，所以 $\|A\|\le d_{\max}$。Q.E.D. 由增长/度上界承诺，取 $c$ 为不小于最大度的常数量级（结合规则结构给出的路径增长界），就有 $$ \left\|\frac{A}{c}\right\|\le1. $$ 这个归一化同时决定了读出量的量纲：我们最终测的是 $\Delta(m)/c^m$，而承诺正是相对于这个量纲给出 gap 的——归一化常数 $c$ 在问题定义与算法两端是同一个数，这不是巧合，而是问题设计的一部分。 ### 4.2 稀疏矩阵的 block encoding 回忆稀疏矩阵输入模型（参见本教程量子游走与 Hamiltonian 模拟章节）：一个 $s$-稀疏 Hermitian 矩阵 $H$（每行至多 $s$ 个非零元）若配备两个预言机——$O_{\rm pos}$：给定行指标 $a$ 与 $j\in[s]$，返回第 $j$ 个非零元的列指标；$O_{\rm val}$：给定 $(a,b)$ 返回矩阵元——则存在 $\|H\|\le1$ 情形下的 block encoding，即一个作用在系统加 $a$ 个辅助比特上的酉 $U_H$，满足 $$ \bigl(\langle 0^a|\otimes I\bigr)\,U_H\,\bigl(|0^a\rangle\otimes I\bigr)=H, $$ 其电路代价是 $O(s)$ 次预言机调用加 $\operatorname{poly}(s,\log N)$ 个基本门。 对我们的问题，$H=A/c$，$N=|\Sigma|^L$，$s=O(L)$。§2.1 已经验证了预言机可以有效实现：$O_{\rm pos}$ 就是"给定字符串与邻居索引，枚举（规则， 位置）对"，$\operatorname{poly}(L)$ 次位操作；$O_{\rm val}$ 返回 $1/c$ 或 $0$，同样简单。因此 $A/c$ 的 block encoding 的每次调用代价是 $\operatorname{poly}(L)$——对图的规模 $N$ 而言是 $\operatorname{polylog}N$。这就是"隐式指数大图"范式成立的技术核心：**图大到不能写下，但局部结构简单到可以按需查询**。 (power-hadamard-test)= ### 4.3 用特征值变换实现 $(A/c)^m$ 由于 $A/c$ 是 Hermitian 的且 $\|A/c\|\le1$，我们可以对它做量子特征值变换（quantum eigenvalue transformation；更一般的框架是 QSVT，参见本站 QSP/QSVT 章节）：对任意有界多项式 $p$（满足奇偶性与 $|p(x)|\le1$ 的约束），存在电路把 block encoding 的每个特征块从 $\lambda$ 变成 $p(\lambda)$，调用 block encoding 的次数等于多项式的次数。 取 $$ p(x)=x^m. $$ 它满足 $|x^m|\le1$（因为 $|x|\le1$）且次数为 $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\rangle$ 做适当时间的演化与测量，从测量统计中读出矩阵元。两条路线的资源 scaling 相同，QSVT 版本的优点是模块化——归一化、多项式、读出三件事各自独立。 ### 4.4 Hadamard test：把矩阵元变成测量偏置 剩下的一步是估计实数 $$ \langle\tau_-|B|s\rangle=\frac{\Delta(m)}{\sqrt2\,c^m}. $$ 注意它是实数：$A$ 是实对称矩阵，$A^m$ 亦然，而 $|s\rangle,|\tau_-\rangle$ 都是实振幅的计算基矢组合。 **态制备。** 我们需要叠加态 $$ |\Phi\rangle=\frac{|0\rangle|s\rangle+|1\rangle|\tau_-\rangle}{\sqrt2}. $$ 因为 $s,t,t'$ 都是显式给定的字符串，制备电路是完全初等的：把控制比特置于 $|+\rangle$，以控制比特为条件把系统从 $|0\cdots0\rangle$ 写成 $|s\rangle$ 或 $|\tau_-\rangle$；后者又只是"写入 $t$ 或 $t'$，并对两串第一位不同的位置施加一个受控的符号翻转"。代价 $O(L)$ 个门。 **可观测量。** 对联合酉算子 $X\otimes W$（$X$ 是控制比特上的 Pauli-$X$，$W$ 是 §4.3 的酉）计算期望值： $$ \langle\Phi|\,X\otimes W\,|\Phi\rangle =\frac12\bigl(\langle s|W|\tau_-\rangle+\langle\tau_-|W|s\rangle\bigr) =\operatorname{Re}\langle\tau_-|W|s\rangle. $$ 第一个等号是直接把 $X\otimes W$ 作用在 $|\Phi\rangle$ 上（$X$ 交换两个控制分支）再与 $\langle\Phi|$ 作内积，交叉项因为控制比特正交而消失；第二个等号是因为两项互为复共轭（$W$ 固定时 $\langle s|W|\tau_-\rangle=\overline{\langle\tau_-|W|s\rangle}$）。再代入 $W$ 的 block encoding 结构：$|s\rangle,|\tau_-\rangle$ 都躺在辅助比特为 $|0^a\rangle$ 的顶块子空间里，$W$ 在该子空间上的有效作用就是 $B$，所以 $$ \operatorname{Re}\langle\tau_-|W|s\rangle=\langle\tau_-|B|s\rangle=\frac{\Delta(m)}{\sqrt2\,c^m}. $$ $X\otimes W$ 是酉的，其期望值可以用标准的 Hadamard test 测量：再加一个测量辅助比特，做 $H$——受控-$(X\otimes W)$——$H$，测得 $0$ 与 $1$ 的概率差正好是该期望值。受控-$X$ 是一个 CNOT，受控-$W$ 与原 $W$ 同阶代价。 ### 4.5 误差预算与符号判决 由 gap 承诺 $|\Delta(m)|\ge\epsilon c^m$，归一化目标量满足 $$ \left|\frac{\Delta(m)}{\sqrt2\,c^m}\right|\ge\frac{\epsilon}{\sqrt2}. $$ 所以只要把期望值估到加性误差严格小于 $\epsilon/\sqrt2$（取 $\epsilon/2$ 量级即可），输出符号就是正确的。Hadamard test 每运行一次给出一个 $\pm1$ 的随机位，其均值就是目标期望值；由 Hoeffding 不等式，$k$ 次独立重复把加性误差压到 $O(1/\sqrt{k})$，取 $$ k=O\!\left(\frac1{\epsilon^2}\right) $$ 即以常数概率得到正确符号（再重复取多数可以把成功概率推到 $1-\delta$，代价乘 $O(\log\frac1\delta)$）。若改用振幅估计代替逐次采样，可把 $1/\epsilon$ 依赖从平方降到线性，但在本问题的参数范围（$1/\epsilon$ 只是逆多对数）里这不是重点。 至此我们看到承诺如何被精确消费：gap 决定所需精度，精度决定采样数，采样数落在 $\operatorname{polylog}L$ 量级，算法因此是高效的。同时注意算法**从不枚举** $c^m$ 条路径中的任何一条——$N_m(s\to t)$ 与 $N_m(s\to t')$ 这两个天文数字自始至终没有单独出现过，出现的只有它们相干相减后的振幅。 ### 4.6 复杂度逐项分析 把各环节的资源乘起来，并对照问题参数解释每个因子的来源： - **寄存器规模**：$\log N=L\log|\Sigma|$ 个系统比特加 $O(1)$ 个辅助比特，即 $O(L)$ 个比特——输入字符串本身就占 $L$ 位，这是下限。 - **单次 block encoding 调用**：$\operatorname{poly}(L)$ 个门。因子来源：稀疏度 $s=O(L)$（规则 × 位置），加上邻居计算的 $\operatorname{poly}(L)$ 位操作。 - **QSVT 实现 $(A/c)^m$**：调用 block encoding $m$ 次，多项式次数就是 $m$ 本身，无逼近开销。总计 $m\cdot\operatorname{poly}(L)$。 - **读出**：Hadamard test 每次运行调用一次受控-$W$，重复 $O(1/\epsilon^2)$ 次（或振幅估计 $O(1/\epsilon)$）。 - **总门数**： $$ m\cdot\operatorname{poly}(L)\cdot O\!\left(\frac1{\epsilon^2}\right). $$ 在承诺的参数范围 $m=\operatorname{polylog}L$、$1/\epsilon=\operatorname{polylog}L$ 下，总量是 $\operatorname{poly}(L)$——对输入长度是多项式，对图的大小 $N=|\Sigma|^L$ 是 polylogarithmic。因此该承诺问题属于 **PromiseBQP**。与 §3 的对照：经典枚举付 $\Theta(c^m)$，量子算法付 $\operatorname{poly}(L)$；加速的来源不是某个单项技巧，而是"隐式稀疏结构（稀疏预言机廉价）+ 振幅相消（差值一次测出）+ 多项式变换（幂运算只花 $m$ 次调用）"三者的组合。 ## 5. 为什么 BQP-hard：把量子电路编成字符串 上一节说明问题"量子可解"。这一节说明它"量子最难"：任何 BQP 语言都能归约到它。方向与直觉相反——我们不是用重写系统去模拟某个具体组合问题，而是用它模拟**任意量子电路**。 (circuit-to-rewriting)= ### 5.1 Feynman 时钟与 history state 设任意量子电路 $$ U=U_T\cdots U_1 $$ 作用在 $n$ 个比特上，门取自某个有限通用门集。Feynman–Kitaev 构造引入一个**时钟 (clock)** 寄存器记录计算进行到哪一步，并定义**history state** $$ |\eta\rangle=\frac{1}{\sqrt{T+1}}\sum_{j=0}^{T}|j\rangle\otimes U_j\cdots U_1|x\rangle, $$ 即把计算的全部历史——第 $j$ 步时的中间态——叠加起来。支持这个叠加的"历史图"是一个层状结构：第 $j$ 层有 $2^n$ 个顶点（所有计算基矢），第 $j$ 层的顶点 $y$ 与第 $j+1$ 层的顶点 $z$ 之间有一条权重为 $\langle z|U_{j+1}|y\rangle$ 的边。 ### 5.2 传播 Hamiltonian 的路径解释 让历史"流动"起来的是 **Feynman propagation Hamiltonian** $$ H_{\rm prop} =\sum_{j=0}^{T-1}\Bigl(|j+1\rangle\langle j|\otimes U_{j+1}+\text{h.c.}\Bigr), $$ 其中 h.c. 表示前一项的 Hermitian 共轭，保证 $H_{\rm prop}$ 是 Hermitian 的。它的非零矩阵元恰好是 $$ \langle j{+}1,z|H_{\rm prop}|j,y\rangle=\langle z|U_{j+1}|y\rangle, $$ 即历史图的边权。把 $H_{\rm prop}$ 看作带权邻接矩阵并对它取幂，矩阵元按 walk-count 恒等式的带权版本展开： $$ \langle T,z|H_{\rm prop}^{m}|0,y\rangle =\sum_{\text{长度 } m \text{ 的历史路径}}\prod_{\text{沿路径的边}}\langle\cdot|U_j|\cdot\rangle. $$ 当时钟从 $0$ 单调走到 $T$ 且各层恰好经过一次时，右边的乘积正是 Feynman 路径积分的一条轨道 $\langle z|U_T\cdots U_1|y\rangle$ 的一个加项。**电路的振幅 = 历史路径的带权和**——这就是要把电路编码进重写的全部理由。 ### 5.3 字符串编码与门 gadget 重写系统版本把上述结构离散化、无权重化。字符串按功能分区： - **数据符号 (data symbols)**：一段长度 $n$ 的区间，表示计算比特的当前取值； - **时钟/头符号 (clock/head symbols)**：标记当前进行到哪一道门，相当于 Feynman 时钟的"读写头"； - **辅助符号**：记录门 gadget 内部的中间状态与符号信息（见下）。 每一条局部重写规则负责把时钟向前推进一步，同时实施相应门的**离散路径 gadget**：对通用门集中每个门的每个非零矩阵元，设计一小段固定长度的局部替换序列，使得"选哪条 gadget 路径"恰好对应"选该门的哪个矩阵元"。为了让每条 gadget 路径的权重变成纯粹的 $\pm1$（从而能被**计数**而不是加权求和），取门集为 Hadamard + Toffoli 这类矩阵元只有 $\pm1/\sqrt2$、$\pm1$ 等简单值的实门集（实量子计算与复量子计算在 BQP 意义下等价），把所有 $1/\sqrt2$ 因子收集起来吸收进归一化常数 $c$；剩下的正负号记录在辅助符号里随路径传播。由于每条规则都要可逆（§1 的对称性要求），gadget 内部也按可逆方式设计：每一步替换都由局部上下文唯一决定，逆规则就是按相反顺序撤销。这正是 $H_{\rm prop}$ 的局部字符串版本。 ### 5.4 符号的归宿：$t$ 与 $t'$ 的分流 最微妙的一步是：路径计数 $N_m$ 是非负整数，而电路振幅有正有负，**带符号的和怎么变成两个无符号计数的差**？答案是把符号信息路由到终点。当所有 $T$ 道门走完、计算停止时， gadget 把时钟引导到一个收尾阶段：读取数据区的输出比特（accept 或 reject）与辅助区记录的路径符号（$+$ 或 $-$），然后沿一条公共的"传送带"走向两个最终字符串之一—— - 终点 $t$：收集（accept, $+$）与（reject, $-$）两类历史路径； - 终点 $t'$：收集（accept, $-$）与（reject, $+$）两类历史路径。 设 $p_{\rm acc},p_{\rm rej}$ 是电路的接受与拒绝概率（以 $\lvert\cdot\rvert^2$ 归一、公共权重因子已提出），于是 $$ N_m(s\to t)-N_m(s\to t') \;\propto\; \sum_{\text{accept 路径}}(\text{符号})-\sum_{\text{reject 路径}}(\text{符号}) \;\propto\; p_{\rm acc}-p_{\rm rej}, $$ 即 $\Delta(m)$ 与电路的**接受偏差 (acceptance bias)** 同号：这正是"两个终点分别收集 accept/reject 分支的带符号路径贡献"的实现方式。符号本身从不被"数成负数"，而是通过终点身份贡献到差式的正确一侧。 ### 5.5 Padding、步数 $m$ 的选择与 gap 还差两个收尾条件。第一，所有历史路径必须有**相同**的总长度 $m$：在计算结束前后插入恒等的"等待"步（padding），让提前走完 gadget 的路径在原地附近踱步到统一步数；这样"恰好 $m$ 步到达 $t$"才能精确对应"完整执行了电路并收尾"。第二，BQP 的承诺是 $p_{\rm acc}-p_{\rm 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\leftrightarrow10, $$ 它只交换相邻两个不同的比特。注意这条规则**保持字符串的 Hamming 重量**（$1$ 的个数），所以重写图按重量分层、各层互不连通。这一节把长度 $L=3$ 的情形彻底算清楚。 (swap-rule-example)= ### 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=\begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix},\qquad A^2=\begin{pmatrix}1&0&1\\0&2&0\\1&0&1\end{pmatrix},\qquad A^3=\begin{pmatrix}0&2&0\\2&0&2\\0&2&0\end{pmatrix}. $$ 每个矩阵元都可以用 Lemma 1 逐条路径核对。例如 $(A^2)_{001,100}=1$ 对应唯一的两步序列 $$ 001\to010\to100; $$ $(A^2)_{001,001}=1$ 对应折返路径 $001\to010\to001$；$(A^2)_{010,010}=2$ 对应 $010\to001\to010$ 与 $010\to100\to010$ 两条；$(A^2)_{001,010}=0$ 因为该图是二分图，偶数步必回到出发一侧。$(A^3)_{001,010}=2$ 对应 $001\to010\to001\to010$ 和 $001\to010\to100\to010$；$(A^3)_{001,100}=0$ 同样由奇偶性排除。 现在取 $s=001$，$t=100$，$t'=010$，算出两种步数下的承诺量： $$ \Delta(2)=N_2(s\to t)-N_2(s\to t')=1-0=1,\qquad \frac{\Delta(2)}{c^2}=\frac14>0; $$ $$ \Delta(3)=0-2=-2,\qquad \frac{\Delta(3)}{c^3}=-\frac{2}{8}=-\frac14<0. $$ 同一组 $(s,t,t')$，仅仅把步数从 $2$ 改成 $3$，答案的符号就翻转了。这说明 $m$ 必须作为输入的一部分被明确给出——"从 $s$ 到 $t$ 还是到 $t'$ 更容易"这个问题本身在步数不确定时没有意义。 ### 7.3 两点讨论 第一，归一化常数的松紧。$A$（重量 $1$ 分量）的特征值是 $\pm\sqrt2$ 与 $0$，谱范数 $\sqrt2$，小于我们按 Lemma 2 取的 $c=d_{\max}=2$。一般图上 $\|A\|$ 可以等于 $d_{\max}$（正则图），所以 $c=d_{\max}$ 是安全而普适的选择；本例说明它不必是紧的。 第二，这个玩具规则与真实构造的距离。这里的路径计数可以直接手算，没有任何量子难度；真正的 BQP-hard 规则集包含时钟符号和门 gadget——每条路径携带从电路矩阵元继承来的符号，终点分流把接受偏差翻译成计数差。玩具例子的价值在于把 Lemma 1、归一化与 $\Delta$ 的符号判决这些**机制**演算一遍，而这些机制在真实构造里逐项原样保留。 ## 8. 小结 - 对称的局部重写规则定义一张稀疏、可有效探测的无向隐式图 $G_R$；恰好 $m$ 步的重写序列数等于邻接矩阵幂的矩阵元 $(A^m)_{ab}$（walk-count identity）。 - 量子算法把路径数之差写成单个矩阵元 $\Delta/\sqrt2=\langle\tau_-|A^m|s\rangle$，经归一化 $\|A/c\|\le1$、block encoding、多项式 $x^m$ 的 QSVT 与 Hadamard test，以 $\operatorname{poly}(L)$ 资源读出 $\Delta(m)/c^m$ 的符号；gap 承诺 $|\Delta|\ge\epsilon c^m$ 是效率的支点。 - 算法从不枚举 $c^m$ 条路径；符号来自两个目标振幅的相干相减。多项式就是 $x^m$ 本身，无逼近误差，唯一误差源是采样。 - Feynman 时钟把任意量子电路的传播 Hamiltonian 编成局部字符串重写；gadget 路径对应门矩阵元，符号经终点分流进入计数差，padding 统一步长——因此该承诺问题是 PromiseBQP-complete 的。 - 同一范式覆盖经典随机游走 mixing 的承诺问题（Zoo 58）与稀疏矩阵幂的估计：难度来自隐式指数状态图与高阶谱矩，而非单步转移。 ## 练习题 **练习 1【计数差问题与承诺】**（→ [1.2 节](#counting-difference-promise)） 1. 基础：写出 $N_m(a\to b)$ 与 $\Delta(m)$ 的定义；在规则 $01\leftrightarrow10$ 下，列出从 $010$ 出发恰好 $2$ 步又回到 $010$ 的全部重写序列，验证 $N_2(010\to010)=2$。 2. 基础：复述 gap 承诺与度上界两条承诺条件，并解释它们为什么保证归一化量 $\Delta(m)/c^m$ 远离零点、符号判决是稳定的。 3. 进阶：设 $N_m(s\to t)$ 与 $N_m(s\to t')$ 都是 $c^m$ 量级但只相差 $1$。写出此时判定符号所需的归一化精度，并据此说明 Hadamard test 路线的采样数如何随 $m$ 增长；解释这与 §1.3"没有 gap 时该问题不一定属于 BQP"的论断为何一致。 > 提示：归一化加性误差须小于 $c^{-m}$，由 Hoeffding 不等式，采样数为 $O(c^{2m})$。 **练习 2【隐式重写图与稀疏性】**（→ [2.1 节](#implicit-rewrite-graph)） 1. 基础：说明重写图的顶点数为何是 $|\Sigma|^L$、最大度为何只有 $O(L)$，并解释"给定字符串与邻居索引、计算该邻居"为什么只需 $\operatorname{poly}(L)$ 次位操作。 2. 进阶：说明规则的对称性 $u\leftrightarrow v$ 为什么使 $A$ 成为 Hermitian（实对称）矩阵。若规则只允许单向替换 $u\to v$，§2–§4 的链条分别在哪一步断裂？ > 提示：依次检查 $G_R$ 是否仍为无向图、$A$ 的对称性、block encoding 与 $x^m$ 变换对算子的要求。 **练习 3【walk-count 恒等式与矩阵元表示】**（→ [2.2 节](#walk-count-identity)） 1. 基础：对三点路径图 $a-b-c$（仅有边 $ab$、$bc$）写出 $A$、$A^2$、$A^3$，并对每个矩阵元列举对应的行走来核对 $(A^m)_{ab}=N_m(a\to b)$。 2. 基础：写出 $|\tau_-\rangle$ 的定义，推导 $\Delta(m)/\sqrt2=\langle\tau_-|A^m|s\rangle$，并指出推导中用到内积的哪条性质。 3. 进阶：补全 Lemma 1 归纳证明中 $m=1$ 的基例，并说明"删去最后一步"的分解为什么对 walk（允许重复经过顶点）仍然成立。如果把问题改成"简单路径"（不允许重复顶点），同样的矩阵恒等式还成立吗？为什么？ > 提示：简单路径删去最后一步仍是简单路径，但"简单路径加一条边"未必还是简单路径，分解不再可逆。 **练习 4【经典算法的瓶颈】**（→ [3.1 节](#classical-bottleneck)） 1. 基础：推导宽度优先枚举的工作量 $\Theta(\sum_{j=0}^{m}d^j)=\Theta(d^m)$，并解释在 $m=\operatorname{polylog}L$、$d=O(L)$ 时它为何是超多项式（准多项式量级）。 2. 进阶：随机采样估计的是频率差 $p_t-p_{t'}$ 而非计数差。给出一个使两者不等的机制，并说明即使校正了这一偏差，BQP-hardness 为什么仍在标准复杂性假设下排除经典多项式时间的符号判定算法。 > 提示：各顶点的合法重写数不同，随机行走的分布不均匀且未知。 **练习 5【归一化与稀疏 block encoding】**（→ [4.1 节](#normalization-block-encoding)） 1. 基础：写出 $O_{\rm pos}$ 与 $O_{\rm val}$ 在本问题中各自完成的任务，并指出由此得到的 $A/c$ block encoding 每次调用的代价。 2. 进阶：用 Gershgorin 定理证明 $\|A\|\le d_{\max}$，再给出一个 $\|A\|=d_{\max}$ 取等的图类，说明 $c=d_{\max}$ 一般不能系统性改进。 > 提示：考虑 $d_{\max}$-正则图，全 $1$ 向量是它的特征向量。 **练习 6【幂变换与 Hadamard test】**（→ [4.3 节](#power-hadamard-test)） 1. 基础：解释取 $p(x)=x^m$ 时为什么不需要任何多项式逼近、算法的唯一误差来源是什么，并说明总门数 $m\cdot\operatorname{poly}(L)\cdot O(1/\epsilon^2)$ 中三个因子各自的来源。 2. 进阶：逐项展开验证 $\langle\Phi|X\otimes W|\Phi\rangle=\operatorname{Re}\langle\tau_-|W|s\rangle$（指出交叉项消失的原因），再用 Hoeffding 不等式推导：要把期望值估到加性误差 $\epsilon/2$、失败概率不超过 $\delta$，需要多少次重复。 > 提示：$k=O(\epsilon^{-2}\log\frac1\delta)$。 **练习 7【从量子电路到重写规则】**（→ [5.1 节](#circuit-to-rewriting)） 1. 基础：写出 history state $|\eta\rangle$ 的定义，并说明时钟寄存器与传播 Hamiltonian $H_{\rm prop}$ 在 Feynman–Kitaev 构造中各自的作用。 2. 基础：说明为什么取 Hadamard + Toffoli 这类实门集能让每条 gadget 路径的权重化为纯计数意义上的 $\pm1$，以及 $1/\sqrt2$ 因子去了哪里。 3. 进阶：解释"门 gadget 路径对应门矩阵元"与"符号分流到 $t,t'$"如何把电路的接受偏差 $p_{\rm acc}-p_{\rm rej}$ 翻译成 $\Delta(m)$ 的符号，并说明 padding 步骤为什么必不可少。 > 提示：只有所有历史路径等长，"恰好 $m$ 步到达 $t$"才对应"完整执行电路并收尾"。 **练习 8【交换规则手算例子】**（→ [7.1 节](#swap-rule-example)） 1. 基础：取 $s=001$、$t=010$、$t'=100$，用 §7.2 的矩阵幂计算 $\Delta(1)$、$\Delta(2)$、$\Delta(3)$ 并给出各自符号。 2. 基础：对重量 $2$ 的连通分量 $\{011,101,110\}$ 写出邻接矩阵，计算 $A^2$，并取 $s=011$、$t=110$、$t'=101$ 计算 $\Delta(2)$ 与 $\Delta(3)$ 及其符号。 3. 进阶：证明对固定的 $(s,t,t')=(001,010,100)$，$\Delta(m)$ 的符号对一切 $m\ge1$ 随 $m$ 的奇偶性严格交替。 > 提示：重写图是二分图；从 $001$ 出发，奇数步只能到达 $010$ 一侧，偶数步只能回到 $\{001,100\}$ 一侧。 ## 参考文献 - Zoo 编号 59：Dominik Janzing 与 Pawel Wocjan, [A PromiseBQP-Complete String Rewriting Problem](https://arxiv.org/abs/0705.1180). - Zoo 编号 58：同作者关于稀疏图经典随机游走 mixing properties 的 BQP-complete 问题。