A quantum algorithm for solving 0-1 Knapsack problems

verfasst von: 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.
Organisationseinheit(en): Institut für Theoretische Physik
Externe Organisation(en): Volkswagen AG
Technische Universität Braunschweig
Typ: Artikel
Journal: npj Quantum information
Band: 11
ISSN: 2056-6387
Publikationsdatum: 26.08.2025
Publikationsstatus: Veröffentlicht
Peer-reviewed: Ja
ASJC Scopus Sachgebiete: Informatik (sonstige), Statistische und nichtlineare Physik, Computernetzwerke und -kommunikation, Theoretische Informatik und Mathematik
Elektronische Version(en): https://doi.org/10.1038/s41534-025-01097-8 (Zugang: Offen)

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",
}