💻 bioinformatics

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

QUANTA is a novel quantum annealing framework that formulates weighted quartet bipartitioning as a QUBO problem to enable species tree estimation on real quantum hardware, achieving state-of-the-art accuracy and significant speedups over classical methods while maintaining scalability for large genomic datasets.

Original authors: Kumar Mondal, N., Bayzid, M. S.

Published 2026-11-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kumar Mondal, N., Bayzid, M. S.

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ⚕️ This is an AI-generated explanation of a preprint that has not been peer-reviewed. It is not medical advice. Do not make health decisions based on this content. Read full disclaimer

Life on Earth is a vast, branching family tree, connecting every species from the smallest bacteria to the tallest redwoods. For decades, scientists have tried to reconstruct this tree of life by reading the genetic code of different organisms. However, this task is far from simple. When researchers look at the history of individual genes within a single species, they often find that these genes tell conflicting stories. One gene might suggest that two species are close relatives, while another gene suggests they are distant cousins. This happens because of complex biological processes, such as the random sorting of ancestral genetic variations, which create a tangled web of evolutionary history rather than a single, straight line. To make sense of this, scientists must piece together the true species tree from thousands of these conflicting gene histories, a challenge that has long strained the limits of traditional computer methods.

In a recent study, researchers from Bangladesh University of Engineering and Technology have taken a bold step toward solving this problem by turning to quantum computing. They developed a new method called QUANTA, which uses the unique properties of quantum machines to piece together species trees more efficiently than ever before. Instead of relying on the standard, step-by-step logic of classical computers, QUANTA treats the problem as a massive puzzle where the goal is to find the arrangement of species that best agrees with the majority of the genetic evidence. The researchers tested this approach on a wide range of simulated data and real biological datasets, including a massive collection of genetic information from 48 bird species. Their results show that QUANTA can reconstruct these evolutionary trees with an accuracy that matches the best existing methods, but it does so with a dramatic increase in speed when handling large groups of species.

The core of the problem lies in how scientists combine small pieces of evolutionary evidence. Imagine taking a group of four species and asking which two are most closely related; this small grouping is called a "quartet." By analyzing millions of these quartets from thousands of genes, researchers can build a picture of the whole tree. Traditional methods, such as the widely used wQFM, work by repeatedly splitting the list of species into two groups to see which split makes the most sense. This splitting process is computationally expensive, like trying to find the best way to divide a large crowd into two teams by testing every possible combination one by one. As the number of species grows, the number of combinations explodes, causing these classical methods to slow down to a crawl.

QUANTA changes the game by using a quantum annealer, a type of quantum computer designed to find the lowest energy state of a complex system. The researchers translated the problem of splitting species into a format that these machines can understand. Instead of checking combinations sequentially, the quantum computer explores many possible splits simultaneously. It uses a principle called quantum tunneling to slip past local dead ends that often trap classical computers, allowing it to find the optimal split much faster. The team proved that their method uses the absolute minimum number of variables needed to represent these splits, making it as efficient as possible for the current generation of quantum hardware.

The researchers put QUANTA to the test on a variety of datasets, ranging from small groups of 11 species to large groups of 200. In the smaller tests, where the problem was simple enough for a standard computer to solve perfectly, QUANTA matched the accuracy of the best existing methods. When they moved to larger datasets, the advantages became clear. On a dataset of 200 species, the quantum-assisted method solved the difficult splitting steps about 4,100 times faster than the traditional method. Even when accounting for the time it takes to send data to the quantum computer and receive the answer, the total time to build the tree was significantly shorter. For a dataset of 101 species, QUANTA finished the analysis in just 4.3 minutes, while the traditional method took over 22 minutes.

The study also applied QUANTA to a challenging real-world dataset involving 48 bird species and nearly 15,000 genes. This group of birds is known for having a very messy evolutionary history, making it difficult to determine their true relationships. QUANTA not only matched the accuracy of the leading methods but also reconstructed a specific group of birds that other methods missed. It produced a tree with a higher score for how well it agreed with the genetic data than the previous best method. This success demonstrates that the new approach can handle the complexity of real biological data, even when the evolutionary signals are weak and conflicting.

While the current quantum computers used in the study are still in an early, noisy stage of development, the results offer a glimpse into the future of evolutionary biology. The researchers emphasize that their method is not tied to the specific hardware used; the mathematical framework they created will work on future, more powerful quantum machines as they become available. As quantum technology matures, this approach could allow scientists to analyze even larger datasets, potentially resolving long-standing mysteries in the tree of life. The study establishes a new foundation for using quantum optimization in phylogenomics, suggesting that the next generation of species tree estimation will be both faster and more accurate than what is possible with classical computers alone.

Technical Summary of QUANTA: A Quantum Annealing Framework for Species Tree Estimation

Problem Definition

Reconstructing species trees from genome-scale data is complicated by pervasive gene tree discordance, often caused by biological processes like incomplete lineage sorting (ILS). While summary methods that combine individual gene trees are popular, they can be sensitive to gene tree estimation errors. Quartet-based methods, such as the QFM (Quartet Fiduccia–Mattheyse) and QMC (Quartet MaxCut) families, offer high accuracy by inferring evolutionary relationships among subsets of four taxa and amalgamating them. However, these methods rely on computationally expensive classical heuristics (FM and MaxCut) to find optimal bipartitions (splits of taxa into two groups) at each step of a divide-and-conquer strategy. As the number of taxa increases, the search space for optimal bipartitions grows super-exponentially, limiting the scalability of these classical approaches.

Methodology

The authors introduce QUANTA (QUantum ANnealing for Tree Amalgamation), a framework that replaces classical bipartitioning heuristics with a quantum optimization approach.

QUBO Formulation:
The core innovation is a novel formulation of the weighted quartet bipartitioning problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem.
- Encoding: Each taxon is assigned a binary variable ( $x_i \in \{0, 1\}$ ) representing which side of the bipartition it belongs to. The authors prove that using $n-1$ variables for $n$ taxa is the minimal possible encoding to represent all unique bipartitions, maximizing the efficiency of limited quantum resources.
- Cost Function: The objective is to minimize an energy function that rewards "satisfied" quartets (where the bipartition separates the two pairs of taxa correctly) and penalizes "violated" quartets. "Deferred" quartets (where three taxa are on one side and one on the other) are left for recursive steps.
- Mathematical Construction: To avoid the need for auxiliary variables (which would increase qubit requirements), the authors adapt a cost function design that penalizes specific "mistakes" (splitting a pair or placing taxa from different pairs on the same side) rather than directly maximizing satisfied quartets. This results in a cost matrix $Q$ containing only linear and quadratic terms, fitting the QUBO format perfectly.
- Theoretical Guarantees: The authors prove that for any positive penalty weights, the energy function correctly orders the states: satisfied quartets have the lowest energy, deferred quartets have intermediate energy, and violated quartets have the highest energy.
Implementation:
- The QUBO matrices are solved using quantum annealing on D-Wave quantum processors via cloud access.
- For partitions exceeding the direct capacity of the quantum processing unit (QPU), the framework utilizes D-Wave's hybrid quantum-classical solver.
- For very small partitions (≤20 taxa), the system uses exhaustive brute-force search on a classical CPU to guarantee optimality.
- The framework is integrated into the wQFM (weighted QFM) pipeline to demonstrate practical utility.

Key Contributions

First Quantum Formulation: QUANTA represents the first quantum formulation of quartet-based species tree inference and the first method for multi-locus data to run on real quantum hardware.
Hardware-Agnostic Optimization: The QUBO formulation is independent of specific amalgamation frameworks or quantum hardware, allowing it to be integrated into various pipelines (e.g., QFM, QMC) and future fault-tolerant quantum computers.
Minimal Encoding: The method achieves the theoretical lower bound for the number of binary variables (qubits) required to represent bipartitions, optimizing resource usage on current noisy intermediate-scale quantum (NISQ) devices.
Scalability: By replacing the FM heuristic with quantum annealing, the method addresses the computational bottleneck of quartet amalgamation.

Experimental Results

The authors evaluated QUANTA on simulated datasets (ranging from 11 to 200 taxa) and biological datasets (including a 48-taxon avian dataset with 14,446 genes).

Accuracy:
- On simulated datasets, QUANTA achieved accuracy comparable to state-of-the-art methods, including wQFM, ASTRAL, and wQMC.
- On the challenging avian dataset, QUANTA reconstructed a species tree with a higher quartet score than wQFM (108,551 more agreeing quartets) and successfully recovered specific clades (e.g., Cursores) that ASTRAL and wQFM failed to resolve.
- On the 101-taxon dataset, QUANTA, wQFM, and ASTRAL produced trees with statistically indistinguishable accuracy.
Speed and Efficiency:
- Bipartition Solving: The quantum annealer solved bipartitions for 90–200 taxa approximately 4,100 times faster than the classical FM heuristic used in wQFM.
- End-to-End Performance: Despite overheads associated with remote hardware access (embedding, communication), QUANTA was significantly faster overall on large datasets. For 200 taxa, QUANTA completed the analysis in 9.3 minutes compared to 2.5 hours for wQFM (a 16-fold speedup).
- Scalability: While current experiments were limited to 200 taxa due to hardware constraints, the authors estimate that the hybrid solver could handle bipartitions of up to ~20,000 taxa using the same formulation.
Solver Comparison: When solved with classical simulated annealing instead of quantum hardware, the method remained accurate but lost the massive speedup on larger partitions, confirming that the performance gain is driven by the quantum annealing process.

Significance and Claims

The paper positions QUANTA as a foundational step toward quantum-assisted phylogenomics. The authors claim that:

QUANTA demonstrates that quantum annealing can effectively replace classical heuristics in complex biological optimization problems, offering substantial speedups even on current NISQ hardware.
The theoretical correctness of the QUBO formulation ensures that the method will remain valid and potentially more powerful as quantum hardware advances toward fault tolerance (e.g., IBM's or Google's future roadmaps).
The framework opens a new direction for solving the broader "maximum quartet support" problem (addressed by methods like ASTRAL) using quantum optimization, promising increased scalability and accuracy for species tree estimation as quantum technology matures.

The authors remain modest regarding current limitations, noting that end-to-end speedups are currently constrained by classical preprocessing and communication overheads, but emphasize that these are engineering challenges rather than fundamental limits of the quantum approach.