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\)，而是：

从易制备对称态投影到适度 \(b\) 的低能态；
利用低能态对优秀经典解的 overlap 大于均匀态；
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。

为一个 2-SAT 例子画出带 unit propagation 的 backtracking tree。
解释 root-to-solution path 如何形成正 witness。
比较 \(T=1.4^n\) 与 brute-force Grover 的指数。
写出 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.
Zoo 422：Ambainis--Kokainis tree-size estimation。
Zoo 423：低秩 SDP 对 homogeneous QUBO/Ising approximation 的加速。