论文标题
量子符合细粒度的复杂性：串联问题的额定时间量子算法
Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems
论文作者
论文摘要
最长的常见基因（LCS），最长的腔质基因（LPS）和ULAM距离（UL）是三个基本的弦问题，可以在几乎线性的时间内经典地解决。在这项工作中，我们为这些问题以及量子下限介绍了均值时间量子算法。我们的结果阐明了一个非常令人惊讶的事实：尽管LCS和LP的经典解决方案几乎是相同的（通过后缀树），但它们的量子计算复杂性却不同。虽然我们给出了一个准确的$ \ tilde o（\ sqrt {n}）$ time算法，但我们证明，LCS至少需要$ \ tildeω（n^{2/3}）$，即使对于0/1字符串。
Longest common substring (LCS), longest palindrome substring (LPS), and Ulam distance (UL) are three fundamental string problems that can be classically solved in near linear time. In this work, we present sublinear time quantum algorithms for these problems along with quantum lower bounds. Our results shed light on a very surprising fact: Although the classic solutions for LCS and LPS are almost identical (via suffix trees), their quantum computational complexities are different. While we give an exact $\tilde O(\sqrt{n})$ time algorithm for LPS, we prove that LCS needs at least time $\tilde Ω(n^{2/3})$ even for 0/1 strings.
