RT Journal Article
T1 Reconstruction of phylogenetic trees via graph-splitting using quantum computing
A1 Fernández Otero, Nicolás
A1 Fernández Pena, Anselmo Tomás
A1 Pichel Campos, Juan Carlos
K1 Phylogenetic tree
K1 Quantum annealing
K1 Quantum approximate optimization algorithm
K1 Mincut
K1 Ncut
AB 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 () 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.
PB Springer
YR 2026
FD 2026-04-06
LK https://hdl.handle.net/10347/46888
UL https://hdl.handle.net/10347/46888
LA eng
NO Fernández-Otero, N., Pena, T.F., & Pichel, J.C. (2026) Reconstruction of phylogenetic trees via graph-splitting using quantum computing. Journal of Supercomputing 82(324). https://doi.org/10.1007/s11227-026-08465-x
NO The authors acknowledge CESGA (Centro de Supercomputación de Galicia) for providing access to the QMIO quantum computer. This work has received financial support from the Agencia Estatal de Investigación (Spain) (PID2022-141623NB-I00 and PID2022-137061OB-C22), Xunta de Galicia - Consellería de Cultura, Educación, Formación Profesional e Universidades (Centro de investigación de Galicia accreditation 2024-2027 ED431G-2023/04 and Reference Competitive Group accreditation ED431C-2022/016), and the European Union (European Regional Development Fund - ERDF).
NO Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature.
DS Minerva
RD 9 may 2026