A mathematical reformulation of coverage constraints known as prefix-sum encoding has demonstrated that structural problem design can significantly improve the performance of quantum annealing processors without requiring changes to underlying hardware. In a research study published in EPJ Quantum Technology, investigators evaluated prefix-sum encoding on the D-Wave Advantage quantum annealer using haplotype inference by pure parsimony, an APX-hard combinatorial optimization challenge from computational genomics. The team reported that their specialized formulation, designated PrefixHI, reduced physical qubit requirements on the quantum processor by eighteen to twenty percent compared to prior formulations. Furthermore, the approach increased the average experimental success probability across fifty test instances from thirty-five to forty percent under existing formulations up to 54.39 percent. These empirical gains emerged purely from mathematical reformulation, establishing that the precise manner in which constraints are mapped onto physical quantum devices plays a determining role in optimization quality.
Combinatorial optimization problems frequently incorporate coverage constraints, which stipulate that at least one element from an assigned candidate set must be selected. These mathematical structures appear across numerous practical domains, including sensor deployment, facility location, job scheduling, and genomic sequence reconstruction, yet determining even the basic feasibility of such systems is frequently NP-complete. Quantum annealing seeks to resolve these hard problems by searching for the low-energy ground states of an Ising Hamiltonian, using quantum tunneling through transverse magnetic fields to escape local energy minima that typically trap classical heuristic algorithms. However, physical quantum annealers remain severely limited by sparse hardware connectivity. On commercial processors such as the D-Wave Advantage system, built upon the Pegasus graph topology, each superconducting physical flux qubit couples directly to at most fifteen neighbors. This restricted physical connectivity contrasts sharply with the complete, all-to-all connectivity required by typical combinatorial formulations.
To execute a dense problem on a sparse architecture, researchers must implement minor embedding, an algorithmic mapping process that assigns each logical decision variable to a chain of ferromagnetically coupled physical qubits. Longer qubit chains introduce significant vulnerability, as thermal fluctuations and noise within the physical apparatus can cause chain breaks, wherein individual physical qubits within a logical chain disagree on their orientation. Existing coverage formulations, such as the Set Cover with Pairs method and the QHIk family of formulations, exacerbate this issue by introducing auxiliary variables governed by dense coupling graphs. These dense patterns inflate total logical variable counts and force embedding algorithms to construct lengthy physical qubit chains across the processor, thereby degrading the probability of discovering true ground-state solutions. Prefix-sum encoding directly circumvents these structural drawbacks by converting disjunctive coverage requirements into sequential chains of binary variables that interact strictly through nearest-neighbor pairings.
Rather than monitoring which particular elements satisfy a given coverage constraint, prefix-sum encoding tracks cumulatively whether satisfaction has taken place at each sequential stage. In a baseline coverage scenario involving several binary indicator variables, the system introduces a chain of auxiliary binary variables that trace a monotone progression from an initial zero boundary to a final unit boundary. Under a tight enforcement scheme, auxiliary variables follow a recursive maximum relation that mandates immediate propagation: as soon as any satisfied indicator appears, the auxiliary record switches to one and stays fixed for all subsequent indices. This deterministic propagation establishes a strict one-to-one correspondence between feasible selections and auxiliary configurations. While mathematically rigorous, tight enforcement locks the auxiliary vector into a single state for each feasible selection, completely eliminating configuration flexibility within the combined optimization landscape.
The central theoretical insight developed by the authors involves replacing tight propagation with lazy enforcement, also characterized as delayed recording. Under lazy enforcement, the auxiliary sequence is governed by three linear conditions: monotonicity, which forbids the auxiliary sequence from stepping backward; jump validity, which dictates that any forward step from zero to one must occur exclusively at an index where the corresponding indicator variable is satisfied; and boundary constants that fix the initial value at zero and the final value at one. The investigators proved mathematically that this relaxed formulation is strictly equivalent to standard coverage constraints. Crucially, lazy enforcement permits the auxiliary sequence to register coverage at any valid position after a satisfied indicator is encountered, rather than demanding an immediate transition. This mathematical leeway introduces ground-state degeneracy, providing multiple valid auxiliary configurations for each feasible indicator assignment and significantly enlarging the target ground-state manifold during physical annealing evolution.
To embed these logical conditions into quadratic unconstrained binary optimization models, the researchers constructed a dual-penalty formulation that incorporates monotonicity penalties alongside jump validity penalties, while fixing boundary conditions through constant substitution. The monotonicity penalty penalizes backward steps through quadratic products of adjacent auxiliary variables, whereas the jump validity penalty penalizes transitions occurring at unsatisfied indicator locations. Bounded coupling represents a primary advantage of this algebraic construction: each auxiliary variable couples to at most two prefix neighbors along the linear chain and at most two indicator variables, ensuring that no auxiliary node exceeds a maximum degree of four in standard coverage. Theoretical penalty analysis established that when the jump penalty coefficient exceeds the objective function sensitivity bound, and the monotonicity coefficient strictly exceeds the jump penalty coefficient, every global minimizer is mathematically guaranteed to satisfy coverage.
The researchers applied this mathematical framework to Haplotype Inference by Pure Parsimony, a problem centered on determining the smallest set of parental haplotypes capable of explaining an observed set of diploid genotypes in a population. In diploid organisms, single-nucleotide polymorphisms yield genotypes represented by sequences of homozygous and heterozygous markers. Resolving a genotype requires selecting at least one compatible pair of candidate haplotypes whose site-by-site combination reconstructs the observed sequence. In the resulting PrefixHI formulation, the cumulative auxiliary chain requires L minus n logical variables, where L denotes the total count of compatible haplotype pairs and n represents the number of genotypes. This represents L fewer variables than the Set Cover with Pairs approach. Because pair satisfaction involves the product of two binary haplotype selections, the authors introduced a linear surrogate expression that counts missing haplotypes, avoiding cubic terms while restricting auxiliary interactions to a maximum degree of six.
The team also derived rigorous penalty bounds specifically tailored for pair coverage constraints. Because the pair surrogate term can reach a maximum magnitude of two when both haplotypes are missing, the theoretical monotonicity condition strengthens to require that the monotonicity penalty coefficient exceed twice the jump validity coefficient. The authors proved that setting the monotonicity parameter to two and the jump parameter to one establishes an exact boundary regime. At these minimal boundary values, any constraint violations that emerge can be resolved through an efficient, deterministic completion procedure running in O(L) time. This post-processing routine examines each genotype, identifies the compatible pair exhibiting maximum partial selection, and activates any remaining missing haplotypes without increasing total Hamiltonian energy, thereby preserving exact global optimality while minimizing hardware quantization errors.
Experimental evaluation was conducted on the D-Wave Advantage system 4.1, housing 5627 superconducting flux qubits in the Pegasus graph architecture operating at approximately 15 millikelvin. The research team generated fifty synthetic HIPP benchmark instances using Hudson’s coalescent simulator paired with Gusfield’s random mating protocol, stratifying problems into small, medium, and large categories spanning 23 to 224 candidate haplotypes. Ground-truth parsimony solutions were established using Google OR-Tools CP-SAT solver, which solved every instance within one second. Physical minor embedding was executed via the minorminer heuristic under a sixty-second timeout. Across the test suite, PrefixHI demonstrated substantial embedding efficiency, requiring 528 physical qubits on a representative 150-pair instance compared to 645 qubits for the Set Cover with Pairs baseline and 583 qubits for the QHI3 model, confirming marked reductions in physical qubit requirements.
Annealing runs using standard twenty-microsecond forward schedules revealed consistent performance advantages for PrefixHI across all instance sizes. PrefixHI achieved an overall solve success probability of 54.39 percent across the fifty benchmarks, noticeably outperforming both Set Cover with Pairs at 35.05 percent and QHI2 at 40.21 percent. In the large problem category, PrefixHI attained a success rate of 32.79 percent, more than double the 13.38 percent recorded for SCP and well above the 20.58 percent for QHI2. Furthermore, PrefixHI delivered superior near-optimal solution quality, maintaining an overall average approximation ratio of 1.114 relative to 1.205 for QHI2 and 1.262 for SCP. By applying the same deterministic repair pipeline to uniformly distributed random bitstrings, which yielded an approximation ratio of 6.25 and zero percent solve probability, the authors demonstrated that the performance gains stemmed directly from the QUBO landscape rather than repair heuristics.
Beyond standard forward annealing, the researchers investigated modified schedule functions, testing pause, quench, and bang-anneal-bang protocols. While intermediate schedule pauses yielded neutral or negative effects on success probability, a optimized bang-anneal-bang schedule—applying rapid Hamiltonian ramps at the start and conclusion separated by a slower intermediate evolution window—delivered the best overall performance. Calibrating the slow phase to begin at two microseconds with an annealing parameter of 0.3 increased average success probability to 59.36 percent and lowered median intrinsic time-to-solution from 0.105 milliseconds down to 0.093 milliseconds, representing an intrinsic speed improvement of approximately twelve percent. Comparative evaluations against classical simulated annealing on an AMD processor showed that quantum annealing achieved roughly twenty-nine times faster sampling per read, although classical simulated annealing achieved higher raw success probability at matched sample counts, and classical runtimes were unburdened by quantum programming and readout latencies.
Finally, the authors demonstrated that prefix-sum encoding generalizes systematically beyond coverage constraints to one-hot selection and packing constraints. By modifying boundary conditions, the identical quadratic penalty framework can enforce equality constraints where exactly one element is chosen, or packing constraints where at most one selection is permitted, while maintaining linear variable scaling and bounded-degree coupling structures. Although the empirical study was confined to instances up to 224 haplotypes on the Pegasus topology, the mathematical principles highlight an important trajectory for quantum algorithm engineering. By combining cumulative auxiliary tracking, bounded physical degrees, and degenerate ground-state landscapes, prefix-sum encoding demonstrates that formulation-level design provides an effective mechanism for extracting superior performance from connectivity-constrained quantum hardware.
Subject of Research: Prefix-sum encoding for coverage constraints in quantum annealing applied to computational genomics
Article Title: Prefix-sum encoding for quantum annealing with application to haplotype inference
Article References: Nghiem, N.-V.-D., Vinh, L. S., Trinh, B., & Dinh, T. N. (2026). Prefix-sum encoding for quantum annealing with application to haplotype inference. EPJ Quantum Technology, 13(1), Article 111. https://doi.org/10.1140/epjqt/s40507-026-00543-6
Image Credits: AI Generated
DOI: 10.1140/epjqt/s40507-026-00543-6
Keywords: quantum annealing, prefix-sum encoding, haplotype inference, computational genomics, combinatorial optimization, D-Wave Advantage, Pegasus topology, QUBO formulation, minor embedding, ground-state degeneracy, lazy enforcement, bang-anneal-bang, time-to-solution, qubit connectivity, pure parsimony, simulated annealing, superconducting flux qubits
Cite Scienmag News
Katie Riggs. (November 21, 2026). Prefix-Sum Encoding Boosts Quantum Annealing Success for Haplotype Inference Problems. Scienmag. https://scienmag.com/prefix-sum-encoding-boosts-quantum-annealing-success-for-haplotype-inference-problems/
Katie Riggs. "Prefix-Sum Encoding Boosts Quantum Annealing Success for Haplotype Inference Problems." Scienmag, 21 November 2026, https://scienmag.com/prefix-sum-encoding-boosts-quantum-annealing-success-for-haplotype-inference-problems/. Accessed 21 November 2026.
Katie Riggs. "Prefix-Sum Encoding Boosts Quantum Annealing Success for Haplotype Inference Problems." Scienmag. November 21, 2026. https://scienmag.com/prefix-sum-encoding-boosts-quantum-annealing-success-for-haplotype-inference-problems/








