Multiple sequence alignment (MSA) reveals homology in biological sequences, which is crucial for phylogenetics, medicine, and molecular biology. Many heuristic MSA algorithms use guide trees to determine sequence alignment order, but finding an optimal guide tree is an NP-hard problem. Conventional guide tree algorithms are greedy heuristics designed for better scalability at the cost of accuracy. Due to the NP-hardness of guide tree construction, it is desirable to explore the utility of quantum algorithms such as quantum annealing. We propose a guide tree construction algorithm that utilizes quantum annealing. The theoretical foundations of our method are both minimum evolution and molecular clock. Unlike classical greedy approaches, we reformulate the minimum evolution problem as a traveling salesperson problem (TSP), which quantum annealing can target. The TSP solution enables the guide tree to be constructed with linear time overhead using the molecular clock. We used the Concorde TSP solver and D-Wave’s quantum-classical hybrid solvers to demonstrate the results instead of native QPU annealing alone, due to limitations in current quantum hardware. Benchmarking on BAliBASE 3.0 showed no statistically significant differences in alignment scores between our method and classical guide trees. When Concorde was used, the empirical wall-clock time scaling of our method was better than that of the textbook UPGMA implementation. Classical TSP solvers allow practical implementation of our method for small-scale guide trees, while larger problems motivate the use of quantum annealing. Further performance analysis should be conducted on larger-scale benchmark tests. Fortunately, rapid advances in quantum hardware may soon enable these tests. This study highlights the potential of quantum algorithms for targeting computational bottlenecks in MSA.
Multiple sequence alignment (MSA) reveals homology in biological sequences, which is crucial for phylogenetics, medicine, and molecular biology. Many heuristic MSA algorithms use guide trees to determine sequence alignment order, but finding an optimal guide tree is an NP-hard problem. Conventional guide tree algorithms are greedy heuristics designed for better scalability at the cost of accuracy. Due to the NP-hardness of guide tree construction, it is desirable to explore the utility of quantum algorithms such as quantum annealing. We propose a guide tree construction algorithm that utilizes quantum annealing. The theoretical foundations of our method are both minimum evolution and molecular clock. Unlike classical greedy approaches, we reformulate the minimum evolution problem as a traveling salesperson problem (TSP), which quantum annealing can target. The TSP solution enables the guide tree to be constructed with linear time overhead using the molecular clock. We used the Concorde TSP solver and D-Wave’s quantum-classical hybrid solvers to demonstrate the results instead of native QPU annealing alone, due to limitations in current quantum hardware. Benchmarking on BAliBASE 3.0 showed no statistically significant differences in alignment scores between our method and classical guide trees. When Concorde was used, the empirical wall-clock time scaling of our method was better than that of the textbook UPGMA implementation. Classical TSP solvers allow practical implementation of our method for small-scale guide trees, while larger problems motivate the use of quantum annealing. Further performance analysis should be conducted on larger-scale benchmark tests. Fortunately, rapid advances in quantum hardware may soon enable these tests. This study highlights the potential of quantum algorithms for targeting computational bottlenecks in MSA.
Multiple sequence alignment (MSA) reveals homology in biological sequences, which is crucial for phylogenetics, medicine, and molecular biology. Many heuristic MSA algorithms use guide trees to determine sequence alignment order, but finding an optimal guide tree is an NP-hard problem. Conventional guide tree algorithms are greedy heuristics designed for better scalability at the cost of accuracy. By utilizing quantum algorithms, such as quantum annealing, we can overcome the problem of local minima that occurs in greedy methods. We propose a scalable guide tree algorithm that achieves scalability through quantum annealing. The theoretical foundations of our method are both minimum evolution and molecular clock. Unlike classical greedy approaches, we directly map the minimum evolution problem to a traveling salesperson problem (TSP), which quantum annealing can solve efficiently. The TSP solution enables the guide tree to be constructed in linear time using the molecular clock. Even with only a single sample from a D-Wave hybrid solver, our guide tree generally performed comparably to classical trees on the BAliBASE 3.0 benchmark. With a single iterative refinement, no statistically significant performance differences were found between our method and classical guide trees. Our scalable guide tree algorithm is practical in the sense that only a single sampling can be enough for constructing a good guide tree. Further performance analysis requires larger-scale benchmark tests. Fortunately, rapid advances in quantum hardware may soon enable these tests. While the practical application of quantum algorithms in bioinformatics has been relatively overlooked, this study highlights the potential of quantum algorithms for targeting computational bottlenecks in the field.
Abstract Quantum computing applies principles of quantum mechanics, such as superposition and entanglement, to process information with exponential parallelism. This paradigm offers significant computational advantages over classical methods, particularly for NP-hard problems like phylogenetic tree reconstruction in evolutionary biology. Phylogenetic trees model the evolutionary relationships among species or genes, and their reconstruction is computationally challenging as the number of possible topologies grows exponentially with the number of taxa. To address this, biologists often rely on heuristic methods; however, recent work has shown that recursive graph-cut techniques can achieve high accuracy in phylogenetic inference, though at high computational cost. In this study, we present a quantum algorithm based on the normalized cut ( Ncut N cut ) criterion, enabling efficient recursive graph partitioning. Implemented using Quantum Annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA), demonstrating promising results on real quantum hardware for complex bioinformatics tasks.
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.
The Traveling Salesman Problem (TSP) serves as a standard benchmark for assessing potential quantum advantage in combinatorial optimization. This paper provides a critical comparative analysis of quantum annealing, gate-based approaches based on quantum phase estimation, and hybrid quantum–classical dynamic programming methods within a unified complexity and implementation framework. While theoretical results indicate reductions of the classical O ( 2 n ) scaling to approximately O ( 1.728 n ) for general instances and to O ( 1.110 n ) for structured cases, these improvements remain largely asymptotic. In practice, all current quantum approaches are strongly constrained by hardware limitations. Quantum annealing suffers from embedding overhead and noise, hybrid methods rely extensively on classical decomposition without guaranteed optimality, and gate-based implementations are limited by circuit depth and error accumulation. As a result, no clear quantum advantage over classical algorithms has been demonstrated at practically relevant problem scales. By systematically separating intrinsic algorithmic scaling from hardware-induced resource constraints, this work clarifies the origin of the gap between theoretical quantum speedups and experimental performance, providing a critical assessment of the current status and realistic prospects of quantum TSP methods.
Benchmarking the performance of quantum optimization algorithms is crucial for identifying utility for industry-relevant use cases. However, Benchmarking processes most often vary between optimization applications and depend on user-specified goals. The heuristic nature of quantum algorithms additionally poses a challenge, especially in the comparison to classical algorithms. A key problem in existing benchmarking frameworks is the lack of equal effort in optimizing for the best quantum and, respectively, classical approaches. This paper presents a comprehensive set of guidelines comprising universal steps towards fair benchmarks. We discuss (1) application-specific algorithm choice, ensuring every solver is provided with the most fitting mathematical formulation of a problem; (2) the selection of benchmark data, including hard instances and real-world samples; (3) the choice of a suitable holistic figure of merit, like time-to-solution or solution quality within time constraints; and (4) equitable hyperparameter training to eliminate bias towards a particular method. Finally, the proposed guidelines are tested across three benchmarking scenarios, utilizing the Max-Cut (MC) and Travelling Salesperson Problem (TSP). The benchmarks employ classical mathematical algorithms, such as Branch-and-Cut (BNC) solvers, classical heuristics, Quantum Annealing (QA), and the Quantum Approximate Optimization Algorithm (QAOA).
Critical decision-making issues in science, engineering, and industry are based on combinatorial optimization; however, its application is inherently limited by the NP-hard nature of the problem. A specialized paradigm of analogue quantum computing, quantum annealing (QA), has been proposed to solve these problems by encoding optimization problems into physical energy landscapes and solving them by quantum tunnelling systematically through exploration of solution space. This is a critical review that summarizes the current applications of quantum annealing to combinatorial optimization and includes a theoretical background, hardware designs, algorithm implementation strategies, encoding and embedding schemes, protocols to benchmark quantum annealing, areas of implementation, and links with the quantum algorithms implementation with gate-based hardware and classical solvers. We develop a unified framework, relating adiabatic quantum dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to modern flux-qubit annealers (Chimera, Pegasus, Zephyr topologies), and emergent architectures (Lechner-Hauke-Zoller systems, Rydberg atom platforms), and hybrids of quantum and classical computation. Through our analysis, we find that overhead in embedding and encoding is the largest determinant of the scalability and performance (this is not just the number of qubits). Minor embeddings also usually have a physical qubit count per logical variable of between 5 and 12 qubits, which limits effective problem capacity by 80-92% and, due to chain-breaking errors, compromises the quality of solutions.