# 量子指数时间动态规划：Path-in-the-Hypercube 与分层 Grover

许多 NP-hard 问题的经典最佳算法不是暴力枚举所有解，而是在所有子集上做**动态规划 (dynamic programming)**，运行时间 $O^*(2^n)$。这条技术路线可以追溯到 1960 年代 Bellman 与 Held–Karp 的工作；以旅行商问题（TSP）为例，Held–Karp 的 $O(n^2 2^n)$ 算法至今仍是已知最好的**精确**经典算法，六十余年没有被实质改进。一个自然的问题是：量子计算机能否攻破这堵 $2^n$ 的墙？

答案比"用 Grover 搜索所有子集"微妙得多。Ambainis、Balodis、Iraids、Kokainis、Prūsis 与 Vihrovs（Zoo 编号 409，arXiv:1807.05209）注意到这类算法有一个共同的几何形状——它们都在 $n$ 维超立方体上求一条**单调路径**——于是把结构抽象成 **path-in-the-hypercube** 问题，并给出 $O^*(1.817^n)$ 的量子算法。技巧的组合是：**经典地**预计算若干低 Hamming 层的动态规划表（这些层只有 $2^{H(\alpha)n}$ 个顶点，远少于 $2^n$），再用递归的量子搜索跨越中间层。同一套思路还给出顶点排序类问题的 $O^*(1.817^n)$、TSP 的 $O^*(1.729^n)$ 型结果、最小集合覆盖的 $O(\operatorname{poly}(m,n)\,1.728^n)$，以及图带宽从经典约 $4.383^n$ 到约 $2.946^n$ 的改进。

本教程假设读者已学完本站 ch01–ch08，特别是 [Grover 算法](../ch03-algo-basics/grover.md)与[振幅放大](../ch03-algo-basics/amplitude-amplification.md)；我们只引用其结论（"$N$ 个候选中找一个命中项需要 $\Theta(\sqrt N)$ 次查询"），不再重新推导。阅读路线图：第 1 节讲来龙去脉与记号；第 2 节形式化定义问题与经典算法；第 3 节用两次失败的尝试解释为什么"直接量子化动态规划"行不通；第 4 节用平实语言给出核心直觉；第 5 节准备熵与 Stirling 的组合工具；第 6 节完整推导一个单层切分的简化方案（含参数平衡的求解过程）；第 7 节说明原文如何用多层不对称切分把它改进到 1.817；第 8 节回到 TSP、集合覆盖、带宽等真实 NP-hard 问题；第 9 节讨论空间、QRAM 与输出解的隐藏成本；第 10 节是一个可以手算的 $n=4$ 小例子。

:::{admonition} 本课知识点
:class: tip

1. **[子集动态规划的范式与瓶颈](#subset-dp-paradigm)**——能列出子集动态规划的"状态、转移、合法性检查"三要素，并解释为什么其成本瓶颈在于 $2^n$ 个状态本身而非单个状态的计算量。
2. **[PATH 问题与经典递推](#hypercube-path-dp)**——能写出有向超立方体上 PATH 问题的定义与 $DP[S]$ 递推，并在小实例上按层自下而上填表验证 $O^*(2^n)$ 的经典算法。
3. **[朴素量子化为什么失败](#naive-quantumization-failure)**——能解出中点递推 $T(r)=2\cdot 2^{r/2}\,T(r/2)$ 并证明 $T(r)=2^{r}\operatorname{poly}(r)$，进而解释量子分支为何无法共享记忆化表。
4. **[熵标尺：Stirling 与低层估计](#entropy-stirling-tools)**——能用 Stirling 公式推导 $\binom{n}{\alpha n}=2^{\,nH(\alpha)}/\operatorname{poly}(n)$，并证明低层求和界 $\sum_{j\le\alpha n}\binom nj\le(\alpha n+1)\,2^{\,nH(\alpha)}$。
5. **[两张经典表与补集镜像](#two-tables-complement-mirror)**——能写出下表 $R_\uparrow$ 与上表 $R_\downarrow$ 的递推，并证明补集对合把"上半段可达性"化为镜像实例的"下半段可达性"。
6. **[单层切分与参数平衡](#single-split-balance)**——能把"中层搜索 × 表证人搜索 × 经典叶子"三个因子相乘得到 $E(\alpha)=\max\{H(\alpha),\ 1-\alpha+\tfrac14H(2\alpha)\}$，并用平衡方程解出 $\alpha^\ast\approx0.3245$、底数 $\approx1.878$。
7. **[从骨架到真实 NP-hard 问题](#np-hard-applications)**——能说明把一个子集动态规划装进 PATH 骨架的三个条件，并比较 TSP、集合覆盖与图带宽各自的量子指数为何不能由 $1.817$ 直接代入。
8. **[QRAM、空间与输出解的账单](#qram-space-output)**——能计算省去 QRAM 时单次表查询成本 $2^{H(\alpha)n/2}$ 叠加后的总指数，并说明 self-reduction 恢复完整解只增加多项式开销。

:::

## 1. 来龙去脉：指数时间动态规划与量子的机会

(subset-dp-paradigm)=
### 1.1 子集动态规划：一个统治了六十年的范式

"子集动态规划"的模板如下。问题的解可以看成对 $n$ 个元素的一个**构建顺序**：状态是"已经构建了哪些元素"，即一个子集 $S \subseteq [n]$（$[n] := \{1,2,\dots,n\}$）；转移是"再构建一个元素" $S \to S\cup\{i\}$；每个状态带一个**合法性检查**（是否满足问题的约束）与一个**值**（代价、最优值等）。答案在 $2^n$ 个状态上递推：

- TSP：状态是（已访问城市集合， 当前所在城市），Held–Karp 递推 $O(n^2 2^n)$；
- 最小集合覆盖：状态是已被覆盖的宇宙子集，$2^n$ 个状态（$n$ 为宇宙大小）；
- 图带宽等顶点排序问题：状态是已排在前缀的顶点集合。

这套范式的成本结构很清楚：状态空间恰好是 $2^n$，因此任何"逐状态填写"的算法至少付出 $2^n$。对 TSP 而言，六十年来各种改进思路都没能把底数压到 2 以下；对带宽等问题的专用经典算法，底数则由它们各自的递推决定（如图带宽约为 $4.383$，见第 8.5 节）。**瓶颈不是单个状态的计算量（那是多项式的），而是状态本身的个数。**

### 1.2 记号：$O^*$ 与常用符号

全文用

$$ O^*(f(n)) := O(f(n)\cdot \operatorname{poly}(n)) $$

表示隐藏多项式因子的复杂度。这样做的理由是：当主项是 $2^{\Theta(n)}$ 时，多项式因子在渐近上无关紧要。例如 $2^n$ 与 $1.817^n$ 的差别在 $n=100$ 时是 $2^{100}/2^{86.2} \approx 1.5\times 10^4$ 倍，而 $n^{10}$ 这样的多项式因子与它相比可以忽略。底数的改进是**指数级**的改进，这正是本文的主题。

为方便查阅，把后文反复出现的符号集中列在这里（首次定义处见括号内的小节）：

| 符号 | 含义 |
|---|---|
| $[n]$，$S\subseteq[n]$，$\lvert S\rvert$ | 元素集 $\{1,\dots,n\}$；超立方体顶点（子集）；顶点重量（§2） |
| $\operatorname{valid}(S)$ | 顶点合法性预言机（§2） |
| $\operatorname{Reach}(u\to v)$ | 从 $u$ 到 $v$ 的（每步加一元素的）路径存在性（§3.1） |
| $H(\alpha)$ | 二元熵函数（§5.1） |
| $\mathcal L_\alpha$，$R_\uparrow$，$R_\downarrow$ | 低层顶点集；下表；上表（§5.1，§6.1） |
| $L(M)$，$U(M)$ | 中点的下半/上半程可达性（§6.3） |
| $\alpha,\beta$ | 切分点所在的 Hamming 分数（§6，§7） |
| $g$，$r$ | 区间长度（叶子间隔；递推中的间隔）（§3.2，§6.3） |
| $\iota(S)=[n]\setminus S$ | 补集对合（§6.1） |

### 1.3 量子侧：工具与障碍

量子的工具箱里，与本问题相关的是无结构搜索的二次加速：在 $N$ 个候选中找一个命中项（或判定没有命中项），量子搜索需要 $\Theta(\sqrt N)$ 次查询，而经典需要 $\Theta(N)$ 次（见 [Grover 算法](../ch03-algo-basics/grover.md)）。更一般地，[振幅放大](../ch03-algo-basics/amplitude-amplification.md)把"成功概率为 $p$ 的子过程"的重复次数从 $O(1/p)$ 降到 $O(1/\sqrt p)$。

障碍则藏在动态规划的本质里。经典动态规划快，是因为**记忆化 (memoization)**：每个状态只算一次，结果存进一张可随机访问的表，后续查询 $O(1)$。量子算法不能"把整张 $2^n$ 的表免费放进 QRAM 然后直接 Grover"——把一张指数大的表做成可相干查询的内存本身就是一件昂贵的硬件假设（第 9 节详细算这笔账）；而且量子分支在叠加中并行地需要中间结果，"先算后查"的经典流水线没有直接的量子对应。原文采取的可行策略因此是：**只**经典预计算**低层**（顶点数 $2^{H(\alpha)n} \ll 2^n$），量子部分只在少数边界/中点候选上做递归搜索，使得每个子问题的结果**不需要跨分支共享**。这一句话就是全文的设计纲领，第 4 节把它的直觉讲透，第 6 节把它算清。

### 1.4 分工：精确算法与近似量子优化的边界

学生常问：量子优化不是有 QAOA、绝热量子计算吗？为什么还要研究指数时间的精确算法？答案是两者的目标不同。本章其他篇目（如[绝热优化](adiabatic-optimization.md)）与 [QAOA](../ch08-qml/qaoa-tutorial.md) 追求的是**近似解**：解的质量由近似比或能量刻画，运行时间多项式，但一般没有"输出一定是最优解"的保证（绝热方法的严格保证依赖谱隙，而谱隙没有一般的多项式下界）。本教程讨论的则是**精确算法**：输出以有界错误概率保证正确，最坏情形运行时间 $O^*(c^n)$、$c<2$——它回答的是"精确求解到底能有多快"这一复杂度理论问题。两者互补：近似方法面向近期的启发式应用，精确指数算法则划定量子计算在 NP-hard 问题上的能力边界。

## 2. 问题定义：有向超立方体可达性

**定义（超立方体与 Hamming 层）**。$n$ 维超立方体的顶点是所有比特串，即所有子集

$$ S \subseteq [n], $$

共 $2^n$ 个。顶点 $S$ 的**重量 (weight)** 是 $|S|$（比特串中 1 的个数）。第 $j$ **层 (Hamming layer)** 是所有满足 $|S| = j$ 的顶点，共 $\binom nj$ 个。两个顶点相邻当且仅当它们恰好相差一个元素。

**定义（有向边）**。只允许"增加一个元素"的有向边

$$ S \to S\cup\{i\},\qquad i \notin S. $$

于是每条边都从第 $j$ 层指向第 $j+1$ 层，整个图是分层的、无环的。

**定义（PATH 问题，path-in-the-hypercube）**。输入是一个**预言机 (oracle)**：给定 $S \subseteq [n]$，返回 $\operatorname{valid}(S) \in \{0,1\}$，表示该顶点是否被允许。边 $S \to S\cup\{i\}$ 存在当且仅当两端都被允许。任务：判定是否存在一条从 $\varnothing$ 到 $[n]$ 的有向路径

$$ \varnothing = S_0 \to S_1 \to \cdots \to S_n = [n]. $$

由于每条边恰好增加一个元素而 $|S_0| = 0$、$|S_n| = n$，这样的路径自动满足 $|S_k| = k$：它**自下而上穿过每一层**，每层恰过一个顶点。

**输入模型注记**。我们按查询复杂度的惯例把 $\operatorname{valid}$ 当作单位成本的黑盒（量子上是一个相干查询的酉）。在真实应用里 $\operatorname{valid}$ 是一个多项式时间的检查程序（比如"前缀对应的偏序是否一致"），此时每个查询多付 $\operatorname{poly}(n)$，被 $O^*$ 吸收，不影响指数。

(hypercube-path-dp)=
### 2.1 经典动态规划

经典算法对每个 $S$ 计算 $DP[S] \in \{0,1\}$，含义是"存在被允许的单调路径从 $\varnothing$ 到 $S$"。递推为

$$
DP[S]=\operatorname{valid}(S)
\land\bigvee_{i\in S}
(DP[S\setminus\{i\}]\land E_{S\setminus i,S}),
$$

其中 $E_{S\setminus i,S}$ 表示边 $(S\setminus\{i\},S)$ 存在（按定义它等价于两端都合法，这里分开写出是为了强调"顶点合法"与"边存在"是模型中的两个谓词）。初始条件 $DP[\varnothing] = \operatorname{valid}(\varnothing)$。由于 $S \setminus \{i\}$ 的重量比 $S$ 小 1，可以**按 $|S|$ 递增**的顺序填表：算第 $j$ 层时只用到已算好的第 $j-1$ 层，每层的工作量是 $\binom nj \cdot O(n)$。总时间为

$$ \sum_{j=0}^{n} \binom nj \cdot O(n) = O^*(2^n), $$

空间同样是 $O^*(2^n)$。输出 $DP[[n]]$ 即得答案。这就是"经典最佳算法是 $O^*(2^n)$ 动态规划"在本问题上的精确含义。

### 2.2 为什么这个问题抓住了子集 DP 的本质

把第 1.1 节的模板逐项对上：子集 DP 的状态就是超立方体的顶点；"再构建一个元素"的转移就是有向边；合法性检查就是 $\operatorname{valid}$；"存在一条从初始状态到终态的合法转移链"就是单调路径可达性。列成对照表：

| 子集动态规划 | 超立方体语言 |
|---|---|
| 状态（已构建的子集 $S$） | 顶点 $S$，重量 $\lvert S\rvert$ |
| 转移"再构建元素 $i$" | 有向边 $S\to S\cup\{i\}$ |
| 约束检查 | 谓词 $\operatorname{valid}(S)$ |
| 转移链（构建顺序） | 单调路径（每层一个顶点） |
| 一张 $2^n$ 的 DP 表 | 全部 $2^n$ 个顶点的可达性 |

因此 PATH 是子集 DP 的**纯可达性骨架**——它剥离了应用问题里具体的目标函数与辅助信息（那些在第 8 节以 TSP、集合覆盖、带宽的形式回归），只留下"$2^n$ 个状态、每步加一个元素"这一共性。原文的做法是先把加速技术在骨架上做出来（$O^*(1.817^n)$），再把每个应用问题装回这个骨架。

(naive-quantumization-failure)=
## 3. 朴素量子化为什么失败

在动手设计正确算法之前，先弄清楚两个看似自然、实则失效的做法。它们失败的方式恰好指出了正确的方向。

### 3.1 第一次尝试：对前驱做 Grover

定义 $\operatorname{Reach}(v) := DP[v]$，即"存在合法路径 $\varnothing \to v$"。按经典递推，$\operatorname{Reach}(v)$ 可以这样求：在 $v$ 的至多 $|v|$ 个前驱 $\{v\setminus\{i\} : i \in v\}$ 中，用 Grover 搜索一个同时满足"$\operatorname{Reach}$ 为真"和"边存在"的前驱。记 $T(k)$ 为计算重量为 $k$ 的顶点的 $\operatorname{Reach}$ 的成本，则

$$ T(k) \;=\; O(\sqrt{k})\cdot T(k-1),\qquad T(0) = O(1), $$

其中 $O(\sqrt k)$ 是 Grover 的查询次数，每次查询要递归地算一个更小的子问题。展开：

$$ T(n) = \prod_{k=1}^{n} O(\sqrt{k}) \;=\; 2^{\,\frac12\sum_{k=1}^n \log_2 k + O(n)} = 2^{\,\frac12 n\log_2 n + O(n)}, $$

这里用了求和估计 $\sum_{k\le n}\log_2 k = \log_2(n!) = n\log_2 n - O(n)$（Stirling 公式取对数）。也就是说，这个做法的指数是 $\frac12 n \log_2 n$，**比经典 $2^n$ 还差**。原因很简单：每个节点的搜索空间只有 $n$ 个候选，$\sqrt n$ 的折扣弥补不了递归深度的累积。

### 3.2 第二次尝试：对中点做 Grover，递归两半

第二个想法更有希望，也正贴近原文的结构。路径穿过每一层，那么"从 $u$（第 $a$ 层）到 $v$（第 $b$ 层）有路径吗"可以分解为：在中间层找一个**中点** $x$（$u \subset x \subset v$，$|x| = (a+b)/2$），使得两半各自可达。中点候选的个数：$x$ 要从 $v \setminus u$ 的 $r := b - a$ 个元素里选出一半，即

$$ \binom{r}{r/2} \approx \frac{2^r}{\sqrt{\pi r/2}} \qquad\text{（Stirling，见第 5.1 节），} $$

Grover 搜索它们需要 $\sqrt{\binom r{r/2}} \approx 2^{r/2}$ 型的查询次数；每次查询是两个**子区间**问题，各长 $r/2$。于是成本满足递推

$$ T(r) \;=\; 2^{r/2}\cdot 2\cdot T(r/2),\qquad T(1) = O(1). $$

把它逐层展开（第 $\ell$ 层递归的区间长度是 $r/2^\ell$）：

$$ T(r) = \left(\prod_{\ell\ge 1} 2^{\,r/2^\ell}\right)\cdot 2^{O(\log r)} = 2^{\,r\left(\frac12+\frac14+\frac18+\cdots\right)}\cdot \operatorname{poly}(r) = 2^{\,r}\cdot \operatorname{poly}(r), $$

其中几何级数 $\sum_{\ell\ge1} 2^{-\ell} = 1$。**多个递归层的指数相加，加起来正好回到 1**：这个"每层打对折"的递归与经典枚举同阶，一分好处也没有。原文"直接递归 Grover 会形成巨大的重复计算树"这一论断的定量含义就是这一行计算。

### 3.3 病根：量子分支没有共享的 memo 表

对比一下经典动态规划为什么只要 $2^r$。经典算法把区间 $[u,v]$ 内**所有** $2^r$ 个中间状态各算**一次**，存进表里，任何分支查询都是 $O(1)$。而量子递归的每个 Grover 分支都"自备"一次完整的子计算：分支 $x_1$ 算过的东西，分支 $x_2$ 用不了。量子的并行是**叠加**意义上的并行，不是"多核共享内存"意义上的并行；要把一张指数大的表在叠加中读写，需要的正是第 9 节讨论的 QRAM 假设，而那相当于先付清 $2^n$ 的内存。

正确的出路（原文的混合策略）是改变递归的**锚点**：

- 对靠近起点的层**经典预计算并存储**——低层的顶点总数只有 $2^{H(\alpha)n}$，对 $\alpha < 1/2$ 这比 $2^n$ 指数级地少，表便宜得起；
- 量子部分只在更少的**边界/中点候选**上递归搜索，且每次搜索的检查项只依赖"$O(1)$ 大小的证据 + 已算好的表 + 一个自包含的区间子程序"；
- 这样**子问题的结果无需跨分支共享**，3.2 节的重复计算树被拆掉。

## 4. 核心直觉：一条路是"每层一个点"

在进入形式推导之前，用平实的语言把"为什么这样做是对的"讲清楚。

**路是一维的，立方体是 $n$ 维的。** 一条合法路径只包含 $n+1$ 个顶点，每层一个；而动态规划要填满全部 $2^n$ 个格子。经典算法别无选择，因为它的信息单位是"一个格子的值"，而它不知道路径会经过哪些格子。但"路径存在"这个判定问题的**证据**非常短：只要每层报一个顶点就够了。短证据 + 大搜索空间，正是量子搜索的主场。

这里值得停下来澄清一个容易混淆的点：**"证据短"本身并不是量子优势**——经典随机算法同样可以在候选空间里找证据，只是它在 $N$ 个候选中平均翻 $\Theta(N)$ 次，而量子搜索翻 $\Theta(\sqrt N)$ 次。整篇文章的全部量子增益，本质上都来自把"在候选层里找一个见证"这一步换成振幅放大；增益能落到指数上，靠的是把候选层的厚度（熵）与经典表的深度（熵）配平。理解了这一点，后面每一节的复杂度表达式都可以按"哪里在搜、搜多大的层、检查多贵"三问来读。

**中层是漏斗。** 任何完整路径必穿过正中间那层（第 6.2 节给出这个不起眼事实的证明）。于是"整条路存在吗"等价于"中间层里存在一个点 $M$，使得上半段和下半段都各自有路吗"。中间层有 $\binom n{n/2} \approx 2^n/\!\sqrt n$ 个候选，Grover 只需约 $2^{n/2}$ 次检查。朴素地看这似乎直接给出 $2^{n/2} = 1.414^n$——**这个幻想正是原文要纠正的第一个错觉**：单次"检查 $M$"本身就是指数贵的（要验证两半各有路），所以 $2^{n/2}$ 只是查询次数，不是总时间。全部艺术在于把"检查 $M$"做便宜。

**低层便宜，锚住它。** 把检查做便宜的办法是给下半段一个免费的证据来源：第 $\alpha n$ 层以下的所有可达性**事先**经典算好，存成表。低 $\alpha n$ 层的顶点总数是 $\sum_{j\le \alpha n}\binom nj = O^*(2^{H(\alpha)n})$，例如 $\alpha = 1/3$ 时 $H(1/3) \approx 0.918$，比 $2^n$ 省 $2^{0.082n}$ 倍——指数级的节省。于是"下半段有路吗"不再递归，而是"找一个落在表里的证人 $w$"，再用 Grover 搜 $w$。

**上半段照镜子。** 上半段（从 $M$ 到 $[n]$）没有现成的表，但超立方体有一个漂亮的对称：把每个集合换成补集 $S \mapsto [n]\setminus S$，第 $j$ 层变成第 $n-j$ 层，"向上走"变成"向下走"。于是"上半段可达"就是镜像实例的"下半段可达"，可以复用同样的"低层表 + Grover"结构（对高层的可达性再建一张表）。这就是原文"对补集反向问题复用同样结构"的含义。

**平衡两笔账。** 最后，参数 $\alpha$ 不能乱取：表太浅（$\alpha$ 小），中层证人稀疏、搜索变贵；表太深（$\alpha$ 大），经典预计算本身逼近 $2^n$。最优值在两项指数相等的地方——第 6.4 节把这个平衡当成一道显式的方程来解。

## 5. 组合工具：熵、Stirling 与搜索的记账

(entropy-stirling-tools)=
### 5.1 二项式系数的熵标尺

全文反复出现的量是**二元熵函数**

$$
H(\alpha)=-\alpha\log_2\alpha
-(1-\alpha)\log_2(1-\alpha),\qquad \alpha\in(0,1),
$$

约定 $0\log_2 0 = 0$。两条基本性质（后文都用到）：$H$ 在 $[0,\tfrac12]$ 上严格递增、在 $\tfrac12$ 处取最大值 $1$（因为 $H'(\alpha) = \log_2\frac{1-\alpha}{\alpha}$，在 $\alpha < 1/2$ 时为正）；以及对称性 $H(\alpha) = H(1-\alpha)$（定义式中交换 $\alpha$ 与 $1-\alpha$ 不变）。

**引理 1（单层的 Stirling 估计）**。对任意 $0 < \alpha < 1$、$\alpha n$ 为整数，

$$ \binom{n}{\alpha n} = \frac{2^{\,nH(\alpha)}}{\sqrt{2\pi n\,\alpha(1-\alpha)}}\,\bigl(1+O(1/n)\bigr). $$

**证明**。把 Stirling 公式 $m! = \sqrt{2\pi m}\,(m/e)^m\,(1+O(1/m))$ 代入 $\binom n{\alpha n} = \frac{n!}{(\alpha n)!\,((1-\alpha)n)!}$。先看指数上的 $e$：分子有 $e^{-n}$，分母有 $e^{-\alpha n}\,e^{-(1-\alpha)n} = e^{-n}$，恰好抵消。再看 $n$ 的幂：$\frac{n^n}{(\alpha n)^{\alpha n}\,((1-\alpha)n)^{(1-\alpha)n}} = \alpha^{-\alpha n}(1-\alpha)^{-(1-\alpha)n} = 2^{\,nH(\alpha)}$，最后一步就是把 $2$ 为底的对数定义反过来用：$\alpha^{-\alpha n} = 2^{-\alpha n\log_2\alpha}$。剩下的根号因子是 $\frac{\sqrt{2\pi n}}{\sqrt{2\pi\alpha n}\sqrt{2\pi(1-\alpha)n}} = \frac{1}{\sqrt{2\pi n\,\alpha(1-\alpha)}}$。Q.E.D.

**推论（中点搜索的平方根因子）**。把引理 1 用到 $\alpha = 1/2$（根号因子变成 $\sqrt{2/(\pi n)}$）：

$$ \binom{n}{n/2} \approx \frac{2^n}{\sqrt{\pi n/2}}, $$

于是量子搜索第 $n/2$ 层的全部候选需要

$$ \sqrt{\binom n{n/2}} \;\approx\; \frac{2^{\,n/2}}{(\pi n/2)^{1/4}} \;=\; O^*\!\left(2^{\,n/2}\right) $$

次查询。同样的代入给出一般区间的版本（第 3.2 节反复使用的形式）：长度为 $r$ 的区间在其中点层搜索，平方根贡献为

$$ \sqrt{\binom{r}{r/2}} \approx 2^{\,r/2}\cdot\operatorname{poly}(r)^{-1}, $$

即"候选中点数的平方根 $\approx 2^{r/2}$ 型因子"。

**另一个常用估计（半空间内的低层）**：在 $M$ 的 $n/2$ 个元素里选 $\alpha n$ 个，

$$ \binom{n/2}{\alpha n} = \binom{N}{pN}\Big|_{N=n/2,\;p=2\alpha} = 2^{\,\frac n2 H(2\alpha)-O(\log n)}, $$

第二个等号是对 $N = n/2$ 用引理 1（注意 $p = \frac{\alpha n}{n/2} = 2\alpha$，所以只要 $\alpha < 1/2$ 就有 $p<1$）。

**引理 2（低层的总和估计）**。对 $0 < \alpha \le \tfrac12$，

$$ \sum_{j\le\alpha n}\binom nj \;\le\; (\alpha n+1)\cdot 2^{\,nH(\alpha)}. $$

**证明**。固定 $\alpha$，对每个 $j \le \alpha n$，把二项式定理 $(\alpha + (1-\alpha))^n = \sum_k \binom nk \alpha^k(1-\alpha)^{n-k} = 1$ 中的每一项都用来做上界：

$$ 1 \;\ge\; \binom nj\,\alpha^{j}(1-\alpha)^{n-j} \quad\Longrightarrow\quad \binom nj \;\le\; \alpha^{-j}(1-\alpha)^{-(n-j)}. $$

记右边为 $g(j) = (1-\alpha)^{-n}\left(\frac{1-\alpha}{\alpha}\right)^{j}$。由 $\alpha < \tfrac12$ 知 $\frac{1-\alpha}{\alpha} > 1$，故 $g$ 关于 $j$ 递增，从而对一切 $j \le \alpha n$ 有 $g(j) \le g(\alpha n) = \alpha^{-\alpha n}(1-\alpha)^{-(1-\alpha)n} = 2^{\,nH(\alpha)}$。对至多 $\alpha n + 1$ 个 $j$ 求和即得。Q.E.D.

结合引理 1（和式中最大的项就是 $j = \alpha n$ 那项）与引理 2，低层顶点总数夹在 $2^{\,nH(\alpha)-O(\log n)}$ 与 $(\alpha n+1)2^{\,nH(\alpha)}$ 之间，因此"低层表大小是 $\Theta^*(2^{\,H(\alpha)n})$"这个说法是严格的。这正是原文"表大小由二元熵给出"这一断言的依据：

$$
\mathcal L_\alpha=\{S:\ |S|\le \alpha n\},\qquad |\mathcal L_\alpha| = \sum_{j\le\alpha n}\binom nj = O^*\!\left(2^{\,H(\alpha)n}\right).
$$

### 5.2 量子搜索的调用成本

我们需要的形式只有一条：设候选空间大小为 $N$，其中至少有一个（或恰好要判定是否有）命中项，命中判定本身是一个错误概率 $\le \delta$ 的量子子程序，那么整个搜索以错误概率 $O(\delta)$、查询次数 $O(\sqrt N\,\log(1/\delta))$ 完成。这是 [Grover 算法](../ch03-algo-basics/grover.md)与[振幅放大](../ch03-algo-basics/amplitude-amplification.md)的标准结论：$O(\sqrt N)$ 来自 $\sin^2((2T+1)\theta)$ 的旋转图像，$\log(1/\delta)$ 来自把单次成功概率放大到 $1-\delta$ 所需的重复次数。

当搜索**嵌套**（外层搜索的检查函数里含内层搜索）时，用并集界记账：外层做 $Q$ 次检查、每次检查调用至多 $q$ 个内层搜索，则总错误 $\le Q\cdot q\cdot\delta_{\mathrm{in}} + \delta_{\mathrm{out}}$。取 $\delta_{\mathrm{in}} \sim 1/\operatorname{poly}$ 即可让总和为常数，代价是每层多一个多项式因子——全部被 $O^*$ 吸收。原文所说的"$O^*$ 隐藏 $\operatorname{poly}(n)$ 和 bounded-error amplification"就是指这一笔。

## 6. 单层切分：完整算法与推导

本节把第 4 节的直觉落成一个可以逐行验证的算法。为了把机制讲透，我们构造一个**最简版本**：两张经典表、两层 Grover、自包含的经典叶子。它给出 $O^*(1.878^n)$；原文用更多层的不对称切分把它改进到 $O^*(1.817^n)$（第 7 节）。设 $n$ 为偶数、$0 < \alpha < 1/2$，且为简单起见设 $\alpha n$ 为整数（舍入到 $\lfloor \alpha n\rfloor$ 只改变 $o(n)$ 的项，不影响任何指数）。

(two-tables-complement-mirror)=
### 6.1 两张经典表

**下表（从空集出发的可达性）**。对一切 $|S| \le \alpha n$ 计算

$$ R_{\uparrow}(S) := \operatorname{Reach}(\varnothing \to S), $$

递推与第 2.1 节完全相同（按层自下而上），成本 $\sum_{j\le \alpha n}\binom nj\cdot O(n) = O^*(2^{H(\alpha)n})$（引理 2）。

**上表（到全集的可达性）**。对一切 $|S| \ge (1-\alpha)n$ 计算

$$ R_{\downarrow}(S) := \operatorname{Reach}(S \to [n]), $$

递推方向反过来（自上而下）：$R_{\downarrow}([n]) = \operatorname{valid}([n])$，

$$ R_{\downarrow}(S) = \operatorname{valid}(S) \land \bigvee_{i\notin S} R_{\downarrow}(S\cup\{i\}). $$

它的成本同样是 $O^*(2^{H(\alpha)n})$，因为高 $j \ge (1-\alpha)n$ 层的顶点数与低 $n - j \le \alpha n$ 层一样多（$\binom nj = \binom n{n-j}$）。

**补集镜像（引理 3）**。映射 $\iota(S) := [n]\setminus S$ 是超立方体的对合，把第 $j$ 层映到第 $n-j$ 层，且把单调链 $S_0 \subset S_1 \subset \cdots \subset S_k$ 反转成 $\iota(S_k) \subset \cdots \subset \iota(S_0)$。因此，在把合法性谓词换成镜像版本 $\operatorname{valid}'(T) := \operatorname{valid}(\iota(T))$ 之后，"从 $S$ 到 $[n]$ 的可达性"恰好等于"从 $\varnothing$ 到 $\iota(S)$ 的可达性"：$R_{\downarrow}(S) = R'_{\uparrow}(\iota(S))$。证毕只需把路径逐顶点取补。**这就是"对补集反向问题复用同一结构"的全部内容**：上表的构建、上半段的搜索，都是下半段在镜像里的复制品。

### 6.2 每条路径穿过每一层

**引理 4（层次穿过）**。设 $S_0 \to S_1 \to \cdots \to S_n$ 是一条从 $\varnothing$ 到 $[n]$ 的（每步加一元素的）路径，则对每个 $j \in \{0,1,\dots,n\}$ 都有 $|S_j| = j$。特别地，路径在第 $n/2$ 层恰有一个顶点。

**证明**。对 $k$ 归纳：$|S_0| = |\varnothing| = 0$；若 $|S_k| = k$，则 $S_{k+1} = S_k \cup \{i\}$（$i \notin S_k$，否则边不存在）给出 $|S_{k+1}| = k+1$。Q.E.D.

这个"显然"的事实是整个分解合法性的来源：它保证"整段可达"与"在指定层找一个分点使两半可达"是**等价**的命题，而不是单向蕴含。

### 6.3 判定的分解：中层 → 表证人 + 区间叶子

定义两个半程量：$L(M) := \operatorname{Reach}(\varnothing \to M)$，$U(M) := \operatorname{Reach}(M \to [n])$。

**顶层**。由引理 4，

$$ \text{答案为 yes}\quad\Longleftrightarrow\quad \exists M\ (\lvert M\rvert = n/2):\ L(M)\ \land\ U(M). $$

（$\Leftarrow$：把两半在 $M$ 处拼接；$\Rightarrow$：路径的中点就是这样的 $M$。）对第 $n/2$ 层的 $\binom n{n/2} \approx 2^n/\!\sqrt{\pi n/2}$ 个候选做量子搜索（5.2 节），查询次数 $O^*(2^{n/2})$。

**下半段 $L(M)$**。由引理 4（应用于子路径），$L(M)$ 成立当且仅当存在**表证人** $w \subseteq M$、$|w| = \alpha n$，使得 $R_{\uparrow}(w) = 1$ 且 $\operatorname{Reach}(w \to M)$。候选 $w$ 的个数是 $\binom{n/2}{\alpha n}$（在 $M$ 的 $n/2$ 个元素中选 $\alpha n$ 个），由 5.1 节的特例：

$$ \binom{n/2}{\alpha n} = 2^{\,\frac n2 H(2\alpha)-O(\log n)} \quad\Longrightarrow\quad \text{量子搜索需 } O^*\!\left(2^{\,\frac n4 H(2\alpha)}\right) \text{ 次检查}. $$

每次检查 = 一次表查询 $R_{\uparrow}(w)$（$O(1)$，相干 QRAM 访问，第 9 节）+ 一次**区间子程序** $\operatorname{Reach}(w \to M)$。

**上半段 $U(M)$**。由补集镜像（引理 3），这是下半段的镜像复制品：$U(M)$ 成立当且仅当存在 $X \supseteq M$、$|X| = (1-\alpha)n$，使得 $\operatorname{Reach}(M \to X)$ 且 $R_{\downarrow}(X) = 1$。候选个数 $\binom{n/2}{(1/2-\alpha)n} = 2^{\frac n2 H(1-2\alpha)-O(\log n)}$；由熵的对称性 $H(2\alpha) = H(1-2\alpha)$，它与下半段的候选数**完全相同**——上下两半的公式因此合一。

**区间子程序 $\operatorname{Reach}(u \to v)$（叶子）**。对 $u \subseteq v$、间隔 $g := |v|-|u|$，区间 $\{T : u \subseteq T \subseteq v\}$ 是一个 $g$ 维子立方体，有 $2^g$ 个顶点、每顶点至多 $g$ 条出边。经典深度优先搜索判定可达性：时间 $O^*(2^g)$，空间多项式（只需保存栈上的一条部分路径）。注意它**不需要**填满整张区间表——这正呼应 3.3 节的教训：叶子只要"判定"，不要"记忆化"。在本方案里，两处叶子的间隔都是 $g = (1/2-\alpha)n$（从 $\alpha n$ 到 $n/2$，或从 $n/2$ 到 $(1-\alpha)n$）。把它嵌进量子检查函数时，按标准的可逆化处理（计算—不可计算，Bennett 技巧），时间多一个多项式因子、空间仍多项式。

(single-split-balance)=
### 6.4 复杂度汇总与参数平衡

把三层成本相乘（外层搜索的每次查询都要付内层检查的钱）：

$$ \underbrace{2^{n/2}}_{\text{顶层：中层 }M}\ \cdot\ \underbrace{2^{\frac n4 H(2\alpha)}}_{\text{中层：表证人 }w/X}\ \cdot\ \underbrace{2^{(1/2-\alpha)n}}_{\text{叶子：区间 }w\!\to\!M\ \text{或}\ M\!\to\!X} \;=\; 2^{\,\left[\tfrac12+\tfrac14 H(2\alpha)+\tfrac12-\alpha\right]n} = 2^{\,\left[1-\alpha+\tfrac14 H(2\alpha)\right]n}. $$

每个因子的来源：$2^{n/2}$ 是 $\sqrt{\binom n{n/2}}$（顶层 Grover 的查询数）；$2^{\frac n4 H(2\alpha)}$ 是 $\sqrt{\binom{n/2}{\alpha n}}$（证人 Grover 的查询数）；$2^{(1/2-\alpha)n}$ 是间隔为 $(\tfrac12-\alpha)n$ 的区间叶子。加上两张表的经典预计算，总时间为两项的**较大者**（两阶段串行，取最大值即可）：

$$ T(\alpha) \;=\; O^*\!\left(2^{\,E(\alpha)\,n}\right),\qquad E(\alpha) \;=\; \max\left\{\, H(\alpha),\;\; 1-\alpha+\tfrac14 H(2\alpha) \,\right\}. $$

**参数平衡的求解过程**。先看两端：$\alpha \to 1/2$ 时表项 $H(\alpha) \to 1$（表变成整张 $2^n$，荒谬）；$\alpha = 1/4$ 时搜索项 $= 1 - \tfrac14 + \tfrac14 H(\tfrac12) = 1$（因为 $H(1/2) = 1$，两条半程的候选层太厚），也不行。所以最优值在 $(\tfrac14, \tfrac12)$ 内部。逐点数值计算（$H$ 用定义直接求）：

| $\alpha$ | 表项 $H(\alpha)$ | 搜索项 $1-\alpha+\tfrac14 H(2\alpha)$ | $E(\alpha)$ |
|---|---|---|---|
| 0.25 | 0.811 | 1.000 | 1.000 |
| 0.27 | 0.842 | 0.979 | 0.979 |
| 0.30 | 0.881 | 0.943 | 0.943 |
| 0.32 | 0.904 | 0.916 | 0.916 |
| 0.325 | 0.910 | 0.909 | **0.910** |
| 0.33 | 0.915 | 0.901 | 0.915 |
| 0.35 | 0.934 | 0.870 | 0.934 |
| 0.40 | 0.971 | 0.781 | 0.971 |

表格呈 V 形：左半边搜索项主导（$\alpha$ 增大让它下降），右半边表项主导（$\alpha$ 增大让它上升）。最小值在两曲线交点处，即解平衡方程

$$ H(\alpha) \;=\; 1-\alpha+\tfrac14 H(2\alpha). $$

在 $\alpha\in(0.32,0.33)$ 上二分：左端函数 $H(\alpha)-[1-\alpha+\tfrac14H(2\alpha)]$ 在 $0.32$ 处为 $0.904-0.916<0$、在 $0.33$ 处为 $0.915-0.901>0$，故根在两者之间；细化得

$$ \alpha^\ast \approx 0.3245,\qquad E(\alpha^\ast) \approx 0.909,\qquad 2^{\,E(\alpha^\ast)} \approx 1.878. $$

（交叉验证斜率：交点左侧搜索项随 $\alpha$ 每增加 $0.01$ 约降 $0.014$，右侧表项约升 $0.011$，斜率反号，交点确为极小点。）

**定理（简化方案）**。上述"两张表 + 两层搜索 + 经典叶子"的算法以至少 $2/3$ 的成功率判定 PATH，取 $\alpha = \alpha^\ast \approx 0.3245$ 时时间为 $O^*(1.878^n)$，空间为 $O^*(2^{H(\alpha)n})$。

**证明（要点）**。正确性：yes 实例的中点 $M$ 满足 $L\land U$（引理 4），两个半程又各自分解为"表证人 + 区间可达"（引理 4 用于子路径），三层搜索的命中项在 yes 时存在、在 no 时不存在，故 Grover 的输出以 $\ge 2/3$ 概率正确；错误率的完整记账见 6.5 节。时间：即上面的三因子乘积加表预计算，如上取最大。空间：两张表 $2\times O^*(2^{H(\alpha)n})$；量子寄存器为多项式（区间叶子按 DFS 可逆化，多项式空间）。Q.E.D.

**两点诚实的注记**。(1) 这一节是我按原文思路构造的最简可证版本，用于把机制算到底；原文的多层方案（第 7 节）把 $0.909$ 的指数改进到 $\log_2 1.817 \approx 0.862$，差距约 $0.047$，来自对"叶子"和"候选层厚度"的进一步打磨。(2) 表查询按单位成本计——这是 QRAM 假设，第 9 节讨论不买单时的后果。

### 6.5 错误控制的两层账本

嵌套搜索的失败概率值得单独算一遍，因为它说明"多项式开销被 $O^*$ 吸收"不是一句空话。本方案的嵌套结构是：顶层（搜 $M$）的检查函数 $= L(M)\land U(M)$，其中 $L$、$U$ 各是一次第二层搜索（搜 $w$、搜 $X$）；而第二层搜索的谓词 = 表查询 + 经典叶子，两者都是**零错误**的。因此随机性只来自两层 Grover 自身的判决。设放大后单个第二层搜索的错误概率为 $\delta_1$、顶层判决错误为 $\delta_0$，则由并集界（顶层约 $Q_0 = \Theta(2^{n/2})$ 次检查、每次至多两个第二层搜索出错）：

$$ \Pr[\text{输出错误}] \;\le\; \delta_0 + 2\,Q_0\,\delta_1 \;\le\; \delta_0 + 2^{\,\frac n2+2}\,\delta_1. $$

要让右边是常数（如 $1/3$），取 $\delta_1 = 2^{-(n/2+3)}$、$\delta_0 = 1/6$ 即可。把一个常数成功概率的 Grover 搜索放大到错误 $2^{-(n/2+3)}$ 需要 $O(\log 2^{n/2}) = O(n)$ 次重复（每次重复本身是 $O(\sqrt N)$ 查询），因此总时间只乘上多项式因子。这就是 5.2 节记号的兑现：**嵌套层数固定时，错误放大永远只花多项式代价**。原文的多层方案嵌套层数是常数（参数组的个数），所以同样的论证逐层适用。

## 7. 多层不对称切分：从 1.88 到 1.817

第 6 节的方案在两处亏指数：**(i)** 叶子是纯经典的 $2^{(1/2-\alpha)n}$，没有享受任何量子折扣；**(ii)** 证人层的厚度 $H(2\alpha)$ 被"平方根一次"就只用掉了 $\tfrac14 H(2\alpha)$，层内结构没有被继续挖掘。原文的改进正是在这两处继续动刀，做法是**递归地复用整套结构，且各层用互不相同（不对称）的 Hamming 分数**，而不是每次都在正中间对半切：

1. 经典计算低重量层的可达性（同第 6.1 节，但层数与位置由参数组决定）；
2. 对较高层的边界顶点做 amplitude amplification——即对"该顶点是否可达"这一小概率事件用振幅放大，而不是朴素重复；
3. 验证两个边界顶点之间有路时，再引入**中间层**继续切分——把第 6.3 节的"经典叶子"换成一个更薄的量子递归；
4. 对补集反向问题（上半段）复用同样的结构（引理 3 的镜像）。

如此一来，总运行时间的指数是若干项的**最大值**：每项都是"某个经典表的熵项 $H(\cdot)$"或"某层 Grover 的 $\tfrac12$ 系数乘上候选层熵，加上剩余递归段的贡献"，形如

$$
\max\left\{H(\alpha),\ \tfrac12H(\beta)+F(\alpha,\beta),\ \ldots\right\}\cdot n,
$$

其中 $F(\alpha,\beta)$ 表示两个切分点 $\alpha,\beta$ 之间那段递归的成本贡献，省略号代表更多层的不对称切分项。对这些 layer fractions 做数值最小化，原文得到

$$ O^*(1.817^n) \;=\; O^*\!\left(2^{\,0.862\,n}\right) $$

（$0.862 = \log_2 1.817$，纯对数换算）。与第 6 节的 $1.878$ 相比，指数再省 $0.047$；与朴素的"中层一次 Grover 就想拿 $2^{n/2} = 1.414^n$"的幻想相比，它如实地为每次检查付了账。

**必须保留的三条限定**（原文明确强调）：

- 该常数来自对明确写出的 recurrence 的数值优化，不是一句"把 $2^n$ 换成 $1.817^n$"的口号；**任意** $2^n$ 动态规划并不能自动替换成 $1.817^n$——必须能把状态与转移表成超立方体上的单调路径（顶点 = 状态、边 = 转移、合法性可查）；
- $O^*$ 里隐藏着 $\operatorname{poly}(n)$ 因子与 bounded-error amplification 的开销（5.2 节）；
- 表查询按单位成本计（QRAM 假设，第 9 节）。

(np-hard-applications)=
## 8. 从 PATH 到真实 NP-hard 问题

### 8.1 通用配方

把一个子集动态规划装进 PATH 骨架，需要三样东西：**状态集**与超立方体顶点对应（允许附带少量辅助寄存器）；**转移**对应"添加一个元素"的边；**合法性**对应多项式可查的 $\operatorname{valid}$。只要满足，第 6–7 节的分层搜索就能整体搬运。下面逐个看原文给出的应用；**注意每个应用的指数都来自它自己的 recurrence，不能由 1.817 直接代入**（这是原文反复强调的一条纪律）。

### 8.2 顶点排序类问题

**Vertex ordering**：状态 $S$ 是已放在 ordering 前缀的顶点集，transition 添加下一顶点，validity 检查当前宽度/约束。因为状态就是纯子集（没有额外寄存器），这类问题与 PATH 骨架严丝合缝，原文给出**同样**的 $O^*(1.817^n)$。

### 8.3 旅行商问题（TSP）

经典 Held–Karp：状态 $(S, j)$（已访问集合 $S$、当前在城市 $j$），值 $C(S,j)$ 为从城市 1 出发、恰访问 $S$、止于 $j$ 的最短哈密顿路径长：

$$ C(S,j) = \min_{i\in S\setminus\{j\}}\ \bigl[\, C(S\setminus\{j\},\,i) + d_{ij} \,\bigr],\qquad C(\{1,j\},j) = d_{1j}, $$

状态数 $n\cdot 2^n$、转移 $O(n)$，总 $O(n^2 2^n)$（1962 年至今未被超越）。与 PATH 的差别在于**状态还含 endpoint**：量子方案对低层子集预计算 Held–Karp 值，再在中层对 **(子集, 端点) 的组合**做量子搜索。见证的结构值得看清楚：把一条最优环在某条边处断开成两条路径，环经过第 $n/2$ 层时在其中点处的形状是"某个重量 $n/2$ 的集合 $M$ + 当时所在的端点 $j$"；于是"存在最优环"等价于"存在 $(M, j)$，使得从起点访问 $M$ 止于 $j$ 的最优半程与从 $j$ 出发访问 $M$ 的补集回到起点的最优半程可以拼起来"。前半程的最优值由低层表与递归搜索给出，后半程由补集镜像给出（引理 3 在这里再次登场，把"访问剩余城市回到起点"变成一个从 $\varnothing$ 出发的子问题），对 $(M,j)$ 的组合空间做量子搜索，递归结构与第 6–7 节同型，得到 $O^*(1.729^n)$ 型结果。指数比 1.817 更低，是因为端点信息让候选空间变薄、recurrence 更有利；也正因此它是 TSP 自己的 recurrence，不是骨架常数。

### 8.4 最小集合覆盖

宇宙 $[n]$、给定 $m$ 个集合；状态是**已被覆盖的宇宙子集** $T \subseteq [n]$，转移是"再选一个集合、覆盖更多元素"（$T \to T \cup A_i$），共 $2^n$ 个状态。按 $|T|$ 分层后套用同样的"低层表 + 中层量子搜索"，结合对集合选择的不同 partition，原文得到约

$$ O(\operatorname{poly}(m,n)\,1.728^n) $$

的运行时间——注意这里多项式因子写在 $O$ 里而不是 $O^*$ 里，因为 $m$ 与 $n$ 是两个独立参数，原文对 $m$ 的依赖给出了明确的多项式界。

### 8.5 图带宽（graph bandwidth）

给图的顶点找一个线性排列 $\pi$，最小化 $\max_{(u,v)\in E}|\pi(u)-\pi(v)|$。它的动态规划状态是"已排好的前缀集合 + 边界窗口内顶点的位置信息"——辅助信息比 TSP 更多，经典递推约 $4.383^n$；套用分层量子搜索后降到约 $2.946^n$。两个数都明显差于骨架的 $1.817$，原因还是同一条：辅助寄存器加厚了候选层，各应用须各自重做 recurrence 优化。

(qram-space-output)=
## 9. 空间、QRAM 与输出解

### 9.1 空间

两张经典表各 $O^*(2^{H(\alpha)n})$（第 6.4 节，$\alpha^\ast\approx 0.3245$ 时 $2^{0.910n}$——与时间同阶，这是本方案的诚实代价）；量子寄存器多项式。与经典 $O^*(2^n)$ 相比，空间指数同样从 1 降到约 0.91。

### 9.2 QRAM：时间上界成立的条件

量子分支在**叠加**中查询经典表 $R_\uparrow$、$R_\downarrow$：一次查询的地址寄存器处于 $\sum_w c_w|w\rangle$ 之类的态，要求硬件对叠加地址返回叠加结果——这正是 [QRAM / 数据加载](../ch07-quantum-info/data-qram-tutorial.md)讨论的能力。**若实现 QRAM 的每次查询成本不计或为 $\operatorname{poly}(n)$，第 6–7 节的时间上界成立；没有随机访问能力时，表查询本身可能主导运行时间。**说得具体些：如果每次相干查询只能靠在表内做 Grover 搜索（比较地址、命中即翻转）来实现，单次查询成本约为 $\sqrt{2^{H(\alpha)n}} = 2^{0.455n}$，它会作为一个乘性因子叠进 6.4 节的三因子乘积，指数直接爆掉。因此本算法族的时间结论应读作"**在 QRAM（或等价的单位成本相干查表）模型下**"。这是量子算法文献里常见的隐藏账单，本站其他章节（如量子机器学习的数据编码）也反复提醒同一件事。

### 9.3 从判定到输出解

判定存在路径后，按 **self-reduction** 恢复完整路径：把找到的中点 $M$ 固定下来，对两半递归地询问"这一半的下一层分点是谁"，每次询问调用判定程序 $\operatorname{poly}(n)$ 次；整体增加多项式（或对数级的错误放大）开销，不改变指数。注意 **TSP 这类问题的输出解包含 $n$ 个选择**（整条排列），不能只给 yes/no——输出本身就有 $\Omega(n)$ 大小，self-reduction 的逐位恢复是必要的一环，好在每一步都在已付的指数预算之内。

## 10. 小例子：$n=4$ 完整手算

取 $n = 4$，允许的顶点集合为

$$
\varnothing,\ \{1\},\ \{2\},\ \{1,3\},\ \{2,3\},\ \{1,3,4\},\ [4].
$$

超立方体 $Q_4$ 各层大小是 $1,4,6,4,1$（$\binom40,\dots,\binom44$），共 16 个顶点，其中 7 个被允许。边在两集合恰好相差新增一个元素且两端都允许时存在。

**经典做法**是把 16 个 $DP[S]$ 全部算掉。逐层算（$R_\uparrow = DP$，见第 2.1 节递推）：

- 第 0 层：$DP[\varnothing] = \operatorname{valid}(\varnothing) = 1$。
- 第 1 层：$\{1\},\{2\}$ 合法且前驱可达，$DP = 1$；$\{3\},\{4\}$ 不合法，$DP = 0$。
- 第 2 层：$\{1,2\}$ 不合法 $\Rightarrow 0$；$\{1,3\}$ 合法、前驱 $\{1\}$ 可达 $\Rightarrow 1$；$\{1,4\},\{2,4\},\{3,4\}$ 不合法 $\Rightarrow 0$；$\{2,3\}$ 合法、前驱 $\{2\}$ 可达 $\Rightarrow 1$。
- 第 3 层：$\{1,3,4\}$ 合法、前驱 $\{1,3\}$ 可达 $\Rightarrow 1$；$\{1,2,3\},\{1,2,4\},\{2,3,4\}$ 不合法 $\Rightarrow 0$。
- 第 4 层：$[4]$ 合法、前驱 $\{1,3,4\}$ 可达 $\Rightarrow 1$。**答案 yes。**

**分层方案**（第 6 节的结构，取"表 = 前 $\alpha n$ 层"，这里 $\alpha n = 1$）：

- 预计算下表 $R_\uparrow$（第 0、1 层，共 $1+4 = 5$ 个顶点）：$R_\uparrow(\varnothing)=1$，$R_\uparrow(\{1\})=R_\uparrow(\{2\})=1$，$R_\uparrow(\{3\})=R_\uparrow(\{4\})=0$。
- 预计算上表 $R_\downarrow$（第 3、4 层，共 5 个顶点）：$R_\downarrow([4]) = 1$；$R_\downarrow(\{1,3,4\}) = \operatorname{valid}\land R_\downarrow([4]) = 1$；其余第 3 层顶点不合法 $\Rightarrow 0$。
- 顶层：在第 2 层（中层）的 6 个候选里搜 $M$ 使 $L(M)\land U(M)$。逐个检查：
  - $M=\{1,3\}$：下半段——第 1 层、含于 $M$ 的证人候选是 $\{1\}$ 与 $\{3\}$，其中 $R_\uparrow(\{3\})=0$、$R_\uparrow(\{1\})=1$ 且区间 $\{1\}\to\{1,3\}$ 是一条合法边，故 $L=1$；上半段——第 3 层、包含 $M$ 的证人候选 $\{1,2,3\},\{1,3,4\}$ 中只有后者合法，$R_\downarrow(\{1,3,4\})=1$ 且区间 $M\to\{1,3,4\}$ 是合法边，故 $U=1$。**命中。**
  - $M=\{2,3\}$：下半段 $L=1$（证人 $w=\{2\}$）；上半段——包含它的第 3 层顶点 $\{1,2,3\},\{2,3,4\}$ 都不合法，$U=0$。未命中。
  - 其余四个候选 $M$ 本身不合法，直接失败。

  量子搜索的迭代次数可以用 [Grover 教程](../ch03-algo-basics/grover.md)的精确公式核对：$N=6$、命中数 $z=1$，单次命中概率 $p = 1/6$，角度 $\theta = \arcsin\sqrt{p} \approx 0.4205$；$T$ 次迭代后成功率 $P_T = \sin^2((2T+1)\theta)$。代入：$T=0$ 时 $P_0 = 1/6 \approx 0.17$；$T=1$ 时 $P_1 = \sin^2(3\theta) \approx 0.907$；$T=2$ 时 $P_2 = \sin^2(5\theta) \approx 0.743$（转过头了）。理论最优 $T = \frac{\pi}{4\theta}-\frac12 \approx 1.37$，取整到 $T=1$，与逐点计算一致：**一次迭代、约 91% 成功率**，而经典顺序扫描平均要检查 $(6+1)/2 = 3.5$ 个候选。

**恢复路径**：固定 $M=\{1,3\}$、$w=\{1\}$、$X=\{1,3,4\}$，得到

$$ \varnothing\to\{1\}\to\{1,3\}\to\{1,3,4\}\to[4], $$

最后一步新增的是元素 $2$。对比：经典做法填 16 个格子；分层方案查一张 5 项的表、另一张 5 项的表，再检查 6 个中点，每次检查是 $O(1)$ 的查表加一步区间验证——**表小、搜索窄、无需枚举全部 16 个状态**，这正是原文技术在玩具尺度上的样子。

最后一个诚实的注脚：熵标尺在 $n=4$ 处只是宽松的界——低层顶点数 $5$，而 $2^{\,H(1/4)\cdot 4} \approx 2^{3.25} \approx 9.5$；引理 1–2 给出的是**渐近**形状（$n$ 大时 $\sum_{j\le\alpha n}\binom nj$ 与 $2^{H(\alpha)n}$ 只差多项式因子），小例子能展示的是结构，不是常数。

## 11. 小结

- 子集动态规划等价于有向超立方体上的单调路径可达性；经典算法逐层填满 $2^n$ 个状态。
- 直接递归 Grover 之所以失败，是重复计算树（指数逐层相加回 1）加上量子分支无法共享 memo 表；出路是经典预计算低层 + 量子递归搜索中间层，使子问题结果无需跨分支共享。
- 熵项 $H(\alpha)$（表大小）与 Grover 的 $\tfrac12$ 系数（边界搜索）构成一对需要平衡的成本；单层切分的平衡方程解出 $\alpha^\ast\approx0.3245$、指数 $\approx0.909$（约 $1.878^n$），原文的多层不对称切分数值优化到 $O^*(1.817^n) = O^*(2^{0.862n})$。
- TSP（$1.729^n$ 型）、最小集合覆盖（$\operatorname{poly}(m,n)\,1.728^n$）、图带宽（约 $2.946^n$）各需专门的 state/recurrence，指数不能由 1.817 直接代入。
- 时间上界依赖 QRAM 式的单位成本相干查表；输出解靠 self-reduction 恢复，TSP 等问题的输出含 $n$ 个选择，不能只给 yes/no。

## 练习题

**练习 1【子集动态规划的范式与瓶颈】**（→ [1.1 节](#subset-dp-paradigm)）

1. 基础：分别写出 TSP、最小集合覆盖与顶点排序问题在子集动态规划模板下的状态、转移与合法性检查。
2. 进阶：解释为什么任何"逐状态填写"的算法至少付出 $2^n$，并说明"瓶颈不是单个状态的计算量，而是状态本身的个数"这句话对第 1.1 节的三个例子各意味着什么。

**练习 2【PATH 问题与经典递推】**（→ [2.1 节](#hypercube-path-dp)）

1. 基础：写出 PATH 问题的输入模型（$\operatorname{valid}$ 预言机）、有向边规则与判定目标，并解释为什么任何 $\varnothing\to[n]$ 的有向路径自动满足 $|S_k|=k$。
2. 基础：设 $n=3$、允许的顶点为 $\varnothing,\{2\},\{1,2\},\{2,3\},[3]$，按层自下而上填出全部 $8$ 个 $DP[S]$，给出答案并写出全部见证路径。
3. 进阶：对照第 2.2 节的表格，解释"顶点合法"与"边存在"为什么要分成两个谓词建模；再说明当 $\operatorname{valid}$ 是多项式时间的检查程序时，每个查询多付的 $\operatorname{poly}(n)$ 为什么不影响指数。

**练习 3【朴素量子化为什么失败】**（→ [第 3 节](#naive-quantumization-failure)）

1. 基础：解出第一次尝试的递推 $T(k)=O(\sqrt{k})\,T(k-1)$、$T(0)=O(1)$，说明其指数 $\tfrac12 n\log_2 n$ 为什么比经典 $2^n$ 还差。
2. 进阶：完整解出递推 $T(r) = 2\cdot 2^{r/2}\,T(r/2)$、$T(1)=O(1)$，证明 $T(r)=2^{\,r}\operatorname{poly}(r)$；再解释经典动态规划为什么只需 $2^{\,r}$，两者的差别究竟出在递推的哪一项上。

> 提示：第 $\ell$ 层递归有 $2^\ell$ 个长为 $r/2^\ell$ 的子问题，几何级数 $\sum_{\ell\ge1}2^{-\ell}=1$；经典递推里没有"每次查询都要重付一次子计算"的因子。

**练习 4【熵标尺：Stirling 与低层估计】**（→ [5.1 节](#entropy-stirling-tools)）

1. 基础：计算 $H(1/3)$（保留两位小数）；据此用引理 1 与引理 2 估计 $n=6$、$\alpha=1/3$ 时的 $\binom 62$ 与 $\sum_{j\le 2}\binom 6j$，并与精确值比较，评论小 $n$ 处估计的松紧。
2. 进阶：补全第 5.1 节的两个证明：(a) 用 Stirling 公式推出 $\binom n{\alpha n} = 2^{\,nH(\alpha)}/\operatorname{poly}(n)$，写清 $e$ 的幂与 $n$ 的幂各自如何相消；(b) 用二项式加权技巧证明 $\sum_{j\le\alpha n}\binom nj\le(\alpha n+1)\,2^{\,nH(\alpha)}$，并说明为什么需要 $\alpha\le\tfrac12$。

> 提示：(b) 中 $g(j)=(1-\alpha)^{-n}\big(\tfrac{1-\alpha}{\alpha}\big)^{j}$ 的单调方向决定上界在哪一项取到。

**练习 5【两张经典表与补集镜像】**（→ [6.1 节](#two-tables-complement-mirror)）

1. 基础：写出上表 $R_\downarrow$ 的递推与初始条件，并用 $\binom nj=\binom n{n-j}$ 说明它的预计算成本为何同样是 $O^*(2^{H(\alpha)n})$。
2. 进阶：证明补集对合 $S\mapsto[n]\setminus S$ 把"从 $S$ 到 $[n]$ 的可达性"化为镜像实例的"从 $\varnothing$ 出发的可达性"；并验证恒等式 $H(2\alpha)=H(1-2\alpha)$，说明为什么它使第 6 节上下两半的成本公式完全相同。

> 提示：把路径逐顶点取补；对熵的定义式交换 $\alpha$ 与 $1-\alpha$。

**练习 6【单层切分与参数平衡】**（→ [6.4 节](#single-split-balance)）

1. 基础：写出三因子乘积 $2^{n/2}\cdot 2^{\frac n4 H(2\alpha)}\cdot 2^{(1/2-\alpha)n}$ 中每个因子的来源，并解释总时间为何取 $\max\{H(\alpha),\ 1-\alpha+\tfrac14H(2\alpha)\}$ 而不是把表成本与搜索成本相加。
2. 进阶：用二分法解平衡方程 $H(\alpha)=1-\alpha+\tfrac14H(2\alpha)$ 至三位小数，验证 $\alpha^\ast\approx0.325$、$E^\ast\approx0.909$、$2^{E^\ast}\approx1.878$；再换算 $\log_2 1.817\approx0.862$，说明多层切分需要补回的指数差约 $0.047$。
3. 进阶：定性讨论：如果把第 6.3 节的经典叶子换成"再切一层"的量子递归，你预期平衡方程会多出哪些项？

> 提示：新的一项形如"$\tfrac12\times$ 新候选层熵 $+$ 更短剩余区间的贡献"；递归层数固定时，错误放大仍只花多项式代价。

**练习 7【从骨架到真实 NP-hard 问题】**（→ [第 8 节](#np-hard-applications)）

1. 基础：列出把一个子集动态规划装进 PATH 骨架的三个条件；写出 TSP 的 Held–Karp 状态与递推 $C(S,j)$，并说明 $O(n^2 2^n)$ 的来源。
2. 进阶：选一个顶点排序问题（如图带宽或最小线性排列），写出它的子集 DP：状态、转移、validity 各是什么？辅助寄存器（如边界窗口内的位置信息）如何使候选层变厚、从而解释为什么它的量子指数（约 $2.946^n$）明显差于骨架的 $1.817^n$？

> 提示：对照 8.2 节"纯子集状态"与 8.5 节"前缀集合 + 边界窗口位置信息"的差别。

**练习 8【QRAM、空间与输出解的账单】**（→ [第 9 节](#qram-space-output)）

1. 基础：说明分层方案的空间为什么是两张 $O^*(2^{H(\alpha)n})$ 的表、与时间同阶；再解释 self-reduction 如何从判定程序恢复完整路径，开销为何只有多项式。
2. 进阶：设每次对大小 $2^{H(\alpha)n}$ 的表的相干查询必须用表内 Grover 实现（单次约 $2^{H(\alpha)n/2}$），把它代入第 6.4 节的三因子乘积：新的总指数是多少？它是否仍然低于 1？由此说明"时间上界在 QRAM 模型下成立"这句话的分量。

> 提示：乘性因子把 $H(\alpha)/2\approx0.455$ 直接加到搜索项的指数上。

## 参考文献

- Zoo 编号 409：Ambainis、Balodis、Iraids、Kokainis、Prūsis 与 Vihrovs, [Quantum Speedups for Exponential-Time Dynamic Programming Algorithms](https://arxiv.org/abs/1807.05209).