QUANTA: A quantum annealing framework for species tree estimation using weighted quartet amalgamation

Abstract

Reconstructing species trees from genome-scale data is challenging due to pervasive gene tree discordance. Maximizing quartet consistency is a widely used approach for species tree inference from multi-locus data. Quartet amalgamation approaches, such as Quartet Fiduccia-Mattheyse (QFM) and Quartet MaxCut (QMC) families, have emerged as highly accurate quartet-based species tree inference techniques, but their reliance on computationally expensive classical bipartitioning heuristics, such as Fiduccia-Mattheyses (FM) and MaxCut, limits their scalability. Here, we introduce QUANTA, a quantum annealing-based quartet amalgamation method that, to our knowledge, represents the first quantum formulation of quartet-based approaches and the first species tree estimation method for multi-locus data that runs on real quantum hardware. At the core of QUANTA is a novel, general formulation of weighted quartet bipartitioning as a quadratic unconstrained binary optimization (QUBO) problem that enables quantum annealing to replace the classical bipartitioning strategies underlying the QFM and QMC families of methods. We prove that our formulation uses the minimum possible number of qubits to represent bipartitions and that its energy function correctly orders satisfied, deferred, and violated quartets for any positive penalty weights. We implemented QUANTA on real D-Wave quantum annealing hardware, and evaluated it on a wide range of simulated and biological datasets. QUANTA achieves accuracy comparable to the state-of-the-art methods, including ASTRAL and wQFM, under challenging evolutionary conditions. We also reanalyzed several biological datasets, including the avian phylogenomic dataset comprising 14,446 genes across 48 genomes, on which QUANTA reconstructed a species tree with a higher quartet score than wQFM. Remarkably, despite running on current noisy intermediate-scale quantum (NISQ) hardware, QUANTA's bipartition technique achieved 4100x speedup over the FM bipartitioning technique in wQFM on bipartition containing 90-200 taxa, while maintaining comparable tree accuracy. By establishing a theoretically grounded, hardware-independent quantum optimization framework for weighted quartet amalgamation, QUANTA opens a new direction for quantum-assisted phylogenomics and provides a foundation for increasingly scalable and accurate species tree estimation as quantum computing hardware advances. QUANTA is publicly available at https://github.com/QuitttCat/QUANTA-Phylogenomics.