Inference of maximum parsimony phylogenetic trees with model-based classical and quantum methods

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 GAPDH 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.

10 pages, 5 figures

References in corpus (18)

• Quantum Computing in the NISQ era and beyond
• A variational eigenvalue solver on a quantum processor
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Barren plateaus in quantum neural network training landscapes
• The theory of variational hybrid quantum-classical algorithms
• Noisy intermediate-scale quantum (NISQ) algorithms
• Quantum algorithms: an overview
• The Variational Quantum Eigensolver: a review of methods and best practices
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Challenges and Opportunities in Quantum Optimization
• Quantum Annealing: An Overview
• Quantum Computing at the Frontiers of Biological Sciences
• Challenges of variational quantum optimization with measurement shot noise
• On the role of dealing with quantum coherence in amplitude amplification
• Quantum computing for genomics: conceptual challenges and practical perspectives
• Scalability Challenges in Variational Quantum Optimization under Stochastic Noise
• Probabilistic imaginary-time evolution in state-vector-based and shot-based simulations and on quantum devices