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

arXiv:2303.03569 · IEEE Transactions on Quantum Engineering

Quantum Algorithm for Position Weight Matrix Matching

Koichi Miyamoto, Naoki Yamamoto, Yasubumi Sakakibara

Published Jan 1, 2023• 3 citations
arXivHTMLPDF

Abstract

We propose two quantum algorithms for a problem in bioinformatics, position weight matrix (PWM) matching, which aims to find segments (sequence motifs) in a biological sequence such as DNA and protein that have high scores defined by the PWM and are thus of informational importance related to biological function. The two proposed algorithms, the naive iteration method and the Monte-Carlo-based method, output matched segments, given the oracular accesses to the entries in the biological sequence and the PWM. The former uses quantum amplitude amplification (QAA) for sequence motif search, resulting in the query complexity scaling on the sequence lengthn, the sequence motif lengthmand the number of the PWMsKas$O(m\sqrt{Kn})$, which means speedup over existing classical algorithms with respect tonandK. The latter also uses QAA, and further, quantum Monte Carlo integration for segment score calculation, instead of iteratively operating quantum circuits for arithmetic in the naive iteration method; then it provides the additional speedup with respect tomin some situation. As a drawback, these algorithms use quantum random access memories and their initialization takesO(n) time. Nevertheless, our algorithms keep the advantage especially when we search matches in a sequence for many PWMs in parallel.

DOI
10.1109/tqe.2023.3293562

Related papers

Fast quantum search algorithms in protein sequence comparisons: Quantum bioinformatics

Lloyd C. L. Hollenberg

Quantum search algorithms are considered in the context of protein sequence comparison in bioinformatics. Given a sample protein sequence of length m (i.e., m residues), the problem considered is to find an optimal match in a large database containing N residues. Initially, Grover's quantum search algorithm is applied to a simple illustrative case-namely, where the database forms a complete set of states over the 2(m) basis states of a m qubit register, and thus is known to contain the exact sequence of interest. This example demonstrates explicitly the typical O(square root of [N]) speedup on the classical O(N) requirements. An algorithm is then presented for the (more realistic) case where the database may contain repeat sequences, and may not necessarily contain an exact match to the sample sequence. In terms of minimizing the Hamming distance between the sample sequence and the database subsequences the algorithm finds an optimal alignment, in O(square root of [N]) steps, by employing an extension of Grover's algorithm, due to Boyer et al. for the case when the number of matches is not a priori known.

arXiv:quant-ph/0002076•Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•Nov 1, 2000•33 citations

Quantum‐based exact pattern matching algorithms for biological sequences

Kapil Kumar Soni, Akhtar Rasool

In computational biology, desired patterns are searched in large text databases, and an exact match is preferable. Classical benchmark algorithms obtain competent solutions for pattern matching in time, whereas quantum algorithm design is based on Grover's method, which completes the search in time. This paper briefly explains existing quantum algorithms and defines their processing limitations. Our initial work overcomes existing algorithmic constraints by proposing the quantum-based combined exact (QBCE) algorithm for the pattern-matching problem to process exact patterns. Next, quantum random access memory (QRAM) processing is discussed, and based on it, we propose the QRAM processing-based exact (QPBE) pattern-matching algorithm. We show that to find all occurrences of a pattern, the best case time complexities of the QBCE and QPBE algorithms are , and the exceptional worst case is bounded by . Thus, the proposed quantum algorithms achieve computational speedup. Our work is proved mathematically and validated with simulation, and complexity analysis demonstrates that our quantum algorithms are better than existing pattern-matching methods.

ETRI Journal•May 11, 2021•13 citations

Quantum-effective exact multiple patterns matching algorithms for biological sequences

Kapil Kumar Soni, Akhtar Rasool

This article presents efficient quantum solutions for exact multiple pattern matching to process the biological sequences. The classical solution takes Ο ( mN ) time for matching m patterns over N sized text database. The quantum search mechanism is a core for pattern matching, as this reduces time complexity and achieves computational speedup. Few quantum methods are available for multiple pattern matching, which executes search oracle for each pattern in successive iterations. Such solutions are likely acceptable because of classical equivalent quantum designs. However, these methods are constrained with the inclusion of multiplicative factor m in their complexities. An optimal quantum design is to execute multiple search oracle in parallel on the quantum processing unit with a single-core that completely removes the multiplicative factor m , however, this method is impractical to design. We have no effective quantum solutions to process multiple patterns at present. Therefore, we propose quantum algorithms using quantum processing unit with C quantum cores working on shared quantum memory. This quantum parallel design would be effective for searching all t exact occurrences of each pattern. To our knowledge, no attempts have been made to design multiple pattern matching algorithms on quantum multicore processor. Thus, some quantum remarkable exact single pattern matching algorithms are enhanced here with their equivalent versions, namely enhanced quantum memory processing based exact algorithm and enhanced quantum-based combined exact algorithm for multiple pattern matching. Our quantum solutions find all t exact occurrences of each pattern inside the biological sequence in $O((m/C)\sqrt{N})$ and $O((m/C)\sqrt{t})$ time complexities. This article shows the hybrid simulation of quantum algorithms to validate quantum solutions. Our theoretical–experimental results justify the significant improvements that these algorithms outperform over the existing classical solutions and are proven effective in quantum counterparts.

PeerJ Computer Science•May 12, 2022•6 citations

Quantum implementation of multi-pattern string matching for 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 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.

•Dec 23, 2025•0 citations

Title: Bio-Information Quantum Algorithm

Jincheng Zhang

This paper explores the potential of quantum algorithms to revolutionize bioinformatics, particularly in genomic analysis, protein structure prediction, and drug discovery. The core concept centers on leveraging the inherent information richness within biological datasets – specifically, DNA sequences and protein structures – to create novel quantum computational approaches. We propose a new algorithmic framework based on constructing quantum circuits directly from biological data structures, aiming to significantly accelerate computationally intensive tasks. The study emphasizes the transformative impact of this approach, focusing on the unique advantages conferred by biological information within the quantum realm. This research addresses the limitations of existing quantum computing approaches by integrating biological data into the core algorithm design.

•Aug 29, 2026•0 citations

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
We propose two quantum algorithms for a problem in bioinformatics, position weight matrix (PWM) matching, which aims to find segments (sequence motifs) in a biological sequence such as DNA and protein that have high scores defined by the PWM and are thus of informational importance related to biological function. The two proposed algorithms, the naive iteration method and the Monte-Carlo-based method, output matched segments, given the oracular accesses to the entries in the biological sequence and the PWM. The former uses quantum amplitude amplification (QAA) for sequence motif search, resulting in the query complexity scaling on the sequence lengthn, the sequence motif lengthmand the number of the PWMsKasO(mKn)O(m\sqrt{Kn})O(mKn​), which means speedup over existing classical algorithms with respect tonandK. The latter also uses QAA, and further, quantum Monte Carlo integration for segment score calculation, instead of iteratively operating quantum circuits for arithmetic in the naive iteration method; then it provides the additional speedup with respect tomin some situation. As a drawback, these algorithms use quantum random access memories and their initialization takesO(n) time. Nevertheless, our algorithms keep the advantage especially when we search matches in a sequence for many PWMs in parallel.
Quantum search algorithms are considered in the context of protein sequence comparison in bioinformatics. Given a sample protein sequence of length m (i.e., m residues), the problem considered is to find an optimal match in a large database containing N residues. Initially, Grover's quantum search algorithm is applied to a simple illustrative case-namely, where the database forms a complete set of states over the 2(m) basis states of a m qubit register, and thus is known to contain the exact sequence of interest. This example demonstrates explicitly the typical O(square root of [N]) speedup on the classical O(N) requirements. An algorithm is then presented for the (more realistic) case where the database may contain repeat sequences, and may not necessarily contain an exact match to the sample sequence. In terms of minimizing the Hamming distance between the sample sequence and the database subsequences the algorithm finds an optimal alignment, in O(square root of [N]) steps, by employing an extension of Grover's algorithm, due to Boyer et al. for the case when the number of matches is not a priori known.
In computational biology, desired patterns are searched in large text databases, and an exact match is preferable. Classical benchmark algorithms obtain competent solutions for pattern matching in time, whereas quantum algorithm design is based on Grover's method, which completes the search in time. This paper briefly explains existing quantum algorithms and defines their processing limitations. Our initial work overcomes existing algorithmic constraints by proposing the quantum-based combined exact (QBCE) algorithm for the pattern-matching problem to process exact patterns. Next, quantum random access memory (QRAM) processing is discussed, and based on it, we propose the QRAM processing-based exact (QPBE) pattern-matching algorithm. We show that to find all occurrences of a pattern, the best case time complexities of the QBCE and QPBE algorithms are , and the exceptional worst case is bounded by . Thus, the proposed quantum algorithms achieve computational speedup. Our work is proved mathematically and validated with simulation, and complexity analysis demonstrates that our quantum algorithms are better than existing pattern-matching methods.
This article presents efficient quantum solutions for exact multiple pattern matching to process the biological sequences. The classical solution takes Ο ( mN ) time for matching m patterns over N sized text database. The quantum search mechanism is a core for pattern matching, as this reduces time complexity and achieves computational speedup. Few quantum methods are available for multiple pattern matching, which executes search oracle for each pattern in successive iterations. Such solutions are likely acceptable because of classical equivalent quantum designs. However, these methods are constrained with the inclusion of multiplicative factor m in their complexities. An optimal quantum design is to execute multiple search oracle in parallel on the quantum processing unit with a single-core that completely removes the multiplicative factor m , however, this method is impractical to design. We have no effective quantum solutions to process multiple patterns at present. Therefore, we propose quantum algorithms using quantum processing unit with C quantum cores working on shared quantum memory. This quantum parallel design would be effective for searching all t exact occurrences of each pattern. To our knowledge, no attempts have been made to design multiple pattern matching algorithms on quantum multicore processor. Thus, some quantum remarkable exact single pattern matching algorithms are enhanced here with their equivalent versions, namely enhanced quantum memory processing based exact algorithm and enhanced quantum-based combined exact algorithm for multiple pattern matching. Our quantum solutions find all t exact occurrences of each pattern inside the biological sequence in O((m/C)N)O((m/C)\sqrt{N})O((m/C)N​) and O((m/C)t)O((m/C)\sqrt{t})O((m/C)t​) time complexities. This article shows the hybrid simulation of quantum algorithms to validate quantum solutions. Our theoretical–experimental results justify the significant improvements that these algorithms outperform over the existing classical solutions and are proven effective in quantum counterparts.
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.
This paper explores the potential of quantum algorithms to revolutionize bioinformatics, particularly in genomic analysis, protein structure prediction, and drug discovery. The core concept centers on leveraging the inherent information richness within biological datasets – specifically, DNA sequences and protein structures – to create novel quantum computational approaches. We propose a new algorithmic framework based on constructing quantum circuits directly from biological data structures, aiming to significantly accelerate computationally intensive tasks. The study emphasizes the transformative impact of this approach, focusing on the unique advantages conferred by biological information within the quantum realm. This research addresses the limitations of existing quantum computing approaches by integrating biological data into the core algorithm design.
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.