Resource-efficient formulations of the Knapsack problem for quantum computing
Abstract
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.
Related
- Numerical study of the three-boson bound-state problem in partial-wave and vector-variable formulations
- Non-Markovian dissipation as a resource for quantum reservoir computing
- Resource-efficient quantum-walker quantum random access memory
- Solving the MAX-k-CUT problem for hypergraphs with quantum computing
- Parameter-efficient neural computing with programmable photonic meshes
BibTeX
@misc{heuvel2026resourceefficient,
title = {{Resource-efficient formulations of the Knapsack problem for quantum computing}},
author = {Pim van den Heuvel and Vrinda Mehta and Dennis Willsch and J. A. Montanez-Barrera and Kristel Michielsen},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.06797},
eprint = {2611.06797},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.06797},
}
RIS
TY - UNPB
TI - Resource-efficient formulations of the Knapsack problem for quantum computing
AU - Pim van den Heuvel
AU - Vrinda Mehta
AU - Dennis Willsch
AU - J. A. Montanez-Barrera
AU - Kristel Michielsen
PY - 2026
DA - 2026/11/04
PB - arXiv
DO - 10.48550/arxiv.2611.06797
UR - https://arxiv.org/abs/2611.06797
AB - 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.
ER -