量子子集和算法：从折半搜索到 \(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}\)。

这次平衡与矩阵乘积验证相似，但数据结构不同：集合要支持相干成员查询、插入、删除和“当前是否已有碰撞”。若用每步移动 \(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. 列出“查询复杂度模型”和“完整容错门/内存模型”中至少三项不同成本。

参考文献