Prefix-sum encoding for quantum annealing with application to haplotype inference

Quantum annealing promises advantages for combinatorial optimization, but current hardware remains limited by sparse qubit connectivity. Encoding constrained problems onto these devices typically requires auxiliary variables that introduce dense couplings, degrading performance. Here we present prefix-sum encoding, which transforms coverage constraints into sequential variable chains with only nearest-neighbor interactions. We prove that a relaxed enforcement scheme, tracking whether coverage occurred rather than where, is mathematically equivalent to standard coverage while creating beneficial degeneracy in the solution landscape. Applied to haplotype inference, a hard problem in computational genomics, our encoding reduces qubit requirements by 18% and improves success rates from 35–40% to 54% on D-Wave quantum hardware. These gains arise purely from reformulation, demonstrating that how problems are encoded can be as important as the hardware or algorithms used to solve them. Our encoding extends naturally to one-hot selection and resource packing constraints, establishing broad applicability across combinatorial optimization.