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

arXiv:2603.25762

QHap: Quantum-Inspired Haplotype Phasing

Rui Zhang, Xian-Zhe Tao, Yibo Chen, Jiawei Zhang, Lei He, Dongming Fang, Lin Yang, Yuhui Sun, Qinyuan Zheng, Xinmeng Shi, Yang Zhou, Wanyi Chen, Chentao Yang, Man-Hong Yung, Jun-Han Huang

q-bio.GNquant-phSubmitted Mar 26, 2026• Announced Mar 27, 2026• Revised May 6, 2026 (v2)
v1 · Mar 26, 2026v2 · May 6, 2026
arXivHTMLPDF

Abstract

Haplotype phasing, the process of resolving parental allele inheritance patterns in diploid genomes, is critical for precision medicine and population genetics, yet the underlying optimization is NP-hard, posing a scalability challenge. To address this, we introduce QHap, a haplotype phasing algorithm that leverages quantum-annealing-inspired optimization. By reformulating haplotype phasing as a Max-Cut problem and deploying a GPU-accelerated ballistic simulated bifurcation solver, QHap accelerates phasing while maintaining accuracy comparable to established phasing tools. On the highly polymorphic human major histocompatibility complex region, QHap demonstrates 4- to 20-fold acceleration over HapCUT2 and WhatsHap with zero switch error across multiple long-read sequencing platforms. The framework implements two strategies: a read-based method for regional phasing, and a single nucleotide polymorphism-based method that, through quality-weighted probabilistic edge construction, efficiently scales to chromosome-scale tasks. Integration of Pore-C chromatin conformation capture data increases the haplotype N50 by up to 15-fold, enabling near-chromosome-scale haplotype reconstruction. QHap demonstrates that quantum-inspired algorithms operating on classical hardware offer a promising approach to addressing the growing computational demands of sequencing data, establishing a new paradigm for applying physics-inspired optimization to fundamental challenges in computational genomics.

Comments
15 pages, 6 figures

Related papers

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

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

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.

Cell Reports Methods•Apr 12, 2024•10 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

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

Neuromorphic Edge Computing: Bridging the Gap Between Energy-Efficient AI and Real-Time Decision Making

Ibrahim Khalil, Longfei Wu

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.

International Journal of Computer Engineering in Research Trends•Sep 30, 2024•0 citations

Performance of quantum annealing inspired algorithms for combinatorial optimization problems

Qingguo Zeng, Xiaopeng Cui, Bowen Liu +3 more

Abstract Two classes of quantum-annealing-inspired-algorithms (QAIA), namely different variants of simulated coherent Ising machine and simulated bifurcation, have been proposed for efficiently solving combinatorial optimization problems recently. In order to certify the superiority of these algorithms, standardized comparisons among them and against other physics-based algorithms are necessary. In this work, for Max-Cut problems up to 20,000 nodes, we benchmark QAIA against quantum annealing and other physics-based algorithms. We found that ballistic simulated bifurcation excelled for chimera and small-scale graphs, achieving nearly a 50-fold reduction in time-to-solution compared to quantum annealing. For large-scale graphs, discrete simulated bifurcation achieves the lowest time-to-target and outperforms D-Wave Advantage system when tasked with finding the maximum cut value in pegasus graphs. Our results suggest that QAIA represents a promising means for solving combinatorial optimization problems in practice, and can act as a natural baseline for competing quantum algorithms.

Communications Physics•Jul 19, 2024•27 citations

Haplotype Inference with Pure Parsimony: A Quantum Computing Approach

Nguyen-Viet-Dung Nghiem, Sy Vinh Le, Tu N. Nguyen +1 more

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.

International Conference on Communications•Jun 9, 2024•0 citations
Haplotype phasing, the process of resolving parental allele inheritance patterns in diploid genomes, is critical for precision medicine and population genetics, yet the underlying optimization is NP-hard, posing a scalability challenge. To address this, we introduce QHap, a haplotype phasing algorithm that leverages quantum-annealing-inspired optimization. By reformulating haplotype phasing as a Max-Cut problem and deploying a GPU-accelerated ballistic simulated bifurcation solver, QHap accelerates phasing while maintaining accuracy comparable to established phasing tools. On the highly polymorphic human major histocompatibility complex region, QHap demonstrates 4- to 20-fold acceleration over HapCUT2 and WhatsHap with zero switch error across multiple long-read sequencing platforms. The framework implements two strategies: a read-based method for regional phasing, and a single nucleotide polymorphism-based method that, through quality-weighted probabilistic edge construction, efficiently scales to chromosome-scale tasks. Integration of Pore-C chromatin conformation capture data increases the haplotype N50 by up to 15-fold, enabling near-chromosome-scale haplotype reconstruction. QHap demonstrates that quantum-inspired algorithms operating on classical hardware offer a promising approach to addressing the growing computational demands of sequencing data, establishing a new paradigm for applying physics-inspired optimization to fundamental challenges in computational genomics.
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.
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.
Abstract Two classes of quantum-annealing-inspired-algorithms (QAIA), namely different variants of simulated coherent Ising machine and simulated bifurcation, have been proposed for efficiently solving combinatorial optimization problems recently. In order to certify the superiority of these algorithms, standardized comparisons among them and against other physics-based algorithms are necessary. In this work, for Max-Cut problems up to 20,000 nodes, we benchmark QAIA against quantum annealing and other physics-based algorithms. We found that ballistic simulated bifurcation excelled for chimera and small-scale graphs, achieving nearly a 50-fold reduction in time-to-solution compared to quantum annealing. For large-scale graphs, discrete simulated bifurcation achieves the lowest time-to-target and outperforms D-Wave Advantage system when tasked with finding the maximum cut value in pegasus graphs. Our results suggest that QAIA represents a promising means for solving combinatorial optimization problems in practice, and can act as a natural baseline for competing quantum algorithms.
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.