# 量子指数时间动态规划：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 成本。

## 参考文献

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