# Constraint Satisfaction：Grover、量子 Backtracking 与 Short-Path 算法

Constraint satisfaction problem（CSP）给变量、取值域和局部约束，要求找到满足全部约束的赋值，或最大化满足数。3-SAT、图着色、QUBO 等包含 NP-hard 实例；量子算法不会普遍变成多项式时间，但可对穷举、经典 backtracking tree 或特定能量景观获得多项式/指数底数改进。

## 1. 问题与朴素 Grover 基线

$n$ 个变量 $x_i\in[D]$，约束 $C_a$ 作用在常数个变量。定义 violation cost

$$
E(x)=\sum_a(1-C_a(x)).
$$

满足性是寻找 $E(x)=0$。若验证一个完整赋值成本 $V(n)$，Grover 在 $D^n$ 个赋值上给

$$
O(D^{n/2}V(n)).
$$

这只相对 brute force 平方加速。经典 SAT/CSP 算法用分支、传播、meet-in-the-middle 等常已优于 $D^n$；正确比较应量子化最好结构化算法，而不是只比较穷举。

## 2. Classical backtracking tree

Backtracking 顶点是 partial assignment

$$
v=(x_1,\ldots,x_\ell),\qquad0\le\ell\le n.
$$

Predicate $P(v)$ 返回：

- reject：已有约束冲突；
- accept：完整满足解；
- continue：按 heuristic $h(v)$ 选择下一变量并生成 children。

给定输入后，经典算法实际探索一棵剪枝树 $\mathcal T$，大小 $T$ 可能远小于 $D^n$。DPLL 的 unit propagation、clause learning（若固定为可逆/可描述规则）都改变 $T$。

## 3. Tree quantum walk 的双反射

把树按深度奇偶分成顶点集合 $A,B$。对每个顶点 $v$ 构造局部 star state，包含 $v$ 与 children 的带权叠加。令 $R_A,R_B$ 分别在偶/奇层 star subspaces 上反射，并对 marked accept vertex 修改反射。Walk

$$
W=R_BR_A.
$$

若存在解，从根到 marked vertex 的路径流构造近零 phase eigenvector，并与根态有逆多项式 overlap。若无解，effective spectral gap lemma 证明根态在小 phase 区域的质量很小。Phase estimation 因而判断树是否含 marked vertex。

若树深至多 $n$、顶点数上界 $T$ 已知，Montanaro 算法用

$$
O(\sqrt T\,n^{3/2}\log n)
$$

次 predicate/heuristic 调用完成判定。主指数是 $\sqrt T$；$n^{3/2}$ 来自谱隙、路径深度和误差放大，不应省成精确 $\sqrt T$。

## 4. 不知道 $T$ 怎么办

真实 backtracking tree 大小通常未知。可以按

$$
T_0,2T_0,4T_0,\ldots
$$

递增假设运行，或先用 quantum tree-size estimation 判断截断树是否超过阈值。Ambainis--Kokainis 算法估计树大小并改进依赖，使搜索无需可靠经典 $T$ 上界。

找到一个解可用 self-reduction：先判定根的哪个 child 子树有解，固定该分支，递归 $n$ 次。额外因子多项式；输出完整赋值至少要 $\Omega(n)$ 位。

## 5. 相对最好经典 SAT 算法的加速

设经典随机/分支算法成本 $O(c^n)$。若它能被整理为：

- 成功概率 $p$、单次成本 $C$ 的随机算法，可 amplitude amplify 到 $O(C/\sqrt p)$；或
- 大小 $T=O(c^n)$ 的 backtracking tree，可降到 $O(c^{n/2}\operatorname{poly}n)$。

但量子化可能需要相干实现数据结构，且 clause learning 产生的动态全局状态不一定直接对应一棵无记忆树。文献针对 3-SAT 和其他 CSP 选择具体经典分解/嵌套搜索，获得相对当时最佳经典算法的多项式指数改进，而非统一的 $2^{n/2}$ 答案。

## 6. Short-path 与 super-Grover 机制

把 cost 写成对角 Hamiltonian $H_Z$，加入弱 transverse/mixing 项：

$$
H(b)=H_Z-bX,\qquad
X=\sum_iX_i
$$

或低度多项式变体。Short-path 算法不从 $b=0$ 完整绝热走到大 $b$，而是：

1. 从易制备对称态投影到适度 $b$ 的低能态；
2. 利用低能态对优秀经典解的 overlap 大于均匀态；
3. amplitude amplify/测量得到 optimum。

在局部随机能量与谱条件下，该 overlap 改善可超过 Grover 指数。Jump-to-the-end 类技术直接准备路径终态/滤波，减少慢演化。结论依具体 cost distribution、gap 与低能谱，不代表任意 CSP super-Grover。

## 7. Approximate QUBO 与 SDP

QUBO/Ising：

$$
\min_{z_i\in\{\pm1\}}
z^TQz.
$$

把 $z_iz_j$ 放宽为 Gram matrix $X_{ij}=v_i\cdot v_j$、$X\succeq0$、$X_{ii}=1$，得到 SDP relaxation。低秩/隐式输入时量子 SDP solver 可平方改善某些参数，再做随机 hyperplane rounding 得近似赋值。这是对 approximation pipeline 的加速，不保证精确 NP-hard optimum。

## 8. 小例子：3-SAT partial tree

Clause

$$
(x_1\lor x_2\lor\neg x_3)
\land(\neg x_1\lor x_3)
$$

在 partial assignment $x_1=1,x_3=0$ 时第二 clause 已冲突，整棵后续 $x_2$ 子树可剪掉。量子 backtracking 使用同一 predicate，不在被剪枝赋值上浪费振幅；优势由实际 $T$ 而非 $2^3$ 衡量。

## 9. 小结与习题

- Grover 只给穷举平方加速，结构化比较应从最佳 backtracking/随机算法开始。
- Tree walk 的 phase gap 与路径 witness 给 $\sqrt T$ 主依赖。
- Tree-size estimation 处理未知 $T$，self-reduction 输出解。
- Short-path 与 SDP approximation 需要额外谱/结构承诺，不能推广为 P=NP。

1. 为一个 2-SAT 例子画出带 unit propagation 的 backtracking tree。
2. 解释 root-to-solution path 如何形成正 witness。
3. 比较 $T=1.4^n$ 与 brute-force Grover 的指数。
4. 写出 MaxCut 的 QUBO 与 Gram SDP relaxation。

## 参考文献与 Zoo 覆盖

- Zoo 133--134、298、492--493：nested search、structured SAT、short-path 与 jump-to-end。
- Zoo 264：Ashley Montanaro, [Quantum Walk Speedup of Backtracking Algorithms](https://arxiv.org/abs/1509.02374).
- Zoo 422：Ambainis--Kokainis tree-size estimation。
- Zoo 423：低秩 SDP 对 homogeneous QUBO/Ising approximation 的加速。