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

许多 NP-hard 问题的经典最佳算法不是枚举解，而是在所有子集上做 dynamic programming，成本 \(O^*(2^n)\)。量子算法不能把整张 \(2^n\) table 放入免费 QRAM 后直接 Grover；可行策略是只经典预计算若干 Hamming layers，再用递归量子搜索跨越中间层。Path-in-the-hypercube 抽象这一结构，得到 \(O^*(1.817^n)\)。

1. Directed hypercube reachability

顶点为 bitstrings/子集

\[ S\subseteq[n]. \]

只允许增加一个元素的有向边

\[ S\to S\cup\{i\}. \]

输入 oracle 决定哪些顶点/边允许。任务判断是否有单调路径

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

经典 recurrence

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

按 \(|S|\) 递增计算所有 \(2^n\) states，故 \(O^*(2^n)\)。

2. 为什么直接 Grover 前驱不够

若每个 \(DP[S]\) 用 Grover 搜索 \(|S|\) 个前驱，但前驱值又递归计算，会形成巨大重复树；memoization 需要存所有 \(2^n\) 值。Quantum superposition 也不能自动可写共享 memo table。

混合策略：对靠近起点的 layers 经典预计算并存储，量子部分只在更少的 boundary/midpoint 候选上递归搜索，使 subproblem 结果无需跨分支共享。

3. 单层切分的基本公式

选 \(0<\alpha<1/2\)，预计算

\[ \mathcal L_\alpha=\{S:|S|\le\alpha n\}. \]

表大小由二元熵

\[ \sum_{j\le\alpha n}\binom nj =O^*(2^{H(\alpha)n}), \]
\[ H(\alpha)=-\alpha\log_2\alpha -(1-\alpha)\log_2(1-\alpha). \]

任意完整路径必穿过 layer \(|S|=n/2\)。Grover 搜索中点 \(M\)，验证

\[ \operatorname{Reach}(\varnothing,M) \land \operatorname{Reach}(M,[n]). \]

每半段再按相对 layer 切分，直到子问题左边界落入已计算 table。候选中点数的平方根贡献

\[ \sqrt{\binom{r}{r/2}} \approx2^{r/2} \]

型因子；多个递归层的指数相加。

4. 多层参数优化得到 1.817

实际算法用不对称的若干 Hamming fractions，而非每次正中切分：

  1. 经典计算低 weight layer 的 reachability；

  2. 对较高 boundary vertex 做 amplitude amplification；

  3. 验证 boundary 间 path 时再引入中间 layer；

  4. 对补集反向问题复用同样结构。

总指数是若干 entropy 项和 Grover 的 \(1/2\) 系数组合：

\[ \max\{H(\alpha), \tfrac12H(\beta)+F(\alpha,\beta),\ldots\}n. \]

对 layer fractions 做数值最小化，得到

\[ O^*(1.817^n) \]

而非朴素 \(2^{n/2}\)。\(O^*\) 隐藏 \(\operatorname{poly}(n)\) 和 bounded-error amplification。

该常数来自明确 recurrence 优化；它不表示任意 \(2^n\) DP 都自动替换成 \(1.817^n\)，必须能把 transition 表成单调 hypercube path。

5. 从 DP 到实际 NP-hard 问题

**Vertex ordering：**state \(S\) 是已放在 ordering 前缀的顶点集，transition 添加下一顶点，validity 检查当前宽度/约束。

**Traveling salesman：**经典 Held--Karp state 还含 endpoint；对 subset layers预计算距离，再量子搜索 split/endpoints，得到

\[ O^*(1.729^n) \]

型结果。

**Minimum set cover：**state 是已覆盖 universe subset；按选择 set 增加覆盖，结合不同 partition 得约

\[ O(\operatorname{poly}(m,n)1.728^n). \]

**Graph bandwidth：**state/边界信息更多，基数从经典约 \(4.383^n\) 降到约 \(2.946^n\)。

每个指数对应单独 recurrence，不能由 path-in-hypercube 的 1.817 直接代入。

6. 空间、QRAM 与输出

低层 classical DP table 仍有

\[ O^*(2^{H(\alpha)n}) \]

空间。量子分支需 coherent 查询该 table；若实现 QRAM 的成本不计或 poly(n)，时间上界成立。没有随机访问时，table lookup 可能主导。

判定存在路径后，按 self-reduction 固定中间点/transition，递归恢复完整 path，增加多项式或对数放大。TSP 等输出解包含 \(n\) 个选择，不能只给 yes/no。

7. 小例子

\(n=4\)，允许顶点集合

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

若边只在两集合相差新增一元素时存在，则路径

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

需要最后一步新增 2。Layer split 搜索 weight-2 中点，只需验证少数前后 reachability，而不是枚举所有 16 states。

8. 小结与习题

  • Subset DP 等价于 directed hypercube 单调路径。

  • 经典预计算低 layers，量子递归搜索中间 layers，避免全量 quantum memoization。

  • Entropy table size 与 Grover boundary search 的参数平衡给 1.817。

  • TSP、set cover、bandwidth 各需专门 state/recurrence 与不同指数。

  1. 推导低 layer table 的 entropy 近似。

  2. 解释直接递归 Grover 为什么重复计算。

  3. 把一个 vertex-ordering DP 写成 hypercube path。

  4. 讨论无 QRAM 时 classical table lookup 成本。

参考文献