We give a near-optimal quantum algorithm for the longest common substring (LCS) problem between two run-length encoded (RLE) strings, with the assumption that the prefix-sums of the run-lengths are given. Our algorithm costs $\tilde{\mathcal{O}}(n^{2/3}/d^{1/6-o(1)}\cdot\mathrm{polylog}(\tilde{n}))$ time, while the query lower bound for the problem is $\tildeΩ(n^{2/3}/d^{1/6})$, where $n$ and $\tilde{n}$ are the encoded and decoded length of the inputs, respectively, and $d$ is the encoded length of the LCS. We justify the use of prefix-sum oracles for two reasons. First, we note that creating the prefix-sum oracle only incurs a constant overhead in the RLE compression. Second, we show that, without the oracles, there is a $Ω(n/\log^2n)$ lower bound on the quantum query complexity of finding the LCS given two RLE strings due to a reduction of $\mathsf{PARITY}$ to the problem. With a small modification, our algorithm also solves the longest repeated substring problem for an RLE string.
We give a near-optimal quantum algorithm for the longest common substring (LCS) problem between two run-length encoded (RLE) strings, with the assumption that the prefix-sums of the run-lengths are given. Our algorithm costs O~(n2/3/d1/6−o(1)⋅polylog(n~)) time, while the query lower bound for the problem is Ω~(n2/3/d1/6), where n and n~ are the encoded and decoded length of the inputs, respectively, and d is the encoded length of the LCS. We justify the use of prefix-sum oracles for two reasons. First, we note that creating the prefix-sum oracle only incurs a constant overhead in the RLE compression. Second, we show that, without the oracles, there is a Ω(n/log2n) lower bound on the quantum query complexity of finding the LCS given two RLE strings due to a reduction of PARITY to the problem. With a small modification, our algorithm also solves the longest repeated substring problem for an RLE string.
We give a sublinear quantum algorithm for the longest common substring (LCS) problem on the run-length encoded (RLE) inputs, under the assumption that the prefix-sums of the runs are given. Our algorithm costs O~(n5/6)⋅O(polylog(n~)) time, where n and n~ are the encoded and decoded length of the inputs, respectively. We justify the use of the prefix-sum oracles by showing that, without the oracles, there is a Ω(n/log2n) lower-bound on the quantum query complexity of finding LCS given two RLE strings due to a reduction of PARITY to the problem.
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≪d≪n was not fully understood. We show that the complexity of LCS with threshold d smoothly interpolates between the two extreme cases up to no(1) factors: LCS with threshold d has a quantum algorithm in n2/3+o(1)/d1/6 query complexity and time complexity, and requires at least Ω(n2/3/d1/6) quantum query complexity. Our result improves upon previous upper bounds O~(min{n/d1/2,n2/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 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 k3/4n1/2+o(1) query complexity and O~(kn1/2) time complexity.
Longest common substring (LCS) is an important text processing problem, which has recently been investigated in the quantum query model. The decision 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≪d≪n was not fully understood. We show that the complexity of LCS with threshold d smoothly interpolates between the two extreme cases up to no(1) factors: — LCS with threshold d has a quantum algorithm in n2/3+o(1)/d1/6 query complexity and time complexity, and requires at least Ω(n2/3/d1/6) quantum query complexity. Our result improves upon previous upper bounds O(min{n/d1/2,n2/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 O(τ1/2+o(1)) time. Our quantum string synchronizing set also yields a near-optimal LCE data structure in the quantum setting. 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 et al. (FOCS 2020), we obtain: — k -mismatch matching has a quantum algorithm with k3/4n1/2+o(1) query complexity and O(kn1/2) time complexity. We also observe a non-matching quantum query lower bound of Ω(kn) .
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 ≪ d ≪ n was not fully understood.
The Longest Common Substring (LCS) and Longest Palindromic Substring (LPS) problems are fundamental challenges in string processing, traditionally solved in linear time using classical computation through suffix trees. Recent breakthroughs by Le Gall and Seddighin [1] introduced sublinear quantum query algorithms, while Akmal and Jin [2] further improved the LCS complexity to O ˜ ( n 2 / 3 ) . While these results are remarkable in the quantum query model , their practical implementation on real quantum hardware remains elusive. In this paper, we bridge this gap by presenting the first O ˜ ( n ) quantum algorithms for both LCS and LPS in the circuit model of computation . Our circuits are explicitly constructed and analyzed in terms of size and depth, achieving polylogarithmic overheads while preserving the O ˜ ( n ) depth bound. This provides, for the first time, concrete circuit-level blueprints and resource estimates for quantum solutions to LCS and LPS.
We study quantum algorithms for several fundamental string problems, including Longest Common Substring, Lexicographically Minimal String Rotation, and Longest Square Substring. These problems have been widely studied in the stringology literature since the 1970s, and are known to be solvable by near-linear time classical algorithms. In this work, we give quantum algorithms for these problems with near-optimal query complexities and time complexities. Specifically, we show that: - Longest Common Substring can be solved by a quantum algorithm in O~(n2/3) time, improving upon the recent O~(n5/6)-time algorithm by Le Gall and Seddighin (2020). Our algorithm uses the MNRS quantum walk framework, together with a careful combination of string synchronizing sets (Kempa and Kociumaka, 2019) and generalized difference covers. - Lexicographically Minimal String Rotation can be solved by a quantum algorithm in n1/2+o(1) time, improving upon the recent O~(n3/4)-time algorithm by Wang and Ying (2020). We design our algorithm by first giving a new classical divide-and-conquer algorithm in near-linear time based on exclusion rules, and then speeding it up quadratically using nested Grover search and quantum minimum finding. - Longest Square Substring can be solved by a quantum algorithm in O~(n) time. Our algorithm is an adaptation of the algorithm by Le Gall and Seddighin (2020) for the Longest Palindromic Substring problem, but uses additional techniques to overcome the difficulty that binary search no longer applies. Our techniques naturally extend to other related string problems, such as Longest Repeated Substring, Longest Lyndon Substring, and Minimal Suffix.