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 ( $$N_{\text {cut}}$$ 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.
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.
Bioinformatics workloads -- including protein structure prediction, molecular dynamics simulation, genomic sequencealignment, and phylogenetic tree reconstruction -- are among the most computationally intensive problems in science,with many exhibiting exponential or combinatorial scaling that overwhelms classical high-performance computing.Quantum computing, leveraging superposition and entanglement to explore exponentially large solution spaces,promises polynomial or exponential speedups for specific bioinformatics tasks. However, current noisyintermediate-scale quantum (NISQ) devices (50-1,000+ qubits, high error rates) are far from fault-tolerant quantumcomputers, and the practical quantum advantage for bioinformatics remains undemonstrated. This study systematicallybenchmarked five computational approaches -- classical exact algorithms, classical heuristics (genetic algorithm,simulated annealing), GPU-accelerated methods, variational quantum algorithms (VQE, QAOA) on NISQ hardware, anda proposed hybrid quantum-classical bioinformatics pipeline (HQC-Bio) combining quantum subroutines for combinatorialsubproblems with classical pre/post-processing -- across four bioinformatics tasks: multiple sequence alignment (MSA, n= 500 protein families), protein folding on lattice models (HP model, chains 20-60 residues), molecular docking scoring(1,000 ligand-receptor pairs), and phylogenetic tree search (taxa sets 10-50). HQC-Bio achieved the highest solutionquality for protein folding (optimal energy found in 84.6% of 40-residue instances vs 62.4% for simulated annealing; p <0.001) and phylogenetic search (log-likelihood within 0.2% of exact ML for 30-taxa trees vs 1.8% for RAxML heuristic).However, quantum wall-clock time exceeded classical GPU by 12-340x due to NISQ hardware overhead (circuitcompilation, shot noise, error mitigation), establishing that current quantum advantage is in solution quality rather thanspeed. Resource estimation projects that fault-tolerant quantum computers with 10,000-100,000 logical qubits couldachieve genuine speedups of 10-1,000x for these tasks within 10-15 years.
ABSTRACT The maximum parsimony phylogenetic tree reconstruction problem is NP‐hard, presenting a computational bottleneck for classical computing and motivating the exploration of emerging paradigms like quantum computing. To this end, we design three optimization models compatible with both classical and quantum solvers. Our method directly searches the complete solution space of all possible tree topologies and ancestral states, thereby avoiding the potential biases associated with pre‐constructing candidate internal nodes. Among these models, the branch‐based model drastically reduces the number of variables and explicit constraints through a specific variable definition, providing a novel modeling approach effective not only for phylogenetic tree building but also for other tree problems. The correctness of this model is validated with a classical solver, which obtains solutions that are generally better than those from heuristics on the gene dataset. Moreover, our quantum simulations successfully find the exact optimal solutions for small‐scale instances with rapid convergence, highlighting the potential of quantum computing to offer a new avenue for solving these intractable problems in evolutionary biology.
Quantum approximate optimization algorithm (QAOA) is a promising hybrid quantum-classical algorithm for solving combinatorial optimization problems. However, it cannot overcome qubit limitation for large-scale problems. Furthermore, the simulation time of QAOA scales poorly with the problem size. We propose a divide-and-conquer QAOA (DC-QAOA) to address the above challenges for graph maximum cut (MaxCut) problem. The algorithm works by recursively partitioning a larger graph into smaller ones whose MaxCut solutions are obtained with small-size noisy intermediate-scale quantum computers. The overall solution is retrieved from the subsolutions by applying the combination policy of measurement distribution reconstruction (MDR). The solution quality depends on the graph partitioning algorithm and MDR policy. Multiple partitioning and reconstruction methods are proposed and compared. Results are evaluated by metrics, such as quantum program runtime, measurement expectation value (EV), and approximation ratio (AR). The results show that DC-QAOA achieves 97.14% AR (20.32% higher than classical counterpart), and 94.79% EV (15.80% higher than quantum annealing). DC-QAOA solves large-scale graph instances with a polynomial rate or returns unsuccessful partition if graph connectivity requirement is not fulfilled otherwise.
The exponential growth of genomic data has transformed evolutionary biology, enabling large-scale analysis of genetic variation, phylogenetic relationships, and adaptive mechanisms across species. However, classical computational approaches increasingly struggle with the combinatorial complexity, high dimensionality, and nonlinear interactions inherent in genomic datasets. This study explores how quantum-enhanced data analysis can augment evolutionary biology by enabling more efficient modeling of genomic variation and species adaptation. By leveraging quantum computing principles such as superposition, entanglement, and quantum parallelism, quantum algorithms offer the potential to accelerate sequence alignment, genotype–phenotype mapping, evolutionary optimization, and adaptive landscape exploration. Through qualitative synthesis of research in quantum computing, computational genomics, and evolutionary theory, this paper examines how quantum-enhanced frameworks can improve the detection of adaptive patterns, epistatic interactions, and evolutionary constraints. The analysis highlights potential applications in phylogenomic reconstruction, population genetics, and predictive modeling of species responses to environmental pressures. While acknowledging current technological limitations, the study argues that quantum-enhanced genomic analysis represents a promising pathway toward more scalable, precise, and predictive evolutionary models. Ultimately, this work positions quantum computing as a transformative tool for advancing our understanding of biological evolution and species resilience in rapidly changing ecosystems.
Quantum computing has emerged as a promising paradigm to tackle computationally intensive problems that classical computers struggle with. In this study, we explore the application of the Edge-based quantum approximate optimization algorithm (QAOA) to the MAX-CUT problem, a well-known combinatorial optimization challenge. MAX-CUT aims to partition the vertices of a graph into two subsets such that the number of edges between the subsets is maximized. We define the edge-based MAX-CUT problem and propose a method for applying QAOA specifically tailored to this formulation. We conduct simulations using IBM’s Qiskit framework, examining both vertex-based and edge-based QAOA implementations across various graph structures. Our results highlight the comparative performance of these approaches in terms of solution quality and computational efficiency. Specifically, we analyze the impact of different graph sizes and edge densities on the complexity and CNOT gate counts of the proposed algorithms. This analysis provides insights into leveraging quantum computing for combinatorial optimization tasks, particularly focusing on the implications for practical applications and future research directions.
Molecular sequence data are used to reconstruct evolutionary relationships among taxa, but reconstruction accuracy depends not only on the tree-building method but also on how pairwise sequence relationships are represented. We evaluated sequence-to-affinity representations in a recursive normalized-cut (Ncut) framework whose graph-partitioning subproblems were formulated as quadratic unconstrained binary optimization (QUBO) models and solved using Simulated Bifurcation. Using simulated amino-acid and nucleotide datasets spanning multiple tree-generation settings and evolutionary divergence, we compared normalized bit-score affinities with representations derived from transformed sequence similarities and evolutionary distances, examined post-swap refinement, and used neighbor joining (NJ) as a distance-based comparator.
Affinity representation substantially affected internal split recovery, particularly for nucleotide data. JC69-based local affinities maintained comparatively high accuracy as divergence increased, whereas normalized bit-score and BLAST-derived kernel representations declined more markedly. Post-swap refinement generally improved recovery, but not consistently across individual reconstructions. NJ achieved higher mean split recovery than corresponding recursive Ncut reconstructions for WAG and JC69 distances across all evaluated conditions, whereas recursive Ncut outperformed NJ for BLAST-derived logarithmic distances under some conditions.
These results show that graph construction is an important determinant of recursive Ncut-based phylogenetic reconstruction. A representation that performs well within Ncut does not necessarily provide the most accurate use of the underlying pairwise distances. Pairwise representation, affinity transformation, optimization, and recursive tree construction should therefore be evaluated jointly.