# 字符串重写量子算法：隐式图路径计数与 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 的一个连通分量。

## 参考文献

- Zoo 编号 59：Dominik Janzing 与 Pawel Wocjan, [A PromiseBQP-Complete String Rewriting Problem](https://arxiv.org/abs/0705.1180).
- Zoo 编号 58：同作者关于稀疏图经典随机游走 mixing properties 的 BQP-complete 问题。