论文标题
用于最频繁的字符串搜索的量子算法，两个字符串序列的交点以及字符串问题的排序
Quantum Algorithms for the Most Frequently String Search, Intersection of Two String Sequences and Sorting of Strings Problems
论文作者
论文摘要
我们研究用于解决字符串三个问题的算法。第一个是最常见的字符串搜索问题。问题是以下内容。假设我们有一组$ n $ strings $ k $的序列。问题是找到最常在序列中发生的字符串。我们提出了一种具有查询复杂性$ \ tilde {o}（n \ sqrt {k}）$的量子算法。该算法显示了与需要$ω（NK）$查询的确定性算法进行比较的速度。第二个是搜索两个字符串序列的相交。所有字符串都具有相同的长度$ k $。第一套的大小为$ n $，第二组的大小为$ m $。我们提出了一种具有查询复杂性$ \ tilde {o}（（n+m）\ sqrt {k}）$的量子算法。该算法显示与需要$ω（（（n+m）k）$查询的确定性算法进行比较。第三个问题是排序$ n $ $ k $的$ n $字符串。一方面，众所周知，量子算法不能比经典算法更快地分类对象。另一方面，我们专注于分类不是任意对象的字符串。我们提出了一种具有查询复杂性$ o（n（\ log n）^2 \ sqrt {k}）$的量子算法。该算法显示与需要$ω（（（n+d）k）$ QUERIES的确定性算法（RADIX排序）相比，其中$ d $是字母的大小。
We study algorithms for solving three problems on strings. The first one is the Most Frequently String Search Problem. The problem is the following. Assume that we have a sequence of $n$ strings of length $k$. The problem is finding the string that occurs in the sequence most often. We propose a quantum algorithm that has a query complexity $\tilde{O}(n \sqrt{k})$. This algorithm shows speed-up comparing with the deterministic algorithm that requires $Ω(nk)$ queries. The second one is searching intersection of two sequences of strings. All strings have the same length $k$. The size of the first set is $n$ and the size of the second set is $m$. We propose a quantum algorithm that has a query complexity $\tilde{O}((n+m) \sqrt{k})$. This algorithm shows speed-up comparing with the deterministic algorithm that requires $Ω((n+m)k)$ queries. The third problem is sorting of $n$ strings of length $k$. On the one hand, it is known that quantum algorithms cannot sort objects asymptotically faster than classical ones. On the other hand, we focus on sorting strings that are not arbitrary objects. We propose a quantum algorithm that has a query complexity $O(n (\log n)^2 \sqrt{k})$. This algorithm shows speed-up comparing with the deterministic algorithm (radix sort) that requires $Ω((n+d)k)$ queries, where $d$ is a size of the alphabet.
