字符串重写量子算法：隐式图路径计数与 PromiseBQP 完备性

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

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

本课知识点

  1. 计数差问题与承诺——能写出对称局部重写规则、\(m\) 步重写序列与计数 \(N_m(a\to b)\)、\(\Delta(m)\) 的定义，陈述 gap 承诺 \(|\Delta(m)|\ge\epsilon c^m\)，并解释没有 gap 时判定符号为何需要指数精度。

  2. 隐式重写图与稀疏性——能说明重写图 \(G_R\) 为何有 \(|\Sigma|^L\) 个顶点而最大度只有 \(O(L)\)，以及给定字符串与邻居索引时为何只需 \(\operatorname{poly}(L)\) 次位操作即可算出邻居。

  3. walk-count 恒等式与矩阵元表示——能用归纳法证明 \((A^m)_{ab}=N_m(a\to b)\)，并把 \(\Delta(m)/\sqrt2\) 写成单个矩阵元 \(\langle\tau_-|A^m|s\rangle\)。

  4. 经典算法的瓶颈——能推导枚举算法 \(\Theta(c^m)\) 的工作量，并从"估计的不是目标量"与 BQP-hardness 两方面说明随机采样为何不能判定 \(\Delta(m)\) 的符号。

  5. 归一化与稀疏 block encoding——能用 Gershgorin 定理证明 \(\|A/c\|\le1\)，并解释 \(O_{\rm pos}\)、\(O_{\rm val}\) 两类预言机如何给出 \(A/c\) 的 block encoding。

  6. 幂变换与 Hadamard test——能解释 \(p(x)=x^m\) 的 QSVT 实现为何无需多项式逼近，推导 \(\langle\Phi|X\otimes W|\Phi\rangle=\Delta(m)/(\sqrt2\,c^m)\)，并算出采样数与总门数。

  7. 从量子电路到重写规则——能解释 history state、传播 Hamiltonian 的路径解释、门 gadget 与符号分流，并说明 padding 与多数放大如何兑现 gap 承诺。

  8. 交换规则手算例子——能在 \(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{ 的重写序列}\}. \]

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. 重写图：从组合计数到矩阵幂

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 能够构造的前提。

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. 经典算法能做到什么

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

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)\)。下面逐块展开。

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\)。这就是"隐式指数大图"范式成立的技术核心：图大到不能写下，但局部结构简单到可以按需查询。

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 语言都能归约到它。方向与直觉相反——我们不是用重写系统去模拟某个具体组合问题，而是用它模拟任意量子电路。

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\) 的情形彻底算清楚。

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)\) 写邻接矩阵并逐次取幂：

\[\begin{split} 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}. \end{split}\]

每个矩阵元都可以用 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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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\}\) 一侧。

参考文献