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

Cell Reports Methods

Haplotype-resolved assembly of diploid and polyploid genomes using quantum computing

Yibo Chen, Jun-Han Huang, Yuhui Sun, Yong Zhang, Yuxiang Li, Xun Xu

Published Apr 12, 2024• 11 citations
Publisher

Abstract

Precision medicine's emphasis on individual genetic variants highlights the importance of haplotype-resolved assembly, a computational challenge in bioinformatics given its combinatorial nature. While classical algorithms have made strides in addressing this issue, the potential of quantum computing remains largely untapped. Here, we present the vehicle routing problem (VRP) assembler: an approach that transforms this task into a vehicle routing problem, an optimization formulation solvable on a quantum computer. We demonstrate its potential and feasibility through a proof of concept on short synthetic diploid and triploid genomes using a D-Wave quantum annealer. To tackle larger-scale assembly problems, we integrate the VRP assembler with Google's OR-Tools, achieving a haplotype-resolved local assembly across the human major histocompatibility complex (MHC) region. Our results show encouraging performance compared to Hifiasm with phasing accuracy approaching the theoretical limit, underscoring the promising future of quantum computing in bioinformatics.

DOI
10.1016/j.crmeth.2024.100754

Related papers

Genome assembly using quantum and quantum-inspired annealing

Aleksey S. Boev, Alexander Rakitko, Sergey R. Usmanov +5 more

Recent advances in DNA sequencing open prospects to make whole-genome analysis rapid and reliable, which is promising for various applications including personalized medicine. However, existing techniques for de novo genome assembly, which is used for the analysis of genomic rearrangements, chromosome phasing, and reconstructing genomes without a reference, require solving tasks of high computational complexity. Here we demonstrate a method for solving genome assembly tasks with the use of quantum and quantum-inspired optimization techniques. Within this method, we present experimental results on genome assembly using quantum annealers both for simulated data and the [Formula: see text]X 174 bacteriophage. Our results pave a way for a significant increase in the efficiency of solving bioinformatics problems with the use of quantum computing technologies and, in particular, quantum annealing might be an effective method. We expect that the new generation of quantum annealing devices would outperform existing techniques for de novo genome assembly. To the best of our knowledge, this is the first experimental study of de novo genome assembly problems both for real and synthetic data on quantum annealing devices and quantum-inspired techniques.

arXiv:2004.06719•Scientific Reports•Jun 23, 2021•72 citations

Quantum Path Integral Approach for Vehicle Routing Optimization With Limited Qubit

Kumar Gautam, Chang Wook Ahn

The Vehicle Routing Problem (VRP) is a crucial combinatorial optimization problem in transportation, logistics, and supply chain management. Quantum computing has gained interest in solving complex optimization issues. This review paper proposes a novel approach that combines quantum computing principles with the Feynman path integral formulation to address the VRP. The paper focuses on limited qubits and how quantum algorithms can circumvent this limitation. Conventional methods, such as Lagrangian and combinatorial optimization, require computational time to solve complex atomic-scale problems. The path integral formulation with the first Born approximation method offers a more elegant explanation of quantum computing. The algorithm investigates quantum system dynamics using the Schrodinger wave equation and computes probability amplitude distributions for optimal vehicle routing techniques. This work will take advantage of entanglement and interference effects for heuristic sampling of high-quality solutions, making the Quantum Path Integral Approach (QPIA) a promising study environment for investigating quantum circuits and algorithms in routing problems with constrained qubits.

IEEE Transactions on Intelligent Transportation Systems•Dec 6, 2023•25 citations

Quantum computing approach in uncertain data optimization problem for vehicle routing problem

Patrisia Teresa Marsoit, Liu Wang Zhang, Deodoro Lakonde +1 more

This research addresses the Vehicle Routing Problem (VRP) with uncertain data and proposes a novel approach using quantum computing techniques. The problem involves optimizing vehicle routes considering uncertain customer demands, time windows, and vehicle capacities. We formulate the problem mathematically and develop an algorithmic framework to tackle it. The approach incorporates multiple scenarios based on the uncertainty distribution and selects the one with the minimum cost to optimize the vehicle routes. Through a numerical example, we demonstrate the effectiveness of the proposed approach in generating optimal routes that minimize the total distance traveled by the vehicles. The results highlight the solution quality, adaptability to uncertainty, and potential benefits in terms of cost reduction and resource utilization. While the computational efficiency of quantum computing approaches is a consideration, this research provides a promising direction for addressing uncertain optimization problems in logistics and transportation. Future research should focus on scalability and refinement of the algorithm to further enhance its applicability in real-world scenarios.

International Journal of Enterprise Modelling•Sep 30, 2021•0 citations

Quantum-Assisted Vehicle Routing: Realizing QAOA-based Approach on Gate-Based Quantum Computer

Talha Azfar, Osama M. Raisuddin, Ruimin Ke +1 more

The Vehicle Routing Problem (VRP) is a fundamental combinatorial optimization challenge with broad applications in logistics and transportation. In this work, we present a quantum-assisted framework that integrates the Quantum Approximate Optimization Algorithm (QAOA) with a link-based formulation of VRP. Our approach encodes flow conservation and subtour elimination directly into the cost Hamiltonian, preserving graph structure while minimizing resource requirements for practical hardware implementation. We design and implement the full pipeline on a gate-based quantum computer, including problem formulation, encoding, circuit synthesis, and execution on IBM Quantum System One. Experimental results on small VRP instances highlight the effects of penalty scaling, coefficient normalization, and circuit depth on solution feasibility under hardware noise. While scalability remains constrained by circuit complexity and decoherence, the study demonstrates a practical pathway for implementing VRP on quantum hardware and identifies methodological directions for advancing near-term quantum optimization.

arXiv:2505.01614•May 2, 2025•23 citations

Algorithm for DNA sequence assembly by quantum annealing

Katarzyna Nałęcz-Charkiewicz, Robert Marek Nowak

BACKGROUND: The assembly task is an indispensable step in sequencing genomes of new organisms and studying structural genomic changes. In recent years, the dynamic development of next-generation sequencing (NGS) methods raises hopes for making whole-genome sequencing a fast and reliable tool used, for example, in medical diagnostics. However, this is hampered by the slowness and computational requirements of the current processing algorithms, which raises the need to develop more efficient algorithms. One possible approach, still little explored, is the use of quantum computing. RESULTS: We present a proof of concept of de novo assembly algorithm, using the Genomic Signal Processing approach, detecting overlaps between DNA reads by calculating the Pearson correlation coefficient and formulating the assembly problem as an optimization task (Traveling Salesman Problem). Computations performed on a classic computer were compared with the results achieved by a hybrid method combining CPU and QPU calculations. For this purpose quantum annealer by D-Wave was used. The experiments were performed with artificially generated data and DNA reads coming from a simulator, with actual organism genomes used as input sequences. To our knowledge, this work is one of the few where actual sequences of organisms were used to study the de novo assembly task on quantum annealer. CONCLUSIONS: Proof of concept carried out by us showed that the use of quantum annealer (QA) for the de novo assembly task might be a promising alternative to the computations performed in the classical model. The current computing power of the available devices requires a hybrid approach (combining CPU and QPU computations). The next step may be developing a hybrid algorithm strictly dedicated to the de novo assembly task, using its specificity (e.g. the sparsity and bounded degree of the overlap-layout-consensus graph).

BMC Bioinformatics•Apr 7, 2022•40 citations

Scaling Vehicle Routing Problem Solvers with QUBO-based Specialized Hardware

Hanjing Xu, Hayato Ushijima‐Mwesigwa, Indradeep Ghosh

The Vehicle Routing Problem (VRP) is an NP-Hard optimization problem that has been widely studied over the last decades due to its wide practical applications. The goal of the VRP is to design efficient routes for vehicles performing service functions such as the distribution of goods from one or more central locations. There exist many variants to the VRP. These variations arise due to application-specific constraints such as vehicle capacities, delivery time windows, split deliveries, and many more. Due to the complexity of the problem, solvers are usually designed for specific variants and do not generally scale well to larger problem instances. As we approach the physical scaling limits of Moore's law, different novel special-purpose hardware are being designed for solving combinatorial optimization problems such as quantum and quantum-inspired devices. However, these devices are able to solve problems up to fixed variable sizes. In this work, we carry out experiments on the Fujitsu Digital Annealer (DA), quantum-inspired hardware, and show that we are able to get near-optimal results for instances of the Capacitated VRP (CVRP) that can be directly solved on the DA. We further develop a hybrid method for solving large-scale VRP instances. In order to achieve this, we develop a novel candidate route generation method, whose core solves a multi-objective clustering problem on the DA. Once a set of candidate routes has been selected, we then solve a Set Partitioning Problem on the DA to get a final solution. We apply our method to the CVRP and the CVRP with Time-Windows and show that we are able to get near-optimal solutions for problem instances significantly larger the base solvers could solve directly, within the same amount of computation time.

IEEE/ACM Symposium on Edge Computing (SEC)•Dec 1, 2022•3 citations
Precision medicine's emphasis on individual genetic variants highlights the importance of haplotype-resolved assembly, a computational challenge in bioinformatics given its combinatorial nature. While classical algorithms have made strides in addressing this issue, the potential of quantum computing remains largely untapped. Here, we present the vehicle routing problem (VRP) assembler: an approach that transforms this task into a vehicle routing problem, an optimization formulation solvable on a quantum computer. We demonstrate its potential and feasibility through a proof of concept on short synthetic diploid and triploid genomes using a D-Wave quantum annealer. To tackle larger-scale assembly problems, we integrate the VRP assembler with Google's OR-Tools, achieving a haplotype-resolved local assembly across the human major histocompatibility complex (MHC) region. Our results show encouraging performance compared to Hifiasm with phasing accuracy approaching the theoretical limit, underscoring the promising future of quantum computing in bioinformatics.
Recent advances in DNA sequencing open prospects to make whole-genome analysis rapid and reliable, which is promising for various applications including personalized medicine. However, existing techniques for de novo genome assembly, which is used for the analysis of genomic rearrangements, chromosome phasing, and reconstructing genomes without a reference, require solving tasks of high computational complexity. Here we demonstrate a method for solving genome assembly tasks with the use of quantum and quantum-inspired optimization techniques. Within this method, we present experimental results on genome assembly using quantum annealers both for simulated data and the [Formula: see text]X 174 bacteriophage. Our results pave a way for a significant increase in the efficiency of solving bioinformatics problems with the use of quantum computing technologies and, in particular, quantum annealing might be an effective method. We expect that the new generation of quantum annealing devices would outperform existing techniques for de novo genome assembly. To the best of our knowledge, this is the first experimental study of de novo genome assembly problems both for real and synthetic data on quantum annealing devices and quantum-inspired techniques.
The Vehicle Routing Problem (VRP) is a crucial combinatorial optimization problem in transportation, logistics, and supply chain management. Quantum computing has gained interest in solving complex optimization issues. This review paper proposes a novel approach that combines quantum computing principles with the Feynman path integral formulation to address the VRP. The paper focuses on limited qubits and how quantum algorithms can circumvent this limitation. Conventional methods, such as Lagrangian and combinatorial optimization, require computational time to solve complex atomic-scale problems. The path integral formulation with the first Born approximation method offers a more elegant explanation of quantum computing. The algorithm investigates quantum system dynamics using the Schrodinger wave equation and computes probability amplitude distributions for optimal vehicle routing techniques. This work will take advantage of entanglement and interference effects for heuristic sampling of high-quality solutions, making the Quantum Path Integral Approach (QPIA) a promising study environment for investigating quantum circuits and algorithms in routing problems with constrained qubits.
This research addresses the Vehicle Routing Problem (VRP) with uncertain data and proposes a novel approach using quantum computing techniques. The problem involves optimizing vehicle routes considering uncertain customer demands, time windows, and vehicle capacities. We formulate the problem mathematically and develop an algorithmic framework to tackle it. The approach incorporates multiple scenarios based on the uncertainty distribution and selects the one with the minimum cost to optimize the vehicle routes. Through a numerical example, we demonstrate the effectiveness of the proposed approach in generating optimal routes that minimize the total distance traveled by the vehicles. The results highlight the solution quality, adaptability to uncertainty, and potential benefits in terms of cost reduction and resource utilization. While the computational efficiency of quantum computing approaches is a consideration, this research provides a promising direction for addressing uncertain optimization problems in logistics and transportation. Future research should focus on scalability and refinement of the algorithm to further enhance its applicability in real-world scenarios.
The Vehicle Routing Problem (VRP) is a fundamental combinatorial optimization challenge with broad applications in logistics and transportation. In this work, we present a quantum-assisted framework that integrates the Quantum Approximate Optimization Algorithm (QAOA) with a link-based formulation of VRP. Our approach encodes flow conservation and subtour elimination directly into the cost Hamiltonian, preserving graph structure while minimizing resource requirements for practical hardware implementation. We design and implement the full pipeline on a gate-based quantum computer, including problem formulation, encoding, circuit synthesis, and execution on IBM Quantum System One. Experimental results on small VRP instances highlight the effects of penalty scaling, coefficient normalization, and circuit depth on solution feasibility under hardware noise. While scalability remains constrained by circuit complexity and decoherence, the study demonstrates a practical pathway for implementing VRP on quantum hardware and identifies methodological directions for advancing near-term quantum optimization.
BACKGROUND: The assembly task is an indispensable step in sequencing genomes of new organisms and studying structural genomic changes. In recent years, the dynamic development of next-generation sequencing (NGS) methods raises hopes for making whole-genome sequencing a fast and reliable tool used, for example, in medical diagnostics. However, this is hampered by the slowness and computational requirements of the current processing algorithms, which raises the need to develop more efficient algorithms. One possible approach, still little explored, is the use of quantum computing. RESULTS: We present a proof of concept of de novo assembly algorithm, using the Genomic Signal Processing approach, detecting overlaps between DNA reads by calculating the Pearson correlation coefficient and formulating the assembly problem as an optimization task (Traveling Salesman Problem). Computations performed on a classic computer were compared with the results achieved by a hybrid method combining CPU and QPU calculations. For this purpose quantum annealer by D-Wave was used. The experiments were performed with artificially generated data and DNA reads coming from a simulator, with actual organism genomes used as input sequences. To our knowledge, this work is one of the few where actual sequences of organisms were used to study the de novo assembly task on quantum annealer. CONCLUSIONS: Proof of concept carried out by us showed that the use of quantum annealer (QA) for the de novo assembly task might be a promising alternative to the computations performed in the classical model. The current computing power of the available devices requires a hybrid approach (combining CPU and QPU computations). The next step may be developing a hybrid algorithm strictly dedicated to the de novo assembly task, using its specificity (e.g. the sparsity and bounded degree of the overlap-layout-consensus graph).
The Vehicle Routing Problem (VRP) is an NP-Hard optimization problem that has been widely studied over the last decades due to its wide practical applications. The goal of the VRP is to design efficient routes for vehicles performing service functions such as the distribution of goods from one or more central locations. There exist many variants to the VRP. These variations arise due to application-specific constraints such as vehicle capacities, delivery time windows, split deliveries, and many more. Due to the complexity of the problem, solvers are usually designed for specific variants and do not generally scale well to larger problem instances. As we approach the physical scaling limits of Moore's law, different novel special-purpose hardware are being designed for solving combinatorial optimization problems such as quantum and quantum-inspired devices. However, these devices are able to solve problems up to fixed variable sizes. In this work, we carry out experiments on the Fujitsu Digital Annealer (DA), quantum-inspired hardware, and show that we are able to get near-optimal results for instances of the Capacitated VRP (CVRP) that can be directly solved on the DA. We further develop a hybrid method for solving large-scale VRP instances. In order to achieve this, we develop a novel candidate route generation method, whose core solves a multi-objective clustering problem on the DA. Once a set of candidate routes has been selected, we then solve a Set Partitioning Problem on the DA to get a final solution. We apply our method to the CVRP and the CVRP with Time-Windows and show that we are able to get near-optimal solutions for problem instances significantly larger the base solvers could solve directly, within the same amount of computation time.