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.
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.
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) .
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.
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.
Longest Common Substring and Longest Palindromic Substring in O~(n) Time
The Longest Common Substring (LCS) and Longest Palindromic Substring (LPS) are classical problems in computer science, representing fundamental challenges in string processing. Both problems can be solved in linear time using a classical model of computation, by means of very similar algorithms, both relying on the use of suffix trees. Very recently, two sublinear algorithms for LCS and LPS in the quantum query model have been presented by Le Gall and Seddighin~\cite{GallS23}, requiring O~(n5/6) and O~(n) queries, respectively. However, while the query model is fascinating from a theoretical standpoint, its practical applicability becomes limited when it comes to crafting algorithms meant for actual execution on real hardware. In this paper we present, for the first time, a O~(n) quantum algorithm for both LCS and LPS working in the circuit model of computation. Our solutions are simpler than previous ones and can be easily translated into quantum procedures. We also present actual implementations of the two algorithms as quantum circuits working in O(nlog5(n)) and O(nlog4(n)) time, respectively.