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• 10 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

VRP Assembler: haplotype-resolved de novo assembly of diploid and polyploid genomes using quantum computing

Yibo Chen, Jun-Han Huang, Yuhui Sun +3 more

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 VRP assembler: a novel approach that transforms this task into a vehicle routing problem, a combinatorial optimization problem 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 assembly across the human major histocompatibility complex (MHC) region. Our results show encouraging performance compared to hifiasm with the phasing accuracy first approaching the theoretical limit, underscoring the promising future of quantum computing in bioinformatics.

•Oct 21, 2023•0 citations

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•63 citations

VRP Assembler: Haplotype-Resolved de novo Assembly of Diploid and Polyploid Genomes Using Quantum Computing

Yibo Chen, Jun-Han Huang, Yuhui Sun +3 more

•Jan 1, 2023•2 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•3 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•17 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.
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 VRP assembler: a novel approach that transforms this task into a vehicle routing problem, a combinatorial optimization problem 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 assembly across the human major histocompatibility complex (MHC) region. Our results show encouraging performance compared to hifiasm with the phasing accuracy first 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.
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.
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.