Quantum Approach for Constructing Phylogenetic Maximum Parsimony Tree

Within the field of phylogenetics, maximum parsimony is one of the main methods for constructing a phylogenetic tree. After a few steps of pre-processing, the problem can be seen as constructing a Steiner tree whose terminal is our gene pool. Find a Steiner tree is known to be NP-complete problem. This paper explores the potential of quantum computing in finding a phylogenetic maximum parsimony tree, which can be encoded into a quadratic unconstrained binary optimization (QUBO) problem. To do this, we propose a new QUBO formulation, called StTopoReduce, to optimize the constraint expressions in order to reduce the problem size. Our comprehensive experiments on the state-of-the-art D-Wave annealer indicate that our proposed approach performs efficiently in terms of both solution quality and execution time.