A sublinear time quantum algorithm for longest common substring problem between run-length encoded strings

Abstract

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 $\tilde{O}(n^{5/6})\cdot O(\mathrm{polylog}(\tilde{n}))$time,where$n$and$\tilde{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 $\Omega (n/{\log }^{2}n)$ lower-bound on the quantum query complexity of finding LCS given two RLE strings due to a reduction of $\mathsf{PARITY}$ to the problem.