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.
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.
Practical applicability of quantum optimisation on near term devices is constrained by limited qubit counts and hardware noise, which restricts the scalability of quantum optimisation algorithms for combinatorial problems. The simulation of large quantum circuits is also difficult and constrained by memory requirement. The Hamiltonian Auto Decomposition Optimisation Framework (HADOF) addresses this by decomposing large QUBOs into smaller subproblems that can be solved iteratively on quantum or classical backends. This allows the scalability of quantum QUBO algorithms beyond device limits, as well as their simulation on classical devices. In this research, we extend the evaluation of HADOF by benchmarking on real IBM QPUs across sequential, single-QPU parallel, and multi-QPU parallel execution modes, advancing toward High Performance Quantum (HPQ) computing for combinatorial optimisation problems.
Experimental results on IBM quantum hardware demonstrate up to 3-4x reduction in wall clock time when utilising four QPUs compared to sequential execution baseline, while maintaining comparable solution quality. Notably, even single QPU execution benefits from parallelised job orchestration and execution, yielding up to 3x speedup. Simulated results predict over 5x speed-up in parallel execution mode. We further validate the practical applicability of the approach on real world genome assembly instances, showing that both sequential and parallel HADOF variants achieve competitive accuracy while significantly improving time to solution. These results highlight the importance of parallelism at both the algorithmic and system levels, positioning HADOF as a viable pathway toward scalable quantum optimisation.
Quantum Annealing (QA) and QAOA are promising quantum optimisation algorithms used for finding approximate solutions to combinatorial problems on near-term NISQ systems. Many NP-hard problems can be reformulated as Quadratic Unconstrained Binary Optimisation (QUBO), which maps naturally onto quantum Hamiltonians. However, the limited qubit counts of current NISQ devices restrict practical deployment of such algorithms. In this study, we present the Hamiltonian Auto-Decomposition Optimisation Framework (HADOF), which leverages an iterative strategy to automatically divide the Quadratic Unconstrained Binary Optimisation (QUBO) Hamiltonian into sub-Hamiltonians which can be optimised separately using Hamiltonian based optimisers such as QAOA, QA or Simulated Annealing (SA) and aggregated into a global solution. We compare HADOF with Simulated Annealing (SA) and the CPLEX exact solver, showing scalability to problem sizes far exceeding available qubits while maintaining competitive accuracy and runtime. Furthermore, we realise HADOF for a toy problem on an IBM quantum computer, showing promise for practical applications of quantum optimisation.
Genome sequencing is essential to decode genetic information, identify organisms, understand diseases and advance personalized medicine. A critical step in any genome sequencing technique is genome assembly. However, de novo genome assembly, which involves constructing an entire genome sequence from scratch without a reference genome, presents significant challenges due to its high computational complexity, affecting both time and accuracy. In this study, we propose a hybrid approach utilizing a quantum computing-based optimization algorithm integrated with classical pre-processing to expedite the genome assembly process. Specifically, we present a method to solve the Hamiltonian and Eulerian paths within the genome assembly graph using gate-based quantum computing through a Higher-Order Binary Optimization (HOBO) formulation with the Variational Quantum Eigensolver algorithm (VQE), in addition to a novel bitstring recovery mechanism to improve optimizer traversal of the solution space. A comparative analysis with classical optimization techniques was performed to assess the effectiveness of our quantum-based approach in genome assembly. The results indicate that, as quantum hardware continues to evolve and noise levels diminish, our formulation holds a significant potential to accelerate genome sequencing by offering faster and more accurate solutions to the complex challenges in genomic research.
The integration of quantum computing into bioinformatics offers transformative advancements in genome sequencing, particularly in addressing computational bottlenecks associated with large-scale genomic data. This study introduces the QuASeR (Quantum Accelerated Sequence Reconstruction) framework, leveraging quantum algorithms such as Grover's search and quantum Fourier transform for DNA sequence reconstruction. Hypothetical simulations were conducted on datasets of varying sizes, ranging from 10 million to 1 billion base pairs, comparing the performance of the proposed quantum approach with state-of-the-art classical algorithms. Results indicate that QuASeR achieves a 40% reduction in processing time for datasets of 10 million base pairs and an 80% reduction for datasets of 1 billion base pairs, highlighting its scalability and efficiency. Moreover, the framework achieved a 95% accuracy rate in sequence alignment tasks, closely matching classical methods while significantly outperforming them in speed. These results underscore the potential of quantum computing in bioinformatics, paving the way for rapid and accurate genome sequencing, which is critical for advancing personalized medicine and large-scale genomic studies. As quantum hardware matures, the proposed framework is expected to achieve even greater practical utility, offering a paradigm shift in computational genomics.
Assembling genomes from short-read sequencing data remains difficult in repetitive regions, where reference bias and combinatorial complexity limit existing methods. Pangenome-guided sequence assembly (PGSA) mitigates reference bias by reconstructing an individual genome as a walk through a population-level graph. The associated problem, identifying a walk whose node visits match read-derived copy numbers, is NP-hard and already challenges classical solvers at a moderate scale. We develop near-term quantum optimisation approaches for this computational bottleneck. We consider two problem encodings: an established quadratic unconstrained binary optimisation and a new higher-order binary optimisation (HUBO) formulation. The latter reduces the number of variables from O(N2) to O(NlogN) and places moderate-sized instances within the qubit budget of current devices. We solve both using the Iterative-QAOA framework, which combines a fixed linear-ramp QAOA schedule with iterative warm-start bias updates, avoiding the overhead of full variational parameter optimisation. A custom circuit compilation strategy reduces hardware gate overhead by up to 67\% compared with standard tools. In noiseless simulations of QUBO problems, Iterative-QAOA reliably identifies optimal assemblies from as few as 10−17% of all candidate solutions, and \textit{IBM} quantum hardware closely reproduces relevant results with sufficient sampling via CVaR-style post-selection. For HUBO, the variable reduction comes at the cost of deeper compiled circuits and greater noise sensitivity: an expected qubit--depth trade-off. Our findings establish pangenome assembly as a concrete, biologically motivated problem class at the scale where quantum optimisation may first provide practical value.
Quantum computing has the potential to solve complex problems that are outside the scope of classical systems, making it a standard shifter. Current devices, which are considered as Noisy Intermediate-Scale Quantum (NISQ) systems, are insufficient in their practical utility due to hardware limitations, error rates, and qubit counts. The dynamic growths wanted to exceed the NISQ era and grow scalable quantum algorithms and architectures that can achieve useful quantum benefit in real-world applications are reviewed in this research. This research gives a comprehensive examination of the complications in scaling quantum systems, adjacent resource efficacy, qubit connectivity, and error correction. In addition to connecting architectural innovations like modular quantum computing, error-resilient circuit design, and distributed quantum systems, the paper provides new hybrid quantum-classical algorithms planned to exploit performance in noisy environments. Results from benchmarking in arenas like machine learning, optimization, and quantum chemistry show how these methods can provide short-term quantum benefit. Lastly, this paper proposes a research roadmap for quantum computing that highlights the requirement of co-designing algorithms, software, and hardware. The goal of this effort is to straighten the progress of quantum systems that can resolve problems in the real world at scale by addressing the inadequacies of NISQ devices and emphasizing scalable solutions.