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

给定整数 $x_1,\ldots,x_n$ 与目标 $s$，子集和问题要求寻找

$$
I\subseteq[n],\qquad
\sum_{i\in I}x_i=s.
$$

它是 NP 完全问题，因此并不期待量子计算把任意实例变成多项式时间。本课研究更细的问题：对接近密度 1 的随机“困难背包”，怎样把指数时间底数从经典约 $2^{0.291n}$ 降到启发式量子 $2^{0.241n}$？答案不是单独使用 Grover，而是把多重表示、模约束、Johnson 图量子行走和可相干更新的数据结构组合起来。

## 1. 先建立正确基线

朴素枚举 $2^n$ 个子集。Grover 搜索可降到

$$
\widetilde O(2^{n/2}),
$$

但经典 meet-in-the-middle 已经达到同一时间指数：把索引分成左右两半，列出

$$
L=\left\{\sum_{i\in I_L}x_i\right\},\qquad
R=\left\{s-\sum_{i\in I_R}x_i\right\},
$$

再寻找 $L,R$ 的碰撞。两张表各有 $2^{n/2}$ 项。因此“对所有子集做 Grover”并没有超越成熟经典算法。

量子折半需要改成不平衡划分。预计算前 $n/3$ 个元素的 $2^{n/3}$ 个和，再对余下 $2n/3$ 个元素的子集做 Grover；搜索域大小 $2^{2n/3}$，平方根仍是 $2^{n/3}$。时间和内存均为

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

## 2. 量子行走如何找到和的碰撞

另一条 $2^{n/3}$ 路线把左右子集和视为碰撞问题。令候选全集大小为 $N=2^{n/2}$，在 Johnson 图 $J(N,r)$ 上维护 $r$ 个候选及其和。若存在唯一配对碰撞，随机 $r$ 元集合包含目标对的比例约

$$
\epsilon\sim(r/N)^2,
$$

而谱隙为 $\delta=\Theta(1/r)$。Szegedy/Ambainis 搜索的查询代价与

$$
r+\frac1{\sqrt{\delta\epsilon}}
\sim r+\frac N{\sqrt r}
$$

同阶。取 $r=N^{2/3}$ 得 $N^{2/3}=2^{n/3}$。

这次平衡与[矩阵乘积验证](matrix-product-verification.md)相似，但数据结构不同：集合要支持相干成员查询、插入、删除和“当前是否已有碰撞”。若用每步移动 $r$ 项的排序数组，门时间会毁掉查询优势。Bernstein 等使用带子树计数的可逆 radix tree，使每次更新只有 $\operatorname{poly}(n)$ 开销；这隐含了对大规模相干随机访问存储的强模型假设。

## 3. 多重表示为什么能进一步降指数

困难随机实例通常取 $x_i,s$ 为约 $n$ 比特整数，目标解权重接近 $n/2$。一个固定解 $I$ 可以用许多方式拆成

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

再把 $I_1,I_2$ 各自二分，最终形成 16 个大小约 $n/16$ 的叶块。算法不要求每一层立即满足精确整数和，只先施加

$$
\Sigma(I_{a})+\Sigma(I_{b})
\equiv s_{ab}\pmod{M_1}
$$

以及更高层的模 $M$ 条件。模筛选让中间列表保持较小，而同一个最终解的海量拆分方式提高“至少一种拆分通过所有随机约束”的概率。这就是 Howgrave-Graham--Joux 的 representation technique。

Becker--Coron--Joux 通过更精细的重叠表示把经典启发式指数降到约

$$
2^{0.291n}.
$$

量子算法不只是对该经典程序整体做 Grover；它把 16 个叶列表本身放进量子行走状态，让一次叶元素替换只局部更新上层碰撞列表。

## 4. $0.241$ 指数的平衡

每个叶块从约 $n/2$ 个可用位置中选 $n/16$ 个元素，完整候选数为

$$
B=\binom{n/2}{n/16}
=2^{(0.271\ldots+o(1))n}.
$$

算法只随机保留每个叶列表的 $r$ 项。建立 8 个叶列表及其 21 个派生碰撞列表的成本为 $\widetilde O(r)$。对一个固定解，8 个指定叶子同时被抽中的概率约为 $(r/B)^8$；振幅放大和行走使恢复成功概率的步数尺度为

$$
\widetilde O\!\left(
\sqrt r\left(\frac Br\right)^4
\right).
$$

令设置成本和行走成本平衡：

$$
r=\sqrt r(B/r)^4
\quad\Longrightarrow\quad
r=B^{4/4.5}.
$$

代入 $\log_2B\approx0.271n$：

$$
\log_2 r
\approx0.271\times\frac4{4.5}n
=0.241\ldots n.
$$

因此得到

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

量子比特操作的启发式渐近成本。

## 5. 为什么必须写上“启发式与模型依赖”

这个指数不是任意输入的最坏情况定理。分析假设随机密度约 1 的实例、目标解数量适中、模余数近似均匀、列表碰撞接近独立，并对单元素影响的派生列表大小施加多项式截断。论文还把量子叠加地址访问指数大数据结构计为多项式开销。

因此结论应准确表述为：在该随机实例与 QRAM 风格成本模型下，组合算法的启发式指数约为 $0.241$。它不证明 NP 包含于 BQP，也不保证现实容错量子机在给定 $n$ 上优于高度优化的经典实现。

## 6. 小例子与算法层次

取 $(3,5,6,7)$，目标 $s=12$。左右分为 $(3,5)$ 与 $(6,7)$：

$$
L=\{0,3,5,8\},\qquad
s-R=\{12,6,5,-1\}.
$$

共同值 5 对应左边选 $\{5\}$、右边选 $\{7\}$，恢复解 $5+7=12$。大型算法仍在寻找这种碰撞，只是用模条件提前筛选，并允许同一个解通过多棵分解树出现。

## 7. 小结与习题

- Grover 的 $2^{n/2}$ 没有胜过经典折半；量子不平衡折半达到 $2^{n/3}$。
- Johnson 图量子行走用“设置成本 vs. 搜索步数”平衡得到同一指数。
- representation technique 让一个解拥有许多分解，提高随机列表命中概率。
- 16 叶量子行走平衡给出启发式 $2^{0.241n}$，但依赖随机实例与相干内存模型。

1. 推导不平衡折半中预计算和 Grover 搜索为何都为 $2^{n/3}$。
2. 最小化 $r+N/\sqrt r$ 的数量级，得到 $r=N^{2/3}$。
3. 用二元熵近似 $\binom{n/2}{n/16}$ 的指数。
4. 列出“查询复杂度模型”和“完整容错门/内存模型”中至少三项不同成本。

## 参考文献

- 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).