H. Ramech, V.Vinay. String matching in $\tilde{O}(\sqrt n + \sqrt m)$ quantum time (2003)

Posted on Edited on In ,

Abstract. 本文是 https://doi.org/10.1016/S1570-8667(03)00010-8 的阅读笔记。他们尝试把 https://doi.org/10.1137/0220002 的技术用在了量子计算机上，发现很有道理。很遗憾的是作者好像不是量子计算从业者，他们的很多 approach 都是有问题的，但也不是不能修复。因为他的思路非常 trivial，所以我们有精力帮他们重新算一遍。最后一节“处理周期性串”看起来比较对，但我们放弃仔细验证了。

简介

你妈啊，整篇文章里的公式只有几个渐进记号的批文章是怎么上 TCS 杂志的？？？

本文章受并行计算中的方法 deterministic sampling [VI91] 启发，提出了一种 $\tilde{O}(\sqrt n + \sqrt m)$ 的字符串匹配的量子算法。

前置知识

我们完全抛弃作者的 Preliminary 一节，因为他是傻逼。

回忆对于一个函数 $f: [n] \rightarrow \{0, 1\}$，若给定复杂度为 $O(T)$ oracle $U_f$，其满足

$$
U_f|x\rangle = (-1)^{f(x)}|x\rangle
$$

那么存在一个 $O(T\sqrt n)$ Grover 算法 $\mathcal{G}_f$，使得

$$
\mathcal{G}_f|0^l\rangle = \sqrt{1-p}|\Psi_0\rangle + \sqrt{p}|\Psi_1\rangle
$$

其中 $U_f|\Psi_i\rangle = (-1)^i |\Psi_i\rangle$，这里 $\Psi_1$ 称为“好元素”，也就是通过 $U_f$ 之后会得到 $1$ 的元素。进行测量，就可以常数概率得到一个 $f(x) = 1$ 的元素。如果你将 $(2)$ 的结果通过一个 $f$，使用 phase kickback 技术，可以把好坏状态表示在一个辅助比特上：

$$
(I\otimes H)(U_f \otimes H)(I \otimes H)(\mathcal{G}_f\otimes I)|0^l\rangle|0\rangle = \sqrt{1-p}|\Psi_0\rangle|0\rangle + \sqrt{p}|\Psi_1\rangle|1\rangle
$$

Remark. 原版的 Grover 算法，在不知元素个数的情况下，需要猜测被标记元素个数为 $1, 2, …, 2^l$，然后进行测量，并配上一些经典过程来完成（以 $\frac{3}{4}$ 概率得到一个被标记元素）。然而我们有延迟测量准则（deferred measurement principle），可以增加 $O(m)$ 个辅助比特来将测量推迟到电路末尾。计算一下可以发现被标记元素的振幅至少是 $3/4$。

如果我其实算错了，也不要紧，可能有两种方法替代：

  • 我自己想了一种办法，来让被标记元素的振幅至少是 $3/ (4\log n)$，如果你不关心 $\log$ 因子，这种做法就 work。（当然有可能这个也算错了）
  • 可以参考 [YL+14]，这种算法本来就不需要测量。（当然这篇文章我还没读完，如果理解错了就寄了）

如果三种办法都寄了，我们就直接润了。

通过如下的方法来将 Grover 算法进行“嵌套”，比如我们有一个二维的函数 $f: [n]\times [m]\rightarrow \{0, 1\}$，我们的目标是借助 $U_f$ 找到其中的一个 $1$。首先固定第一维，我们有 Grover oracle

$$
\mathcal{G}_{f_i}|i\rangle|0^l_m\rangle|0\rangle = \sqrt {p_i} |i\rangle|\Psi_{i, 1}\rangle|1\rangle + \sqrt{1 - p_i} |i\rangle|\Psi_{i, 0}\rangle|0\rangle
$$

如果某一行有 $1$，那么 $p\geq 3/4$，否则 $p = 0$。现在向第一个寄存器传入均一叠加态，结果应当是

$$
\frac{1}{\sqrt n}\left(\sum_{i\in [n]}\sqrt {p_i} |i\rangle|\Psi_{i, 1}\rangle\right)|1\rangle + \frac{1}{\sqrt n}\left(\sum_{i\in [n]}\sqrt {1 - p_i} |i\rangle|\Psi_{i, 0}\rangle\right)|0\rangle
$$

求和式子内部的向量是两两正交的，根据勾股定理，好元素的振幅是

$$
\sqrt{\sum_{i\in [n]} p_i}\geq \sqrt{\frac{3}{4n}}
$$

只需要做 $O(\sqrt n)$ 的振幅放大，就可以将好元素的振幅放至接近 $1$。注意此时你只知道振幅的下界，所以仍然需要猜测振幅为 $\sqrt{\frac{3}{4n}}, \sqrt{2\frac{3}{4n}}, \sqrt{4\frac{3}{4n}}, …$，配合一些经典过程。此时测量前两个寄存器，可以以 $\frac{3}{4}$ 得到一个 $(i, j)$ 使得 $f(i, j) = 1$。

另外，[DH96] 指出给定一个列表，可以在 $O(\sqrt n)$ 时间内找到其中的最小值，即存在一个 oracle $U_M$，满足

$$
U_M|0^l\rangle = \sqrt p |i_M\rangle + \sqrt{1 - p}|\bot\rangle
$$

其中 $i_M$ 的每个分量 $i_M’$ 都满足 $a_{i_{M’}} \leq a_j, \forall j$。

关于字符串的部分，在上一篇文章中有所谈及。

下文假设给定两字符串的随机访问 Oracle。文本串称为 $T_{1, …, m}$，模式串称为 $P_{1, …, m}$。则 $U_T$ 给出酉变换 $|i\rangle|0\rangle\mapsto|i\rangle|T_i\rangle$，$U_P$ 同理。假设对态完成算术运算的复杂度是 $O(1)$。

朴素的 $\tilde{O}(\sqrt{nm})$ 的算法

首先可以实现 $g(i, j)$ 表示 $T_{i + j}$ 和 $P_j$ 是否不匹配，这是一个 $O(1)$ 的经典算法。因此我们有了 $O(1)$ 的 oracle

$$
U_g|i\rangle|j\rangle = (-1)^{g(i, j)}|i\rangle|j\rangle
$$

在第二个寄存器上用 grover 搜索，如果存在不匹配的位置，能将其振幅放大至至少 $3/4$，也就是我们能够实现一个 $O(\sqrt m)$ 的 $U_f$，使得

$$
U_f|i\rangle|0^l\rangle|0\rangle = \begin{cases}
|i\rangle|\Psi\rangle|0\rangle & \text{the pattern matches at $i$} \\
\sqrt p|i\rangle|\Psi_1\rangle|1\rangle + \sqrt{1 - p}|i\rangle|\Psi_0\rangle|0\rangle & \text{the pattern doesn’t matches at $i$}
\end{cases}
$$

如果使用早期 grover 算法，这里就会出现奇怪的问题：此处 $p$ 的下界是 $3/4$ 如果你现在直接对第三个寄存器上是 $0$ 的元素做振幅放大（on the top of $i$），你最后得到的东西是匹配上了的位置和未匹配上的位置的分量混合在一起的东西。要使得这两部分的振幅之比变成 $O(1)$ 而非现在的 $O(1/n)$，需要在第二、三寄存器上做振幅放大。这里除了 [YL+14] 中的办法，我不知道还有什么别的途径。总之这里我们可以付出 $O(\mathrm{polylog}(n))$ 的代价，使得 $p = 1 - o(1)$。

现在在第一、三寄存器上做 $O(\sqrt n)$ 振幅放大，然后测量第一个寄存器，就可以常数概率得到一个确实匹配上了的位置。总复杂度是 $\tilde{O}(\sqrt {nm})$。

针对非周期性模式串的 $\tilde{O}(\sqrt n)$ 文本分析

这节以及下一节思路来自 [VI91]，我们的阅读笔记是链接。假定我们能计算出 deterministic sampling。将序列分成 $2n / m$ 块（块长为 $m/2$），回忆我们做的事情是求出最小、最大的匹配上所有 deterministic sample 的位置。

首先容易设计 $O(\log n)$ 的经典算法 $k(i, j)$，如果第 $i$ 块的第 $j$ 位匹配了所有的 deterministic sample，就将此位置置为 $j$，否则置为 $\infty$，具体地：

$$
U_k|i\rangle|j\rangle|0\rangle = \begin{cases}
|i\rangle|j\rangle|j\rangle & \text{if all deterministic sample matches}\\
|i\rangle|j\rangle|\infty\rangle & \text{otherwise}
\end{cases}
$$

将 $U_f|i\rangle$ 用作 DH96 的 oracle，将得到一个算法，其读入 $|i\rangle|0\rangle$ 使得块中最小的匹配上所有 deterministic sample 的位置（记作 $mn_i$）的振幅超过 $3/4$，即

$$
U_{mn}|i\rangle|0^l\rangle = \sqrt{p}|i\rangle|mn_i\rangle + \sqrt{1 - p}|\bot\rangle
$$

此 oracle 的时间为 $O(\sqrt m\log m)$。接下来，在第二个寄存器（附加辅助比特 $|0^l\rangle|0\rangle$）上作用 $(9)$ 式中的酉变换 $U_f$，得到一个 $O(\sqrt m\mathrm{polylog}(n))$ 的 oracle，使得

$$
U_{h}|i\rangle|0^l\rangle|0\rangle|0\rangle = \begin{cases}
|i\rangle|\Phi\rangle|\Psi\rangle|0\rangle & \text{if the candidate matches} \\
\sqrt{p} |i\rangle|\Phi_1\rangle|\Psi_1\rangle|1\rangle + \sqrt{1-p} |i\rangle|\Phi_0\rangle|\Psi_0\rangle|0\rangle & \text{otherwise}
\end{cases}
$$

其中 $p = 1 - o(1)$。接下来在第一个寄存器上均一叠加 $|i\rangle$，以此为 Oracle 在第一、四寄存器上做 $O(\sqrt {n/m})$ 的振幅放大，即可得到确实匹配上了的位置。总复杂度为 $O(\sqrt n\mathrm{polylog}(n))$。

现在问题只剩下了 deterministic sample 的求解。

针对非周期性模式串的 $\tilde{O}(\sqrt m)$ 模式分析

这一节非常傻逼。首先这里思路参考 [VI91] 中的随机化模式分析算法，大致思路是找到 witness 之后不是选择相同字符数量较少的一个，而是随机选一个。

因为 deterministic sample 一共只有 $O(\log n)$ 位，我们选择分 $O(\log n)$ 个阶段来计算这个问题，每阶段量子计算用于配合搜索 witness 和 $\min A_i$、$\max A_i$。计算 $\min A_i$ 和 $\max A_i$ 的手法和 $(10), (11)$ 式如出一辙，而计算 witness 则是非常 trivial 的 Grover 搜索。

显然复杂度是 $\tilde{O}(\sqrt m)$。

处理周期性模式串

首先找串的周期。使用经典过程套量子搜索：

利用 $(9)$ 中的 oracle，容易判断 $v$ 是否是原串的周期。如果上一节的算法在某一阶段并没有找到 witness，那么周期必然是 $|v| = \min A_i - \max A_i$ 的因数之一。那么可以尝试除掉其每一个质因子，然后用量子算法判断是否确实是周期，因此可以在 $O(\sqrt m\mathrm{polylog}(m))$ 的时间内求出周期。

现在设 $P = v^kw$，我们已经知道了 $|v|$，并可以求出 $v$ 的 deterministic sample。现在如果串在 $[im/2, (i + 1)m/2)$ 这段区间有出现，$v+w$ 必然在 $[(i+1)m/2 - |v|, (i+1)m/2)$ 这段区间有出现，而且只需要考虑最前面一次出现和最后面一次出现，用 [DH96] 中的算法可以解决。假设最、后前面一次出现位置分别为 $l, r$。再用 DH96 可以求出与 $l \bmod |v|$ 同余的最早出现位置和最晚出现位置，只要这两个的差距 $\geq k$，就说明这一块确实有匹配。对于 $r$ 同理。然后做振幅放大。

唉唉，看起来确实是一些可逆经典电路和量子电路叠起来即可，那你说是对的就是对的吧，我也懒得细算了。

参考文献

[BB+96] M. Boyer, G. Brassard, P. Hoyer, A. Tapp. Tight bounds on quantum searching. Proceedings of 4th Workshop on Physics and Computation-PhysComp (1996), pp. 36-43

[DH96] C. Dürr, P. Hoyer. A quantum algorithm for finding the minimum. Quantum Physics E-Print Archive. http://xxx.lanl.gov/quant-ph/9607014. 1996

[YL+14] Theodore J. Yoder, Guang Hao Low, and Isaac L. Chuang. Fixed-Point Quantum Search with an Optimal Number of Queries. Phys. Rev. Lett. 113, 210501.

[VI91] Uzi Vishkin. Deterministic Sampling–A New Technique for Fast Pattern Matching. SIAM Journal on Computing 1991 20:1, 22-40