The Signal
Researchers Report Slackless Knapsack QUBO Method Performs Best
A preprint compares three resource-efficient ways to formulate the knapsack problem as a QUBO, testing them in LR-QAOA simulations and on a D-Wave quantum annealer. All three raise the probability of finding an optimal solution, while the slackless method produces gains of several orders of magnitude even for relatively small problems.

A preprint reports that three resource-efficient ways of formulating the knapsack problem as a Quadratic Unconstrained Binary Optimization problem raise the probability of finding an optimal solution. The researchers tested the approaches in simulations of the linear ramp Quantum Approximate Optimization Algorithm, or LR-QAOA, and on a D-Wave quantum annealer. The method that avoids slack variables performed best, with reported success probabilities increasing by several orders of magnitude even for relatively small problem sizes.
Source arxiv.org
Why compare knapsack formulations?
Quantum optimization approaches usually work on problems expressed as QUBOs. Many optimization problems can be reformulated in this form, and a problem can have more than one possible formulation. The authors write: “The choice of formulation can considerably affect the performance of QUBO solvers in practice.” Their study examines that issue using the knapsack problem, which they describe as a canonical example of a problem with inequality constraints.
The paper, “Resource-efficient formulations of the Knapsack problem for quantum computing,” was submitted to arXiv on 4 Nov 2026. Its authors are Pim van den Heuvel, Vrinda Mehta, Dennis Willsch, J. A. Montanez-Barrera and Kristel Michielsen.
Three approaches to the QUBO
In the standard formulation described in the abstract, inequality constraints are converted into penalty terms. That approach requires additional slack variables. The researchers investigate three alternatives intended to make the formulation more resource-efficient, comparing them with the standard approach through their reported solver tests.
The first two alternatives modify the standard formulation in different ways. One derives a smaller penalty constant; the other reduces the number of slack variables. The third takes a different route and eliminates slack variables altogether. The abstract characterizes this final approach as a wholly different method, rather than another adjustment to the standard formulation.
Reported performance
The researchers report that all three alternatives increase the probability of finding the optimal solution in both types of evaluation: LR-QAOA simulations and tests on a D-Wave quantum annealer. Instead, it says the slackless method performs best among them.
For that method, the reported increase in success probability reaches several orders of magnitude, including for relatively small problem sizes. The result concerns the probability of finding an optimal solution in the evaluations described by the authors.
The comparison therefore focuses on how choices in encoding the knapsack problem affect the reported outcomes of QUBO solvers. In the study’s account, reducing the penalty constant and reducing the number of slack variables are both beneficial, while removing slack variables entirely gives the strongest reported performance.
Source
Related stories
- Jülich Researchers Find Oscillating Limits in an Exact Ising Model
- Study finds hybrid quantum grid solver did not beat random sampling
- Adiabatic VQA Study Tests Entanglement Detection on Three Qubits
- Researchers Model Cavity-Loss Solver for MaxCut and MIS
- Study reports higher simulated Max-Cut ratios with cat-qubit QAOA