论文标题
用于构造字典问题文本的经典和量子算法
Classical and Quantum Algorithms for Constructing Text from Dictionary Problem
论文作者
论文摘要
我们研究了解决词典（小字符串序列）构建文本（长字符串）的问题的算法。该问题在生物信息学中具有应用，并且与序列组装方法有联系，用于重建来自小片段的长DNA序列。问题是从字符串$ s^1，\ dots，s^m $与可能的交叉点构建一个长度$ n $的字符串$ t $。我们提供一种具有运行时间$ o \ left的经典算法（n+l+m（\ log n）^2 \ right）= \ tilde {o}（n+l）$，其中$ l $是$ s^1的长度的总和，\ s^1，\ dots，s^m $。我们提供了一个量子算法的运行时间$ o \ left（n +\ log n \ cdot（\ log m +\ log \ log \ log n）\ cdot \ cdot \ sqrt {m \ cdot l} \ right）= \ tilde {o}此外，我们表明经典算法的下限为$ω（n+l）$。因此，我们的经典算法是对数因子的最佳选择，并且在字典中非恒定长度的字符串长度的情况下，与任何经典算法相比，我们的量子算法显示了速度。
We study algorithms for solving the problem of constructing a text (long string) from a dictionary (sequence of small strings). The problem has an application in bioinformatics and has a connection with the Sequence assembly method for reconstructing a long DNA sequence from small fragments. The problem is constructing a string $t$ of length $n$ from strings $s^1,\dots, s^m$ with possible intersections. We provide a classical algorithm with running time $O\left(n+L +m(\log n)^2\right)=\tilde{O}(n+L)$ where $L$ is the sum of lengths of $s^1,\dots,s^m$. We provide a quantum algorithm with running time $O\left(n +\log n\cdot(\log m+\log\log n)\cdot \sqrt{m\cdot L}\right)=\tilde{O}\left(n +\sqrt{m\cdot L}\right)$. Additionally, we show that the lower bound for the classical algorithm is $Ω(n+L)$. Thus, our classical algorithm is optimal up to a log factor, and our quantum algorithm shows speed-up comparing to any classical algorithm in a case of non-constant length of strings in the dictionary.
