Quantum Pattern Matching in Generalised Degenerate Strings

Quantum Physics [Submitted on 17 Mar 2026] Quantum Pattern Matching in Generalised Degenerate Strings Massimo Equi, Md Rabiul Islam Khan, Veli Mäkinen A degenerate string is a sequence of sets of characters. A generalized degenerate (GD) string extends this notion to the sequence of sets of strings, where strings of the same set are of equal length. Finding an exact match for a pattern string inside a GD string can be done in O(mn+N) time (Ascone et al., WABI 2024), where m is the pattern length, n is the number of strings and N the total length of strings constituting the GD string. We modify this algorithm to work under a quantum model of computation, achieving running time \tilde{O}(\sqrt{mnN}). Subjects: Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS) Cite as: arXiv:2603.16297 [quant-ph]   (or arXiv:2603.16297v1 [quant-ph] for this version)   https://doi.org/10.48550/arXiv.2603.16297 Focus to learn more Submission history From: Massimo Equi [view email] [v1] Tue, 17 Mar 2026 09:35:02 UTC (58 KB) Access Paper: HTML (experimental) view license Current browse context: quant-ph < prev   |   next > new | recent | 2026-03 Change to browse by: cs cs.DS References & Citations INSPIRE HEP NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)