Curator's Take
AI Commentary
This article shows that the way a combinatorial problem is encoded for quantum hardware can be as important as the algorithm itself, demonstrating that more compact QUBO formulations of the classic Knapsack problem dramatically boost success rates on both LR‑QAOA simulations and D‑Wave annealers. By cutting slack variables or tightening penalty constants, the authors achieve several orders of magnitude higher optimal‑solution probabilities, a result that directly addresses one of the biggest bottlenecks—excess qubit overhead—in near‑term quantum optimization. The work therefore provides a practical template for other inequality‑constrained problems, suggesting that smarter encodings could unlock better performance from today’s noisy intermediate‑scale quantum devices.
— Mark Eatherly
Summary
Quantum computing has emerged as a new tool for solving combinatorial optimization problems. Quantum optimization approaches usually operate on the subclass of Quadratic Unconstrained Binary Optimization (QUBO) problems. Many optimization problems can be reformulated in this form, though there are often multiple ways to do so. The choice of formulation can considerably affect the performance of QUBO solvers in practice. In this work, we study QUBO formulations of the Knapsack problem, a canonical example of a problem with inequality constraints. In the standard formulation these constraints are converted into penalty terms, which requires additional slack variables. Here, we investigate three more resource-efficient approaches for formulating the Knapsack as a QUBO. The first two modify the standard formulation, either by deriving a smaller penalty constant or by reducing the number of slack variables. The third approach is a wholly different method, which avoids the use of slack variables entirely. All three approaches increase the probability of finding the optimal solution, both in simulations of the linear ramp Quantum Approximate Optimization Algorithm (LR-QAOA) and on a D-Wave quantum annealer. The slackless method performs best, increasing success probabilities by several orders of magnitude even for relatively small problem sizes.