ABSTRACT The maximum parsimony phylogenetic tree reconstruction problem is NP‐hard, presenting a computational bottleneck for classical computing and motivating the exploration of emerging paradigms like quantum computing. To this end, we design three optimization models compatible with both classical and quantum solvers. Our method directly searches the complete solution space of all possible tree topologies and ancestral states, thereby avoiding the potential biases associated with pre‐constructing candidate internal nodes. Among these models, the branch‐based model drastically reduces the number of variables and explicit constraints through a specific variable definition, providing a novel modeling approach effective not only for phylogenetic tree building but also for other tree problems. The correctness of this model is validated with a classical solver, which obtains solutions that are generally better than those from heuristics on the gene dataset. Moreover, our quantum simulations successfully find the exact optimal solutions for small‐scale instances with rapid convergence, highlighting the potential of quantum computing to offer a new avenue for solving these intractable problems in evolutionary biology.
ABSTRACT The maximum parsimony phylogenetic tree reconstruction problem is NP‐hard, presenting a computational bottleneck for classical computing and motivating the exploration of emerging paradigms like quantum computing. To this end, we design three optimization models compatible with both classical and quantum solvers. Our method directly searches the complete solution space of all possible tree topologies and ancestral states, thereby avoiding the potential biases associated with pre‐constructing candidate internal nodes. Among these models, the branch‐based model drastically reduces the number of variables and explicit constraints through a specific variable definition, providing a novel modeling approach effective not only for phylogenetic tree building but also for other tree problems. The correctness of this model is validated with a classical solver, which obtains solutions that are generally better than those from heuristics on the gene dataset. Moreover, our quantum simulations successfully find the exact optimal solutions for small‐scale instances with rapid convergence, highlighting the potential of quantum computing to offer a new avenue for solving these intractable problems in evolutionary biology.
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 ( 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.
Haplotype inference with pure parsimony (HIPP) problem seeks to reconstruct a minimum set of haplotypes that explain a given set of genotypes observed from a population. This important problem is known to be NP-hard. In this paper, we explore the potential of quantum computing in retrieving optimal solutions for HIPP. We investigate several approaches to encode HIPP into quadratic unconstrained binary optimization (QUBO), which can be solved on quantum annealers. Further, we propose a new QUBO for HIPP, termed QHI, exploiting the structure of HIPP to reduce the QUBO size. Our comprehensive experiments on the state-of-the-art D-Wave annealer indicate comparable solution quality for quantum annealing approaches compared to classical simulated annealing. They also validate the effectiveness of our proposed QHI formulation in both solution quality and size.
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.
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.
ABSTRACT Background Quantum algorithms exploit superposition and parallelism to address complex combinatorial problems, many of which fall into the non‐polynomial (NP) class. Sudoku, a widely known logic‐based puzzle, is proven to be NP‐complete and thus presents a suitable testbed for exploring quantum optimization approaches. The Ising model—originally introduced for NP‐hard Ising spin glass problems—provides a natural mathematical framework for expressing constraints in a form amenable to quantum computation. Objective This work aims to develop a quantum Sudoku solver inspired by the Ising model that minimizes the number of logical qubits required, making it suitable for today's resource‐limited quantum hardware. The broader goal is to demonstrate a modeling strategy that may generalize to other NP optimization problems. Methods The solver construction begins by translating Sudoku constraints into mathematical expressions represented through couplings of atomic spins. These constraints are formulated into observable operators using Pauli operators, enabling the calculation of expectation values over candidate quantum states. Individual quantum algorithmic components are then integrated into a global optimization pipeline. The performance and correctness of this solver are evaluated through the Quantum Approximate Optimization Algorithm (QAOA) combined with the COBYLA classical optimizer within the IBM Qiskit SDK. A code example illustrates the implementation of multiple puzzle constraints and the verification of the resulting quantum circuits. Results The modeling approach successfully encodes Sudoku rules into an Ising Hamiltonian with reduced qubit requirements. Preliminary evaluations using QAOA and COBYLA demonstrate that the solver can identify puzzle‐consistent solutions while maintaining low resource consumption. The quantum circuit construction matches theoretical expectations, and the code snippet confirms successful constraint enforcement within the Qiskit environment. Conclusions The proposed quantum Sudoku solver highlights the potential of Ising‐based formulations to address NP optimization problems on near‐term quantum devices. By reducing logical qubit usage without sacrificing algorithmic integrity, this strategy may support broader applications in constrained optimization. The implementation serves as both a proof of concept and a practical guide for extending Ising‐inspired quantum modeling to other NP‐hard domains.
Biological evolution provides an immensely powerful toolset for problem solving, while evolutionary computation attempts to harness the power of biological evolution for solving problems using classical computing paradigms. Quantum computing offers many apparent advantages over classical computing for certain types of problems, such as searching or optimizing over large solution sets. Once practical quantum computers are available, we would like to take advantage of their highly parallel computing capabilities for use in evolutionary computation. In this work we explore the nexus between quantum and evolutionary computation, and propose an approach toward a practical framework for performing evolutionary computation on quantum computers