Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum implementation of multi-pattern string matching for k-mer detection

Christos Papalitsas, Ioannis Mouratidis, Michail Patsakis, Evangelos Stogiannos, Ilias Georgakopoulos‐Soares, Grigorios Koulouras

Published Dec 23, 2025• 0 citations
Publisher

Abstract

Motivation: 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. Method: We implement two quantum algorithms for DNA multi pattern string matching for k-mer detection based on Grover's amplitude amplification with quantum random access memory (QRAM). 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. Results: We present 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. Conclusions: 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.

DOI
10.64898/2025.12.21.695808

Related papers

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

Christos Papalitsas, Ioannis Mouratidis, Michail Patsakis +3 more

Motivation: 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. Method: 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. Results: 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. Conclusion: 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. Availability and Implementation: To maximize accessibility and practical use, we provide our methodology at: https://github.com/Georgakopoulos-Soares-lab/quantum-multi-motif-finder.

Frontiers in Bioinformatics•Jun 12, 2026•0 citations

Grover search revisited: Application to image pattern matching

Hiroyuki Tezuka, Kouhei Nakaji, Takahiko Satoh +1 more

The landmark Grover algorithm for amplitude amplification serves as an essential subroutine in various types of quantum algorithms, with guaranteed quantum speedup in query complexity. However, there has been no proposal to realize the original motivating application of the algorithm, i.e., the database search or more broadly the pattern matching in a practical setting, mainly due to the technical difficulty in efficiently implementing the data loading and amplitude amplification processes. In this paper, we propose a quantum algorithm that approximately executes the entire Grover database search or pattern matching algorithm. The key idea is to use the recently proposed approximate amplitude encoding method on a shallow quantum circuit, together with the easily implementable inversion-test operation for realizing the projected quantum state having similarity to the query data, followed by the amplitude amplification operation that is independent to the target data index. We provide a thorough demonstration of the algorithm in the problem of image pattern matching.

arXiv:2108.10854•Physical Review A•Mar 24, 2022•35 citations

QiBAM: Approximate Sub-String Index Search on Quantum Accelerators Applied to DNA Read Alignment

Aritra Sarkar, Zaid Al-Ars, Carmen G. Almudéver +1 more

With small-scale quantum processors transitioning from experimental physics labs to industrial products, these processors in a few years are expected to scale up and be more robust for efficiently computing important algorithms in various fields. In this paper, we propose a quantum algorithm to address the challenging field of data processing for genome sequence reconstruction. This research describes an architecture-aware implementation of a quantum algorithm for sub-sequence alignment. A new algorithm named QiBAM (quantum indexed bidirectional associative memory) is proposed, which uses approximate pattern-matching based on Hamming distances. QiBAM extends the Grover’s search algorithm in two ways, allowing: (1) approximate matches needed for read errors in genomics, and (2) a distributed search for multiple solutions over the quantum encoding of DNA sequences. This approach gives a quadratic speedup over the classical algorithm. A full implementation of the algorithm is provided and verified using the OpenQL compiler and QX Simulator framework. Our implementation represents a first exploration towards a full-stack quantum accelerated genome sequencing pipeline design.

Electronics•Oct 7, 2021•20 citations

Quantum Pattern Matching

Paulo Mateus, Yasser Omar

We propose a quantum algorithm for closest pattern matching which allows us to search for as many distinct patterns as we wish in a given string (database), requiring a query function per symbol of the pattern alphabet. This represents a significant practical advantage when compared to Grover's search algorithm as well as to other quantum pattern matching methods, which rely on building specific queries for particular patterns. Our method makes arbitrary searches on long static databases much more realistic and implementable. Our algorithm, inspired by Grover's, returns the position of the closest substring to a given pattern of size $M$ with non-negligible probability in $O(\sqrt{N})$ queries, where $N$ is the size of the string. Furthermore, we give the full recipe to implement our algorithm (together with its total circuit complexity), thus offering an oracle-based quantum algorithm ready to be implemented.

arXiv:quant-ph/0508237•Aug 31, 2005•8 citations

Convergence of Bioinformatics and Quantum Computing: A Novel Framework for Genome Sequencing Acceleration

Jun‐Han Huang, Fabrizio Falchi, Eneko Osaba

The exponential growth of genomic data presents significant computational challenges in the field of bioinformatics, particularly in genome sequencing. Traditional methods struggle to meet the increasing demand for speed, accuracy, and efficiency. This paper introduces a novel framework that leverages quantum computing to accelerate genome sequencing processes. The proposed framework integrates quantum algorithms, such as Grover's search and quantum Fourier transform, with classical bioinformatics techniques to optimize key tasks, including sequence alignment, variant detection, and large-scale data analysis. By exploiting the inherent parallelism and computational power of quantum systems, the framework achieves substantial reductions in processing time while maintaining high accuracy. A case study on large-scale genomic datasets demonstrates the framework's ability to outperform state-of-the-art classical approaches, particularly in handling complex and large-scale sequencing tasks. Furthermore, this research highlights the potential of quantum computing in advancing bioinformatics, paving the way for more efficient and scalable solutions to address the computational bottlenecks of modern genomics. The implications of this interdisciplinary approach extend beyond genomics, offering transformative possibilities in data-driven life sciences.

International Journal of Computer Engineering in Research Trends•Aug 31, 2024•0 citations

An algorithm for DNA read alignment on quantum accelerators

Aritra Sarkar, Zaid Al-Ars, Carmen G. Almudéver +1 more

With small-scale quantum processors transitioning from experimental physics labs to industrial products, these processors allow us to efficiently compute important algorithms in various fields. In this paper, we propose a quantum algorithm to address the challenging field of big data processing for genome sequence reconstruction. This research describes an architecture-aware implementation of a quantum algorithm for sub-sequence alignment. A new algorithm named QiBAM (quantum indexed bidirectional associative memory) is proposed, that uses approximate pattern-matching based on Hamming distances. QiBAM extends the Grover's search algorithm in two ways to allow for: (1) approximate matches needed for read errors in genomics, and (2) a distributed search for multiple solutions over the quantum encoding of DNA sequences. This approach gives a quadratic speedup over the classical algorithm. A full implementation of the algorithm is provided and verified using the OpenQL compiler and QX simulator framework. This represents a first exploration towards a full-stack quantum accelerated genome sequencing pipeline design. The open-source implementation can be found on https://github.com/prince-ph0en1x/QAGS.

arXiv:1909.05563•Sep 12, 2019•15 citations
Motivation: 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. Method: We implement two quantum algorithms for DNA multi pattern string matching for k-mer detection based on Grover's amplitude amplification with quantum random access memory (QRAM). 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. Results: We present 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. Conclusions: 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.
Motivation: 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. Method: 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. Results: 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. Conclusion: 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. Availability and Implementation: To maximize accessibility and practical use, we provide our methodology at: https://github.com/Georgakopoulos-Soares-lab/quantum-multi-motif-finder.
The landmark Grover algorithm for amplitude amplification serves as an essential subroutine in various types of quantum algorithms, with guaranteed quantum speedup in query complexity. However, there has been no proposal to realize the original motivating application of the algorithm, i.e., the database search or more broadly the pattern matching in a practical setting, mainly due to the technical difficulty in efficiently implementing the data loading and amplitude amplification processes. In this paper, we propose a quantum algorithm that approximately executes the entire Grover database search or pattern matching algorithm. The key idea is to use the recently proposed approximate amplitude encoding method on a shallow quantum circuit, together with the easily implementable inversion-test operation for realizing the projected quantum state having similarity to the query data, followed by the amplitude amplification operation that is independent to the target data index. We provide a thorough demonstration of the algorithm in the problem of image pattern matching.
With small-scale quantum processors transitioning from experimental physics labs to industrial products, these processors in a few years are expected to scale up and be more robust for efficiently computing important algorithms in various fields. In this paper, we propose a quantum algorithm to address the challenging field of data processing for genome sequence reconstruction. This research describes an architecture-aware implementation of a quantum algorithm for sub-sequence alignment. A new algorithm named QiBAM (quantum indexed bidirectional associative memory) is proposed, which uses approximate pattern-matching based on Hamming distances. QiBAM extends the Grover’s search algorithm in two ways, allowing: (1) approximate matches needed for read errors in genomics, and (2) a distributed search for multiple solutions over the quantum encoding of DNA sequences. This approach gives a quadratic speedup over the classical algorithm. A full implementation of the algorithm is provided and verified using the OpenQL compiler and QX Simulator framework. Our implementation represents a first exploration towards a full-stack quantum accelerated genome sequencing pipeline design.
We propose a quantum algorithm for closest pattern matching which allows us to search for as many distinct patterns as we wish in a given string (database), requiring a query function per symbol of the pattern alphabet. This represents a significant practical advantage when compared to Grover's search algorithm as well as to other quantum pattern matching methods, which rely on building specific queries for particular patterns. Our method makes arbitrary searches on long static databases much more realistic and implementable. Our algorithm, inspired by Grover's, returns the position of the closest substring to a given pattern of size MMM with non-negligible probability in O(N)O(\sqrt{N})O(N​) queries, where NNN is the size of the string. Furthermore, we give the full recipe to implement our algorithm (together with its total circuit complexity), thus offering an oracle-based quantum algorithm ready to be implemented.
The exponential growth of genomic data presents significant computational challenges in the field of bioinformatics, particularly in genome sequencing. Traditional methods struggle to meet the increasing demand for speed, accuracy, and efficiency. This paper introduces a novel framework that leverages quantum computing to accelerate genome sequencing processes. The proposed framework integrates quantum algorithms, such as Grover's search and quantum Fourier transform, with classical bioinformatics techniques to optimize key tasks, including sequence alignment, variant detection, and large-scale data analysis. By exploiting the inherent parallelism and computational power of quantum systems, the framework achieves substantial reductions in processing time while maintaining high accuracy. A case study on large-scale genomic datasets demonstrates the framework's ability to outperform state-of-the-art classical approaches, particularly in handling complex and large-scale sequencing tasks. Furthermore, this research highlights the potential of quantum computing in advancing bioinformatics, paving the way for more efficient and scalable solutions to address the computational bottlenecks of modern genomics. The implications of this interdisciplinary approach extend beyond genomics, offering transformative possibilities in data-driven life sciences.
With small-scale quantum processors transitioning from experimental physics labs to industrial products, these processors allow us to efficiently compute important algorithms in various fields. In this paper, we propose a quantum algorithm to address the challenging field of big data processing for genome sequence reconstruction. This research describes an architecture-aware implementation of a quantum algorithm for sub-sequence alignment. A new algorithm named QiBAM (quantum indexed bidirectional associative memory) is proposed, that uses approximate pattern-matching based on Hamming distances. QiBAM extends the Grover's search algorithm in two ways to allow for: (1) approximate matches needed for read errors in genomics, and (2) a distributed search for multiple solutions over the quantum encoding of DNA sequences. This approach gives a quadratic speedup over the classical algorithm. A full implementation of the algorithm is provided and verified using the OpenQL compiler and QX simulator framework. This represents a first exploration towards a full-stack quantum accelerated genome sequencing pipeline design. The open-source implementation can be found on https://github.com/prince-ph0en1x/QAGS.