⚛️ quantum physics

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

This paper proposes three novel optimization models for the NP-hard maximum parsimony phylogenetic tree problem that enable both classical and quantum solvers to directly search the complete solution space, demonstrating that a streamlined branch-based model outperforms classical heuristics and that quantum simulations can efficiently find exact optimal solutions for small-scale instances.

Original authors: Jiawei Zhang, Yibo Chen, Yang Zhou, Jun-Han Huang

Published 2026-03-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jiawei Zhang, Yibo Chen, Yang Zhou, Jun-Han Huang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a massive family reunion mystery. You have a photo album of 20 different people (the "leaf nodes"), and your job is to figure out how they are all related. You need to draw a family tree that explains their similarities and differences using the fewest possible changes in their DNA.

In the world of biology, this is called Maximum Parsimony. The rule is simple: nature usually takes the path of least resistance. The "best" family tree is the one that requires the fewest evolutionary mutations to explain why everyone looks the way they do.

However, there's a catch. As the number of people grows, the number of possible family trees explodes into the billions. Finding the perfect tree is like trying to find a single specific grain of sand on a beach that keeps getting bigger every second. This is a "computational nightmare" for standard computers.

Here is how the authors of this paper tackled the problem, using some clever tricks and a peek into the future of computing.

1. The Old Way vs. The New Way

The Old Way (The Flawed Map):
Previously, scientists tried to solve this by guessing what the "ancestors" (the missing links in the family tree) might look like before they started drawing the tree. It's like trying to solve a jigsaw puzzle by first guessing what the picture on the box is, and then only looking for pieces that fit that guess. If your guess is wrong, you'll never find the real picture. This method is biased and often misses the best solution.

The New Way (The Three Models):
The authors created three new "blueprints" (mathematical models) to solve this. Instead of guessing the ancestors, they let the computer search through every possible tree and every possible ancestor at the same time.

They designed three different ways to organize this search:

The Depth Model: Organizing the tree by how "deep" each generation is. (Too messy, too many rules).
The Position Model: Assigning every ancestor a specific seat number. (Better, but the math gets complicated).
The Branch Model (The Winner): This is their "magic trick." Instead of worrying about depth or seats, they simply defined the connections between people. By using a clever rule (you can only connect to someone with a higher ID number), they automatically prevented the tree from forming loops (which is impossible in a family tree). This model is so efficient it uses half the variables of the other methods. It's like switching from a massive, tangled ball of yarn to a neat, straight line.

2. Testing the Theory (The Classical Test)

First, they tested their "Branch Model" on a regular computer using a powerful solver (a very smart search engine).

The Result: For small groups, it found the perfect tree instantly.
The Reality Check: When they tried it on a real biological dataset (20 amphibian species), the computer started to sweat. The time it took to solve the problem grew exponentially. It's like trying to count every grain of sand on a beach by hand; eventually, you just run out of time.
The Good News: Even though it was slow, their method found better trees than the standard "heuristic" methods (which are like guessing and checking). They found trees that required fewer mutations, meaning a more accurate evolutionary history.

3. The Quantum Leap (The Future)

Since regular computers hit a wall, the authors asked: What if we use a Quantum Computer?

Think of a regular computer as a hiker trying to find the lowest point in a mountain range. They have to walk up and down every single hill to make sure they found the absolute bottom.
A Quantum Computer is like a ghost that can be in all the valleys at the same time. It can "tunnel" through the hills to find the lowest point instantly.

The authors translated their "Branch Model" into a language quantum computers understand (a "Hamiltonian"). They then used two quantum algorithms:

QAOA: This one tried to find the bottom but got stuck in "local valleys" (it thought a small dip was the bottom, but it wasn't).
VQE (Variational Quantum Eigensolver): This one was the star. It successfully found the exact lowest point (the perfect tree) for the small test cases they ran.

The Big Picture

This paper is a proof-of-concept. It says:

We have a better map: The "Branch Model" is a much more efficient way to mathematically describe the problem of building family trees.
Classical computers are hitting a limit: Even with the best map, regular computers struggle with large datasets.
Quantum computers are the future: Early quantum simulations show that they can solve these "impossible" problems perfectly, at least for small groups.

In simple terms: The authors built a better engine for a car (the model), tested it on a regular road (classical computer), and then showed that if you switch to a rocket ship (quantum computer), you can fly over the traffic jams that have been slowing down biologists for decades. While the rocket ship is still in the prototype phase, the blueprint for the flight is now ready.

1. Problem Statement

The paper addresses the Maximum Parsimony (MP) problem in phylogenetic tree reconstruction. The goal is to infer the evolutionary tree topology and ancestral states that minimize the total number of evolutionary changes (substitutions) required to explain observed genetic sequences.

Computational Challenge: The MP problem is NP-hard. As the number of species ( $n$ ) increases, the search space of possible tree topologies and ancestral states grows exponentially.
Limitations of Current Methods:
- Heuristics: Classical algorithms (e.g., SPR, TBR) are fast but do not guarantee global optimality, often getting trapped in local optima, especially in large datasets.
- Existing Mathematical Models: Previous approaches often map MP to the Steiner Tree problem. These methods typically require pre-constructing a finite set of candidate ancestral nodes. If the true optimal ancestral sequence is not in this pre-defined set, the solution is suboptimal. Furthermore, these models involve numerous explicit constraints and high computational costs.

2. Methodology

The authors propose a novel framework that formulates phylogenetic tree reconstruction as a combinatorial optimization problem. The core innovation is the design of three mathematical models that simultaneously infer the tree topology and ancestral states without pre-defining candidate internal nodes.

A. Three Optimization Models

The authors designed three distinct models to represent the unrooted tree structure:

Depth-based Model: Assigns nodes to specific depth levels relative to a reference node.
- Drawback: Requires a large number of variables and constraints to prevent cycles, leading to poor scalability.
Position-based Model: Assigns a unique position index to each internal node.
- Drawback: While it reduces variables compared to the depth model, the objective function involves complex higher-order interactions, increasing computational difficulty.
Branch-based Model (Proposed Solution):
- Mechanism: Defines binary variables $e_{u,v}$ representing a direct edge between internal node $u$ and node $v$ , with the strict condition that the index of $v$ must be greater than $u$ ( $v > u$ ).
- Key Innovation: This variable definition implicitly enforces acyclicity (no cycles possible if indices strictly increase) and degree constraints (leaf nodes have out-degree 0, reference node has in-degree 0).
- Efficiency: It reduces the problem to just two explicit constraints (in-degree for non-reference nodes and out-degree for internal nodes), drastically lowering the number of variables and penalty terms.

B. Classical Validation

Solver: The branch-based model was implemented using the CP-SAT solver (Google OR-Tools).
Benchmarking:
- Single-site: Compared against exact Branch-and-Bound algorithms (MEGA software).
- Biological Dataset: Applied to GAPDH gene sequences from 20 amphibian species (NCBI data). The model was tested on sequence fragments (50–250 bp) and compared against standard heuristics (SPR, TBR, Min-Mini).

C. Quantum Implementation

To address the scalability limits of classical solvers, the authors mapped the branch-based model to a Quantum Hamiltonian.

Algorithms: Two Variational Quantum Algorithms (VQAs) were tested:
1. QAOA (Quantum Approximate Optimization Algorithm): Used with varying circuit depths.
2. VQE (Variational Quantum Eigensolver): Used with a hardware-efficient ansatz (alternating layers of single-qubit rotations and entangling gates).
Simulation: Conducted using Qiskit and PennyLane on noiseless statevector simulators, comparing results against exact ground states calculated via classical diagonalization.

3. Key Contributions

Novel Modeling Approach: The introduction of the branch-based model eliminates the need for pre-constructing ancestral nodes, ensuring the search space covers all possible solutions. It achieves this with significantly fewer variables and constraints than previous depth or position-based models.
Superior Classical Performance: The branch-based model, when solved classically, consistently finds solutions with lower parsimony scores (fewer substitutions) than standard heuristics (SPR, TBR) on real biological datasets, demonstrating higher solution quality.
Quantum Feasibility: The study successfully demonstrates that variational quantum algorithms can solve the MP problem. Specifically, VQE rapidly converged to the exact theoretical ground state for small-scale instances, whereas QAOA struggled to escape local optima.
Generalizability: The modeling technique (implicit acyclicity via index ordering) offers a new paradigm for solving other tree-based combinatorial optimization problems.

4. Results

Variable Reduction: The branch-based model requires significantly fewer variables than the other two models. For $n=500$ leaf nodes, the branch-based model uses ~375k variables compared to ~1.5M for the depth-based model (Table II).
Classical Solver Performance:
- For small problems ( $n < 150$ ), the solver finds optimal solutions quickly.
- For larger problems, solving time grows near-exponentially, confirming the NP-hard nature and the need for new paradigms.
- On the GAPDH dataset, the model found solutions with fewer average substitutions than SPR, TBR, and Min-Mini across all fragment lengths (e.g., 433.8 vs. 445.6 for 250 bp fragments).
Quantum Performance:
- VQE: Successfully found the exact ground state energy (optimal solution) for all tested small-scale instances with rapid convergence.
- QAOA: Failed to reach the true ground state, getting trapped in local optima even with increased circuit depth.

5. Significance and Future Outlook

Evolutionary Biology: This work provides a rigorous method to find globally optimal or near-optimal phylogenetic trees, improving the accuracy of evolutionary relationship inference, which is critical for species identification, disease tracking, and drug discovery.
Quantum Utility: It serves as a proof-of-concept that quantum computing, specifically via VQE, can tackle intractable biological optimization problems that are currently limited by classical heuristics.
Future Directions:
- Scalability: Applying the model to phylogenomic datasets (concatenated multi-gene data) to reduce stochastic errors.
- Hardware Adaptation: Reducing higher-order terms in the objective function to quadratic forms to make the model compatible with quantum annealers (e.g., D-Wave).
- Algorithm Optimization: Developing advanced VQA variants to handle complex Hamiltonians and improve convergence speed on noisy intermediate-scale quantum (NISQ) devices.

In conclusion, the paper bridges the gap between classical combinatorial optimization and quantum computing, offering a mathematically elegant and computationally superior approach to one of the most challenging problems in evolutionary biology.