# 量子子集和算法：从折半搜索到 $2^{0.241n}$ 量子行走

给定整数 $x_1,\ldots,x_n$ 与目标值 $s$，**子集和问题 (subset sum problem)** 要求寻找指标集

$$
I\subseteq[n]:=\{1,2,\ldots,n\},\qquad
\sum_{i\in I}x_i=s,
$$

或者判定这样的 $I$ 是否存在。它是 Karp 列出的经典 NP 完全问题之一，因此我们并不期待量子计算把**任意**实例变成多项式时间——本课也不会给出这样的结论。本课研究的是一个更细、也更有实际意义的问题：对一类"随机困难实例"，目前已知的经典指数时间算法的底数大约是多少，量子算法又能把底数压到多少？具体地说，经典启发式算法（Becker–Coron–Joux）把底数降到约 $2^{0.291n}$，而 Bernstein、Jeffery、Lange、Meurer 的量子算法在同一类启发式假设下达到

$$
\widetilde O\!\left(2^{0.241n}\right),
$$

其中 $\widetilde O(\cdot)$ 表示忽略 $n$ 的多项式因子（这是指数时间算法文献的标准记号，因为底数才是竞争的主战场）。

值得强调的是，这个加速**不是**"对一切子集做 Grover"能得到的。正如我们将看到的，朴素 Grover 给出的 $2^{n/2}$ 甚至追不上 1974 年的经典折半搜索。真正的答案是把四种成分组合起来：**多重表示 (multiple representations)**、**模约束筛选 (modular filtering)**、**Johnson 图上的量子行走**、以及**可相干更新的数据结构**。本课的目标是把这四种成分逐一讲清楚，并完整复现 $0.241$ 这个指数的平衡计算。

**前置知识**：读者应已完成本站的 [Grover 算法](../ch03-algo-basics/grover.md)与[振幅放大](../ch03-algo-basics/amplitude-amplification.md)，并对[量子行走](../ch06-scientific-computing/quantum-walk-tutorial.md)与[碰撞/元素不同性搜索](../ch11-query-complexity/collision-element-distinctness.md)有基本了解。本课不会重新推导这些工具，但会在用到时指出每一步引用了哪个结论。

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

1. **[密度与困难随机实例](#subset-sum-density)**——能写出密度 $d=n/m$ 的定义并推导期望解数估计 $\frac{2^{n-m}}{n}$，解释密度接近 $1$ 的承诺可解随机实例为何处于最困难区域。
2. **[折半搜索与朴素 Grover 的平局](#meet-in-the-middle)**——能构造左右两张表把子集和化为碰撞查找，写出折半搜索的时间与空间 $\widetilde O(2^{n/2})$，并解释朴素 Grover 为何只能追平而不能超过它。
3. **[量子不平衡折半](#unbalanced-mitm)**——能用参数 $\lambda$ 建立成本模型 $T(\lambda)=\widetilde O(2^{\lambda n}+2^{(1-\lambda)n/2})$，推导平衡点 $\lambda=\frac13$ 与总复杂度 $\widetilde O(2^{n/3})$。
4. **[Johnson 图量子行走](#johnson-graph-walk)**——能定义 Johnson 图 $J(N,r)$ 与标记顶点，推导标记占比 $\epsilon\approx(r/N)^2$ 与谱隙 $\delta=\Theta(1/r)$。
5. **[行走搜索的代价公式与平衡](#walk-cost-formula)**——能由步数公式 $O(1/\sqrt{\delta\epsilon})$ 推出总查询成本 $r+\frac{N}{\sqrt r}$，并平衡得 $r=N^{2/3}$、复杂度 $\widetilde O(2^{n/3})$。
6. **[可相干更新的数据结构](#coherent-data-structure)**——能区分查询复杂度与时间复杂度，解释可逆 radix tree 为何把每步行走的更新成本控制在 $\operatorname{poly}(n)$，而排序数组方案会毁掉查询优势。
7. **[多重表示与模约束筛选](#multiple-representations)**——能计算一个解的二分表示数 $\binom{n/2}{n/4}=2^{(1/2+o(1))n}$，并解释模约束如何按 $1/M$ 的比例筛掉候选、控制中间列表的大小。
8. **[16 叶量子行走的 0.241 指数](#leaf-walk-balance)**——能由 $\log_2 B\approx 0.271n$、$\epsilon=(r/B)^8$、$\delta=\Theta(1/r)$ 推导平衡点 $r=B^{8/9}$ 与启发式指数 $2^{0.241n}$。

:::

## 1. 问题背景：密度、困难实例与历史

(subset-sum-density)=
### 1.1 密度与"困难背包"

子集和实例的难易程度用一个无量纲参数刻画。设所有 $x_i$ 都是约 $m$ 比特的整数（即 $x_i < 2^m$），定义实例的**密度 (density)** 为

$$
d:=\frac{n}{m}.
$$

直觉如下：所有子集和的取值落在区间 $[0,\, n\cdot 2^m]$ 内，该区间的长度约为 $n\,2^m$；而子集共有 $2^n$ 个。由抽屉原理，一个"典型"目标值 $s$ 的期望解数约为

$$
\frac{2^n}{n\,2^m}=\frac{2^{n-m}}{n}.
$$

- 当 $d<1$（即 $m>n$，数字比个数"长"）时，$n-m<0$，上面的估计失效；实际上此时子集和撞在同一个值上的机会很多，解通常很多，随机找一个解反而容易。
- 当 $d>1$（即 $m<n$）时，期望解数指数级小：随机取的 $s$ 多半无解，而一旦承诺有解，解往往唯一。

密度接近 $1$ 的实例处在两种 regime 的交界处：解的数量是常数级的（不多不少），任何"碰运气"的策略都没有可乘之机。这正是公认的最困难区域，也是密码学与指数算法文献重点研究的对象。本课涉及的**困难随机实例**就是指：$x_i$ 与 $s$ 取为约 $n$ 比特的整数（即 $m\approx n$、$d\approx 1$），并承诺至少存在一个解（典型地，解的数量为常数级，目标解的权重 $|I|$ 接近 $n/2$——这是随机解的最大似然权重，因为 $\binom{n}{n/2}$ 是所有 $\binom{n}{k}$ 中最大的）。

### 1.2 为什么这个问题重要

- **理论地位**：子集和是 NP 完全问题中最"干净"的一个——输入只有一行整数。它是检验"量子计算对 NP 完全问题到底能加速多少"这一问题的试金石：目前的证据都指向"最多加速指数底数，而不能去除指数"。
- **密码学动机**：早期的背包公钥密码体制（Merkle–Hellman 等）直接建立在子集和的困难性之上；虽然那些具体体制已被攻破，"随机背包有多难"至今仍是衡量格密码与编码类密码安全余量的参照系之一。
- **算法史**：子集和是指数时间精确算法发展的一条主线。本课涉及的里程碑有：
  - 穷举搜索：$O^{*}(2^n)$（$O^{*}$ 同样表示忽略多项式因子）；
  - Horowitz–Sahni 折半搜索（1974）：时间与空间 $\widetilde O(2^{n/2})$；
  - Schroeppel–Shamir（1981）：时间仍为 $\widetilde O(2^{n/2})$，但空间降到 $\widetilde O(2^{n/4})$——它提示我们**内存**往往是这类算法的真正瓶颈；
  - Howgrave-Graham–Joux（2010）提出 **representation technique**（多重表示技术），把随机困难实例的启发式时间指数降到明显低于折半的 $1/2$；
  - Becker–Coron–Joux（2011）用更精细的重叠表示把经典启发式指数降到约 $2^{0.291n}$；
  - Bernstein–Jeffery–Lange–Meurer（2013）把多重表示与量子行走结合，给出启发式 $\widetilde O(2^{0.241n})$，这正是本课的主线（对应文末 Zoo 编号 178）。

### 1.3 本课路线图

我们将按指数从大到小的顺序，依次讲透四个层次：

1. 为什么朴素 Grover 的 $2^{n/2}$ 没有超过经典折半（第 2 节）；
2. 量子不平衡折半如何把指数降到 $1/3$（第 3 节）；
3. Johnson 图量子行走如何独立地达到同一个 $1/3$，以及它引入的数据结构问题（第 4 节）；
4. 多重表示 + 16 叶量子行走如何把指数进一步压到 $0.241$，以及这个结论附带哪些"启发式与模型依赖"的保留条款（第 5–7 节）。

## 2. 经典基线：穷举、折半与朴素 Grover 的失败

(meet-in-the-middle)=
### 2.1 穷举与折半搜索

穷举所有 $2^n$ 个子集需要 $\Theta(2^n)$ 次求和，这是底数 $2$ 的起点。

**折半搜索 (meet-in-the-middle)** 把指标集任意分成大小各 $n/2$ 的左右两半 $[n]=L\mathbin{\dot\cup}R$（$\dot\cup$ 表示无交并）。对任意子集 $I\subseteq[n]$，记 $I_L=I\cap L$、$I_R=I\cap R$，则

$$
\sum_{i\in I}x_i=s
\quad\Longleftrightarrow\quad
\sum_{i\in I_L}x_i=s-\sum_{i\in I_R}x_i.
$$

也就是说：$I$ 是解，当且仅当"左半部分的子集和"与"$s$ 减去右半部分的子集和"在数值上相等。这提示我们构造两张表

$$
\mathcal L=\left\{\sum_{i\in J}x_i:\ J\subseteq L\right\},
\qquad
\mathcal R=\left\{s-\sum_{i\in K}x_i:\ K\subseteq R\right\},
$$

然后在两张表之间寻找**碰撞 (collision)**——即同时出现在 $\mathcal L$ 与 $\mathcal R$ 中的数值。每张表有 $2^{n/2}$ 项。具体的实现是：生成两张表（$O(2^{n/2})$ 次求和），把 $\mathcal L$ 排序（$\widetilde O(2^{n/2})$ 次比较），再对 $\mathcal R$ 的每一项在 $\mathcal L$ 中做二分查找（$2^{n/2}$ 次查找、每次 $O(n)$）。总时间与总空间都是

$$
\widetilde O\!\left(2^{n/2}\right).
$$

相对穷举，底数从 $2$ 降到了 $\sqrt 2\approx 1.414$。注意这个算法的本质是**用空间换时间**：两张表各占 $2^{n/2}$ 个存储单元，这正是 Schroeppel–Shamir 后来专门优化内存的原因。第 8 节会给出一个可以手工执行的小例子。

### 2.2 为什么朴素 Grover 追不上经典

学完 Grover 算法后的第一反应是：把 $2^n$ 个子集看作搜索空间，用预言机标记"和等于 $s$"的子集，迭代 $\frac{\pi}{4}\sqrt{2^n}$ 次，得到时间

$$
\widetilde O\!\left(2^{n/2}\right).
$$

但这与 Horowitz–Sahni 的经典折半**完全相同**，而经典算法早在 1974 年就有了。换句话说：Grover 提供的平方根加速，恰好等于"把问题分成两半再用平方倍的存储"这一经典技巧的收益，两者撞在同一条指数曲线上。要想真正超过经典，必须找到一种"经典算法已经榨干了平方根、但量子还能再榨一次"的结构。下面两节给出两条这样的路线。

## 3. 量子路线一：不平衡折半搜索

### 3.1 关键观察：折半的"一半"与 Grover 的"平方根"不能叠加在表小的一侧

折半搜索中，左右两半各贡献 $2^{n/2}$ 的表。如果直接对"右半表中的匹配项"做 Grover，搜索空间是 $2^{n/2}$，开平方得 $2^{n/4}$——看似巨大改进，但**左半表本身要花 $2^{n/2}$ 的时间建立**，总时间仍是 $2^{n/2}$。表太大，把 Grover 的收益吃掉了。

出路是**不对称**：让需要显式建表的一侧小一些，让只做相干搜索的一侧大一些，使"建表成本"与"搜索成本"在指数上相等。

(unbalanced-mitm)=
### 3.2 参数化与平衡推导

引入参数 $\lambda\in(0,1)$：取前 $\lambda n$ 个元素为"左半"（显式建表），剩下 $(1-\lambda)n$ 个元素为"右半"（相干搜索）。

- **建表成本**：左半有 $2^{\lambda n}$ 个子集，枚举其和并排序，成本为 $\widetilde O(2^{\lambda n})$。排序后的表支持 $O(n)$ 时间的成员查询——暂不计模型问题（见 3.3 与第 7 节）。
- **搜索成本**：对右半的 $2^{(1-\lambda)n}$ 个子集做 Grover 搜索，标记条件是"$s$ 减去该子集的和，出现在左半表中"。搜索空间大小为 $2^{(1-\lambda)n}$，解的数量为常数级（密度 1 的困难实例，见 1.1），故 Grover 迭代次数为

$$
\widetilde O\!\left(\sqrt{2^{(1-\lambda)n}}\right)=\widetilde O\!\left(2^{(1-\lambda)n/2}\right),
$$

每次迭代的预言机查询是一次对左半表的成员判定，多项式开销被吸收进 $\widetilde O$。

总成本为两项之和：

$$
T(\lambda)=\widetilde O\!\left(2^{\lambda n}+2^{(1-\lambda)n/2}\right).
$$

渐近意义下，和式由指数较大的一项主导，所以要最小化的是

$$
\max\left\{\lambda,\ \frac{1-\lambda}{2}\right\}.
$$

第一项随 $\lambda$ 递增，第二项随 $\lambda$ 递减；一个递增函数与一个递减函数的最大值，在两者**相等**时取到最小（若 $\lambda$ 比交点小，则第二项更大且随 $\lambda$ 减小而减小，说明还能改进；对称地，$\lambda$ 比交点大时第一项主导且仍可减小）。令

$$
\lambda=\frac{1-\lambda}{2}
\quad\Longrightarrow\quad
2\lambda=1-\lambda
\quad\Longrightarrow\quad
3\lambda=1
\quad\Longrightarrow\quad
\lambda=\frac13.
$$

代回即得建表成本与搜索成本同为 $\widetilde O(2^{n/3})$，因此总时间与总内存为

$$
\widetilde O\!\left(2^{n/3}\right).
$$

具体写出来：预计算前 $n/3$ 个元素的 $2^{n/3}$ 个和并排序；再对余下 $2n/3$ 个元素的 $2^{2n/3}$ 个子集做 Grover，搜索域大小的平方根是 $\sqrt{2^{2n/3}}=2^{n/3}$，恰好与表的大小相等。这就是"不平衡"二字的由来：经典折半的最优划分是 $1/2$ 对 $1/2$，而"建表 + Grover"的最优划分是 $1/3$ 对 $2/3$。

### 3.3 一个埋下的伏笔

上面的分析把"对排序表的成员查询"计为多项式开销。在经典 RAM 里这毫无问题；但在量子线路里，Grover 迭代的每一步都要对**叠加态中的地址**做查询，即需要相干地实现

$$
\sum_{j}\alpha_j\,|j\rangle|0\rangle\ \longmapsto\ \sum_{j}\alpha_j\,|j\rangle|\,\mathcal L[j]\rangle,
$$

也就是一个**量子随机访问存储 (QRAM)** 操作。对大小为 $2^{n/3}$ 的表，这是否真的只需 $\operatorname{poly}(n)$ 个基本门，是一个很强的模型假设。这个伏笔将在第 4 节的数据结构讨论和第 7 节的保留条款中反复出现，请务必带着它往下读。

## 4. 量子路线二：Johnson 图量子行走

不平衡折半给出的 $2^{n/3}$ 还可以从另一条看似完全不同的路线得到：把折半的碰撞寻找问题直接翻译成[碰撞搜索](../ch11-query-complexity/collision-element-distinctness.md)，用 **Johnson 图上的量子行走**求解。这条路线本身指数相同，但它引入的"行走 + 数据结构"框架正是通往 $0.241$ 的必经之路。

### 4.1 从折半到碰撞问题

回到第 2 节的两张表：左半表 $\mathcal L$ 与右半表 $\mathcal R$ 各有 $N:=2^{n/2}$ 项，算法要找一个数值同时出现在两表中。抽象地说：候选全集大小为 $N$，其中存在一个（或极少数）**目标配对**——左表中的某个和与右表中的某个和相等——我们要把这一对找出来。

(johnson-graph-walk)=
### 4.2 Johnson 图与行走状态

**Johnson 图 (Johnson graph)** $J(N,r)$ 的定义：顶点是一个 $N$ 元全集的所有 $r$ 元子集，两个顶点相邻当且仅当它们恰相差一个元素（即把一个元素换成另一个元素）。量子行走的状态对应"当前持有 $r$ 个候选及其和"，一步行走对应"替换其中一个候选"。

称一个顶点是**标记的 (marked)**，如果它持有的 $r$ 个候选中**同时包含目标配对的两个元素**——此时通过检查手中的数据就能发现碰撞（见 4.5）。

**标记顶点占比**：随机一个 $r$ 元子集同时包含两个指定元素的概率为

$$
\epsilon=\frac{\binom{N-2}{r-2}}{\binom{N}{r}}
=\frac{(N-2)!\,r!\,(N-r)!}{(r-2)!\,(N-r)!\,N!}
=\frac{r(r-1)}{N(N-1)}
\approx\left(\frac{r}{N}\right)^2,
$$

最后一步用到了 $r\ll N$（下文将看到 $r=N^{2/3}\ll N$），因此 $r-1\approx r$、$N-1\approx N$。注意 $\epsilon$ 是**平方**关系：因为需要"两个都中"。

**谱隙**：Johnson 图 $J(N,r)$ 上简单随机行走的谱隙为

$$
\delta=\Theta\!\left(\frac1r\right)
$$

（这是 Johnson 图的标准谱性质；直观地说，一步只换掉 $r$ 个元素中的一个，因此需要 $\Theta(r)$ 步才能让状态"忘记"初始持有的元素，混合时间就是 $\Theta(r)$ 量级，谱隙是其倒数）。

(walk-cost-formula)=
### 4.3 Szegedy/Ambainis 搜索的代价公式

量子行走搜索（Szegedy 框架，以及 Ambainis 为元素不同性问题发展的版本，Zoo 编号 7）告诉我们：在"谱隙 $\delta$、标记占比 $\epsilon$"的图上检测一个标记顶点，所需的行走步数尺度为

$$
O\!\left(\frac{1}{\sqrt{\delta\epsilon}}\right),
$$

外加一次性**设置成本 (setup cost)**——把初始的 $r$ 个候选装入数据结构，需要 $r$ 次查询。若每步行走的**更新成本 (update cost)** 与每次的**检查成本 (checking cost)** 都是 $O(1)$ 次查询（这一点要靠 4.5 的数据结构保证），总查询复杂度为

$$
r+\frac{1}{\sqrt{\delta\epsilon}}
\;\sim\;
r+\frac{1}{\sqrt{\frac1r\cdot\frac{r^2}{N^2}}}
\;=\;
r+\frac{N}{\sqrt r},
$$

其中代入 $\delta=\Theta(1/r)$ 与 $\epsilon\approx(r/N)^2$ 后，根号内的 $r$ 因子相约：$\frac{1}{r}\cdot\frac{r^2}{N^2}=\frac{r}{N^2}$，开方得 $\frac{\sqrt r}{N}$，取倒数即 $\frac{N}{\sqrt r}$。

### 4.4 参数平衡：$r=N^{2/3}$ 的来源

最小化 $f(r)=r+N\,r^{-1/2}$。两项分别是增函数与减函数，最优点在两项同阶处（也可以严格求导：$f'(r)=1-\frac12 N r^{-3/2}=0$ 给出 $r^{3/2}=N/2$，与下同阶）。令

$$
r=\frac{N}{\sqrt r}
\quad\Longrightarrow\quad
r^{3/2}=N
\quad\Longrightarrow\quad
r=N^{2/3}.
$$

代回：两项均为 $N^{2/3}$。由 $N=2^{n/2}$，

$$
N^{2/3}=2^{n/3},
$$

即总查询复杂度 $\widetilde O(2^{n/3})$——与不平衡折半殊途同归。

(coherent-data-structure)=
### 4.5 数据结构：查询复杂度不等于时间

这次平衡与[矩阵乘积验证](matrix-product-verification.md)中的情形非常相似，但有一个本质区别必须讲透：上面的计数是**查询复杂度**，它假设"替换一个候选、查询其和、检查手中是否出现碰撞"都只要 $O(1)$。要把它变成真实的**时间复杂度**，行走状态必须由真正的数据结构承载，且该结构要在**相干叠加**下支持四种操作：

1. 成员查询（某个和是否已在手中）；
2. 插入一个新候选；
3. 删除一个旧候选；
4. 回答"当前手中是否已出现目标碰撞"。

为什么朴素方案不行？若用排序数组存储 $r$ 个候选，一次插入/删除要移动 $\Theta(r)$ 个表项，更新成本从 $O(1)$ 变成 $\Theta(r)$；总时间变成 $r\cdot(\text{步数})$，即 $r\cdot\frac{N}{\sqrt r}=\sqrt r\,N$，代入 $r=N^{2/3}$ 得 $N^{7/6}$——比穷举还差。**门时间会彻底毁掉查询优势。**

Bernstein 等人的解法是使用**带子树计数的可逆 radix tree**：把候选按其和的二进制前缀组织成检索树，每个内部节点记录子树中的元素个数。成员查询、插入、删除都只需沿树走 $O(\log)$ 层，而"子树计数"使碰撞标志（例如两个指定数值是否同时出现）可以在插入/删除时沿路径增量维护。所有操作都可以做成可逆线路，每次更新的开销为 $\operatorname{poly}(n)$，从而

$$
\text{总时间}=\widetilde O\!\left(r+\frac{N}{\sqrt r}\right)=\widetilde O\!\left(2^{n/3}\right).
$$

但请注意代价：这隐含假设了对一个**大小为 $2^{n/3}$ 的指数级数据结构**可以做相干（叠加地址）读写，且每次访问只计 $\operatorname{poly}(n)$。这就是 3.3 埋下的伏笔在行走框架中的再现——一个 QRAM 风格的强模型假设，第 7 节会正式把它列为保留条款。

## 5. 多重表示：为什么指数还能继续降

前两节的 $2^{n/3}$ 有一个令人不安的事实：它**高于**最佳经典启发式指数 $0.291$（Becker–Coron–Joux）。也就是说，仅把"折半 + 碰撞"量子化，反而不如最好的经典算法。要真正领先，必须把经典算法领先的原因——多重表示——也搬进量子行走。

(multiple-representations)=
### 5.1 一个解有许多张"彩票"

设目标解 $I$ 的权重为 $|I|=n/2$（见 1.1，这是随机解的典型权重）。把它拆成两个无交的半解

$$
I=I_1\mathbin{\dot\cup}I_2,
\qquad |I_1|=|I_2|=n/4.
$$

这样的**有序**拆分有多少种？答案是从 $I$ 的 $n/2$ 个元素中选出 $n/4$ 个给 $I_1$：

$$
\binom{n/2}{n/4}=2^{(1/2+o(1))n},
$$

其中指数由二元熵公式给出（推导见第 6.1 节的同款计算）：$\frac1n\log_2\binom{n/2}{n/4}\to\frac12 H(1/2)=\frac12$。也就是说，**同一个解有指数多种表示**。每一种表示都是一张独立的"彩票"：只要算法碰巧重构出其中任何一种拆分，就恢复了整个解。

### 5.2 模约束：让列表保持苗条的筛子

多重表示本身不直接省时间——表示虽多，每种表示的候选空间也大。Howgrave-Graham–Joux 的 **representation technique** 的关键是把"多表示"与"随机模约束"配对使用。以第一层为例：不直接要求

$$
\Sigma(I_1)+\Sigma(I_2)=s
$$

（$\Sigma(J):=\sum_{i\in J}x_i$ 是子集和的简记），而是先只施加一个较弱的同余条件

$$
\Sigma(I_1)+\Sigma(I_2)\equiv s\pmod{M_1},
$$

其中 $M_1$ 是一个精心选取的模数。效果是一个**筛子**：随机一对候选的和在模 $M_1$ 下近似均匀分布，所以只有约 $1/M_1$ 比例的候选对能通过这层约束——中间列表的长度被压缩到"候选数乘积再除以 $M_1$"。通过约束的对再往上合并，施加更高层的模 $M$ 条件，直到最后一层才检查精确的整数等式。

于是形成一场精妙的拉锯：**模筛选**按 $1/M_1$ 的比例淘汰候选，让每个中间列表保持较小；而**多重表示**提供 $\binom{n/2}{n/4}$ 张彩票，提高"至少一种拆分恰好通过所有随机约束"的概率。只要每层模数取得与列表大小相协调，就能做到"列表不爆炸、彩票不浪费"。这就是 Howgrave-Graham–Joux 的 representation technique 的核心思想。

### 5.3 更深的树与历史

把上述二分递归下去：$I_1,I_2$ 各自再二分，层层施加模约束，最终形成 $16$ 个大小约 $n/16$ 的**叶块 (leaf blocks)**（配合 Becker–Coron–Joux 式的重叠表示，叶块之间允许共享元素，因此叶块总大小可以超过解的支集本身——这正是"重叠"二字的含义，也是表示数进一步增大的来源）。

- Howgrave-Graham–Joux（2010）首次系统使用这一技术，把随机困难背包的启发式指数降到明显低于折半的 $1/2$；
- Becker–Coron–Joux（2011，Zoo 编号 404）通过更精细的重叠表示把经典启发式指数降到约

$$
2^{0.291n}.
$$

### 5.4 量子化不是"对经典程序整体做 Grover"

一个自然的想法是：BCJ 程序内部是一系列列表构造，能不能直接把它当作经典子程序、外层套一个 Grover？答案是否定的，原因有二。其一，BCJ 程序的运行时间已经是 $2^{0.291n}$，把它作为黑盒做振幅放大只会得到 $\sqrt{2^{0.291n}}=2^{0.146n}$ 次"调用"、但每次调用本身仍是 $2^{0.291n}$——平方根作用在错误的对象上（何况该程序内部还有不可逆的列表排序与碰撞筛选，不能直接相干化）。其二，真正的收益在于更细的操作：**把 16 个叶列表本身放进量子行走的状态**，让"替换一个叶元素"只触发上层碰撞列表的**局部更新**——这正是第 4 节"行走 + 可增量维护的数据结构"框架的用武之地。下一节给出完整的平衡计算。

## 6. 16 叶量子行走与 $0.241$ 指数的平衡

### 6.1 单个叶块的候选空间

每个叶块从约 $n/2$ 个可用位置中选取 $n/16$ 个元素（"约 $n/2$ 个可用位置"来自重叠表示的随机化分解：每个叶块可以在整个支集池中取样，见 5.3）。因此一个叶块的完整候选数为

$$
B=\binom{n/2}{n/16}.
$$

用 Stirling 公式把它化成指数形式。回忆 $\log_2 m!=m\log_2 m-(\log_2 e)m+O(\log m)$，对 $\binom{N}{K}=\frac{N!}{K!(N-K)!}$ 逐项展开：

$$
\log_2\binom{N}{K}
=N\log_2 N-K\log_2 K-(N-K)\log_2(N-K)+O(\log N)
=N\,H\!\left(\frac KN\right)+O(\log N),
$$

其中

$$
H(p):=-p\log_2 p-(1-p)\log_2(1-p)
$$

是二元熵函数。取 $N=n/2$、$K=n/16$（故 $K/N=1/8$）：

$$
\frac1n\log_2 B\;\longrightarrow\;\frac12\,H\!\left(\frac18\right).
$$

数值计算（本课把每一步都算出来）：

$$
-\tfrac18\log_2\tfrac18=\tfrac18\cdot 3=0.375,
\qquad
-\tfrac78\log_2\tfrac78=\tfrac78\log_2\tfrac87\approx 0.875\times 0.1926\approx 0.1686,
$$

两者相加得 $H(1/8)\approx 0.5436$，再乘 $\frac12$：

$$
\log_2 B=(0.271\ldots+o(1))\,n.
$$

### 6.2 行走状态与设置成本

量子行走在 Johnson 图式的产品空间上进行，状态持有 **8 个叶列表**，每个列表保留 $r$ 个随机抽出的叶块候选（论文的具体构造把 16 叶分解树的最底一层合并进列表元素与预处理；对复杂度分析而言，关键数字只有两个——单个叶列表的候选空间 $B$，以及需要同时命中的列表个数 8）。除叶列表外，状态还携带由分解树内部节点与模约束层派生出的 **21 个碰撞列表**（具体层次安排见原文）；由于列表总数是常数，建立全部 8 个叶列表及其 21 个派生列表的设置成本为

$$
\widetilde O(r).
$$

借助第 4.5 节的可逆 radix tree，一次行走步（替换某个叶列表中的一个元素、并沿分解树增量更新受影响的派生列表）只需 $\operatorname{poly}(n)$ 开销。

### 6.3 标记占比与行走步数

一个顶点（即一组 8 个叶列表的当前内容）是标记的，当且仅当它能拼出完整的目标解。固定目标解后，它在每个叶列表中对应一个**指定的叶块**；8 个叶列表各自独立地以约 $r/B$ 的概率抽中自己的指定叶块，故 8 个指定叶块同时被抽中的概率约为

$$
\epsilon\approx\left(\frac rB\right)^{8}.
$$

行走的谱隙仍为 Johnson 图的 $\delta=\Theta(1/r)$（一步只替换一个叶元素）。套用第 4.3 节的步数公式：

$$
\frac{1}{\sqrt{\delta\epsilon}}
=\frac{1}{\sqrt{\frac1r\left(\frac rB\right)^8}}
=\frac{1}{\sqrt{\frac{r^7}{B^8}}}
=\frac{B^4}{r^{7/2}}
=\sqrt r\left(\frac Br\right)^{4}.
$$

恢复一个完整解（用振幅放大把标记概率从 $\epsilon$ 提升到常数）所需的行走步数即为此量级。注意这个表达式里两个因子的来源泾渭分明：$\sqrt r$ 来自谱隙（状态混合的代价），$(B/r)^4$ 来自 $\epsilon^{-1/2}$（八重巧合的代价）。

(leaf-walk-balance)=
### 6.4 最终平衡

总成本为设置成本与行走成本之和：

$$
T(r)=\widetilde O\!\left(r+\sqrt r\left(\frac Br\right)^{4}\right).
$$

令两项同阶（增项与降项的最优平衡，与 3.2、4.4 同理）：

$$
r=\sqrt r\left(\frac Br\right)^4
\quad\Longrightarrow\quad
\sqrt r=\frac{B^4}{r^4}
\quad\Longrightarrow\quad
r^{1/2}\,r^{4}=B^4
\quad\Longrightarrow\quad
r^{9/2}=B^4
\quad\Longrightarrow\quad
r=B^{4/4.5}=B^{8/9}.
$$

代入 $\log_2 B\approx 0.271\,n$：

$$
\log_2 r\approx\frac89\times 0.271\,n,
\qquad
\frac89\times 0.271=\frac{2.168}{9}\approx 0.241.
$$

因此 16 叶量子行走的启发式渐近成本为

$$
\widetilde O\!\left(2^{0.241n}\right)
$$

个量子比特操作。作为对照：经典最佳启发式为 $2^{0.291n}$（Becker–Coron–Joux），本算法在同一类假设下把底数从 $2^{0.291}$ 降到 $2^{0.241}$。

## 7. 为什么必须写上"启发式与模型依赖"

$0.241$ 这个指数**不是**对任意输入成立的最坏情况定理。把结论引用出去之前，必须连同以下保留条款一起引用：

1. **随机实例假设**：分析针对密度约 1 的随机实例（$x_i,s$ 为约 $n$ 比特随机整数，见 1.1），并假设目标解数量适中（常数级）。对刻意构造的对抗性实例，列表大小与碰撞数的估计都可能失效。
2. **均匀性启发式**：模 $M_1$、$M$ 等约束把候选筛掉约 $1/M$ 的比例，这依赖于"子集和在模 $M$ 下近似均匀分布"的假设；同样地，分析假设各列表中的碰撞行为接近独立。这些都是启发式而非已证明的引理。
3. **多项式截断**：单个叶元素的替换会影响上层派生列表的大小，分析假设可以把这种影响截断在多项式范围内而不显著改变成功概率。
4. **QRAM 风格成本模型**：论文把"对指数级大数据结构做量子叠加地址访问"计为每次 $\operatorname{poly}(n)$ 开销（即 3.3 与 4.5 讨论的相干 radix tree）。在只允许最近邻基本门的容错量子计算模型中，这一假设可能引入额外因子。

因此准确的表述是：**在随机密度 1 实例与 QRAM 风格成本模型下，该组合算法的启发式时间指数约为 $0.241$。** 它既不证明 $\mathrm{NP}\subseteq\mathrm{BQP}$（甚至不暗示这一点——它只覆盖一类随机实例），也不保证现实的容错量子计算机在具体 $n$ 上优于高度优化的经典实现。它与 Grover 对对称密码的加速属于同一类型：指数底数的缩小，而非问题难度类别的改变。

## 8. 小例子：手工执行折半与多重表示

### 8.1 折半搜索的完整手算

取实例 $(x_1,x_2,x_3,x_4)=(3,5,6,7)$，目标 $s=12$。把指标分成左半 $L=\{1,2\}$（元素 $3,5$）与右半 $R=\{3,4\}$（元素 $6,7$）。

**第一步**，枚举左半的全部子集和（$2^2=4$ 项）：

$$
\varnothing\mapsto 0,\qquad
\{1\}\mapsto 3,\qquad
\{2\}\mapsto 5,\qquad
\{1,2\}\mapsto 8,
$$

即 $\mathcal L=\{0,3,5,8\}$（已排序）。

**第二步**，枚举右半的全部子集和，并用 $s$ 去减：

$$
\varnothing\mapsto 12-0=12,\quad
\{3\}\mapsto 12-6=6,\quad
\{4\}\mapsto 12-7=5,\quad
\{3,4\}\mapsto 12-13=-1,
$$

即 $s-\mathcal R=\{12,6,5,-1\}$。

**第三步**，找碰撞：逐一检查 $s-\mathcal R$ 中的值是否出现在 $\mathcal L=\{0,3,5,8\}$ 中。$12$ 不在，$6$ 不在，$5$ **在**，$-1$ 不在。唯一的碰撞值是 $5$。

**第四步**，恢复解：左半中和为 $5$ 的子集是 $\{2\}$（即元素 $x_2=5$）；右半中需要 $12-5=7$，对应的子集是 $\{4\}$（即元素 $x_4=7$）。合并得 $I=\{2,4\}$，验证 $5+7=12$。由于碰撞唯一，解也唯一。

### 8.2 多重表示的手算

取 $n=8$，设目标解为 $I=\{1,2,3,4\}$（权重 $4=n/2$）。把它有序拆成两个大小为 $2$ 的无交块，方式数为 $\binom{4}{2}=6$：

$$
\begin{aligned}
&\{1,2\}\mathbin{\dot\cup}\{3,4\},\quad
\{1,3\}\mathbin{\dot\cup}\{2,4\},\quad
\{1,4\}\mathbin{\dot\cup}\{2,3\},\\
&\{2,3\}\mathbin{\dot\cup}\{1,4\},\quad
\{2,4\}\mathbin{\dot\cup}\{1,3\},\quad
\{3,4\}\mathbin{\dot\cup}\{1,2\}.
\end{aligned}
$$

现在施加一个模约束，例如要求 $\Sigma(I_1)\equiv c\pmod 3$（$c$ 为某个预定余数）。对随机数据，每张"彩票"通过约束的概率约为 $1/3$；单买一张彩票只有 $1/3$ 的中奖率，而 6 张彩票同时买，"至少一张通过"的机会明显增大——尽管这些彩票共享元素、并不独立，精确概率无法简单相乘，**这正是第 7 节"启发式"三个字的具体含义**。当 $n$ 增大时，彩票数 $\binom{n/2}{n/4}\approx 2^{n/2}$ 指数增长，而每层模约束只筛掉一个常数比例（$1/M$），拉锯的结果就是第 5–6 节的指数下降。

大型算法仍在寻找 8.1 中那种数值碰撞，只是用模条件提前筛选、用 8.2 中的多重表示提高命中概率，并把整个搜索放进量子行走的状态里。

## 9. 小结

**小结**：

- 对全部 $2^n$ 个子集直接做 Grover 得到 $2^{n/2}$，并没有胜过 1974 年的经典折半搜索；要超过经典，必须利用"建表成本"与"搜索成本"之间的不平衡。
- 量子不平衡折半（$1/3$ 对 $2/3$ 划分）把指数降到 $1/3$；Johnson 图量子行走通过"设置成本 $r$ 对搜索步数 $N/\sqrt r$"的平衡独立得到同一指数，但要求可相干更新的数据结构（可逆 radix tree），隐含 QRAM 风格假设。
- 多重表示让同一个解拥有指数多种拆分；配合模约束筛选控制列表大小，是经典算法降到 $2^{0.291n}$（Becker–Coron–Joux）的原因。
- 把 16 叶表示树装进量子行走状态，令"8 个叶列表同时命中"的概率 $\epsilon=(r/B)^8$ 与谱隙 $\delta=\Theta(1/r)$ 相平衡，得到启发式指数 $2^{0.241n}$；该结论依赖随机实例、均匀性启发式与相干内存模型，不蕴含 $\mathrm{NP}\subseteq\mathrm{BQP}$。

## 练习题

**练习 1【密度与困难随机实例】**（→ [1.1 节](#subset-sum-density)）

1. 写出密度 $d$ 的定义，并对 $(n,m)=(200,100)$ 与 $(n,m)=(100,200)$ 分别计算期望解数 $\frac{2^{n-m}}{n}$ 的量级（写出 2 的幂次即可）。
2. 解释为什么"密度接近 $1$ 且承诺至少存在一个解"的随机实例处在最困难区域：从期望解数公式出发，说明此时解的数量为常数级、任何碰运气的策略都没有可乘之机。

**练习 2【折半搜索与朴素 Grover 的平局】**（→ [2.1 节](#meet-in-the-middle)）

1. 对实例 $(x_1,x_2,x_3,x_4)=(2,3,5,8)$、目标 $s=10$ 完整执行折半搜索：列出两张表、找出所有碰撞并恢复所有解。（应能找到两个解。）
2. 解释为什么"对整个 $2^n$ 搜索空间做 Grover"不能超越经典折半搜索。分别写出穷举、折半、朴素 Grover、量子不平衡折半四种方法的时间与空间复杂度（用 $\widetilde O$）。

> 提示：比较两个 $2^{n/2}$ 各自的来源——一个来自把搜索空间开平方，一个来自把问题切成两半。

**练习 3【量子不平衡折半】**（→ [3.2 节](#unbalanced-mitm)）

1. 取 $\lambda=\frac13$，分别计算建表成本 $2^{\lambda n}$ 与搜索成本 $2^{(1-\lambda)n/2}$ 的指数，验证两者相等并写出总时间与总内存。
2. 证明：最小化 $\max\{\lambda,\frac{1-\lambda}{2}\}$ 的最优解必在两式相等处取得，并求出 $\lambda^\ast=\frac13$。
3. 解释 3.3 的伏笔：Grover 迭代中"对叠加态中的地址查询排序表"为什么是一个 QRAM 式的强模型假设，而在经典 RAM 中只是平凡操作。

> 提示：一个随 $\lambda$ 递增、一个随 $\lambda$ 递减，二者的最大值在交点处最小。

**练习 4【Johnson 图量子行走】**（→ [4.2 节](#johnson-graph-walk)）

1. 写出 Johnson 图 $J(N,r)$ 的顶点与相邻关系的定义，说明"标记顶点"的含义，并写出谱隙 $\delta$ 的量级。
2. 补全 4.2 的标记占比推导：验证 $\binom{N-2}{r-2}\big/\binom{N}{r}=\frac{r(r-1)}{N(N-1)}$，并说明当 $r=N^{2/3}$ 时为什么可以用 $(r/N)^2$ 近似。

> 提示：把阶乘展开相消；近似时用 $r\ll N$ 蕴含 $r-1\approx r$、$N-1\approx N$。

**练习 5【行走搜索的代价公式与平衡】**（→ [4.3 节](#walk-cost-formula)）

1. 写出行走搜索的步数公式 $O(1/\sqrt{\delta\epsilon})$，并把 $\delta=\Theta(1/r)$、$\epsilon\approx(r/N)^2$ 代入，把总查询成本 $r+\frac{1}{\sqrt{\delta\epsilon}}$ 化简为 $r+\frac{N}{\sqrt r}$。
2. 对 $f(r)=r+\frac{N}{\sqrt r}$ 求导，验证最小值在 $r^{3/2}=\frac N2$ 即 $r=\Theta(N^{2/3})$ 处取得，并说明代入 $N=2^{n/2}$ 后总复杂度为 $\widetilde O(2^{n/3})$。

> 提示：$f'(r)=1-\frac12Nr^{-3/2}$，令其为零。

**练习 6【可相干更新的数据结构】**（→ [4.5 节](#coherent-data-structure)）

1. 列出行走状态的数据结构必须在相干叠加下支持的四类操作，并分别说出设置成本、更新成本、检查成本的含义。
2. 解释为什么用排序数组存储 $r$ 个候选会把每步行走的更新成本从 $O(1)$ 放大到 $\Theta(r)$、从而毁掉量子行走的查询优势，并说明带子树计数的可逆 radix tree 如何把每次更新控制在 $\operatorname{poly}(n)$。
3. 列举"查询复杂度模型"与"完整容错门/内存模型"之间至少三项不同的成本来源，并讨论：其中哪一项对 $2^{0.241n}$ 这一结果的现实意义影响最大？为什么？

**练习 7【多重表示与模约束筛选】**（→ [5.1 节](#multiple-representations)）

1. 解释"多重表示"的含义：对 $n=8$、目标解 $I=\{1,2,3,4\}$，列举全部 $\binom{4}{2}=6$ 种有序二分拆分，并写出一般情形（$|I|=n/2$）下拆分数的表达式。
2. 解释模约束 $\Sigma(I_1)+\Sigma(I_2)\equiv s\pmod{M_1}$ 为什么能把中间列表压缩约 $1/M_1$ 的比例，并说明"彩票多"与"筛子紧"之间的拉锯如何决定各层模数的取法。

> 提示：随机候选对的和在模 $M_1$ 下近似均匀分布；表示数 $\binom{n/2}{n/4}$ 随 $n$ 指数增长。

**练习 8【16 叶量子行走的 0.241 指数】**（→ [6.4 节](#leaf-walk-balance)）

1. 写出 $\log_2 B\approx 0.271n$、$\epsilon=(r/B)^8$、$\delta=\Theta(1/r)$ 三个量的含义与来源，并把行走步数 $\frac{1}{\sqrt{\delta\epsilon}}$ 化简为 $\sqrt r\,(B/r)^4$。
2. 模仿 6.1，用 Stirling 公式证明 $\frac1n\log_2\binom{n/2}{n/4}\to\frac12 H(1/2)=\frac12$（这就是 5.1 中"一个解有 $2^{(1/2+o(1))n}$ 种二分表示"的依据），并把 $H(1/8)$ 的数值验证到小数点后三位。
3. 在 6.3–6.4 中，从 $\epsilon=(r/B)^8$ 与 $\delta=\Theta(1/r)$ 出发，完整重推行走步数 $\sqrt r\,(B/r)^4$ 与平衡点 $r=B^{8/9}$；然后回答：如果表示树只有 4 个叶列表（$\epsilon=(r/B)^4$），平衡指数会变成多少？由此说明"叶数越多越好"的直觉在哪里开始失效。

> 提示：考虑叶块候选空间 $B$ 随叶数的变化。

## 参考文献

- Zoo 编号 178：Daniel J. Bernstein、Stacey Jeffery、Tanja Lange 与 Alexander Meurer, [Quantum Algorithms for the Subset-Sum Problem](https://cr.yp.to/qsubsetsum/qsubsetsum-20130407.pdf).
- Zoo 编号 7：Andris Ambainis, [Quantum Walk Algorithm for Element Distinctness](https://arxiv.org/abs/quant-ph/0311001).
- Zoo 编号 404：Anja Becker、Jean-Sébastien Coron 与 Antoine Joux, [Improved Generic Algorithms for Hard Knapsacks](https://eprint.iacr.org/2011/474).