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

字符串重写看似纯组合：按固定局部规则把一个字符串逐步改成另一个。若规则对称，每个长度 \(L\) 字符串是一个巨大无向图的顶点，一次局部替换是一条边；恰好 \(m\) 步的重写序列数就是邻接矩阵幂的 entry。量子算法估计两个目标路径数之差的归一化符号，而 Feynman history 构造又能把任意量子电路编进局部规则，因此该 promise problem 是 BQP-complete。

1. 问题定义

固定有限 alphabet \(\Sigma\) 和常数长度局部规则集合

\[ u\leftrightarrow v,\qquad u,v\in\Sigma^{O(1)}. \]

给三个长度 \(L\) 字符串 \(s,t,t'\)。一部重写可在任意位置把 \(u\) 换成 \(v\) 或反向。令

\[ N_m(a\to b) \]

为恰好 \(m\) 步从 \(a\) 到 \(b\) 的重写序列数，目标判断

\[ \Delta(m)=N_m(s\to t)-N_m(s\to t') \]

的正负。参数 \(m=\operatorname{polylog}L\)。

承诺存在常数 \(c\) 与逆多对数 \(\epsilon\)：

\[ |\Delta(m)|\ge\epsilon c^m, \]

并有适当 growth/degree bound 保证任意相关路径数不超过 \(c^n\) 尺度。没有 gap 时，区分相差 1 的两个指数大计数不一定属于 BQP。

2. Rewrite graph 与矩阵幂

定义隐式图 \(G_R\)：顶点为 \(\Sigma^L\)，若两字符串可一步互换则相邻。邻接矩阵 \(A\) 实对称，且每个字符串只有

\[ O(L) \]

个“规则 × 位置”候选邻居；给定字符串与邻居索引可在 \(\operatorname{polylog}|\Sigma^L|=\operatorname{poly}(L)\) 位操作内生成。

标准 walk-count identity：

\[ (A^m)_{ab}=N_m(a\to b). \]

所以

\[ \Delta(m) =\langle t|A^m|s\rangle -\langle t'|A^m|s\rangle. \]

取

\[ |\tau_-\rangle=(|t\rangle-|t'\rangle)/\sqrt2, \]

则 \(\Delta/\sqrt2=\langle\tau_-|A^m|s\rangle\)。

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

由最大 rewrite degree/growth 构造 \(A/c\) 的 sparse block encoding，使

\[ \|A/c\|\le1 \]

（原论文用等价的谱测量/随机行走构造；现代语言可用 QSVT）。对多项式

\[ p(x)=x^m \]

做 quantum singular/eigenvalue transformation，得到 top block 近似 \((A/c)^m\)。Hadamard test 在 \(|s\rangle\) 与 \(|\tau_-\rangle\) 间估计

\[ \frac{\Delta(m)}{\sqrt2,c^m} \]

到加性误差 \(O(\epsilon)\)。Promise gap 保证符号稳定。

因 \(m\)、\(1/\epsilon\) 与 sparse-oracle 成本均为 \(\operatorname{polylog}\) 或多项式输入长度，总算法属于 PromiseBQP。算法不枚举 \(c^m\) 条路径；正负来自两个目标振幅的相干相减。

4. 为什么 BQP-hard

给任意量子电路

\[ U=U_T\cdots U_1, \]

构造字符串编码：

  • 数据 symbols 表示计算 qubits；

  • clock/head symbols 标记当前门位置；

  • 局部可逆 rewrite 把 clock 前进一步并施加相应门的离散路径 gadget；

  • 两个终点 \(t,t'\) 分别收集 accept/reject 分支的带符号路径贡献。

这相当于 Feynman propagation Hamiltonian

\[ H_{\rm prop} =\sum_{j=0}^{T-1} \bigl(|j+1\rangle\langle j|\otimes U_{j+1}+h.c.\bigr) \]

的局部字符串版本。适当 padding 与选择 \(m\) 后，\(\Delta(m)/c^m\) 与电路接受偏差同号且有逆多项式 gap。因此能解 rewriting promise problem 就能决定任意 BQP language。

5. 与经典随机行走 mixing 的联系

若把 \(A\) 归一化为 stochastic matrix，\((P^m)_{ab}\) 是随机游走转移概率。Janzing--Wocjan 还构造了关于稀疏图经典 walk mixing/相关统计的 BQP-complete promise problems。困难来自隐式指数状态图和高阶谱矩，不是每一步 transition 本身复杂。

6. 小例子

规则

\[ 01\leftrightarrow10 \]

只交换相邻不同 bit。长度 3 从 001 到 100 恰需两步：

\[ 001\to010\to100. \]

所以 \((A^2)_{001,100}=1\)。若另取 \(t'=010\)，两步返回/绕行数量可能不同，\(\Delta(2)\) 由相应矩阵元差给出。真实 BQP-hard 规则集包含 clock 和门 gadget，而不是这一简单交换规则。

7. 小结与习题

  • 对称局部 rewrite rules 定义稀疏无向隐式图。

  • \(m\) 步重写数等于邻接矩阵 \(A^m\) 的 entry。

  • 量子算法估计 \(\Delta/c^m\) 的加性符号，promise gap 至关重要。

  • Feynman clock 把量子电路传播编成局部字符串重写，证明 BQP-hard。

  1. 证明 walk-count identity \((A^m)_{ab}\)。

  2. 说明为何规则对称使 \(A\) Hermitian。

  3. 解释没有 \(|\Delta|\ge\epsilon c^m\) 时符号估计会怎样变难。

  4. 对简单交换规则列出长度 3 rewrite graph 的一个连通分量。

参考文献