# Constraint Satisfaction：Grover、量子 Backtracking 与 Short-Path 算法 约束满足问题（constraint satisfaction problem，CSP）是这样一类问题：给定一组变量、每个变量的取值域，以及一组只牵涉少数变量的局部约束，要求找到一组同时满足全部约束的赋值（**判定/搜索版本**），或者找一组使被违反约束最少的赋值（**优化版本**，如 Max-SAT、MaxCut）。3-SAT、图着色、数独、QUBO/Ising 能量最小化都可以写成 CSP。 CSP 之所以重要，一方面是因为它几乎无处不在——调度、验证、规划、编译器优化最终都要解某种 CSP；另一方面是因为它是 NP-hard 问题的"标准载体"：Cook–Levin 定理之后，3-SAT 一直是 NP 完全性的基准实例，"量子计算能不能加速 NP-hard 问题"这个问题，最自然的试验场就是 CSP。 本篇要回答的问题因此非常具体：**对 CSP，量子算法到底能省多少？** 简短的回答是： - 对"穷举所有赋值"这一最朴素的做法，Grover 搜索给出平方加速（[第 3 章](../ch03-algo-basics/grover.md)）； - 但经典算法从不真的穷举——DPLL 式 backtracking、随机游走、meet-in-the-middle 等早已远优于穷举。正确的比较对象是**最好的经典结构化算法**，而这正是量子 backtracking（Montanaro 2015，Zoo 264）与树大小估计（Ambainis–Kokainis，Zoo 422）所做的事； - 在特定能量景观假设下，short-path 类算法（Zoo 492–493）可以在指数底数上做得比 Grover 的 $1/2$ 更好，但这些结论依赖额外的谱假设，**不能**推广成"量子多项式时间解任意 CSP"——后者会蕴含 $\mathrm{NP}\subseteq\mathrm{BQP}$，目前没有证据，主流观点也不相信它成立。 阅读本篇需要的前置知识：Grover 搜索与[振幅放大](../ch03-algo-basics/amplitude-amplification.md)、[相位估计](../ch03-algo-basics/phase-estimation.md)，以及量子游走的基本概念。全篇的复杂度都以对问题结构的**查询次数**（predicate/heuristic 调用、约束验证）计，每个寄存器操作视为多项式开销。 :::{admonition} 本课知识点 :class: tip 1. **[CSP 形式化与 Grover 基线](#csp-formal-definition)**——能写出 CSP 的三要素与违反代价 $E(x)$，推导朴素 Grover 基线 $O(D^{n/2}\,V(n))$ 的两个因子来源，并解释为什么诚实的比较对象是结构化经典算法而非穷举。 2. **[谓词—启发式框架与剪枝树](#backtracking-framework)**——能定义部分赋值、谓词 $P$ 的三种返回值与分支启发式 $h$，并说明剪枝树大小 $T$ 为何是经典 backtracking 的正确代价参数。 3. **[星态与双反射量子游走](#star-states-reflections)**——能写出奇偶二分、星态与游走算子 $W = R_B R_A$ 的构造，并解释 accept 节点如何被"摘出"星子空间以充当谱标记。 4. **[谱分离与判定复杂度](#spectral-separation)**——能解释有解与无解两种情形下根态在小相位本征态上的质量差异，并把 $O(\sqrt{T}\,n^{3/2}\log n)$ 逐项分解到相位估计精度与每步反射的实现成本。 5. **[未知树大小：加倍猜测与自归约](#doubling-trick)**——能用等比数列求和验证加倍猜测只损失常数因子，并说明树大小估计与 self-reduction 如何在 $T$ 未知时仍完成完整搜索。 6. **[底数比较与相干化条件](#speedup-comparison)**——能把 $T = c^n$ 的经典树换算成量子指数底数 $\sqrt{c}$ 并完成数值比较，同时指出相干化实现谓词与启发式的限制（如 CDCL 的动态子句库）。 7. **[Short-path 机制与保留条款](#short-path-mechanism)**——能写出 $H(b) = H_Z - bX$ 并概述"投影—overlap 放大—读出"三步流程，推导 super-Grover 底数 $D^{\alpha/2}$ 的来源并列出其依赖的谱假设。 8. **[QUBO 的 SDP relaxation](#qubo-sdp-relaxation)**——能把 QUBO 松弛成 Gram 矩阵 SDP 并证明 SDP 最优值是真实最优值的下界，说明 rounding 流水线中量子加速的切入点。 ::: ## 1. 问题形式化与朴素 Grover 基线 (csp-formal-definition)= ### 1.1 CSP 的正式定义 一个 CSP 实例由三部分组成： - **变量** $x_1,\ldots,x_n$，每个变量在有限取值域中取值，$x_i \in [D] := \{0,1,\ldots,D-1\}$（布尔情形 $D=2$）； - **约束** $C_1,\ldots,C_m$，每个约束 $C_a$ 只作用在常数个变量上（称为约束的**宽度**；3-SAT 的宽度是 3），并输出 $C_a(x) \in \{0,1\}$：$1$ 表示该约束被赋值 $x$ 满足，$0$ 表示被违反； - **目标**：找到 $x$ 使所有 $C_a(x)=1$（判定/搜索），或最小化被违反的约束数（优化）。 为统一两种版本，定义**违反代价 (violation cost)** $$ E(x)=\sum_{a=1}^{m}\left(1-C_a(x)\right). $$ 每一项 $1-C_a(x)$ 恰在约束 $a$ 被违反时贡献 $1$，否则贡献 $0$，所以 $E(x)$ 就是被违反约束的总数。判定版本等价于问 $\min_x E(x) = 0$ 是否成立；优化版本就是求 $\min_x E(x)$。把 $E(x)$ 写成对角的"代价哈密顿量" $H_Z = \sum_x E(x)|x\rangle\langle x|$，就得到了后面 short-path 与绝热算法的出发点（第 6 节）。 ### 1.2 Grover 基线：对穷举的平方加速 假设验证一个完整赋值 $x$ 是否满足全部约束的成本是 $V(n)$（逐个检查 $m$ 个约束，每个约束只读常数个变量，因此 $V(n) = O(m) = \mathrm{poly}(n)$，具体指数不影响下面的讨论）。把所有 $D^n$ 个赋值当作搜索空间，把"$E(x)=0$"当作标记条件，直接套用 Grover/BBHT（解的个数未知时的版本，见第 3 章振幅放大一篇），找到一组解的代价是 $$ O\!\left(D^{n/2}\,V(n)\right). $$ 这个表达式的两个因子来源很清楚：搜索空间大小为 $D^n$，Grover 需要 $O(\sqrt{D^n}) = O(D^{n/2})$ 次预言机调用；每次调用要相干地计算标记谓词，即验证一个赋值，成本 $V(n)$。相对经典穷举的 $O(D^n V(n))$，这是查询意义上的平方加速。 ### 1.3 为什么这个比较是错的 然而，"量子 $D^{n/2}$ 对经典 $D^n$"是一个误导性的比较，因为**没有经典算法真的穷举**。三个典型的经典杠杆： - **分支与剪枝 (branch and prune)**：backtracking 类算法逐变量赋值，一旦某个部分赋值已经违反约束，就立刻回溯，不再展开它下面的整棵子树。实际运行时间由剪枝后的搜索树大小 $T$ 决定，$T$ 可以远小于 $D^n$； - **传播与学习**：DPLL 及其现代后代（CDCL solver）用 unit propagation 自动推出被强制的变量取值，用 clause learning 记录冲突原因以避免重蹈覆辙，在实践中能解百万变量级的工业 SAT 实例； - **随机化与折半**：随机化 SAT 算法（随机初始赋值 + 局部翻转）和 meet-in-the-middle 技巧，对许多 CSP 给出底数显著小于 $D$ 的指数时间算法。 因此，诚实的量子加速声明必须从"**把最好的经典结构化算法量子化**"出发，而不是从穷举出发。接下来两节先看清经典 backtracking 的结构，再构造它的量子版本。 ## 2. 经典 Backtracking 与剪枝树 (backtracking-framework)= ### 2.1 部分赋值与判定谓词 Backtracking 算法的每个中间状态是一个**部分赋值 (partial assignment)** $$ v=(x_1,\ldots,x_\ell),\qquad 0\le\ell\le n, $$ 即只给前 $\ell$ 个变量（或启发式选出的某 $\ell$ 个变量）赋了值，其余变量尚未决定。$\ell=0$ 是树根（空赋值），$\ell=n$ 是完整赋值。 算法的全部"领域知识"封装在两个黑盒里： - **判定谓词 (predicate)** $P(v)$，对任一节点返回三种结果之一： - **reject**：$v$ 中已被赋值的变量之间已经出现约束冲突（存在某个 $C_a$，其涉及的所有变量都已被赋值，且 $C_a(v)=0$）。此时 $v$ 下面的整棵子树不可能含解； - **accept**：$v$ 是一组完整的满足赋值，$E(v)=0$； - **continue**：以上都不是——还有变量未赋值，且目前没有可判定的冲突。 - **分支启发式 (branching heuristic)** $h(v)$：在 continue 情形，挑选下一个要赋值的变量（例如"出现在最短未满足子句中的变量"），并生成子节点 $v0, v1, \ldots, v(D-1)$，即该变量的所有可能取值。 给定输入后，经典算法的整个运行过程等价于在隐式定义的搜索树上做深度优先遍历：遇 reject 就剪枝回溯，遇 accept 就停机。我们把**实际被展开的那棵树**记为 $\mathcal T$，其顶点数记为 $T$。$T$ 是衡量经典算法真实代价的正确参数：运行时间是 $O(T \cdot \mathrm{poly}(n))$，而 $T$ 可能远小于 $D^n$——也可能接近它，取决于实例和启发式。 ### 2.2 传播与学习如何改变 $T$ 值得强调：DPLL 的 unit propagation（某子句只剩一个未赋值文字时，该文字的取值被强制，直接赋值而不再分支）和 CDCL 的 clause learning，**不改变算法解的是什么问题，只改变树 $\mathcal T$ 的形状与大小**——强制的变量不再产生分支，学到的子句让某些子树更早被剪掉。只要这些规则被固定为可描述的确定性过程，"经典 backtracking 算法"就是"谓词 $P$ + 启发式 $h$ + 深度优先遍历"这一抽象框架的特例，而下面量子化的对象正是这个抽象框架本身。 ### 2.3 随机 backtracking 许多现代 SAT solver 本质上是随机的：随机化变量取值顺序、随机重启。对随机算法，有意义的量是"找到解的期望时间"，它与 $T$ 和成功概率 $p$ 都有关。第 5 节会看到，这类算法对应量子化的另一条路径（振幅放大），与树游走路径互补。 ## 3. 树上的量子游走：Montanaro 算法 本节构造量子 backtracking 算法。目标先放低一点：**只判定树中是否存在 accept 节点**（第 4 节再讲如何真正找出一组解）。 ### 3.1 核心思想：不问"哪个叶子是解"，只问"树里有没有解" 经典深度优先遍历要逐个访问叶子，量子算法换一个问法：把整棵树 $\mathcal T$ 当作一个图，构造一个定义在树上的量子游走，使得"树中含 accept 节点"与"不含 accept 节点"这两种情形，在**根节点附近的相位谱**上留下可区分的痕迹。随后用相位估计（其精度—开销关系读者已从相位估计一篇熟悉）读出这个痕迹。 为什么这样可能有效？直觉来自电网络。把树想象成一张电网：每棵子树若不含解，从根看进去是一条"死路"，电流流进去就没有出口；若某条根到叶子的路径尽头是 accept 节点，我们就人为地在那里接一个"出口"。"有解"等价于"从根到某个出口存在一条长度不超过 $n$ 的通路"，而这会体现为根处的等效电阻（从而游走的谱）发生可测的变化。下面把这个直觉逐步形式化。 (star-states-reflections)= ### 3.2 二分分层与星态 把树按深度的奇偶性分成两个顶点集合： $$ A = \{v : \mathrm{depth}(v)\ \text{为偶数}\},\qquad B = \{v : \mathrm{depth}(v)\ \text{为奇数}\}. $$ 树是二分图，每条边都连接 $A$ 与 $B$——这正是可以套用"两个反射之积"框架（与 Grover/振幅放大同一个骨架）的原因。 对每个非叶节点 $v$，定义它的**星态 (star state)**：以 $v$ 与其所有子节点为支撑的归一化叠加 $$ |s_v\rangle \propto |v\rangle + \sum_{w\ \text{为}\ v\ \text{的子节点}}\lambda_{v,w}\,|w\rangle, $$ 其中权重 $\lambda_{v,w} > 0$ 按子节点的度（子树的局部大小）选取。权重的设计原则是：使得从根出发、沿任意一条根到叶路径，可以把单位"流量"逐级分摊到各条边上，而每条边上分摊到的振幅平方和（即流的"能量"）恰好被路径长度控制住。这个性质是后面 witness 构造能成立的关键，具体权重公式不影响理解主线，这里从略。 记 $\mathcal S_A = \mathrm{span}\{|s_v\rangle : v \in A\}$、$\mathcal S_B = \mathrm{span}\{|s_v\rangle : v \in B\}$ 为两族星态张成的子空间，并定义两个反射算子： $$ R_A = 2\Pi_{\mathcal S_A} - I,\qquad R_B = 2\Pi_{\mathcal S_B} - I, $$ 其中 $\Pi$ 表示向对应子空间的正交投影。对 accept 节点要做一处修改：把它从所在星子空间中"摘掉"（等价地，让它对应的反射方向翻转符号），使它成为谱上的标记点。**量子游走算子**定义为两个反射的乘积 $$ W = R_B R_A. $$ 与 Grover 迭代一样，两个反射的复合限制在适当的不变子空间上是一系列二维旋转（见 Grover 一篇 Theorem 4 的同一几何图像），相位估计要读的正是这些旋转角（本征相位）。 (spectral-separation)= ### 3.3 有解与无解的谱分离 记根的星态为 $|r\rangle$（以根为心的均匀带权叠加，容易从空赋值直接制备）。算法的有效性基于下面两条性质（这是 Montanaro 分析的核心，属于 effective spectral gap 类引理；这里给出陈述与证明思路，完整技术细节见原论文）： **关键事实 1（有解 ⇒ 根附近有小相位本征态）。** 若树中存在 accept 节点 $v_*$，则 $W$ 有一个本征值为 $e^{i\varphi}$、相位 $$ |\varphi| = O\!\left(\frac{1}{\sqrt{nT}}\right) $$ 的本征态，且它与 $|r\rangle$ 的 overlap 为常数级（不随 $n,T$ 缩小）。 *证明思路。* 取根到 $v_*$ 的唯一路径。利用上节星态权重的设计，沿这条路径构造一个"近零相位"的候选本征态：在路径的每个节点上，把振幅按星态的比例逐级传递下去，路径外振幅为零。路径长度至多为 $n$（树深至多为 $n$，因为每下一层多赋一个变量），而整个构造相对"全空间均匀模式"的归一化代价由 $\sqrt{T}$ 控制——粗略地说，候选态要把 $\Theta(1)$ 的概率质量铺在一条长度 $n$ 的路径上，而根态在树上的总质量是 $T$，两者内积贡献出 $1/\sqrt{T}$ 量级的因子，路径长度贡献出 $1/\sqrt{n}$ 量级的因子，合起来相位尺度就是 $1/\sqrt{nT}$。这个候选态就是电网络语言里"从根到出口的单位流"所对应的 **正 witness**。 **关键事实 2（无解 ⇒ 根在小相位区几乎没有质量）。** 若树中不存在 accept 节点，则 $|r\rangle$ 在 $W$ 的所有相位 $|\varphi| \le \Theta(1/\sqrt{nT})$（常数取得比事实 1 中稍大）的本征态上的总投影质量可以做到任意小（例如小于 $1/10$）。 *证明思路。* 无解时，电网络没有出口：任何从根出发的流都没有汇，effective spectral gap lemma 类型的论证表明，此时所有小相位本征方向都必须对应"流向无穷远"的模式，而有限树中不存在这样的模式，于是根态只能由相位显著大于 $1/\sqrt{nT}$ 的本征态组成。 两条事实合起来：以精度 $\Theta(1/\sqrt{nT})$ 对态 $|r\rangle$ 关于 $W$ 做相位估计—— - 有解时，以常数概率测到落在小相位窗口内的读数； - 无解时，测得小相位的概率可压到任意小。 重复常数次即可把两种情况以高置信度区分开。 ### 3.4 复杂度：$O(\sqrt{T}\,n^{3/2}\log n)$ 的逐项来源 设树深至多为 $n$、顶点数的上界 $T$ 已知（不知道怎么办是第 4 节的事）。Montanaro 算法完成上述判定的谓词/启发式调用次数为 $$ O\!\left(\sqrt{T}\,n^{3/2}\log n\right). $$ 逐项解释每个因子（下面是对原论文分析的结构性还原，常数与 $\log$ 的精确归属以原文为准）： - **相位估计精度 → $O(\sqrt{nT})$ 步游走。** 相位估计要把相位测到精度 $\varepsilon$ 需要 $O(1/\varepsilon)$ 次受控 $W$ 调用（这是相位估计的标准精度—开销关系）。这里 $\varepsilon = \Theta(1/\sqrt{nT})$，故需要 $O(\sqrt{nT})$ 步游走。把它再拆开：$\sqrt{T}$ 是"搜索空间大小开根号"这一 Grover 式主项；$\sqrt{n}$ 来自根到解的**路径深度**——电网络语言中等效电阻被路径长度 $n$ 控制，路径越深、信号越弱、所需精度越高。 - **每步游走的实现成本 → $O(n\log n)$。** 一步 $W = R_B R_A$ 是两次反射。实现每次反射要在星子空间上做投影，而每个星态的制备涉及：读出长度为 $O(n)$ 的部分赋值、调用 $h(v)$ 生成子节点、调用 $P$ 判定 reject/accept/continue——每个节点的描述与处理都是 $O(n)$ 量级的寄存器操作；此外，整轮相位估计共 $O(\sqrt{nT})$ 步，为使总误差不累积，每步的近似精度要随步数收紧，谱放大/相位估计的精度开销贡献出 $\log n$ 级别的因子。合起来每步 $O(n\log n)$ 次调用。 两者相乘：$O(\sqrt{nT}) \times O(n\log n) = O(\sqrt{T}\,n^{3/2}\log n)$。 **强调**：这个复杂度的主指数是 $\sqrt{T}$，而 $n^{3/2}\log n$ 是谱隙、路径深度与误差放大堆出来的多项式开销。**不能**把它"约简"成精确的 $\sqrt{T}$——在与经典算法比较底数时，这个多项式因子必须始终带上（第 5 节会看到它不影响指数底数的比较，但影响有限规模下的结论）。 ## 4. 不知道树大小 $T$ 怎么办 第 3.4 节假设了 $T$ 的上界已知——这决定了相位估计的精度。但真实 backtracking 树的大小恰恰是我们事先不知道的（它依赖于实例与启发式的相互作用）。有两条互补的出路。 (doubling-trick)= ### 4.1 加倍猜测（doubling trick） 按 $$ T_0,\ 2T_0,\ 4T_0,\ \ldots $$ 递增的猜测值依次运行第 3 节的判定算法：每个猜测 $T_i$ 对应一个相位估计精度；若该轮报告"有解"（可以再用常数次重复把误报率压低），就停止；否则把猜测翻倍再来。 **总代价分析。** 设真实树大小为 $T$，算法最多跑到第一个满足 $2^k T_0 \ge T$ 的 $k$（此时精度足够，有解必被发现），即 $2^k T_0 < 2T$。各轮代价是公比为 $\sqrt{2}$ 的等比数列，求和得 $$ \sum_{i=0}^{k}\sqrt{2^i T_0}\,n^{3/2}\log n =\sqrt{T_0}\,n^{3/2}\log n\cdot\frac{2^{(k+1)/2}-1}{\sqrt{2}-1} =O\!\left(\sqrt{2^k T_0}\,n^{3/2}\log n\right) =O\!\left(\sqrt{T}\,n^{3/2}\log n\right), $$ 其中第一步用了等比数列求和公式 $\sum_{i=0}^{k} r^i = \frac{r^{k+1}-1}{r-1}$（$r=\sqrt{2}$），第二步把分母 $\sqrt{2}-1$ 吸收进常数、并把 $2^{(k+1)/2} = \sqrt{2}\cdot\sqrt{2^k}$ 合并进 $O(\sqrt{2^k T_0})$，最后一步用 $2^k T_0 = O(T)$。结论：**等比数列被最后一项主导，加倍猜测只损失常数因子**。每轮还要把失败概率压到 $O(1/k)$ 量级以便对 $k$ 轮做 union bound，这只引入额外的对数因子。 ### 4.2 量子树大小估计 更系统的做法是 Ambainis–Kokainis 的量子树大小估计（Zoo 422）：在运行搜索之前，先用量子方法估计（可能截断的）backtracking 树的顶点数 $T$ 本身——例如判断"树是否比给定阈值大"。把估计子程序与第 3 节的检测子程序嵌套起来，就得到一个**不需要任何可靠经典 $T$ 上界**的完整搜索算法，其开销仍由真实 $T$ 的平方根量级（乘以 $n$ 的多项式）控制。这把"量子 backtracking 的加速由实际剪枝效果决定"这一原则贯彻到底：连"剪枝效果有多好"这个问题本身也交给量子算法回答。 ### 4.3 从判定到搜索：self-reduction 到目前为止只解决了判定（树里有没有解）。找出一组完整解用标准的**自归约 (self-reduction)**： 1. 对根节点的每个子节点，递归判定"该子树是否含解"（每个子树本身也是一棵合法的 backtracking 树）； 2. 找到第一个回答"是"的子节点，固定这一层变量的取值，下钻一层； 3. 重复 $n$ 次，逐层确定 $x_1,\ldots,x_n$ 的全部取值。 每一层至多 $D$ 次判定调用，共 $n$ 层，额外开销是 $O(Dn)$ 次判定——相对判定的指数级主项只是个多项式因子。这个开销也无法再压缩太多：输出一组赋值本身就需要写下 $\Omega(n)$ 位信息。 (speedup-comparison)= ## 5. 相对最好经典算法，到底加速了多少 现在可以回到第 1.3 节的问题：诚实的比较是什么结果。设针对某类 CSP，最好的经典算法成本为 $O(c^n)$（底数 $c < D$ 是经典算法设计几十年积累的成果）。量子化有两条路径，对应两类经典算法： - **随机算法 → 振幅放大。** 若经典算法是"单次成本 $C$、成功概率 $p$"的随机过程（随机化 backtracking、随机重启都属此类），把它相干化后直接套振幅放大：代价从 $O(C/p)$ 降为 $O(C/\sqrt{p})$，即把成功概率的依赖开根号； - **backtracking → 树游走。** 若经典算法等价于大小 $T = O(c^n)$ 的 backtracking 树，第 3–4 节给出 $O(\sqrt{T}\,\mathrm{poly}(n)) = O(c^{n/2}\,\mathrm{poly}(n))$，即**指数底数开根号**：$c \mapsto \sqrt{c}$。 **一个具体的数值比较。** 设某经典算法给出 $T = 1.4^n$ 的树。则： - 经典运行：$1.4^n$； - 量子 backtracking：主项 $\sqrt{1.4^n} = (\sqrt{1.4})^n \approx 1.183^n$（因为 $\sqrt{1.4} \approx 1.1832$，验证：$1.1832^2 \approx 1.4000$）； - 朴素 Grover 基线（对 $2^n$ 个布尔赋值穷举搜索）：$2^{n/2} = (\sqrt{2})^n \approx 1.414^n$（$\sqrt{2} \approx 1.4142$）。 三个底数 $1.183 < 1.4 < 1.414$ 的次序说明：量子化结构化经典算法（$1.183^n$）远优于量子化穷举（$1.414^n$）——**量子收益的大小由经典算法的质量决定**，这正是"从最好经典算法出发"这一原则的定量含义。 同时必须保留原文的两条警示： 1. **相干化有成本。** 上述量子化要求谓词 $P$、启发式 $h$ 及其数据结构能被相干地实现（可逆、可叠加地执行）。对简单的分支规则这通常可行；但现代 solver 的 clause learning 维护一个随运行不断增长的**动态全局状态**（学到的子句库），它不对应一棵"无记忆"的树——每个节点的行为依赖于整条历史路径。这类算法不能直接套进第 3 节的框架。 2. **没有统一答案。** 文献中的做法是针对 3-SAT 等具体问题，选择特定的经典分解（嵌套搜索、特定 backtracking 结构，Zoo 133–134、298），逐一证明相对**当时最佳经典算法**的指数底数改进。结论是"对这些问题、相对这些经典算法，底数从 $c$ 降到 $\sqrt{c}$（或更好）"，而**不是**一个适用于一切 CSP 的统一 $2^{n/2}$ 答案。 ## 6. Short-path 与 super-Grover 机制 第 3–5 节的加速都是"平方根型"的：指数底数开根号。一个自然的问题是：能不能做得更好——**超过 Grover 的 $1/2$ 指数**？short-path 类算法（Zoo 492–493）在额外的谱假设下给出了肯定答案。 ### 6.1 setup：代价哈密顿量加混合项 把第 1.1 节的违反代价写成对角哈密顿量 $$ H_Z = \sum_{x\in[D]^n} E(x)\,|x\rangle\langle x|, $$ 并加入横向（混合）项，定义单参数哈密顿量族 $$ H(b) = H_Z - bX,\qquad X = \sum_{i=1}^{n} X_i, $$ 其中 $X_i$ 是作用在第 $i$ 个变量上的 Pauli $X$（布尔情形；对一般取值域可用相应的移位算子或低度多项式变体）。两个极端的行为是： - $b \to \infty$：$H(b) \approx -bX$，基态近似 $|+\rangle^{\otimes n}$（所有赋值的均匀叠加），**容易制备**； - $b = 0$：$H(0) = H_Z$，基态就是最优赋值 $|x_*\rangle$，这正是我们想要的。 (short-path-mechanism)= ### 6.2 为什么不走完整的绝热路径 标准绝热算法（见本站[绝热优化](adiabatic-optimization.md)一篇）从 $b$ 很大的易制备基态出发，缓慢地把 $b$ 降到 $0$，依靠绝热定理保持在瞬时基态上。问题在于：沿路径的最小能隙可以指数小，绝热定理要求的演化时间相应指数长——对困难的 CSP 实例，这条"全程慢速驾驶"的路径没有任何加速保证。 Short-path 的想法是**不走完这条路**。它观察到：为了最终拿到最优解，并不需要一直待在基态上——只需要在路径上找到**某个点**，该点的低能态对最优解（或足够好的解）的 overlap 显著大于均匀叠加的 $D^{-n/2}$。具体分三步： 1. **投影。** 从易制备的对称态（大 $b$ 端）出发，用一个相对短时的演化或谱滤波，把态投影到**适度 $b$** 处的低能子空间——只走"路径的一小段"，绕开中途可能出现的小能隙区域； 2. **利用 overlap 放大。** 在该低能子空间中，低能态的振幅不再均匀分布，而是向代价 $E(x)$ 低的赋值集中：因为 $H(b)$ 的能量由 $H_Z$ 主导、被 $-bX$ 微扰，微扰论直觉告诉我们，低能本征态在低 $E(x)$ 的组态上有更大的权重。于是测量该态得到优秀经典解的概率 $p$，大于均匀测量的 $D^{-n}$； 3. **放大并读出。** 对这个"以概率 $p$ 成功"的子过程做振幅放大（$O(1/\sqrt{p})$ 次重复），或直接重复测量，得到最优/近似最优解。 **为什么可能超过 Grover？** Grover 式方法从均匀叠加出发，初始 overlap 是 $D^{-n/2}$。若第 2 步的谱性质使得投影后的 overlap 是 $D^{-\alpha n/2}$、$\alpha < 1$，则同样的振幅放大会给出底数 $D^{\alpha/2}$ 的复杂度——严格优于 $D^{1/2}$。这就是 "super-Grover" 一词的含义。 与此相关的 jump-to-the-end 类技术更进一步：干脆不做慢演化，而是想办法**直接制备路径终态**（或用谱滤波把终态从初态中滤出），把"沿路径开车"换成"空运到终点附近"，同样是为了规避小能隙带来的慢演化。 ### 6.3 必须保留的保留条款 以上机制**不是**对任意 CSP 都成立。它的成立条件包括（原文的保留条款，此处展开解释）： - **代价分布的随机性/规则性**：证明依赖"局部随机能量景观"类的假设——例如把 $E(x)$ 建模为局部随机代价函数，此时低能谱有可参考的浓度现象； - **谱与能隙条件**：第 1 步的投影成本、第 2 步的 overlap 大小，都取决于 $H(b)$ 低能区的具体谱结构（低能态个数、与激发态的间隙），这些量对一般 CSP 实例无法控制； - **结论的外推限度**：因此 short-path 的 super-Grover 结论**只对其定理假设覆盖的代价分布与谱条件成立**，不代表"任意 CSP 都能超过 Grover 指数"，更与 $\mathrm{P}=\mathrm{NP}$ 型结论无关。对最坏情形的 NP-hard 实例，目前已知的量子加速仍然是平方根型的。 ## 7. 近似优化：QUBO 与 SDP relaxation 如果放弃精确最优，只要**有质量保证的近似解**，量子算法还有另一条加速通道：加速经典的 relaxation + rounding 流水线。 ### 7.1 QUBO/Ising 形式 许多组合优化问题可以写成二次无约束二值优化（QUBO），即 Ising 能量最小化： $$ \min_{z\in\{\pm1\}^n}\ z^T Q z = \min_{z\in\{\pm1\}^n}\ \sum_{i,j} Q_{ij}\,z_i z_j, $$ 其中 $Q$ 是给定的实对称矩阵。例如 MaxCut：对图 $G=(V,E)$，取 $z_i = \pm1$ 表示顶点 $i$ 属于哪一侧，则 $(1 - z_i z_j)/2$ 恰在边 $(i,j)$ 被割开时等于 $1$，于是割的大小为 $\frac12\sum_{(i,j)\in E}(1 - z_i z_j)$，最大化它是 QUBO 的特例。一般 QUBO 是 NP-hard 的。 (qubo-sdp-relaxation)= ### 7.2 从 QUBO 到 SDP：relaxation 的推导 困难在于约束 $z_i \in \{\pm1\}$ 是离散的。松弛的标准做法是"升维"：为每个变量 $z_i$ 配一个单位矢量 $v_i \in \mathbb{R}^d$，并定义 **Gram 矩阵** $$ X_{ij} = v_i \cdot v_j,\qquad X \succeq 0,\qquad X_{ii} = 1. $$ 两个条件的含义：$X \succeq 0$（半正定）正是"$X$ 是某组矢量的 Gram 矩阵"的充要条件；$X_{ii} = \|v_i\|^2 = 1$ 把每个矢量钉在单位球面上。把目标中的乘积 $z_i z_j$ 替换为内积 $v_i \cdot v_j = X_{ij}$，目标函数变成 $$ \sum_{i,j} Q_{ij} X_{ij} = \operatorname{Tr}(QX), $$ 对 $X$ 是**线性**的。于是一个 NP-hard 的离散优化被放松成一个半定规划（SDP）： $$ \min_{X \succeq 0,\ X_{ii}=1}\ \operatorname{Tr}(QX). $$ **松弛方向的验证（为什么 SDP 给出下界）。** 任取一组合法赋值 $z \in \{\pm1\}^n$，令 $X = zz^T$，即 $X_{ij} = z_i z_j$。逐条检查约束：$X_{ii} = z_i^2 = 1$ ✓；对任意矢量 $u$，$u^T X u = u^T z z^T u = (z^T u)^2 \ge 0$，故 $X \succeq 0$ ✓；目标值 $\operatorname{Tr}(Qzz^T) = \operatorname{Tr}(z^T Q z) = z^T Q z$（第一步用迹的循环性 $\operatorname{Tr}(AB) = \operatorname{Tr}(BA)$）✓。所以**每组离散赋值都对应 SDP 的一个可行解**（秩 1 的 Gram 矩阵），SDP 在更大的可行集上最小化，必有 $$ \operatorname{SDP}_{\min} \le \operatorname{QUBO}_{\min}. $$ SDP 最优值是真实最优值的下界，两者之差称为 integrality gap。 ### 7.3 Rounding 与量子加速点 解完 SDP 后还要回到离散世界：随机取一个超平面（随机方向 $r$，令 $\hat z_i = \mathrm{sgn}(v_i \cdot r)$），把单位矢量"舍入"成 $\pm1$ 赋值。对 MaxCut，这一经典流水线（Goemans–Williamson）保证期望割值不低于最优值的 $0.878$ 倍——这就是"approximation pipeline"的含义：**松弛给出可计算的下界，舍入给出有证明保证的赋值**。 量子加速作用在流水线的中间环节：当 $Q$（或等价的输入矩阵）具有**低秩或隐式表示**（不必读出全部 $n^2$ 个矩阵元）时，量子 SDP solver（见本站[量子半定规划](semidefinite-programming.md)一篇）可以对某些参数（矩阵维数、稀疏度相关的因子）给出平方级改善，再衔接同样的随机超平面舍入（Zoo 423）。 同样要强调保留条款：这是对**近似流水线**的加速——输出的是带近似比的赋值，不保证解出精确 NP-hard 最优解；且加速依赖低秩/隐式输入的表示假设，对一般的稠密显式输入不成立。 ## 8. 小例子：一个 3-SAT 实例的完整计算 用一个可手算的实例把第 1–4 节的概念全部过一遍。取 $n=3$、$D=2$ 的公式 $$ \varphi = \underbrace{(x_1\lor x_2\lor\neg x_3)}_{C_1}\ \land\ \underbrace{(\neg x_1\lor x_3)}_{C_2}. $$ ### 8.1 先枚举：哪些赋值是解 全部 $2^3 = 8$ 组赋值逐个检查（$C_a=1$ 表示满足）： | $x_1x_2x_3$ | $C_1$ | $C_2$ | $E(x)=2-C_1-C_2$ | |---|---|---|---| | 000 | $0\lor0\lor1=1$ | $1\lor0=1$ | 0（解） | | 001 | $0\lor0\lor0=0$ | $1\lor1=1$ | 1 | | 010 | $0\lor1\lor1=1$ | $1\lor0=1$ | 0（解） | | 011 | $0\lor1\lor0=1$ | $1\lor1=1$ | 0（解） | | 100 | $1\lor0\lor1=1$ | $0\lor0=0$ | 1 | | 101 | $1\lor0\lor0=1$ | $0\lor1=1$ | 0（解） | | 110 | $1\lor1\lor1=1$ | $0\lor0=0$ | 1 | | 111 | $1\lor1\lor0=1$ | $0\lor1=1$ | 0（解） | 共 5 组解。注意违反赋值的分布很有结构：$x_1=1$ 且 $x_3=0$ 的两组赋值（100、110）都因 $C_2$ 失败——它们将被同一刀剪掉。 ### 8.2 朴素 Grover 基线 搜索空间 $N=8$，解数 $M=5$，Grover 迭代次数约 $\frac{\pi}{4}\sqrt{N/M} = \frac{\pi}{4}\sqrt{8/5} \approx 1.0$——一次迭代即接近最优。这个实例解太密，体现不出搜索算法的价值；它用来展示 backtracking 的**结构**，而非量子优势的大小。 ### 8.3 Backtracking 树：剪枝如何发生 取分支启发式 $h$ 为"优先选择出现在最短子句中的变量"：$C_2$ 最短（2 个文字），故分支顺序为 $x_1 \to x_3 \to x_2$。逐节点展开： - **根**（空赋值）：两个子句都有未赋值文字，continue。 - **$x_1 = 0$**：$C_2 = 1 \lor x_3$ 已满足；$C_1$ 待定。continue，下一层分支 $x_3$。 - **$x_3 = 0$**：$C_1 = 0 \lor x_2 \lor 1 = 1$，**两个子句都已满足**，$x_2$ 无论取什么都无所谓——直接 accept。这一刀剪掉了 $x_2$ 下面的 2 组完整赋值（000、010 都是解，一次输出即可）。 - **$x_3 = 1$**：$C_1 = 0 \lor x_2 \lor 0 = x_2$，悬而未决。continue，分支 $x_2$： - $x_2 = 0$：$C_1 = 0$，reject（对应赋值 001，与表中 $E=1$ 一致）； - $x_2 = 1$：$C_1 = 1$，accept（赋值 011）。 - **$x_1 = 1$**：$C_2 = 0 \lor x_3 = x_3$，$C_1$ 已满足（$x_1=1$）。continue，分支 $x_3$。 - **$x_3 = 0$**：$C_2 = 0$——**冲突已判定，reject**。这就是原文指出的剪枝点：部分赋值 $(x_1, x_3) = (1, 0)$ 让 $C_2$ 的所有文字都已被赋值且全为假，于是它下面的整棵 $x_2$ 子树（赋值 100、110）被一刀剪掉，不再展开。 - **$x_3 = 1$**：$C_2 = 1$，两子句均满足，accept（覆盖 101、111）。 **统计这棵树。** 顶点：根 1 个 + 第 1 层 2 个 + 第 2 层 4 个 + 第 3 层 2 个（只有 $(x_1,x_3)=(0,1)$ 需要展开 $x_2$）$= 9$ 个，即 $T = 9$。对比穷举的 $D^n = 8$ 组完整赋值——这个玩具实例上剪枝甚至"不划算"，这是任何固定开销方法在小规模下的通病。要点在于**渐近行为**：好的启发式让 $T$ 随 $n$ 以 $c^n$（$c<2$）增长，而量子 backtracking 的开销由 $\sqrt{T}$ 决定，且**不在被剪枝的赋值上浪费任何振幅**——第 3 节的游走只在这 9 个顶点对应的星态子空间里演化，被拒掉的子树从未进入 Hilbert 空间。 ## 9. 小结 **小结。** - Grover 只给穷举平方加速：$O(D^{n/2}V(n))$。由于经典算法从不穷举，一切诚实的量子加速声明都应从最佳结构化经典算法（backtracking、随机化算法、relaxation 流水线）出发。 - Backtracking 把经典运行归结为大小 $T$ 的剪枝树；树上量子游走用双反射 $W = R_B R_A$ 加相位估计判定解的存在性，根到解的路径流给出相位尺度 $1/\sqrt{nT}$ 的正 witness，主复杂度因子是 $\sqrt{T}$，而 $n^{3/2}\log n$ 来自路径深度、每步反射的实现与误差放大，不能省略。 - 树大小未知时，加倍猜测只损失常数因子（等比数列被末项主导），Ambainis–Kokainis 树大小估计（Zoo 422）把对 $T$ 的依赖彻底自动化；self-reduction 以多项式额外开销把判定升级为搜索。 - Short-path 与 jump-to-the-end（Zoo 492–493）在局部随机能量与谱条件下可超过 Grover 指数，但结论严格依赖代价分布与低能谱假设；量子 SDP solver 加速的是低秩/隐式输入下的近似流水线。两者都不能推广成"量子多项式时间解任意 CSP"，更与 $\mathrm{P}=\mathrm{NP}$ 无关。 ## 练习题 **练习 1【CSP 形式化与 Grover 基线】**（→ [1.1 节](#csp-formal-definition)） 1. 基础：写出 CSP 三要素（变量与取值域、约束、目标）在 3-SAT 中的对应；对第 8 节公式 $\varphi=(x_1\lor x_2\lor\neg x_3)\land(\neg x_1\lor x_3)$ 的赋值 $x=100$ 与 $x=101$ 分别计算违反代价 $E(x)$，并与第 8.1 节的表格核对。 2. 基础：取 $D=3$、$n=20$，比较朴素 Grover 基线与经典穷举所需的谓词调用次数（$3^{10}$ 对 $3^{20}$），并写出一般情形 $O(D^{n/2}\,V(n))$ 中两个因子各自的来源。 3. 进阶：解释"量子 $D^{n/2}$ 对经典 $D^n$"为什么是误导性比较：列举第 1.3 节的三类经典杠杆（分支与剪枝、传播与学习、随机化与折半），并说明各自对应的哪个量（剪枝树大小、期望时间等）应当取代 $D^n$ 出现在诚实的比较中。 > 提示：剪枝后的运行时间不再是 $D^n$ 的函数——是哪个量的函数？ **练习 2【谓词—启发式框架与剪枝树】**（→ [2.1 节](#backtracking-framework)） 1. 基础：写出谓词 $P(v)$ 的 reject/accept/continue 三种返回值各自的判定条件；对第 8.3 节的部分赋值 $(x_1,x_3)=(1,0)$ 指出 $P$ 的返回值，并解释为什么它下面的整棵 $x_2$ 子树（赋值 100、110）可以被一刀剪掉。 2. 进阶：解释 unit propagation 与 clause learning 为什么只改变树 $\mathcal T$ 的形状与大小、而不破坏"谓词 $P$ + 启发式 $h$ + 深度优先遍历"这一抽象框架；这为什么是第 3 节量子化得以成立的前提？ 3. 进阶：对 2-SAT 公式 $\psi = (x_1 \lor x_2)\land(\neg x_1 \lor x_3)\land(\neg x_2 \lor \neg x_3)$，按变量顺序 $x_1 \to x_2 \to x_3$ 画出带 unit propagation 的 backtracking 树：每个节点标注部分赋值与 $P(v)$ 的返回值（reject/accept/continue），数出 $T$，并与穷举的 $2^3$ 比较。 > 提示：先手工判断 $\psi$ 可满足。 **练习 3【星态与双反射量子游走】**（→ [3.2 节](#star-states-reflections)） 1. 基础：写出奇偶二分 $A$、$B$ 的定义与星态 $|s_v\rangle$ 的一般形式，并说明"树是二分图"与"游走算子可写成两个反射之积 $W = R_B R_A$"之间的关系。 2. 进阶：解释 accept 节点是如何从星子空间中被"摘出"的、为什么这一步使它成为谱上的标记点；并说明 $W$ 限制在不变子空间上为什么是一系列二维旋转、这与 Grover 迭代的几何图像有何联系。 3. 进阶：复述星态权重 $\lambda_{v,w} > 0$ 的设计原则（沿根到叶路径分摊单位"流量"、每条边上的"能量"被路径长度控制），并说明该性质在第 3.3 节 witness 构造中扮演的角色。 > 提示：对照 Grover 一篇 Theorem 4 的"两个反射 = 旋转"图像。 **练习 4【谱分离与判定复杂度】**（→ [3.3 节](#spectral-separation)） 1. 基础：陈述关键事实 1 与关键事实 2（有解/无解时，根态 $|r\rangle$ 在 $W$ 的小相位本征态上的质量分别如何），并说明相位估计的精度应取到什么量级才能把两种情形区分开。 2. 进阶：把 $O(\sqrt{T}\,n^{3/2}\log n)$ 分解为"相位估计精度 → $O(\sqrt{nT})$ 步游走"与"每步实现成本 → $O(n\log n)$"两项，逐个解释 $\sqrt T$、$\sqrt n$、$n$、$\log n$ 四个因子的来源，并说明为什么不能把它约简成精确的 $\sqrt T$。 3. 进阶：用第 8.3 节的树，具体写出从根到某个 accept 节点的路径，并解释：为什么沿这条路径构造的"近零相位"态与根态的 overlap 只按 $1/\sqrt{T}$ 缩小，而不按 $1/\sqrt{D^n}$ 缩小？这一区别为什么正是量子 backtracking 优于朴素 Grover 的根源？ > 提示：近零相位候选态只把 $\Theta(1)$ 的概率质量铺在一条长度 $\le n$ 的路径上，而根态的质量分布在全部 $T$ 个顶点上。 **练习 5【未知树大小：加倍猜测与自归约】**（→ [4.1 节](#doubling-trick)） 1. 基础：说明加倍猜测中每个猜测值 $T_i$ 如何决定该轮相位估计的精度、为什么各轮代价构成公比为 $\sqrt 2$ 的等比数列；再简述 self-reduction 如何以 $O(Dn)$ 次判定调用把判定升级为搜索。 2. 进阶：补全第 4.1 节的计算：设各轮代价为 $\sqrt{2^i T_0}\cdot P(n)$（$P(n)$ 为多项式因子），证明 $k$ 轮总代价不超过 $\frac{\sqrt{2}}{\sqrt{2}-1}\sqrt{2^k T_0}\cdot P(n)$，并解释为什么"猜测值按 $T_0, 2T_0, \ldots$ 增长"优于"按 $T_0, T_0+1, \ldots$ 线性增长"。 3. 进阶：解释 Ambainis–Kokainis 的量子树大小估计（Zoo 422）为什么能把"对 $T$ 的依赖"也交给量子算法处理；相对加倍猜测，它额外解决了什么问题？ > 提示：等比数列求和 $\sum_{i=0}^{k} r^i = \frac{r^{k+1}-1}{r-1}$（$r=\sqrt2$）。 **练习 6【底数比较与相干化条件】**（→ [第 5 节](#speedup-comparison)） 1. 基础：设某类 CSP 上最好的经典算法是"单次成本 $C$、成功概率 $p$"的随机算法，写出经典期望代价 $O(C/p)$ 与振幅放大后的代价 $O(C/\sqrt p)$；再设经典 backtracking 给出 $T = c^n$ 的树，写出量子 backtracking 的复杂度并指出底数变化 $c \mapsto \sqrt c$。 2. 进阶：设经典算法的树大小为 $T = c^n$（布尔情形 $D=2$）。证明：只要 $c < 2$，量子 backtracking 的指数底数 $\sqrt{c}$ 就严格优于朴素 Grover 的 $\sqrt{2}$；并对 $c = 1.4$ 算出三个底数 $\sqrt{c}$、$\sqrt{2}$、$c$ 的数值（保留 4 位小数），排成不等式。 3. 进阶：CDCL solver 的 clause learning 会把冲突中学到的新子句加入全局子句库，影响之后所有节点的判定。为什么这使得对应的搜索过程**不再是一棵"无记忆的"树**？这对第 3 节的量子化框架意味着哪一步会失败？ > 提示：$\sqrt c < \sqrt 2 \iff c < 2$；三个底数中最大的那个对应朴素 Grover。 **练习 7【Short-path 机制与保留条款】**（→ [6.2 节](#short-path-mechanism)） 1. 基础：写出 $H(b) = H_Z - bX$ 的定义（$H_Z$、$X$ 各是什么），并说明 $b\to\infty$ 与 $b=0$ 两个极端处的基态分别是什么、为什么大 $b$ 端的基态容易制备。 2. 进阶：概述 short-path 的三步流程（投影—利用 overlap 放大—放大并读出），并解释：若投影后的 overlap 为 $D^{-\alpha n/2}$（$\alpha<1$），为什么最终复杂度的指数底数 $D^{\alpha/2}$ 严格优于 Grover 的 $D^{1/2}$。 3. 进阶：列出 short-path 结论的三类保留条款（代价分布的随机性、低能谱条件、结论外推限度），并解释为什么它们不能推广成"量子多项式时间解任意 CSP"——后一会蕴含哪个复杂性包含关系？ > 提示：成功概率 $p$ 是振幅 overlap 的平方，把它代入振幅放大的 $O(1/\sqrt p)$。 **练习 8【QUBO 的 SDP relaxation】**（→ [7.2 节](#qubo-sdp-relaxation)） 1. 基础：把 MaxCut 写成 QUBO：说明 $\frac{1-z_i z_j}{2}$ 为什么恰在边 $(i,j)$ 被割开时等于 $1$，并写出割的大小的表达式；再写出 Gram SDP 的两条约束 $X \succeq 0$、$X_{ii} = 1$ 各自的几何含义。 2. 进阶：对最小化形式的 QUBO，验证任取赋值 $z\in\{\pm1\}^n$、令 $X = zz^T$ 都给出 SDP 的可行解且目标值相同（逐条检查 $X_{ii}=1$、$X\succeq 0$、$\operatorname{Tr}(Qzz^T) = z^T Q z$），从而证明 $\operatorname{SDP}_{\min} \le \operatorname{QUBO}_{\min}$，并说出两者之差的名称。 3. 进阶：对三角形 $K_3$（3 个顶点、3 条边）的 MaxCut：(a) 写出它的 QUBO 形式 $\frac12\sum_{(i,j)\in E}(1 - z_i z_j)$；(b) 写出对应的 Gram SDP relaxation（变量、约束、目标）；(c) 验证 $X = zz^T$ 对任意 $z\in\{\pm1\}^3$ 可行，从而说明 SDP 最优值不小于真实最大割。(d) 真实最大割是 2；若 SDP 返回 $X^* = \frac32 I - \frac12 J$（$J$ 为全 1 矩阵），它可行吗？对应的目标值是多少？ > 提示：$J$ 的特征值是 $3, 0, 0$。 ## 参考文献与 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 的加速。