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:2403.17979 · The Journal of Computational Science Education

Preliminary Results of Applying Modified MSA Algorithm on Quantum Annealers (MAQ)

M.W. Lee

Published Jul 1, 2023• 2 citations
arXivHTMLPDF

Abstract

We propose a modified MSA algorithm on quantum annealers with applications in areas of bioinformatics and genetic sequencing.To understand the human genome, researchers compare extensive sets of these genetic sequences -or their protein counterparts -to identify patterns.This comparison begins with the alignment of the set of (multiple) sequences.However, this alignment problem is considered nondeterministically-polynomial time complete and, thus, current classical algorithms at best rely on brute force or heuristic methods to find solutions.Quantum annealing algorithms are able to bypass this need for sheer brute force due to their use of quantum mechanical properties.However, due to the novelty of these algorithms, many are rudimentary in nature and limited by hardware restrictions.We apply progressive alignment techniques to modify annealing algorithms, achieving a linear reduction in spin usage whilst introducing more complex heuristics to the algorithm.This opens the door for further exploration into quantum computing-based bioinformatics, potentially allowing for a deeper understanding of disease detection and monitoring.

DOI
10.22369/issn.2153-4136/14/1/5

Related papers

Quantum Biology-Inspired Bioinformatics Algorithms

Jincheng Zhang

This paper explores the application of principles from quantum biology to design novel bioinformatics algorithms. Traditional bioinformatics relies heavily on classical computational models, often neglecting the potential influence of quantum effects observed within biological systems. This research proposes a framework that leverages these quantum phenomena, specifically focusing on quantum tunneling, superposition, and entanglement, to address complex challenges in biological data analysis. The core mechanism involves simulating quantum effects during processes like protein folding and DNA sequence recognition, and utilizing quantum algorithms – such as Grover's algorithm and quantum annealing – to optimize sequence data analysis. We present a conceptual approach to formulating biological problems as quantum computing problems, offering a fundamentally new perspective for bioinformatics. The potential impact of this approach lies in developing more efficient and accurate algorithms for tasks including genomic sequence alignment, protein structure prediction, and drug discovery. This work aims to bridge the gap between quantum mechanics and biology, paving the way for a new era of bioinformatics driven by quantum principles. ---

•Aug 29, 2026•0 citations

A biological sequence comparison algorithm using quantum computers

Büsra Kösoglu-Kind, Robert Loredo, Michele Grossi +3 more

Genetic information is encoded as linear sequences of nucleotides, represented by letters ranging from thousands to billions. Differences between sequences are identified through comparative approaches like sequence analysis, where variations can occur at the individual nucleotide level or collectively due to various phenomena such as recombination or deletion. Detecting these sequence differences is vital for understanding biology and medicine, but the complexity and size of genomic data require substantial classical computing power. Inspired by human visual perception and pixel representation on quantum computers, we leverage these techniques to implement pairwise sequence analysis. Our method utilizes the Flexible Representation of Quantum Images (FRQI) framework, enabling comparisons at a fine granularity to single letters or amino acids within gene sequences. This novel approach enhances accuracy and resolution, surpassing traditional methods by capturing subtle genetic variations with precision. In summary, our approach offers algorithmic advantages, including reduced time complexity, improved space efficiency, and accurate sequence comparisons. The novelty lies in applying the FRQI algorithm to compare quantum images in genome sequencing, allowing for examination at the individual letter or amino acid level. This breakthrough holds promise for advancing biological data analysis and enables a more comprehensive understanding of genetic information.

arXiv:2303.13608•Scientific Reports•Sep 4, 2023•28 citations

Bioinformatics Quantum Algorithm

Jincheng Zhang

This paper explores the potential of quantum computing to revolutionize bioinformatics, specifically focusing on enhanced gene sequence analysis and protein structure prediction. The core concept centers around utilizing quantum error correction and quantum computation to accelerate these computationally intensive tasks. We propose a novel algorithm architecture leveraging quantum entanglement and superposition to overcome limitations inherent in classical approaches. The paper details the design of a quantum algorithm for sequence alignment and protein folding, emphasizing the key quantum mechanisms that underpin its enhanced performance. We present a preliminary analysis of the algorithm's potential advantages, focusing on reduced computational complexity and improved accuracy compared to existing classical methods. The research highlights the significance of quantum algorithms in addressing critical challenges within the field of bioinformatics.

•Aug 31, 2026•0 citations

Multi-sequence alignment using the Quantum Approximate Optimization Algorithm

Sebastian Yde Madsen, Frederik K. Marqversen, S. E. Rasmussen +1 more

The task of Multiple Sequence Alignment (MSA) is a constrained combinatorial optimization problem that is generally considered a complex computational problem. In this paper, we first present a binary encoding of MSA and devise a corresponding soft-constrained cost-function that enables a Hamiltonian formulation and implementation of the MSA problem with the variational Quantum Approximate Optimization Algorithm (QAOA). Through theoretical analysis, a bound on the ratio of the number of feasible states to the size of the Hilbert space is determined. Furthermore, we consider a small instance of our QAOA-MSA algorithm in both a quantum simulator and its performance on an actual quantum computer. While the ideal solution to the instance of MSA investigated is shown to be the most probable state sampled for a shallow p<5 quantum circuit in the simulation, the level of noise in current devices is still a formidable challenge for the kind of MSA-QAOA algorithm developed here. In turn, we are not able to distinguish the feasible solutions from other states in the quantum hardware output data at this point. This indicates a need for further investigation into both the strategy utilized for compiling the quantum circuit, but also the possibility of devising a more compact ansatz, as one might achieve through constraint-preserving mixers for QAOA.

arXiv:2308.12103•Aug 23, 2023•4 citations

Quantum Computing Genome Sequence Prediction

Jincheng Zhang

Quantum Computing Genome Sequence Prediction investigates the potential of quantum computing to revolutionize gene sequencing analysis. Traditional methods face computational bottlenecks, hindering the accurate prediction of genetic sequences. This research explores the application of quantum algorithms to accelerate the prediction process, ultimately aiming to improve the accuracy and efficiency of gene sequence analysis. The core claim centers on leveraging quantum computation's unique properties to overcome limitations in classical algorithms and achieve superior prediction results. The investigation will detail a novel quantum approach to sequence prediction, focusing on reducing computational complexity and enhancing prediction fidelity. This paper will present a comprehensive overview of the proposed methodology, including mathematical formulations, key algorithmic steps, and potential performance benchmarks. The study will also address challenges related to quantum hardware limitations and the integration of existing bioinformatics tools.

•Sep 2, 2026•0 citations

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•36 citations
We propose a modified MSA algorithm on quantum annealers with applications in areas of bioinformatics and genetic sequencing.To understand the human genome, researchers compare extensive sets of these genetic sequences -or their protein counterparts -to identify patterns.This comparison begins with the alignment of the set of (multiple) sequences.However, this alignment problem is considered nondeterministically-polynomial time complete and, thus, current classical algorithms at best rely on brute force or heuristic methods to find solutions.Quantum annealing algorithms are able to bypass this need for sheer brute force due to their use of quantum mechanical properties.However, due to the novelty of these algorithms, many are rudimentary in nature and limited by hardware restrictions.We apply progressive alignment techniques to modify annealing algorithms, achieving a linear reduction in spin usage whilst introducing more complex heuristics to the algorithm.This opens the door for further exploration into quantum computing-based bioinformatics, potentially allowing for a deeper understanding of disease detection and monitoring.
This paper explores the application of principles from quantum biology to design novel bioinformatics algorithms. Traditional bioinformatics relies heavily on classical computational models, often neglecting the potential influence of quantum effects observed within biological systems. This research proposes a framework that leverages these quantum phenomena, specifically focusing on quantum tunneling, superposition, and entanglement, to address complex challenges in biological data analysis. The core mechanism involves simulating quantum effects during processes like protein folding and DNA sequence recognition, and utilizing quantum algorithms – such as Grover's algorithm and quantum annealing – to optimize sequence data analysis. We present a conceptual approach to formulating biological problems as quantum computing problems, offering a fundamentally new perspective for bioinformatics. The potential impact of this approach lies in developing more efficient and accurate algorithms for tasks including genomic sequence alignment, protein structure prediction, and drug discovery. This work aims to bridge the gap between quantum mechanics and biology, paving the way for a new era of bioinformatics driven by quantum principles. ---
Genetic information is encoded as linear sequences of nucleotides, represented by letters ranging from thousands to billions. Differences between sequences are identified through comparative approaches like sequence analysis, where variations can occur at the individual nucleotide level or collectively due to various phenomena such as recombination or deletion. Detecting these sequence differences is vital for understanding biology and medicine, but the complexity and size of genomic data require substantial classical computing power. Inspired by human visual perception and pixel representation on quantum computers, we leverage these techniques to implement pairwise sequence analysis. Our method utilizes the Flexible Representation of Quantum Images (FRQI) framework, enabling comparisons at a fine granularity to single letters or amino acids within gene sequences. This novel approach enhances accuracy and resolution, surpassing traditional methods by capturing subtle genetic variations with precision. In summary, our approach offers algorithmic advantages, including reduced time complexity, improved space efficiency, and accurate sequence comparisons. The novelty lies in applying the FRQI algorithm to compare quantum images in genome sequencing, allowing for examination at the individual letter or amino acid level. This breakthrough holds promise for advancing biological data analysis and enables a more comprehensive understanding of genetic information.
This paper explores the potential of quantum computing to revolutionize bioinformatics, specifically focusing on enhanced gene sequence analysis and protein structure prediction. The core concept centers around utilizing quantum error correction and quantum computation to accelerate these computationally intensive tasks. We propose a novel algorithm architecture leveraging quantum entanglement and superposition to overcome limitations inherent in classical approaches. The paper details the design of a quantum algorithm for sequence alignment and protein folding, emphasizing the key quantum mechanisms that underpin its enhanced performance. We present a preliminary analysis of the algorithm's potential advantages, focusing on reduced computational complexity and improved accuracy compared to existing classical methods. The research highlights the significance of quantum algorithms in addressing critical challenges within the field of bioinformatics.
The task of Multiple Sequence Alignment (MSA) is a constrained combinatorial optimization problem that is generally considered a complex computational problem. In this paper, we first present a binary encoding of MSA and devise a corresponding soft-constrained cost-function that enables a Hamiltonian formulation and implementation of the MSA problem with the variational Quantum Approximate Optimization Algorithm (QAOA). Through theoretical analysis, a bound on the ratio of the number of feasible states to the size of the Hilbert space is determined. Furthermore, we consider a small instance of our QAOA-MSA algorithm in both a quantum simulator and its performance on an actual quantum computer. While the ideal solution to the instance of MSA investigated is shown to be the most probable state sampled for a shallow p<5 quantum circuit in the simulation, the level of noise in current devices is still a formidable challenge for the kind of MSA-QAOA algorithm developed here. In turn, we are not able to distinguish the feasible solutions from other states in the quantum hardware output data at this point. This indicates a need for further investigation into both the strategy utilized for compiling the quantum circuit, but also the possibility of devising a more compact ansatz, as one might achieve through constraint-preserving mixers for QAOA.
Quantum Computing Genome Sequence Prediction investigates the potential of quantum computing to revolutionize gene sequencing analysis. Traditional methods face computational bottlenecks, hindering the accurate prediction of genetic sequences. This research explores the application of quantum algorithms to accelerate the prediction process, ultimately aiming to improve the accuracy and efficiency of gene sequence analysis. The core claim centers on leveraging quantum computation's unique properties to overcome limitations in classical algorithms and achieve superior prediction results. The investigation will detail a novel quantum approach to sequence prediction, focusing on reducing computational complexity and enhancing prediction fidelity. This paper will present a comprehensive overview of the proposed methodology, including mathematical formulations, key algorithmic steps, and potential performance benchmarks. The study will also address challenges related to quantum hardware limitations and the integration of existing bioinformatics tools.
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.