Nonvariational quantum optimisation approaches to pangenome-guided sequence assembly
Josh Cudby, Sergii Strelchuk · 2026
Read Nonvariational quantum optimisation approaches to pangenome-guided sequence assembly by Josh Cudby, Sergii Strelchuk (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-06106.txt.
Introduction
Cudby and Strelchuk develop quantum optimisation for pangenome-guided sequence assembly, whose walk problem is NP-hard. They test quadratic unconstrained binary optimisation and a new higher-order binary optimisation, or HUBO. HUBO cuts variables from order N squared to order N log N. Both encodings run under nonvariational Iterative-QAOA, a fixed linear-ramp schedule with warm-start bias updates. In noiseless simulations, Iterative-QAOA finds optimal assemblies from as few as 10 to the minus 17 percent of candidates. IBM hardware closely reproduces results with CVaR-style post-selection.
Catalog record
| CREATOR | Josh Cudby, Sergii Strelchuk |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 51272 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.06106
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Nonvariational quantum optimisation approaches to pangenome-guided sequence assembly Josh Cudby, Sergii Strelchuk 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 ) O(N^{2}) to O ( N log N ) 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 % 10^{-17}\% of all candidate solutions, and 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. 1 Introduction In [ 6 ] , we introduced pangenome-guided sequence assembly (PGSA), a method for assembling short reads from an individual using a high-quality precomputed pangenome as a reference. We showed that PGSA attains assembly quality comparable to de novo assemblers while producing substantially fewer contigs. We proposed a Quadratic Unconstrained Binary Optimisation (QUBO) formulation of PGSA, demonstrating improved robustness to noise arising from missing or divergent genomic regions compared to traditional search-based methods. We also compared several classical optimisation strategies and provided a proof-of-principle for a quantum optimisation approach. For a short genomics primer and background on sequence assembly, see section S1 . In this work, we investigate the potential for quantum optimisation to provide practical utility for PGSA. We develop a Higher-order Unconstrained Binary Optimisation (HUBO) formulation of PGSA. By encoding node indices in binary rather than enumerating node–time pairs, this formulation reduces the number of variables from \mathcal{O}\left\lparen TN\right\rparen to \mathcal{O}\left\lparen T\log(N)\right\rparen . We employ Iterative-QAOA (following [ 15 ] ) to solve both QUBO- and HUBO-encoded problems, exploring the trade-offs between quantum resources and solution quality. PGSA comprises a multi-step workflow, shown in fig. 1 , which can be summarised as: 1. Problem inputs: A synthetic pangenome and a randomly-sampled set of short fragments of DNA (or reads ) from a new genome. 2. Map reads and estimate frequencies: The reads are matched against the sequence data contained in the nodes of the graph. The number of appearances of each node in the new genome is estimated from the number of hits per node, normalised by the node length and the number of input reads. 3. Map to binary form and solve: The goal of this step is to identify a path through the pangenome graph that best fits the observed frequencies, and it is the main computational bottleneck, referred to as Oriented Tangle Resolution . We map to a binary optimization form and solve using Iterative-QAOA. 4. Post-process: When the ground truth is known, as is the case for our synthetic problems in this work, we can evaluate the quality of the assembled genome compared. For a full treatment, see [ 6 ] . In this work, we focus on the computational bottleneck in step three. Figure 1 : A sketch of the PGSA procedure. (1) Problem inputs are a pangenome graph and a set of reads. (2) Reads are matched onto nodes of the graph, and an estimate of the number of visits to each node is calculated. (3) The path-finding problem is mapped to a binary optimization and solved with Iterative-QAOA. (4) Post-processing evaluates the quality of the assembly. After step three, we have a pangenome graph G whose vertex set V is partitioned into two subsets V_{+} and V_{-} , where a vertex v_{-}\in V_{-} corresponds to the reverse complement of the DNA corresponding to v_{+}\in V_{+} . Each vertex has a corresponding weight, given by the function w:V\rightarrow\mathbb{R}_{+} . This path-finding task is formalised as the following optimisation problem, which we call Oriented Tangle Resolution . Problem 1 (Oriented Tangle Resolution) . Given a vertex-weighted, oriented graph G=(V_{+}\cup V_{-},E,w) , find a walk W on G that minimises C_{G}(W)=\sum_{v\in V}\Bigl(\#W(v_{+})+\#W(v_{-})-w(v)\Bigr)^{2}, (1) where \#W(v_{+}),\#W(v_{-}) are the number of times W visits v_{+} and v_{-} respectively. Quantum optimisation offers a promising avenue for quantum utility and advantage, particularly for combinatorial problems in which the solution space grows exponentially. QAOA [ 9 ] addresses optimisation problems by mapping a cost function C to a Hamiltonian H_{C} whose ground state(s) correspond to optimal solution(s). In its standard form, a QAOA circuit first prepares an initial state that is the ground state of a mixer Hamiltonian, often choosing the simple H_{M}\coloneqq-\sum_{i}X_{i} and corresponding initial state \ket{+}^{\otimes n} . The state is then evolved by applying p layers of alternating \exp(-i\gamma_{k}H_{C}) and \exp(-i\beta_{k}H_{M}) operations for real vectors \beta=(\beta_{1},\ldots,\beta_{p}) and \gamma=(\gamma_{1},\ldots,\gamma_{p}) . A classical optimiser is used to find optimal values of \beta and \gamma such that measurements of the final state are low-cost assignments with high probability. HUBO formulations allow higher-order interaction terms, enabling more compact encodings in this setting; the downside is that (classically) solving them is generally more difficult and less well-explored in the literature. Standard classical approaches use a variable expansion to map HUBO instances onto QUBO instances. Notably, however, HUBO may not have such a large solution overhead when mapped to QAOA algorithms on quantum computers. In that setting, each layer of the cost Hamiltonian now contains multi-qubit Z rotations, rather than only single- and two-qubit rotations. These gates need to be compiled down to 2-qubit gates, but constructions that are linear in the number of qubits involved exist [ 11 ] . Further depth reductions are possible through careful compilation (see section 4.2 ). Due to their simple circuit structure, QAOA circuits are well-suited for implementation on Noisy Intermediate-Scale Quantum (NISQ) devices in the near term. There is evidence that, for certain problem classes, QAOA offers an advantage over classical methods [ 22 , 18 , 5 ] . However, the potential utility of quantum optimisation is severely limited by hardware constraints. The depth of QAOA circuits increases linearly with the hyperparameter p , and there is evidence that local quantum algorithms, such as p=1 QAOA, cannot offer any advantage over classical methods [ 1 ] . This creates a tension between increasing p to enhance expressivity and keeping p small enough for practical implementation. Moreover, the variational loop involved in optimising the parameters is costly and can be challenging due to the presence of barren plateaus [ 10 ] . Several