论文标题
字符串同步集的量子加速度，最长的常见子字符串和k-匹配匹配
Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and k-mismatch Matching
论文作者
论文摘要
最长的常见基因（LCS）是一个重要的文本处理问题，最近在量子查询模型中进行了研究。该问题的决策版本，具有阈值$ d $的LCS询问两个长度-N $输入字符串是否具有长度为$ d $的常见子字符串。 $ d = 1 $和$ d = n $的两个极端情况分别对应于元素的独特性和非结构化搜索，这两个基本问题问题的复杂性两个基本问题。但是，中间情况$ 1 \ ll d \ ll n $尚未完全理解。 We show that the complexity of LCS with threshold $d$ smoothly interpolates between the two extreme cases up to $n^{o(1)}$ factors: LCS with threshold $d$ has a quantum algorithm in $n^{2/3+o(1)}/d^{1/6}$ query complexity and time complexity, and requires at least $ω（n^{2/3}/d^{1/6}）$量子查询复杂度。我们的结果在以前的上限$ \ tilde o（\ min \ {n/d^{1/2}，n^{2/3} \}））$（Le Gall和Seddighin ITCS 2022，Akmal和Jin Soda 2022）上，并回答Akmal and Jin的公开问题。 我们的主要技术贡献是Kempa和Kociumaka引入的强大弦乐同步集合技术的量子加速（Stoc 2019）。它一致地样本$ n/τ{1-o（1）} $根据其长度 - $θ（τ）$上下文在字符串中的同步位置，并且每个同步位置都可以通过$ \ tilde o（τ^{1/2+o（1）} $ \ tilde o（tillemization）$ time报告。 作为我们的量子字符串同步集的另一个应用程序，我们研究了$ k $ miSMATCH匹配问题，该问题询问该模式是否在文本中发生，最多$ k $ hamming不匹配。 Using a structural result of Charalampopoulos, Kociumaka, and Wellnitz (FOCS 2020), we obtain a quantum algorithm for $k$-mismatch matching with $k^{3/4} n^{1/2+o(1)}$ query complexity and $\tilde O(kn^{1/2})$ time complexity.
Longest Common Substring (LCS) is an important text processing problem, which has recently been investigated in the quantum query model. The decisional version of this problem, LCS with threshold $d$, asks whether two length-$n$ input strings have a common substring of length $d$. The two extreme cases, $d=1$ and $d=n$, correspond respectively to Element Distinctness and Unstructured Search, two fundamental problems in quantum query complexity. However, the intermediate case $1\ll d\ll n$ was not fully understood. We show that the complexity of LCS with threshold $d$ smoothly interpolates between the two extreme cases up to $n^{o(1)}$ factors: LCS with threshold $d$ has a quantum algorithm in $n^{2/3+o(1)}/d^{1/6}$ query complexity and time complexity, and requires at least $Ω(n^{2/3}/d^{1/6})$ quantum query complexity. Our result improves upon previous upper bounds $\tilde O(\min \{n/d^{1/2}, n^{2/3}\})$ (Le Gall and Seddighin ITCS 2022, Akmal and Jin SODA 2022), and answers an open question of Akmal and Jin. Our main technical contribution is a quantum speed-up of the powerful String Synchronizing Set technique introduced by Kempa and Kociumaka (STOC 2019). It consistently samples $n/τ^{1-o(1)}$ synchronizing positions in the string depending on their length-$Θ(τ)$ contexts, and each synchronizing position can be reported by a quantum algorithm in $\tilde O(τ^{1/2+o(1)})$ time. As another application of our quantum string synchronizing set, we study the $k$-mismatch Matching problem, which asks if the pattern has an occurrence in the text with at most $k$ Hamming mismatches. Using a structural result of Charalampopoulos, Kociumaka, and Wellnitz (FOCS 2020), we obtain a quantum algorithm for $k$-mismatch matching with $k^{3/4} n^{1/2+o(1)}$ query complexity and $\tilde O(kn^{1/2})$ time complexity.
