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

Frontiers in Bioinformatics

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

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

Published Jun 12, 2026• 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, 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.

DOI
10.3389/fbinf.2026.1802517

Related papers

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

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.

arXiv:1909.05563•Electronics•Oct 7, 2021•43 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•43 citations

An inspectable Grover algorithm-based amplitude-amplification workflow for k-mer discovery and motif scanning with genomic coordinate traceability

Akshay Uttarkar, Vidya Niranjan

Abstract Motif discovery and motif scanning remain core primitives in genomics, but both tasks face combinatorial growth as k-mer length increases and as mismatch-tolerant searches expand the candidate space. In this work, we present MotifQu, a Python package and command-line tool that maps two common motif-analysis workflows—(i) scanning a genome for a user-specified consensus motif and (ii) de novo discovery of recurrent k-mers above a user-defined count threshold—onto Grover-style amplitude amplification circuits executed reproducibly via Qiskit Aer statevector simulation. We evaluate MotifQu on the SARS-CoV-2 reference contig (29,903 bp) and S. cerevisiae S288C reference genome, where the classical census identifies strongly non-uniform motif frequencies dominated by A/T-rich 5-mers and returns explicit coordinate lists across the full genome span. We further execute the same logical 10-qubit search on IBM hardware showing that while end- to-end execution is feasible, transpilation-induced circuit depth and entangling-gate volume produce a diffuse measurement distribution whose probabilities remain close to the uniform 1/1024 scale, limiting observable amplitude concentration under current NISQ constraints. Finally, we demonstrate the full discovery workflow on the S. cerevisiae S288C reference genome (12,157,105 bp) to illustrate search results (ranked motifs, probability summaries, circuit diagrams, and position plots) and to highlight the regime where a large, marked set reduces the sharpness of Grover amplification.

•Oct 13, 2026•0 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•17 citations

Quantum Pattern Matching for Early Prediction of Blood Culture Positivity: A Theoretical Biomedical Framework

Matías Alfredo Gacitúa Ruiz

Abstract Rapid identification of bloodstream infections is critical for reducing sepsis-related mortality, as each hour of delay in antibiotic administration increases patient risk. Current automated blood culture systems depend on threshold-based $\text{CO}_2$ monitoring, typically requiring 12–18 hours before declaring positivity. While subtle kinetic fluctuations often emerge within the first 1–4 hours, distinguishing these early signals from noise requires rigorous comparison against vast datasets of known growth signatures. In this biomedical engineering proposal, we introduce a quantum-enhanced framework to accelerate this early identification process. Instead of simple thresholding, the problem is modeled as a nearest-neighbor search against a massive library of $N$ reference kinetic patterns (representing various pathogens and growth conditions). We propose a hybrid pipeline where patient sensor data is compared against a quantum superposition of these reference patterns. By utilizing Grover’s amplitude amplification , the system can identify the optimal matching pattern in $O(\sqrt{N})$ iterations, offering a quadratic speed-up over the classical $O(N)$ linear search required for exhaustive database matching. This theoretical approach addresses the computational bottleneck of real-time diagnostics against large-scale libraries, potentially enabling a reproducible “early-warning” layer hours before standard positivity. This study reports multi-seed simulation averages with $95\%$ confidence intervals to validate the search mechanism and outlines a roadmap for integrating quantum algorithms into clinical microbiology workflows.

•Dec 1, 2025•0 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, 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 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 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.
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.
Abstract Motif discovery and motif scanning remain core primitives in genomics, but both tasks face combinatorial growth as k-mer length increases and as mismatch-tolerant searches expand the candidate space. In this work, we present MotifQu, a Python package and command-line tool that maps two common motif-analysis workflows—(i) scanning a genome for a user-specified consensus motif and (ii) de novo discovery of recurrent k-mers above a user-defined count threshold—onto Grover-style amplitude amplification circuits executed reproducibly via Qiskit Aer statevector simulation. We evaluate MotifQu on the SARS-CoV-2 reference contig (29,903 bp) and S. cerevisiae S288C reference genome, where the classical census identifies strongly non-uniform motif frequencies dominated by A/T-rich 5-mers and returns explicit coordinate lists across the full genome span. We further execute the same logical 10-qubit search on IBM hardware showing that while end- to-end execution is feasible, transpilation-induced circuit depth and entangling-gate volume produce a diffuse measurement distribution whose probabilities remain close to the uniform 1/1024 scale, limiting observable amplitude concentration under current NISQ constraints. Finally, we demonstrate the full discovery workflow on the S. cerevisiae S288C reference genome (12,157,105 bp) to illustrate search results (ranked motifs, probability summaries, circuit diagrams, and position plots) and to highlight the regime where a large, marked set reduces the sharpness of Grover amplification.
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.
Abstract Rapid identification of bloodstream infections is critical for reducing sepsis-related mortality, as each hour of delay in antibiotic administration increases patient risk. Current automated blood culture systems depend on threshold-based CO2\text{CO}_2CO2​ monitoring, typically requiring 12–18 hours before declaring positivity. While subtle kinetic fluctuations often emerge within the first 1–4 hours, distinguishing these early signals from noise requires rigorous comparison against vast datasets of known growth signatures. In this biomedical engineering proposal, we introduce a quantum-enhanced framework to accelerate this early identification process. Instead of simple thresholding, the problem is modeled as a nearest-neighbor search against a massive library of NNN reference kinetic patterns (representing various pathogens and growth conditions). We propose a hybrid pipeline where patient sensor data is compared against a quantum superposition of these reference patterns. By utilizing Grover’s amplitude amplification , the system can identify the optimal matching pattern in O(N)O(\sqrt{N})O(N​) iterations, offering a quadratic speed-up over the classical O(N)O(N)O(N) linear search required for exhaustive database matching. This theoretical approach addresses the computational bottleneck of real-time diagnostics against large-scale libraries, potentially enabling a reproducible “early-warning” layer hours before standard positivity. This study reports multi-seed simulation averages with 95%95\%95% confidence intervals to validate the search mechanism and outlines a roadmap for integrating quantum algorithms into clinical microbiology workflows.