Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

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

Niloy Kumar Mondal, Md. Shamsuzzoha Bayzid

Published Nov 6, 2026• 0 citations
PDF (CC BY)Publisher

Abstract

Reconstructing species trees from genome-scale data is challenging due to pervasive gene tree discordance. Maximizing quartet consistency is a widely used approach for species tree inference from multi-locus data. Quartet amalgamation approaches, such as Quartet Fiduccia-Mattheyse (QFM) and Quartet MaxCut (QMC) families, have emerged as highly accurate quartet-based species tree inference techniques, but their reliance on computationally expensive classical bipartitioning heuristics, such as Fiduccia-Mattheyses (FM) and MaxCut, limits their scalability. Here, we introduce QUANTA, a quantum annealing-based quartet amalgamation method that, to our knowledge, represents the first quantum formulation of quartet-based approaches and the first species tree estimation method for multi-locus data that runs on real quantum hardware. At the core of QUANTA is a novel, general formulation of weighted quartet bipartitioning as a quadratic unconstrained binary optimization (QUBO) problem that enables quantum annealing to replace the classical bipartitioning strategies underlying the QFM and QMC families of methods. We prove that our formulation uses the minimum possible number of qubits to represent bipartitions and that its energy function correctly orders satisfied, deferred, and violated quartets for any positive penalty weights. We implemented QUANTA on real D-Wave quantum annealing hardware, and evaluated it on a wide range of simulated and biological datasets. QUANTA achieves accuracy comparable to the state-of-the-art methods, including ASTRAL and wQFM, under challenging evolutionary conditions. We also reanalyzed several biological datasets, including the avian phylogenomic dataset comprising 14,446 genes across 48 genomes, on which QUANTA reconstructed a species tree with a higher quartet score than wQFM. Remarkably, despite running on current noisy intermediate-scale quantum (NISQ) hardware, QUANTA's bipartition technique achieved 4100x speedup over the FM bipartitioning technique in wQFM on bipartition containing 90-200 taxa, while maintaining comparable tree accuracy. By establishing a theoretically grounded, hardware-independent quantum optimization framework for weighted quartet amalgamation, QUANTA opens a new direction for quantum-assisted phylogenomics and provides a foundation for increasingly scalable and accurate species tree estimation as quantum computing hardware advances. QUANTA is publicly available at https://github.com/QuitttCat/QUANTA-Phylogenomics.

DOI
10.64898/2026.11.05.764558

Related papers

Reconstruction of phylogenetic trees via graph-splitting using quantum computing

Nicolás Fernández Otero, Tomás F. Pena, Juan C. Pichel

Abstract Quantum computing applies principles of quantum mechanics, such as superposition and entanglement, to process information with exponential parallelism. This paradigm offers significant computational advantages over classical methods, particularly for NP-hard problems like phylogenetic tree reconstruction in evolutionary biology. Phylogenetic trees model the evolutionary relationships among species or genes, and their reconstruction is computationally challenging as the number of possible topologies grows exponentially with the number of taxa. To address this, biologists often rely on heuristic methods; however, recent work has shown that recursive graph-cut techniques can achieve high accuracy in phylogenetic inference, though at high computational cost. In this study, we present a quantum algorithm based on the normalized cut ( $$N_{\text {cut}}$$ N cut ) criterion, enabling efficient recursive graph partitioning. Implemented using Quantum Annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA), demonstrating promising results on real quantum hardware for complex bioinformatics tasks.

The Journal of Supercomputing•Apr 6, 2026•1 citation

Quantum-enhanced Monte Carlo Tree Search framework for combinatorial optimization problems

Yohan Finet, Yves Bérubé-Lauzière, Victor Drouin-Touchette

Over the past decades, the operations research community has developed numerous effective optimization algorithms, yet quantum computing is emerging as a new computational paradigm with the potential to approach optimization problems more efficiently. Grover's algorithm offers a provable speedup for combinatorial optimization, but its circuit depth places it beyond current noisy intermediate-scale quantum (NISQ) devices. A more accessible alternative is to reformulate the optimization problem as a quadratic unconstrained binary optimization (QUBO) problem and apply quantum annealing; however, practical problem instances remain out of reach for existing hardware. We introduce AtomTreeSearch, a hybrid classical-quantum algorithm that integrates a quantum subroutine natively implementable on neutral-atom quantum computers within a Monte Carlo Tree Search framework. At each expansion step, a maximal weighted independent set of candidate actions provided by the quantum processor is selected, and these collective actions are performed to obtain a child node. We benchmark our method on the Traveling Salesman Problem, with instances of up to 60 cities on random Euclidean instances and up to 100 cities on TSPLIB instances. Our hybrid algorithm generally matches or outperforms both OR-Tools and simulated annealing on these instances, and we find that the quantum subroutine produces more diverse and higher-quality branches compared to classical alternate subroutines. These results suggest that carefully scoped quantum subroutines embedded in classical search frameworks represent a promising path toward near-term quantum utility in combinatorial optimization.

quant-pharXiv:2606.30415•Jun 30, 2026•1 citation

Quantum-Enhanced Genomic Data Analysis for Evolutionary Biology and Species Adaptation Modeling

Duru Çakır

The exponential growth of genomic data has transformed evolutionary biology, enabling large-scale analysis of genetic variation, phylogenetic relationships, and adaptive mechanisms across species. However, classical computational approaches increasingly struggle with the combinatorial complexity, high dimensionality, and nonlinear interactions inherent in genomic datasets. This study explores how quantum-enhanced data analysis can augment evolutionary biology by enabling more efficient modeling of genomic variation and species adaptation. By leveraging quantum computing principles such as superposition, entanglement, and quantum parallelism, quantum algorithms offer the potential to accelerate sequence alignment, genotype–phenotype mapping, evolutionary optimization, and adaptive landscape exploration. Through qualitative synthesis of research in quantum computing, computational genomics, and evolutionary theory, this paper examines how quantum-enhanced frameworks can improve the detection of adaptive patterns, epistatic interactions, and evolutionary constraints. The analysis highlights potential applications in phylogenomic reconstruction, population genetics, and predictive modeling of species responses to environmental pressures. While acknowledging current technological limitations, the study argues that quantum-enhanced genomic analysis represents a promising pathway toward more scalable, precise, and predictive evolutionary models. Ultimately, this work positions quantum computing as a transformative tool for advancing our understanding of biological evolution and species resilience in rapidly changing ecosystems.

Next generation.•Dec 10, 2025•0 citations

QHap: Quantum-Inspired Haplotype Phasing

Rui Zhang, Xian-Zhe Tao, Yibo Chen +12 more

Haplotype phasing, the process of resolving parental allele inheritance patterns in diploid genomes, is critical for precision medicine and population genetics, yet the underlying optimization is NP-hard, posing a scalability challenge. To address this, we introduce QHap, a haplotype phasing algorithm that leverages quantum-annealing-inspired optimization. By reformulating haplotype phasing as a Max-Cut problem and deploying a GPU-accelerated ballistic simulated bifurcation solver, QHap accelerates phasing while maintaining accuracy comparable to established phasing tools. On the highly polymorphic human major histocompatibility complex region, QHap demonstrates 4- to 20-fold acceleration over HapCUT2 and WhatsHap with zero switch error across multiple long-read sequencing platforms. The framework implements two strategies: a read-based method for regional phasing, and a single nucleotide polymorphism-based method that, through quality-weighted probabilistic edge construction, efficiently scales to chromosome-scale tasks. Integration of Pore-C chromatin conformation capture data increases the haplotype N50 by up to 15-fold, enabling near-chromosome-scale haplotype reconstruction. QHap demonstrates that quantum-inspired algorithms operating on classical hardware offer a promising approach to addressing the growing computational demands of sequencing data, establishing a new paradigm for applying physics-inspired optimization to fundamental challenges in computational genomics.

q-bio.GNCross-listedarXiv:2603.25762•Mar 27, 2026

Scaling Quantum Optimisation Beyond Hardware Limits for Real-World Scientific Workloads: Genome Assembly on Current Quantum Hardware

Namasi G Sankar, Georgios Miliotis, Simon J. Caton

Abstract Genome assembly is important in infectious disease surveillance, antimicrobial resistance monitoring, and cancer genomics. The task of reconstructing full genomic sequences from fragmented reads, can be framed as a large scale combinatorial optimisation problem. Recent advances in quantum computing have introduced new optimisation algorithms with potential advantages for navigating complex combinatorial search spaces. However, practical deployment is limited by noisy intermediate-scale quantum (NISQ) hardware, including restricted qubit counts, limited connectivity, and high error rates. In this research, we employ the Hamiltonian Auto Decomposition Optimisation Framework (HADOF), an algorithm agnostic framework that enables scalable quantum optimisation through federated solving across small subproblems. HADOF enabled the quantum-assisted genome assembly of a 7.1 Million base pairs Pseudomonas aeruginosa genome, to our knowledge, representing the largest genome assembly graph studied on real quantum hardware to date. The results achieved a 99.348% genome fraction and 1.0 duplication ratio, demonstrating that biologically plausible genome reconstructions can be obtained despite current hardware limitations.

•Sep 9, 2026•0 citations

Towards scalable quantum annealing for pooling and blending problems: A methodological proof-of-concept

Vasileios K. Mappas, Bogdan Dorneanu, Eduardo Nolasco +2 more

Industrial optimization challenges, such as the pooling and blending problem (PBP), require advanced computational methods to address non-convexity and scalability limitations in classical solvers. This work introduces a novel methodological framework for solving PBPs using quantum annealing (QA) that transforms the PBP into quadratic unconstrained binary optimization (QUBO) formulations at two resolution levels, enabling direct deployment on quantum annealers. Key innovations include a discretization technique tailored for PBP’s bilinear constraints and an embedding method optimized for current quantum hardware. Benchmarking against classical solvers focuses on Haverly’s classical three-stream PBP, enabling transparent comparison and development of quantum embedding and solution techniques. The proposed framework offers a scalable template for adapting similar engineering systems to quantum annealing architectures. Addressing genuine industrial-scale instances will require future advances in quantum hardware and embedding algorithms. The results demonstrate that QA exhibits the best performance among the examined alternatives, provide foundational insights towards leveraging QA in Process Systems Engineering.

Process Safety and Environmental Protection•Aug 24, 2025•2 citations
Reconstructing species trees from genome-scale data is challenging due to pervasive gene tree discordance. Maximizing quartet consistency is a widely used approach for species tree inference from multi-locus data. Quartet amalgamation approaches, such as Quartet Fiduccia-Mattheyse (QFM) and Quartet MaxCut (QMC) families, have emerged as highly accurate quartet-based species tree inference techniques, but their reliance on computationally expensive classical bipartitioning heuristics, such as Fiduccia-Mattheyses (FM) and MaxCut, limits their scalability. Here, we introduce QUANTA, a quantum annealing-based quartet amalgamation method that, to our knowledge, represents the first quantum formulation of quartet-based approaches and the first species tree estimation method for multi-locus data that runs on real quantum hardware. At the core of QUANTA is a novel, general formulation of weighted quartet bipartitioning as a quadratic unconstrained binary optimization (QUBO) problem that enables quantum annealing to replace the classical bipartitioning strategies underlying the QFM and QMC families of methods. We prove that our formulation uses the minimum possible number of qubits to represent bipartitions and that its energy function correctly orders satisfied, deferred, and violated quartets for any positive penalty weights. We implemented QUANTA on real D-Wave quantum annealing hardware, and evaluated it on a wide range of simulated and biological datasets. QUANTA achieves accuracy comparable to the state-of-the-art methods, including ASTRAL and wQFM, under challenging evolutionary conditions. We also reanalyzed several biological datasets, including the avian phylogenomic dataset comprising 14,446 genes across 48 genomes, on which QUANTA reconstructed a species tree with a higher quartet score than wQFM. Remarkably, despite running on current noisy intermediate-scale quantum (NISQ) hardware, QUANTA's bipartition technique achieved 4100x speedup over the FM bipartitioning technique in wQFM on bipartition containing 90-200 taxa, while maintaining comparable tree accuracy. By establishing a theoretically grounded, hardware-independent quantum optimization framework for weighted quartet amalgamation, QUANTA opens a new direction for quantum-assisted phylogenomics and provides a foundation for increasingly scalable and accurate species tree estimation as quantum computing hardware advances. QUANTA is publicly available at https://github.com/QuitttCat/QUANTA-Phylogenomics.
Abstract Quantum computing applies principles of quantum mechanics, such as superposition and entanglement, to process information with exponential parallelism. This paradigm offers significant computational advantages over classical methods, particularly for NP-hard problems like phylogenetic tree reconstruction in evolutionary biology. Phylogenetic trees model the evolutionary relationships among species or genes, and their reconstruction is computationally challenging as the number of possible topologies grows exponentially with the number of taxa. To address this, biologists often rely on heuristic methods; however, recent work has shown that recursive graph-cut techniques can achieve high accuracy in phylogenetic inference, though at high computational cost. In this study, we present a quantum algorithm based on the normalized cut ( NcutN_{\text {cut}}Ncut​ N cut ) criterion, enabling efficient recursive graph partitioning. Implemented using Quantum Annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA), demonstrating promising results on real quantum hardware for complex bioinformatics tasks.
Over the past decades, the operations research community has developed numerous effective optimization algorithms, yet quantum computing is emerging as a new computational paradigm with the potential to approach optimization problems more efficiently. Grover's algorithm offers a provable speedup for combinatorial optimization, but its circuit depth places it beyond current noisy intermediate-scale quantum (NISQ) devices. A more accessible alternative is to reformulate the optimization problem as a quadratic unconstrained binary optimization (QUBO) problem and apply quantum annealing; however, practical problem instances remain out of reach for existing hardware. We introduce AtomTreeSearch, a hybrid classical-quantum algorithm that integrates a quantum subroutine natively implementable on neutral-atom quantum computers within a Monte Carlo Tree Search framework. At each expansion step, a maximal weighted independent set of candidate actions provided by the quantum processor is selected, and these collective actions are performed to obtain a child node. We benchmark our method on the Traveling Salesman Problem, with instances of up to 60 cities on random Euclidean instances and up to 100 cities on TSPLIB instances. Our hybrid algorithm generally matches or outperforms both OR-Tools and simulated annealing on these instances, and we find that the quantum subroutine produces more diverse and higher-quality branches compared to classical alternate subroutines. These results suggest that carefully scoped quantum subroutines embedded in classical search frameworks represent a promising path toward near-term quantum utility in combinatorial optimization.
The exponential growth of genomic data has transformed evolutionary biology, enabling large-scale analysis of genetic variation, phylogenetic relationships, and adaptive mechanisms across species. However, classical computational approaches increasingly struggle with the combinatorial complexity, high dimensionality, and nonlinear interactions inherent in genomic datasets. This study explores how quantum-enhanced data analysis can augment evolutionary biology by enabling more efficient modeling of genomic variation and species adaptation. By leveraging quantum computing principles such as superposition, entanglement, and quantum parallelism, quantum algorithms offer the potential to accelerate sequence alignment, genotype–phenotype mapping, evolutionary optimization, and adaptive landscape exploration. Through qualitative synthesis of research in quantum computing, computational genomics, and evolutionary theory, this paper examines how quantum-enhanced frameworks can improve the detection of adaptive patterns, epistatic interactions, and evolutionary constraints. The analysis highlights potential applications in phylogenomic reconstruction, population genetics, and predictive modeling of species responses to environmental pressures. While acknowledging current technological limitations, the study argues that quantum-enhanced genomic analysis represents a promising pathway toward more scalable, precise, and predictive evolutionary models. Ultimately, this work positions quantum computing as a transformative tool for advancing our understanding of biological evolution and species resilience in rapidly changing ecosystems.
Haplotype phasing, the process of resolving parental allele inheritance patterns in diploid genomes, is critical for precision medicine and population genetics, yet the underlying optimization is NP-hard, posing a scalability challenge. To address this, we introduce QHap, a haplotype phasing algorithm that leverages quantum-annealing-inspired optimization. By reformulating haplotype phasing as a Max-Cut problem and deploying a GPU-accelerated ballistic simulated bifurcation solver, QHap accelerates phasing while maintaining accuracy comparable to established phasing tools. On the highly polymorphic human major histocompatibility complex region, QHap demonstrates 4- to 20-fold acceleration over HapCUT2 and WhatsHap with zero switch error across multiple long-read sequencing platforms. The framework implements two strategies: a read-based method for regional phasing, and a single nucleotide polymorphism-based method that, through quality-weighted probabilistic edge construction, efficiently scales to chromosome-scale tasks. Integration of Pore-C chromatin conformation capture data increases the haplotype N50 by up to 15-fold, enabling near-chromosome-scale haplotype reconstruction. QHap demonstrates that quantum-inspired algorithms operating on classical hardware offer a promising approach to addressing the growing computational demands of sequencing data, establishing a new paradigm for applying physics-inspired optimization to fundamental challenges in computational genomics.
Abstract Genome assembly is important in infectious disease surveillance, antimicrobial resistance monitoring, and cancer genomics. The task of reconstructing full genomic sequences from fragmented reads, can be framed as a large scale combinatorial optimisation problem. Recent advances in quantum computing have introduced new optimisation algorithms with potential advantages for navigating complex combinatorial search spaces. However, practical deployment is limited by noisy intermediate-scale quantum (NISQ) hardware, including restricted qubit counts, limited connectivity, and high error rates. In this research, we employ the Hamiltonian Auto Decomposition Optimisation Framework (HADOF), an algorithm agnostic framework that enables scalable quantum optimisation through federated solving across small subproblems. HADOF enabled the quantum-assisted genome assembly of a 7.1 Million base pairs Pseudomonas aeruginosa genome, to our knowledge, representing the largest genome assembly graph studied on real quantum hardware to date. The results achieved a 99.348% genome fraction and 1.0 duplication ratio, demonstrating that biologically plausible genome reconstructions can be obtained despite current hardware limitations.
Industrial optimization challenges, such as the pooling and blending problem (PBP), require advanced computational methods to address non-convexity and scalability limitations in classical solvers. This work introduces a novel methodological framework for solving PBPs using quantum annealing (QA) that transforms the PBP into quadratic unconstrained binary optimization (QUBO) formulations at two resolution levels, enabling direct deployment on quantum annealers. Key innovations include a discretization technique tailored for PBP’s bilinear constraints and an embedding method optimized for current quantum hardware. Benchmarking against classical solvers focuses on Haverly’s classical three-stream PBP, enabling transparent comparison and development of quantum embedding and solution techniques. The proposed framework offers a scalable template for adapting similar engineering systems to quantum annealing architectures. Addressing genuine industrial-scale instances will require future advances in quantum hardware and embedding algorithms. The results demonstrate that QA exhibits the best performance among the examined alternatives, provide foundational insights towards leveraging QA in Process Systems Engineering.