Quantum optimization method improves reconstruction of Y chromosome evolutionary trees
A Block Decomposed QUBO Workflow for Chromosome-Y Phylogeny Reconstruction
Distributed, Parallel, and Cluster Computing
Summary
Figuring out how different groups of people are related through their Y chromosomes can be tricky and needs a lot of computing power. The authors created a new step-by-step system that turns this problem into special math puzzles called QUBO, which computers and quantum devices can solve more efficiently. They split big problems into smaller chunks and use a new kind of quantum solver that doesn’t require complex repeated steps. This lets them handle bigger datasets than before while keeping accurate results, helping scientists understand human ancestry better.
What this means in practice
- •For population genomics analysts: Construct detailed Y-chromosome family trees from genetic variant data using an optimization workflow scalable to large datasets.
- •For quantum computing engineers: Experiment with block-decomposed QUBO problems combined with counter-diabatic quantum optimization to solve large combinatorial problems beyond current qubit limits.
Authors
Giuliana Siddi Moreau, Riccardo Berutti, Manuela Profir, Lorenzo Pisani, Maria Laura Clemente, Lidia Leoni
Abstract
This paper sets out a computational workflow that reconstructs the phylogeny of human Y-chromosome populations from a Variant Call Format (VCF) file of biallelic Single Nucleotide Polymorphisms (SNP). The two classical phylogenetic decisions - topology selection and root placement - are cast as Quadratic Unconstrained Binary Optimisation (QUBO) problems. The workflow combines two QUBO formulations with an Alternating Direction Method of Multipliers (ADMM) decomposition strategy and a plug-in Digitized Counter-Diabatic Quantum Optimization (DCQO) solver, enabling large phylogenetic optimization problems to be executed across multiple classical or quantum computing resources. The DCQO gate-based optimizer drives each ADMM-block QUBO with short-depth counter-diabatic circuits in the impulse regime, without the necessity for an outer variational loop. The combination of ADMM decomposition and the DCQO block solver facilitates problem sizes that surpass the qubit budget of any individual digital quantum processing unit call, while maintaining the integrity of the original objective. The workflow extracts genotype information from VCF files, reconstructs topology and rooting through two QUBO formulations, and annotates the resulting tree using PhyloTree. The resultant data set comprises a Nexus-annotated rooted tree, in addition to diagnostic figures. The workflow demonstrates the potential of modest-scale QUBO formulations combined with ADMM decomposition to serve as a scalable alternative to greedy heuristics in the domain of population genomics.