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.
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.
Several optimization solvers inspired by quantum annealing have been recently developed, either running on actual quantum hardware or simulating it on traditional digital computers. Industry and academics look at their potential in solving hard combinatorial optimization problems. Formally, they provide heuristic solutions for Ising models, which are equivalent to quadratic unconstrained binary optimization (QUBO). Constraints on solutions feasibility need to be properly encoded. We experiment on different ways of performing such an encoding. As benchmark we consider the cardinality constrained quadratic knapsack problem (CQKP), a minimal extension of QUBO with one inequality and one equality constraint. We consider different strategies of constraints penalization and variables encoding. We compare three QUBO solvers: quantum annealing on quantum hardware (D-Wave Advantage), probabilistic algorithms on digital hardware and mathematical programming solvers. We analyze their QUBO resolution quality and time, and the persistence values extracted in the quantum annealing sampling process. Our results show that a linear penalization of CQKP inequality improves current best practice. Furthermore, using such a linear penalization, persistence values produced by quantum hardware in a generic way allow to match a specific CQKP metric from literature. They are therefore suitable for general purpose variable fixing in core algorithms for combinatorial optimization.
Quantum annealing is a promising approach for solving combinatorial optimization problems. However, its performance is often limited by the overhead of additional qubits required for embedding logical QUBO models onto quantum annealers. This overhead becomes severe when logical QUBO models have dense connectivity. Such dense structures frequently arise when formulating equality and inequality constraints. To address this issue, we propose a method to construct a significantly sparser logical QUBO model for these constraints. By adding auxiliary variables based on specific network structures, our approach decomposes the original constraint into smaller, more manageable constraints. We demonstrate that this method reduces the number of edges (quadratic terms) from O(N2) to O(N) for the one-hot constraint and to O(NlogN) in the worst case for general equality constraints, where N is the number of variables. Experimental results on D-Wave's hardware show that our formulation leads to substantial reductions in the number of qubits required for embedding, shorter average chain lengths, lower chain break rates, and higher feasible solution rates compared to conventional methods. This work provides a practical tool for efficiently solving constrained optimization problems on current and future quantum annealers.
Critical decision-making issues in science, engineering, and industry are based on combinatorial optimization; however, its application is inherently limited by the NP-hard nature of the problem. A specialized paradigm of analogue quantum computing, quantum annealing (QA), has been proposed to solve these problems by encoding optimization problems into physical energy landscapes and solving them by quantum tunnelling systematically through exploration of solution space. This is a critical review that summarizes the current applications of quantum annealing to combinatorial optimization and includes a theoretical background, hardware designs, algorithm implementation strategies, encoding and embedding schemes, protocols to benchmark quantum annealing, areas of implementation, and links with the quantum algorithms implementation with gate-based hardware and classical solvers. We develop a unified framework, relating adiabatic quantum dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to modern flux-qubit annealers (Chimera, Pegasus, Zephyr topologies), and emergent architectures (Lechner-Hauke-Zoller systems, Rydberg atom platforms), and hybrids of quantum and classical computation. Through our analysis, we find that overhead in embedding and encoding is the largest determinant of the scalability and performance (this is not just the number of qubits). Minor embeddings also usually have a physical qubit count per logical variable of between 5 and 12 qubits, which limits effective problem capacity by 80-92% and, due to chain-breaking errors, compromises the quality of solutions.
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.
Quadratic unconstrained binary optimization (QUBO) is the standard interface to quantum annealers, yet a single constrained task admits many QUBO encodings whose penalty choices reshape the energy landscape experienced by hardware. We study a Job Shop Scheduling instance using a two-parameter family of encodings controlled by penalty weights psum (one-hot/sum constraints) and ppair (precedence constraints). Sweeping (psum,ppair), we observe sharp transitions in feasibility and solver success across classical annealing-inspired heuristics and on a D-Wave Advantage processor. Going beyond solution probability, we treat the annealer as an open thermodynamic system and perform cyclic reverse-annealing experiments initialized from thermal samples, measuring the stochastic processor energy change. From the first two moments of this energy change we infer lower bounds on entropy production, work, and exchanged heat via thermodynamic uncertainty relations, and corroborate the observed trends with adiabatic master equation simulations. We find that the same encoding transitions that govern computational hardness also reorganize dissipation: weak penalties generate low-energy infeasible manifolds, while overly strong penalties suppress the effective problem energy scale and increase irreversibility, reducing the thermodynamic efficiency. Our results establish QUBO penalties as thermodynamic control knobs and motivate thermodynamics-aware encoding strategies for noisy intermediate-scale quantum annealers.
One of the potential use cases of a quantum computer is to solve combinatorial optimisation problems more efficiently than is possible with the most advanced classical computers. Combinatorial optimisation problems that appear in industry often involve a large number of constraints. This thesis investigates algorithmic techniques that improve the performance of quantum optimisation algorithms in solving problems with constraints. We test these techniques on customer data science problems. We study an alternative penalty method for encoding constraints in Ising Hamiltonians, which can be applied to various quantum algorithms. This method only introduces linear terms to the Ising Hamiltonian, allowing for more efficient use of hardware resources than the standard quadratic penalty method. These efficiency improvements are particularly beneficial for near-term devices with a limited number of qubits that are sparsely connected. We analyse the impact of using this alternative encoding method on the performance of the quantum approximate optimisation algorithm and quantum annealing applied to example problems in customer data science. Our results are based on numerical simulations and experiments on quantum hardware. We introduce a new variant of the quantum approximate optimisation algorithm that improves its ability to solve problems with constraints. In this variant of the algorithm, the strengths of penalty functions are associated with additional variational parameters, allowing them to take different values in each layer of the quantum circuit. We perform numerical simulations of multiple variants of the quantum approximate optimisation algorithm and compare their performance.