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

The Journal of Supercomputing

Reconstruction of phylogenetic trees via graph-splitting using quantum computing

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

Published Apr 6, 2026• 1 citation
Publisher

Abstract

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.

DOI
10.1007/s11227-026-08465-x

Related papers

Quantum Computing Prospects in Bioinformatics

Sofia Ivanov, Ivan Dubois, Isabella Ivanov

Bioinformatics workloads -- including protein structure prediction, molecular dynamics simulation, genomic sequencealignment, and phylogenetic tree reconstruction -- are among the most computationally intensive problems in science,with many exhibiting exponential or combinatorial scaling that overwhelms classical high-performance computing.Quantum computing, leveraging superposition and entanglement to explore exponentially large solution spaces,promises polynomial or exponential speedups for specific bioinformatics tasks. However, current noisyintermediate-scale quantum (NISQ) devices (50-1,000+ qubits, high error rates) are far from fault-tolerant quantumcomputers, and the practical quantum advantage for bioinformatics remains undemonstrated. This study systematicallybenchmarked five computational approaches -- classical exact algorithms, classical heuristics (genetic algorithm,simulated annealing), GPU-accelerated methods, variational quantum algorithms (VQE, QAOA) on NISQ hardware, anda proposed hybrid quantum-classical bioinformatics pipeline (HQC-Bio) combining quantum subroutines for combinatorialsubproblems with classical pre/post-processing -- across four bioinformatics tasks: multiple sequence alignment (MSA, n= 500 protein families), protein folding on lattice models (HP model, chains 20-60 residues), molecular docking scoring(1,000 ligand-receptor pairs), and phylogenetic tree search (taxa sets 10-50). HQC-Bio achieved the highest solutionquality for protein folding (optimal energy found in 84.6% of 40-residue instances vs 62.4% for simulated annealing; p <0.001) and phylogenetic search (log-likelihood within 0.2% of exact ML for 30-taxa trees vs 1.8% for RAxML heuristic).However, quantum wall-clock time exceeded classical GPU by 12-340x due to NISQ hardware overhead (circuitcompilation, shot noise, error mitigation), establishing that current quantum advantage is in solution quality rather thanspeed. Resource estimation projects that fault-tolerant quantum computers with 10,000-100,000 logical qubits couldachieve genuine speedups of 10-1,000x for these tasks within 10-15 years.

The Biosis Bulletin: Bioscience and Information science Journal•Oct 8, 2024•0 citations

Large-Scale Quantum Approximate Optimization via Divide-and-Conquer

Junde Li, Mahabubul Alam, Swaroop Ghosh

Quantum approximate optimization algorithm (QAOA) is a promising hybrid quantum-classical algorithm for solving combinatorial optimization problems. However, it cannot overcome qubit limitation for large-scale problems. Furthermore, the simulation time of QAOA scales poorly with the problem size. We propose a divide-and-conquer QAOA (DC-QAOA) to address the above challenges for graph maximum cut (MaxCut) problem. The algorithm works by recursively partitioning a larger graph into smaller ones whose MaxCut solutions are obtained with small-size noisy intermediate-scale quantum computers. The overall solution is retrieved from the subsolutions by applying the combination policy of measurement distribution reconstruction (MDR). The solution quality depends on the graph partitioning algorithm and MDR policy. Multiple partitioning and reconstruction methods are proposed and compared. Results are evaluated by metrics, such as quantum program runtime, measurement expectation value (EV), and approximation ratio (AR). The results show that DC-QAOA achieves 97.14% AR (20.32% higher than classical counterpart), and 94.79% EV (15.80% higher than quantum annealing). DC-QAOA solves large-scale graph instances with a polynomial rate or returns unsuccessful partition if graph connectivity requirement is not fulfilled otherwise.

arXiv:2102.13288•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Oct 5, 2022•63 citations

Edge-based quantum approximate optimization algorithm for MAX-CUT problem

Youngjin Seo, Jun Heo

Quantum computing has emerged as a promising paradigm to tackle computationally intensive problems that classical computers struggle with. In this study, we explore the application of the Edge-based quantum approximate optimization algorithm (QAOA) to the MAX-CUT problem, a well-known combinatorial optimization challenge. MAX-CUT aims to partition the vertices of a graph into two subsets such that the number of edges between the subsets is maximized. We define the edge-based MAX-CUT problem and propose a method for applying QAOA specifically tailored to this formulation. We conduct simulations using IBM’s Qiskit framework, examining both vertex-based and edge-based QAOA implementations across various graph structures. Our results highlight the comparative performance of these approaches in terms of solution quality and computational efficiency. Specifically, we analyze the impact of different graph sizes and edge densities on the complexity and CNOT gate counts of the proposed algorithms. This analysis provides insights into leveraging quantum computing for combinatorial optimization tasks, particularly focusing on the implications for practical applications and future research directions.

Quantum Information Processing•Sep 23, 2025•2 citations

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

A Variational Qubit-Efficient MaxCut Heuristic Algorithm

Yovav Tene-Cohen, Tomer Kelman, Ohad Lev +1 more

Abstract MaxCut is a key NP-hard combinatorial optimization problem. Quantum computing offers methods to solve such problems potentially better than classical counterparts, with the Quantum Approximate Optimization Algorithm (QAOA) being a state-of-the-art example. However, the performance of quantum methods is currently hindered by hardware noise and limited qubit volumes. We present a variational Qubit-Efficient MaxCut (QEMC) algorithm that requires only $$O(\log N)$$ O ( log N ) qubits to tackle graphs of size N , an exponential reduction compared to QAOA. We demonstrate cutting-edge performance for 32-node graph instances (5 qubits) on real superconducting hardware, and for graphs with up to 2048 nodes (11 qubits) via classical simulations. The QEMC algorithm is based on an innovative encoding scheme, with potentially broad applicability, that empowers it with strong noise resilience, but also enables its efficient classical simulation. As such, the QEMC algorithm provides a challenging benchmark for QAOA on noisy devices and offers a novel quantum-inspired approach.

arXiv:2308.10383•npj Quantum Information•Feb 16, 2026•12 citations

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

Niloy Kumar Mondal, Md. Shamsuzzoha Bayzid

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.

•Nov 6, 2026•0 citations
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.
Bioinformatics workloads -- including protein structure prediction, molecular dynamics simulation, genomic sequencealignment, and phylogenetic tree reconstruction -- are among the most computationally intensive problems in science,with many exhibiting exponential or combinatorial scaling that overwhelms classical high-performance computing.Quantum computing, leveraging superposition and entanglement to explore exponentially large solution spaces,promises polynomial or exponential speedups for specific bioinformatics tasks. However, current noisyintermediate-scale quantum (NISQ) devices (50-1,000+ qubits, high error rates) are far from fault-tolerant quantumcomputers, and the practical quantum advantage for bioinformatics remains undemonstrated. This study systematicallybenchmarked five computational approaches -- classical exact algorithms, classical heuristics (genetic algorithm,simulated annealing), GPU-accelerated methods, variational quantum algorithms (VQE, QAOA) on NISQ hardware, anda proposed hybrid quantum-classical bioinformatics pipeline (HQC-Bio) combining quantum subroutines for combinatorialsubproblems with classical pre/post-processing -- across four bioinformatics tasks: multiple sequence alignment (MSA, n= 500 protein families), protein folding on lattice models (HP model, chains 20-60 residues), molecular docking scoring(1,000 ligand-receptor pairs), and phylogenetic tree search (taxa sets 10-50). HQC-Bio achieved the highest solutionquality for protein folding (optimal energy found in 84.6% of 40-residue instances vs 62.4% for simulated annealing; p <0.001) and phylogenetic search (log-likelihood within 0.2% of exact ML for 30-taxa trees vs 1.8% for RAxML heuristic).However, quantum wall-clock time exceeded classical GPU by 12-340x due to NISQ hardware overhead (circuitcompilation, shot noise, error mitigation), establishing that current quantum advantage is in solution quality rather thanspeed. Resource estimation projects that fault-tolerant quantum computers with 10,000-100,000 logical qubits couldachieve genuine speedups of 10-1,000x for these tasks within 10-15 years.
Quantum approximate optimization algorithm (QAOA) is a promising hybrid quantum-classical algorithm for solving combinatorial optimization problems. However, it cannot overcome qubit limitation for large-scale problems. Furthermore, the simulation time of QAOA scales poorly with the problem size. We propose a divide-and-conquer QAOA (DC-QAOA) to address the above challenges for graph maximum cut (MaxCut) problem. The algorithm works by recursively partitioning a larger graph into smaller ones whose MaxCut solutions are obtained with small-size noisy intermediate-scale quantum computers. The overall solution is retrieved from the subsolutions by applying the combination policy of measurement distribution reconstruction (MDR). The solution quality depends on the graph partitioning algorithm and MDR policy. Multiple partitioning and reconstruction methods are proposed and compared. Results are evaluated by metrics, such as quantum program runtime, measurement expectation value (EV), and approximation ratio (AR). The results show that DC-QAOA achieves 97.14% AR (20.32% higher than classical counterpart), and 94.79% EV (15.80% higher than quantum annealing). DC-QAOA solves large-scale graph instances with a polynomial rate or returns unsuccessful partition if graph connectivity requirement is not fulfilled otherwise.
Quantum computing has emerged as a promising paradigm to tackle computationally intensive problems that classical computers struggle with. In this study, we explore the application of the Edge-based quantum approximate optimization algorithm (QAOA) to the MAX-CUT problem, a well-known combinatorial optimization challenge. MAX-CUT aims to partition the vertices of a graph into two subsets such that the number of edges between the subsets is maximized. We define the edge-based MAX-CUT problem and propose a method for applying QAOA specifically tailored to this formulation. We conduct simulations using IBM’s Qiskit framework, examining both vertex-based and edge-based QAOA implementations across various graph structures. Our results highlight the comparative performance of these approaches in terms of solution quality and computational efficiency. Specifically, we analyze the impact of different graph sizes and edge densities on the complexity and CNOT gate counts of the proposed algorithms. This analysis provides insights into leveraging quantum computing for combinatorial optimization tasks, particularly focusing on the implications for practical applications and future research directions.
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.
Abstract MaxCut is a key NP-hard combinatorial optimization problem. Quantum computing offers methods to solve such problems potentially better than classical counterparts, with the Quantum Approximate Optimization Algorithm (QAOA) being a state-of-the-art example. However, the performance of quantum methods is currently hindered by hardware noise and limited qubit volumes. We present a variational Qubit-Efficient MaxCut (QEMC) algorithm that requires only O(log⁡N)O(\log N)O(logN) O ( log N ) qubits to tackle graphs of size N , an exponential reduction compared to QAOA. We demonstrate cutting-edge performance for 32-node graph instances (5 qubits) on real superconducting hardware, and for graphs with up to 2048 nodes (11 qubits) via classical simulations. The QEMC algorithm is based on an innovative encoding scheme, with potentially broad applicability, that empowers it with strong noise resilience, but also enables its efficient classical simulation. As such, the QEMC algorithm provides a challenging benchmark for QAOA on noisy devices and offers a novel quantum-inspired approach.
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.