🧬 biology

Lossless Reductions and Hybrid Sampling for Phylogeny Using the Maximum Compatibility Criterion

This paper enhances maximum compatibility phylogeny reconstruction by introducing lossless graph reductions and hybrid quantum-classical sampling techniques to efficiently enumerate all optimal character sets, demonstrating their effectiveness on SARS-CoV-2 data while addressing the limitations of traditional Lagrange multipliers on noisy quantum devices.

Original authors: Orson Ye, James Bonfield, Joshua Cudby, Richard Durbin, Sergii Strelchuk

Published 2026-10-14

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Orson Ye, James Bonfield, Joshua Cudby, Richard Durbin, Sergii Strelchuk

Original paper licensed under CC BY 4.0 (http://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 story written in the genetic code of every living thing, a history of how populations split, migrated, and changed over millions of years. To read this history, scientists build family trees, known as phylogenies, which map the relationships between different organisms. These trees are not just academic curiosities; they help researchers understand how cancer evolves within a single body, how to design drugs that target specific pathogens, and how to track the spread of new viral variants like SARS-CoV-2. However, reconstructing these trees is difficult because we only have the genetic snapshots of living organisms today, not the full record of the past. Scientists must infer the most likely path of evolution from the data they have, looking for patterns that suggest how traits were passed down or changed.

One powerful way to do this is by finding the largest group of genetic traits that fit together perfectly on a single tree without contradiction. Imagine a puzzle where most pieces fit together easily, but a few are warped or have been shaped by convergent evolution—where unrelated species develop similar traits independently. The goal is to find the biggest set of pieces that form a coherent picture, ignoring the ones that break the pattern. This is known as the maximum compatibility problem. While finding just one good solution is hard, finding every single possible best solution is even harder, yet it is crucial for building a complete and accurate family tree. If scientists only find one solution, they might miss important alternative histories that the data supports.

A team of researchers has developed a new approach to solve this difficult puzzle, combining classical computer techniques with emerging quantum methods to find not just one, but all the best possible evolutionary trees. Their work focuses on a specific step in the process where the computer must sift through millions of possibilities to find the largest groups of compatible traits. The researchers found that while traditional methods are good at finding a single answer, they often struggle to capture the full diversity of equally good solutions. To fix this, they introduced a two-part strategy: first, they created a set of rules to shrink the massive puzzle down to a manageable size without losing any of the possible answers; second, they tested a new way of using quantum computers to sample these solutions, treating the quantum machine not as a magic solver, but as a tool to generate a diverse set of candidates that can be cleaned up and verified by classical computers.

The researchers began by examining the data from hundreds of thousands of SARS-CoV-2 virus sequences, a dataset large enough to test the limits of current technology. They discovered that the standard way of using quantum computers to solve this problem was not optimal. Typically, quantum algorithms are tuned to strictly enforce rules, ensuring that every candidate solution follows the laws of the puzzle perfectly. However, the team found that on noisy, real-world quantum devices, this strictness was a hindrance. Instead, they discovered that it was better to allow the quantum computer to produce "messy" candidates that might break a few rules, and then use a fast, classical computer program to fix them. This repair process is like a skilled editor taking a rough draft and polishing it into a final, perfect version. By letting the quantum machine explore a wider range of possibilities and then cleaning up the results, they could find more distinct solutions than by trying to force the quantum machine to be perfect from the start.

To make this process efficient enough for current technology, the team also developed a method to compress the problem before sending it to the quantum computer. They realized that many parts of the genetic data were so predictable that they could be removed from the calculation entirely, as long as the researchers kept a record of how to put them back later. This is similar to removing the frame from a painting to see the canvas underneath, knowing exactly how to reattach it later. By applying these lossless reduction rules, they could shrink a complex graph representing the genetic data from hundreds of nodes down to just a handful. In one specific test case involving 350 virus samples, their method reduced the problem from a graph with 64 points down to a tiny, simple graph with only five points. This meant that the final step of finding the answer became trivial, allowing them to recover the complete set of optimal evolutionary trees with certainty.

The results of their experiments showed a clear difference between finding one answer and finding all of them. When they used standard classical tools to find the best solution, they were often successful at finding a single top result. However, when they tried to find all the different ways the data could be arranged, those same tools often missed many valid solutions, even after running thousands of times. Their hybrid approach, which combined the graph compression with a modified quantum sampling method, proved much better at uncovering this hidden diversity. On a test graph with 64 points, their modified quantum method found more distinct, verified solutions than a random guessing method in every single trial. While this did not yet prove that quantum computers are superior to classical ones for this task, it demonstrated that the combination of smart data reduction and quantum sampling is a powerful way to tackle problems that were previously too large or complex to solve completely.

Ultimately, this work suggests a new path forward for evolutionary biology. By treating the problem as a modular system where data is first simplified, then sampled, and finally reconstructed, scientists can now handle much larger datasets than before. The researchers showed that they could take a massive set of viral sequences, strip away the predictable parts, use a quantum device to explore the remaining complex core, and then rebuild the full picture with perfect accuracy. This approach does not rely on quantum computers being perfect or error-free; instead, it uses them as a source of diverse ideas that are then refined by classical logic. As quantum technology continues to improve, this method of combining the strengths of both classical and quantum computing could allow scientists to reconstruct the history of life with a level of detail and completeness that was previously out of reach.

Technical Summary: Lossless Reductions and Hybrid Sampling for Phylogeny Using the Maximum Compatibility Criterion

Problem Definition

The paper addresses the computational challenge of reconstructing phylogenetic trees using the Maximum Compatibility (MC) criterion. Unlike Maximum Parsimony or Maximum Likelihood, which may struggle when characters (e.g., genomic mutations) are inconsistent with a single tree due to homoplasy or convergent evolution, MC seeks the largest set of mutually compatible characters.

The core computational subproblem is the Maximum Weighted Clique (MWC) Enumeration Problem. Given a compatibility graph where vertices represent characters and edges represent pairwise compatibility, the goal is to enumerate all maximum weight cliques. This differs significantly from standard optimization tasks where finding a single optimal solution suffices; in MC phylogeny, the downstream construction of a strict consensus tree requires the complete set of equally optimal solutions to resolve evolutionary relationships accurately.

The problem is NP-hard, and existing exact solvers (like Cherry's algorithm) face memory bottlenecks when the number of distinct maximum cliques grows large. Furthermore, heuristic solvers often fail to provide broad coverage of the solution space, missing distinct optima necessary for consensus building.

Methodology

The authors propose a modular pipeline combining classical graph reductions, deterministic postprocessing, and quantum sampling.

1. Lossless Graph Reductions

To address the enumeration bottleneck, the authors introduce lossless graph reduction rules applied to the complement graph (transforming the MWC problem into a Maximum Weighted Independent Set, or MWIS, problem). These rules preserve the complete set of optimal solutions while reducing the problem size:

Degree-1 Reduction: Removes vertices of degree 1 in the complement graph. If a vertex $v$ is connected only to $w$ , any MWIS must contain exactly one of them. The weight of $w$ is adjusted by subtracting $w(v)$ , and $v$ is removed. If the resulting weight of $w$ is non-positive, it is removed entirely.
Degree-2 Reduction: Applies similar logic to vertices connected to a pair of mutually connected vertices.
Reconstruction: The reductions are reversible. The algorithm records the removed vertices and weight adjustments, allowing the full set of MWISs (and thus MWCs) of the original graph to be deterministically reconstructed from the solutions of the reduced graph.

2. Hybrid Classical-Quantum Preprocessing

The pipeline integrates these reductions with classical preprocessing (greedy lower bounds and vertex coloring upper bounds) and a hybrid quantum-classical sampler (LeapHybridSampler on D-Wave).

The hybrid sampler is used to generate high-quality vertex colorings and cliques to tighten the bounds used in pruning.
Unlike the original Cherry algorithm, which relies on greedy approximations, this approach uses stochastic sampling to potentially find stronger bounds, thereby removing more vertices before the final enumeration step.

3. Quantum Formulation and Sampling

The authors formulate the MWIS problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem suitable for the Quantum Approximate Optimization Algorithm (QAOA).

Hamiltonian Construction: The cost function is derived by converting binary variables to $\{-1, +1\}$ , resulting in a Hamiltonian that penalizes edge conflicts.
Correction-in-the-Loop: Recognizing that current noisy quantum devices may not strictly enforce constraints, the authors employ a deterministic postprocessing step. Sampled bitstrings are treated as subgraphs; a classical greedy algorithm repairs them by removing conflicts and extending them to maximal cliques.
Lagrange Multiplier Tuning: Contrary to conventional wisdom requiring large Lagrange multipliers to strictly enforce constraints, the authors find that smaller multipliers (e.g., 0.1 times the max vertex weight) yield better results in the presence of postprocessing. This allows the Hamiltonian to act as a sampling objective for low-energy states that can be efficiently repaired into valid MWCs, rather than an exact encoder of feasibility.

Key Results

The authors evaluated their methods on graphs derived from SARS-CoV-2 genome sequences (up to 20,000 sequences).

Classical Benchmarks: Exact solvers (CliSAT, IncMaxCLQ) are fast at finding one optimum but struggle with the memory and time required to enumerate all optima. Heuristic solvers (SCCWalk4L) find high-quality cliques quickly but exhibit significant sampling bias, often missing distinct optima even after thousands of runs.
Reduction Efficacy: The proposed lossless reductions (Degree-1 and Degree-2) reduced the number of vertices by approximately 36.1% and conflict edges by 42.4% on an 819-sample instance. In a specific 350-sample case, the hybrid pipeline reduced the graph from 64 vertices to just 5, making the enumeration trivial.
Quantum Performance: On a 64-qubit IBM Heron device, the modified QAOA procedure (with correction-in-the-loop) outperformed a random-shot baseline in recovering distinct certified MWCs across 10 runs. While the authors note this is not a claim of quantum advantage, it demonstrates improved sample coverage over random sampling.
Modular Success: The hybrid approach successfully reduced instances to sizes where the full optimum set could be recovered exactly and deterministically, bypassing the need for exhaustive quantum enumeration of the original large graph.

Significance and Claims

The paper claims that the combination of lossless graph reduction and hybrid sampling offers a practical pathway to address the enumeration bottleneck in maximum compatibility phylogeny.

Exact Reconstruction: The primary significance lies in the ability to retain exact reconstruction of the complete set of optimal solutions. The reduction rules ensure that no optimal solution is lost, allowing the final output to be a strict consensus tree derived from the full set of optima.
Feasibility on NISQ Devices: The work demonstrates that current Noisy Intermediate-Scale Quantum (NISQ) devices can be useful components in a modular solver. By offloading the "hard core" of the problem to quantum sampling and using classical repair, the system can handle problem sizes that would otherwise be intractable for pure quantum enumeration.
Distinction in Objectives: The authors emphasize a critical distinction in combinatorial optimization: finding one optimum is a different task from recovering the optimum set. Their methods are specifically designed for the latter, which is essential for biological applications like consensus tree construction where diverse evolutionary histories must be captured.

The authors remain modest regarding quantum advantage, framing their contribution as a demonstration of how quantum sampling can be effectively integrated into a classical pipeline to solve specific, biologically relevant enumeration problems that are currently difficult for purely classical heuristics.