A quantum algorithm for solving 0-1 Knapsack problems

authored by: Sören Wilkening, Andreea Iulia Lefterovici, Lennart Binkowski, Michael Perk, Sándor P. Fekete, Tobias J. Osborne
Abstract: We present two novel contributions for achieving and assessing quantum advantage in solving difficult optimisation problems, both in theory and foreseeable practice. (1) We introduce the “Quantum Tree Generator” to generate in superposition all feasible solutions of a given 0-1 knapsack instance; combined with amplitude amplification, this identifies optimal solutions. Assuming fully connected logical qubits and comparable quantum clock speed, QTG offers perspectives for runtimes competitive to classical state-of-the-art knapsack solvers for instances with only 100 variables. (2) By introducing a new technique that exploits logging data from a classical solver, we can predict the runtime of our method way beyond the range of existing quantum platforms and simulators, for benchmark instances with up to 600 variables. Under the given assumptions, we demonstrate the QTG’s potential practical quantum advantage for such instances, indicating the promise of an effective approach for hard combinatorial optimisation problems.
Organisation(s): Institute of Theoretical Physics
External Organisation(s): Volkswagen AG
Technische Universität Braunschweig
Type: Article
Journal: npj Quantum information
Volume: 11
ISSN: 2056-6387
Publication date: 26.08.2025
Publication status: Published
Peer reviewed: Yes
ASJC Scopus subject areas: Computer Science (miscellaneous), Statistical and Nonlinear Physics, Computer Networks and Communications, Computational Theory and Mathematics
Electronic version(s): https://doi.org/10.1038/s41534-025-01097-8 (Access: Open)

BibTeX

@article{86a4eedc1318478292f3cfedfa6802ab,
title = "A quantum algorithm for solving 0-1 Knapsack problems",
abstract = "We present two novel contributions for achieving and assessing quantum advantage in solving difficult optimisation problems, both in theory and foreseeable practice. (1) We introduce the “Quantum Tree Generator” to generate in superposition all feasible solutions of a given 0-1 knapsack instance; combined with amplitude amplification, this identifies optimal solutions. Assuming fully connected logical qubits and comparable quantum clock speed, QTG offers perspectives for runtimes competitive to classical state-of-the-art knapsack solvers for instances with only 100 variables. (2) By introducing a new technique that exploits logging data from a classical solver, we can predict the runtime of our method way beyond the range of existing quantum platforms and simulators, for benchmark instances with up to 600 variables. Under the given assumptions, we demonstrate the QTG{\textquoteright}s potential practical quantum advantage for such instances, indicating the promise of an effective approach for hard combinatorial optimisation problems.",
author = "S{\"o}ren Wilkening and Lefterovici, {Andreea Iulia} and Lennart Binkowski and Michael Perk and Fekete, {S{\'a}ndor P.} and Osborne, {Tobias J.}",
note = "Publisher Copyright: {\textcopyright} The Author(s) 2025.",
year = "2025",
month = aug,
day = "26",
doi = "10.1038/s41534-025-01097-8",
language = "English",
volume = "11",
journal = "npj Quantum information",
issn = "2056-6387",
publisher = "Nature Partner Journals",
number = "1",
}