A foundational quantum framework for multi-pattern string matching in k-mer detection

The exponential growth of publicly available genomic data has created unprecedented opportunities for sequence-based discovery. Locating specific k-mers is fundamental to diverse applications, including metagenomic classification, pathogen and cancer detection, and variant calling yet efficient identification of multiple k-mer patterns across large sequencing data and massive databases remains a significant computational challenge.

We implement two quantum algorithms for DNA multi-pattern string matching for k-mer detection, leveraging Grover's amplitude amplification under the idealized quantum random access memory (QRAM) framework. The first algorithm uses an enumerate-m oracle that sequentially checks a loaded text substring against all m patterns achieving O (√S) query complexity for S text positions but requiring O (m · L) work per oracle call. The second algorithm employs nested Grover search with an outer loop over text positions and an inner loop over pattern space, reducing oracle complexity to O(L) while performing O (√S · √m) in total. These asymptotic gains highlight the potential advantages that could be unlocked by future large-scale, low-noise QRAM architectures, positioning our results as a promising proof-of-concept foundation.

This work introduces two quantum implementations of multi-pattern string matching tailored for k-mer detection. Leveraging quantum parallelism and Grover-inspired search primitives, our methods accelerate dictionary-based pattern matching, particularly in contexts involving large sequences, such as genomic data, and extensive pattern sets.

While implementation challenges such as QRAM overhead remain, this study demonstrates both the promise and current limitations of quantum-enhanced string matching, establishing a foundational step toward quantum readiness in bioinformatics.

To maximize accessibility and practical use, we provide our methodology at: https://github.com/Georgakopoulos-Soares-lab/quantum-multi-motif-finder.