In computer science, a degenerate string is a sequence of sets of characters, while a generalized degenerate (GD) string extends this concept to sequences of sets of strings, where strings in the same set have equal lengths. According to the study by Ascone et al. at WABI 2024, finding an exact match for a pattern string within a GD string has a time complexity of $O(mn+N)$, where $m$ is the pattern length, $n$ is the number of strings, and $N$ is the total length of strings constituting the GD string. This is currently the best classical algorithm available, with no matching lower bounds proven, either unconditional or conditional.
We propose a quantum algorithm that achieves a running time of $\tilde{O}(\sqrt{mnN})$, surpassing the current best classical solution. To our knowledge, this is the first quantum algorithm proposed in the context of GD strings. We present our results starting from the framework of classical parallel computing, which we believe makes them intuitive to understand and potentially easy to generalize to other similar structures.
Blogger's Review: This paper presents a quantum algorithm that significantly improves upon classical methods for pattern matching in generalized degenerate strings, indicating the potential of quantum computing in string processing. It is worth monitoring its performance and scalability in practical applications.