Nonvariational quantum optimisation approaches to pangenome-guided sequence assembly

• URL: http://arxiv.org/abs/2604.06106v1
• Date: Tue, 07 Apr 2026 17:17:34 GMT
• Title: Nonvariational quantum optimisation approaches to pangenome-guided sequence assembly
• Abstract summary: We develop near-term quantum optimisation approaches for genome assembly problems.<n>We use the Iterative-QAOA framework, which combines a fixed linear-ramp QAOA schedule with iterative warm-start bias updates.<n>A custom circuit compilation strategy reduces hardware gate overhead by up to 67% compared with standard tools.
• Score: 0.42970700836450487
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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(N^2)$ to $O(N\log N)$ 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.

Related papers

• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
  arXiv  Detail & Related papers  (2026-06-14T14:11:07Z)
• Towards Scalable Persistence-Based Topological Optimization [44.16669776030478]
  Persistence-based topological optimization deforms a point cloud $X subset mathbbRd$ by minimizing objectives of the form $L(X) = ell(mathrmDgm(X))$, where $mathrmDgm(X)$ is a persistence diagram.<n>In practice, optimization is limited by two coupled issues: persistent homology is typically computed on subsamples, and the resulting topological gradients are highly sparse, with only a few anchor points receiving nonzero updates.
  arXiv  Detail & Related papers  (2026-05-09T15:47:20Z)
• Quantum Optimization Methods for the Generalized Traveling Salesman Problem [2.4029307306254513]
  This paper studies quantum optimization baselines for the Generalized Traveling Salesman Problem (GTSP)<n>We propose a novel GTSP QUBO formulation focused on maintaining feasible solutions for quantum annealing.<n>We implement a constrained QAOA variant using an XY-mixer, which preserves the stepwise Hamming weight in the ideal circuit model.
  arXiv  Detail & Related papers  (2026-04-28T11:58:35Z)
• A Scalable Distributed Quantum Optimization Framework via Factor Graph Paradigm [46.08923284345648]
  We introduce a structure-aware framework for distributed quantum optimization.<n>We find that for a search space of size $N$, our framework achieves $O(sqrtN)$ query complexity up to processors and separator dependent factors.<n>We show that structure-aware decomposition delivers a practical path to scalable distributed quantum optimization on quantum networks.
  arXiv  Detail & Related papers  (2026-03-08T15:15:52Z)
• On the Convergence of Single-Loop Stochastic Bilevel Optimization with Approximate Implicit Differentiation [44.084531611147305]
  We provide a refined convergence analysis of the Single-loop Approximate Implicit Differentiation (SSAID) algorithm.<n>Our result is noteworthy in two aspects: (i) it matches the optimal $mathcalO(-2)$ rate of state-of-the-art multi-loop methods; and (ii) it provides the first explicit, fine-grained characterization of the $$-dependence.
  arXiv  Detail & Related papers  (2026-02-27T03:12:08Z)
• Pangenome-guided sequence assembly via binary optimisation [0.040993632551842324]
  We propose a framework for pangenome-guided sequence assembly.<n>It can resolve short-read data in complex regions without bias towards a single reference genome.<n>Our method frames assembly as a graph optimisation problem, which can be implemented on quantum computers.
  arXiv  Detail & Related papers  (2025-08-11T17:17:21Z)
• Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
  Branch-and-bound algorithms effectively solve convex optimization problems, relying on the relaxation the objective function to obtain tight lower bounds.<n>We propose a branch-and-bound digitized counterdiabatic quantum optimization (BB-DCQO) algorithm that addresses the relaxation difficulties.
  arXiv  Detail & Related papers  (2025-04-21T18:19:19Z)
• Near-Optimal Parameter Tuning of Level-1 QAOA for Ising Models [3.390330377512402]
  We show how to reduce the two-dimensional $(gamma, beta)$ search to a one-dimensional search over $gamma$, with $beta*$ computed analytically.<n>This approach is validated using Recursive QAOA (RQAOA), where it consistently outperforms both coarsely optimised RQAOA and semidefinite programs.
  arXiv  Detail & Related papers  (2025-01-27T19:00:00Z)
• Direct phase encoding in QAOA: Describing combinatorial optimization problems through binary decision variables [0.7015624626359264]
  We show a more qubit-efficient circuit construction for optimization problems by the example of the Travelingperson Sales Problem (TSP)<n>Removing certain redundancies, the number of required qubits can be reduced by a linear factor compared to the aforementioned conventional encoding.<n>Our experiments show that for small instances results are just as accurate using our proposed encoding, whereas the number of required classical iterations increases only slightly.
  arXiv  Detail & Related papers  (2024-12-10T12:12:34Z)
• Quantum Annealing Solutions for the Closest String Problem with D-Wave Systems [0.0]
  Closest String Problem is an NP-complete problem which appears more commonly in bioinformatics and coding theory. Two QUBO formulations have been proposed, with one being a slight modification over the other. DWave annealers have been used, while providing guidelines for optimality on certain platform-specific concerns.
  arXiv  Detail & Related papers  (2023-10-19T16:03:25Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  We propose a novel method named Multi-block-probe Variance Reduced (MSVR) to alleviate the complexity of compositional problems. Our results improve upon prior ones in several aspects, including the order of sample complexities and dependence on strongity.
  arXiv  Detail & Related papers  (2022-07-18T12:03:26Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.