【Hanged】Shyan Akmal, Ce Jin. Near-Optimal Quantum Algorithms for String Problems
Abstract. 解决了三个问题：最长公共子串、最小字典序循环移位、最长平方子串。暂时只看懂了最小字典序循环移位。
前置知识
字符串基础
记号
- 字符串 $s_1$ 字典序小于 $s_2$ 记作 $s_1\prec s_2$，类似地定义 $\succ, \preceq, \succeq$。
- $s$ 的反串记作 $s^R$。
- $s$ 的周期记作 $\textsf{per}(s)$。若 $\textsf{per}(s)\leq |s| / 2$，则称 $s$ 是周期性的。若 $\textsf{per}(s)\nmid |s|$，称 $s$ primitive。
引理 1. 给定字符串 $s_1\preceq s_2 \preceq \cdots\preceq s_m$，则 $\mathsf{lcp}(s_1, s_m) = \min_{1\leq i < m} \mathsf{lcp}(s_{i}, s_{i + 1})$。
这就是后缀排序时使用的经典结论。
引理 2（Weak Periodicity Lemma）. 若 $p, q$ 都是 $s$ 的周期，且 $p + q \leq |s|$，那么 $\gcd(p, q)$ 也是 $s$ 的周期。
引理 3. 假设 $|s| / 2 \leq |t| \leq |s|$，$t$ 在 $s$ 中出现的所有位置为 $i_1, …, i_m$，则 $i_1, …, i_m$ 是等差数列，且若 $m\geq 3$，$\textsf{per}(t)$ 正是该等差数列的公差。
对于一个 primitive $s$，若其是所有循环位移中最小的一个，则称其为 Lyndon word。一个周期为 $p$ 的串的 Lyndon root 定义为其循环节的最小字典序循环位移。
计算模型
假设有字符串 $s$ 的随机访问 Oracle $O_s : |i, b\rangle\mapsto |i, b \oplus s_i\rangle$。
这个 Oracle 的实现或许需要所谓的 QRAM（支持叠加查询的存储原价）：$|i, b, z_1, …, z_m\rangle \mapsto |i, z_i, z_1, …, b, …, z_m\rangle$。
量子算法
引理 4. 存在一个量子算法能够在 $\tilde{O}(\sqrt n)$ 复杂度内求 $\mathsf{lcp}$ 和判断字典序大小关系。
证明. 回忆 Grover 可以判定两个字符串是否相等，在外面套上一层二分即可。
引理 5. 存在一个量子算法，能够在 $\tilde{O}(\sqrt n)$ 复杂度内判断 $s$ 在 $t$ 中是否出现。
这就是臭名昭著的 [RV03]。
量子游走
本文考虑 Johnson 图 $J(m, r)$ 上的量子游走，此图有 $\binom{m}{r}$ 个点，每个点是 $[m]$ 的一个 $r$-子集，两点连边当且仅当边距为 $1$（相当于 Hamming 图 $H(m, r)$ 的一个诱导子图）。
按照惯例设启动代价是 $S$，更新代价是 $U$，检验代价是 $C$，假设 marked item 占比是 $\varepsilon$。这个图的 Spectral Gap 看起来像 $\frac{1}{r}$ 的，所以说有
定理 6. 存在一个时间为 $O(S + \frac{1}{\sqrt{\varepsilon}}(\sqrt rU + V))$ 量子算法，判断图是全空还是存在占比至少 $\varepsilon$ 的 mark item。
这个复杂度有点怪，我们先当 input 用，之后再细看。
【Under Construction】最长公共子串问题
问题是求两个串的最长公共（连续）子串。
最小字典序循环移位
之前的工作是 [WY20]，我们的笔记参见 Qisheng Wang, Mingsheng Ying. Quantum Algorithm for Lexicographically Minimal String Rotation (2022)
回忆在 [WY20] 中，他们首先求了 LMSR 的长度为 $B$ 的前缀，即全串中最小的长度为 $B$ 的子串，然后用这些前缀作为候选直接跑出了整个串的 LMSR。这里能不能不是直接把 $B$ 扩展到 $n$ 而是用倍增之类的办法逐渐增大上去？
首先做一些规约，我们证明 LMSR 弱于字典序最小的固定长度子串问题。
定义 3.1（最小 $\mathcal{l}$-子串问题）. 对于长为 $n$ 的字符串 $s$ 和 $\ell\geq n / 2$，求字典序最小的长度为 $\ell$ 的子串。如果有多个，用等差数列表示。
定理 3.2. 最小字典序循环移位弱于最小字典序后缀。
证明. 把 $s$ 复制两份后在后面加一个字典序极大的字符 $\infty = |\Sigma| + 1$。容易证明此串的最小字典序后缀对应原串的最小字典序循环移位。
定理 3.3. 最小字典序后缀弱于最小字典序 $\ell$-子串。
证明. 在 $s$ 后面加 $n - 1$ 个 $0$。容易证明此串的最小 $n$ 子串对应原串的最小字典序后缀。
注意到
引理 3.4. 设 $I$ 是 $s$ 的最小字典序 $\ell$-子串的下标集合。给定 $a, k$ 满足 $a\geq 1, k\geq 1, a + k\leq n - \ell + 1$，$J$ 是 $s[a, a + 2k)$ 的最小 $k$-子串的下标集合。那么如果 $I\cap J\ne \varnothing$，则 $I\cap \{\min J, \max J\}\ne \varnothing$。
证明. 设 $I\cap J = i$，$J$ 的公差是 $p$，这表明 $u = s[i..i+p)$ 是一切 $s[a, a + 2k)$ 的最小 $k$-子串的周期。设 $s[i..i+\ell) = u^tr$，其中 $\textsf{lcp}(u, r) < p$，那么根据 $u, r$ 的字典序关系，或者有 $u^{t + 1}r < u^tr$，或者有 $u^{t - 1}r < u^t r$，即要么 $i$ 的上一项也在 $I$ 中，要么 $i$ 的下一项也在 $I$ 中。一直推下去可以得到 $J$ 的首项或者末项在 $I$ 中。
Remark. 这个引理为递归提供了基础。即如果我们把整个串划分成若干个子问题，那么能够成为解的只有每个子问题的解的首项和末项。
下面是一个最小 $n / 2$-子串的 $O(n\log n)$ 的经典分治算法：
- 令 $s_1 = s[1..n/2], s_2 = s[n/4..3n/4]$，$m = n / 4$。
- 递归求解 $s_1, s_2$ 的最小 $m$-子串问题。假设 $u_1, v_1$ 分别是 $s_1$ 的最小 $m$-子串的首项、末项，$u_2, v_2$ 分别是 $s_2$ 的最小 $m$-子串的首项、末项。
- 根据引理 4.4，答案和 $\{u_1, v_1, u_2, v_2\}$ 存在交集。
- 用字符串匹配求出全体匹配的位置。
其时间复杂度为满足递推关系：
$$
T(n) = 2T(n / 2) + O(n)
$$
其中 $O(n)$ 来自 $O(1)$ 次字典序比较和一次字符串匹配。
现在我们来做量子加速，整个过程是一个鸡巴复杂度演算。注意如果做 $b$ 叉分治，那么你只需要 $\tilde O(\sqrt b)$ 时间的 Quantum Minimum Finding 就可以完成答案的合并。那么设 $T(n)$ 表示常数概率成功的算法的复杂度。为了做 $\tilde{O}(\sqrt b)$ 的 Quantum Minimum Finding，需要把误差 bound 在 $O(1 / b)$，需要 $\mathrm{poly} \log b$ 的 Amplification of the success。无论如何我们有
$$
T(n) = \tilde O(\sqrt b)\left(T(n / b) + \tilde{O}(\sqrt n)\right) + \tilde{O}(\sqrt n) = \tilde O(\sqrt b)\left(T(n / b) + \tilde{O}(\sqrt n)\right)
$$
令
$$
b = 2^{d(\log n)^{2/3}} = O(n^{o(1)})
$$
Remark. 感觉有点理论计算机科学魅力时刻了。我们来收集一些这个数字的性质。
- $b = O(n^{o(1)})$。
- $\log b = O(\mathrm{poly} \log n)$。
- $d(\log n/b)^{2/3} = \Omega(\log b)$，这是因为 $b = n^{o(1)} < \sqrt n$，而 $\log n = \log \sqrt n$。于是 $d(\log n/b)^{2/3} = \Omega(d(1/2 \log n)^{2/3}) = \Omega(\log b)$。
其中 $d$ 是足够大的常数。我们证明 $T(n) \leq n^{1/2}2^{d(\log n)^{2/3}}$。那么有
$$
\begin{align}
T(n) &\leq c\log^{e} b\sqrt b\left((n/b)^{1/2}2^{d(\log n/b)^{2/3}} + \sqrt n\right) \\
&\leq c\log^e b \sqrt n\left(2^{d(\log n/b)^{2/3}} + \sqrt b\right) \\
&\leq 2c\log^e b\sqrt n 2^{d(\log n/b)^{2/3}} \\
&\leq 2c n^{1/2}2^{d(\log n)^{2/3}} {\color{orange} 2^{e\log\log b - d((\log n)^{2/3} - (\log n - \log b)^{2/3})}}
\end{align}
$$
注意根据 $x^{2/3}$ 的凸性
$$
\begin{align}
(\log n)^{2/3} - (\log n - \log b)^{2/3} &\geq \frac 23 \log b (\log n)^{-1/3} \\
&= \frac 23 d(\log n)^{1/3} \\
&\geq \omega(\log \log b)
\end{align}
$$
得到橙色部分不超过 $1$。于是
$$
T(n) \leq O(n^{1/2 + o(1)})
$$
我们得到了一个几乎最优的 LMSR 的量子算法。
参考文献
[WY20] Qisheng Wang, Mingsheng Ying. Quantum Algorithm for Lexicographically Minimal String Rotation. https://doi.org/10.48550/arXiv.2012.09376