A Block Decomposed QUBO Workflow for Chromosome-Y Phylogeny Reconstruction

A Block Decomposed QUBO Workflow for Chromosome-Y Phylogeny Reconstruction (arXiv:2609.29856v1), submitted on 24 Sep 2026, is a computational method by Giuliana Siddi Moreau et al. that reconstructs human Y-chromosome phylogeny from Variant Call Format (VCF) files of biallelic SNPs.

The workflow casts topology selection and root placement as Quadratic Unconstrained Binary Optimisation (QUBO) problems, solved using an Alternating Direction Method of Multipliers (ADMM) decomposition strategy paired with a Digitized Counter-Diabatic Quantum Optimization (DCQO) solver. This approach enables large phylogenetic optimization problems to be executed across multiple classical or quantum computing resources, demonstrating scalability beyond the qubit budget of individual digital quantum processing units.

Key features include: Unified Framework: Combines two QUBO formulations for tree structure and rooting within a single Python workflow. Scalability: Uses ADMM to partition global QUBO instances into overlapping blocks, allowing execution on near-term quantum hardware without requiring global embedding. Benchmarking: Successfully applied to 78 populations from the gnomAD v3.1.2 HGDP+1KG chromosome-Y callset, recovering roots in deep African lineages with precision comparable to classical simulated annealing. Output: Generates Nexus-annotated rooted trees annotated with PhyloTree-Y haplogroups, compatible with standard viewers like FigTree and iTOL.

The paper presents a computational workflow for inferring human Y-chromosome population phylogenies directly from a Variant Call Format (VCF) file containing biallelic single-nucleotide polymorphisms (SNPs). Its central idea is to recast two core phylogenetic inference tasks—tree topology selection and root placement—as Quadratic Unconstrained Binary Optimization (QUBO) problems. In this formulation, binary variables encode candidate evolutionary relationships and root assignments, while the QUBO objective captures fitness criteria derived from SNP compatibility and phylogenetic consistency. The key technical contribution is a block-decomposed QUBO workflow: rather than treating the full phylogenetic inference problem as one monolithic combinatorial optimization, the method partitions it into smaller, more manageable blocks, improving tractability while preserving an end-to-end objective for reconstructing a plausible Y-chromosome tree.

This matters because Y-chromosome SNP phylogenies are widely used to trace paternal lineages, population divergences, and historical migration patterns, yet the underlying tree-selection problem can become combinatorially challenging as the number of lineages and informative variants grows. By expressing the problem in a standard QUBO form, the workflow makes it compatible with a broad range of optimization tools, including classical QUBO solvers and annealing-oriented hardware, and provides a modular path toward scalable phylogenetic reconstruction from raw variant data. More broadly, the work illustrates how classical phylogenetic decisions can be reframed as discrete optimization problems, potentially enabling more systematic, reproducible, and solver-friendly approaches to genome-history inference.