Loading [MathJax]/extensions/tex2jax.js

A quantum algorithm for the solution of the 0-1 Knapsack problem

Research output: Working paper/PreprintPreprint

Authors

External Research Organisations

  • Volkswagen AG
  • Technische Universität Braunschweig

Details

Original languageEnglish
Publication statusE-pub ahead of print - 10 Oct 2023

Abstract

Here we present two novel contributions for achieving quantum advantage in solving difficult optimisation problems, both in theory and foreseeable practice. (1) We introduce the "Quantum Tree Generator", an approach to generate in superposition all feasible solutions of a given instance, yielding together with amplitude amplification the optimal solutions for 0-1 knapsack problems. The QTG offers massive memory savings and enables competitive runtimes compared to the classical state-of-the-art knapsack solvers (such as COMBO, Gurobi, CP-SAT, Greedy) already for instances involving as few as 100 variables. (2) By introducing a new runtime calculation technique that exploits logging data from the classical solver COMBO, we can predict the runtime of our method way beyond the range of existing quantum platforms and simulators, for various benchmark instances with up to 600 variables. Combining both of these innovations, we demonstrate the QTG's potential practical quantum advantage for large-scale problems, indicating an effective approach for combinatorial optimisation problems.

Cite this

A quantum algorithm for the solution of the 0-1 Knapsack problem. / Wilkening, Sören; Lefterovici, Andreea-Iulia; Binkowski, Lennart et al.
2023.

Research output: Working paper/PreprintPreprint

Wilkening, S., Lefterovici, A.-I., Binkowski, L., Perk, M., Fekete, S., & Osborne, T. J. (2023). A quantum algorithm for the solution of the 0-1 Knapsack problem. Advance online publication. https://doi.org/10.48550/arXiv.2310.06623
Wilkening S, Lefterovici AI, Binkowski L, Perk M, Fekete S, Osborne TJ. A quantum algorithm for the solution of the 0-1 Knapsack problem. 2023 Oct 10. Epub 2023 Oct 10. doi: 10.48550/arXiv.2310.06623
Download
@techreport{370f2c1150314559a47ef98f22253728,
title = "A quantum algorithm for the solution of the 0-1 Knapsack problem",
abstract = "Here we present two novel contributions for achieving quantum advantage in solving difficult optimisation problems, both in theory and foreseeable practice. (1) We introduce the {"}Quantum Tree Generator{"}, an approach to generate in superposition all feasible solutions of a given instance, yielding together with amplitude amplification the optimal solutions for 0-1 knapsack problems. The QTG offers massive memory savings and enables competitive runtimes compared to the classical state-of-the-art knapsack solvers (such as COMBO, Gurobi, CP-SAT, Greedy) already for instances involving as few as 100 variables. (2) By introducing a new runtime calculation technique that exploits logging data from the classical solver COMBO, we can predict the runtime of our method way beyond the range of existing quantum platforms and simulators, for various benchmark instances with up to 600 variables. Combining both of these innovations, we demonstrate the QTG's potential practical quantum advantage for large-scale problems, indicating an effective approach for combinatorial optimisation problems. ",
author = "S{\"o}ren Wilkening and Andreea-Iulia Lefterovici and Lennart Binkowski and Michael Perk and S{\'a}ndor Fekete and Osborne, {Tobias J.}",
year = "2023",
month = oct,
day = "10",
doi = "10.48550/arXiv.2310.06623",
language = "English",
type = "WorkingPaper",

}

Download

TY - UNPB

T1 - A quantum algorithm for the solution of the 0-1 Knapsack problem

AU - Wilkening, Sören

AU - Lefterovici, Andreea-Iulia

AU - Binkowski, Lennart

AU - Perk, Michael

AU - Fekete, Sándor

AU - Osborne, Tobias J.

PY - 2023/10/10

Y1 - 2023/10/10

N2 - Here we present two novel contributions for achieving quantum advantage in solving difficult optimisation problems, both in theory and foreseeable practice. (1) We introduce the "Quantum Tree Generator", an approach to generate in superposition all feasible solutions of a given instance, yielding together with amplitude amplification the optimal solutions for 0-1 knapsack problems. The QTG offers massive memory savings and enables competitive runtimes compared to the classical state-of-the-art knapsack solvers (such as COMBO, Gurobi, CP-SAT, Greedy) already for instances involving as few as 100 variables. (2) By introducing a new runtime calculation technique that exploits logging data from the classical solver COMBO, we can predict the runtime of our method way beyond the range of existing quantum platforms and simulators, for various benchmark instances with up to 600 variables. Combining both of these innovations, we demonstrate the QTG's potential practical quantum advantage for large-scale problems, indicating an effective approach for combinatorial optimisation problems.

AB - Here we present two novel contributions for achieving quantum advantage in solving difficult optimisation problems, both in theory and foreseeable practice. (1) We introduce the "Quantum Tree Generator", an approach to generate in superposition all feasible solutions of a given instance, yielding together with amplitude amplification the optimal solutions for 0-1 knapsack problems. The QTG offers massive memory savings and enables competitive runtimes compared to the classical state-of-the-art knapsack solvers (such as COMBO, Gurobi, CP-SAT, Greedy) already for instances involving as few as 100 variables. (2) By introducing a new runtime calculation technique that exploits logging data from the classical solver COMBO, we can predict the runtime of our method way beyond the range of existing quantum platforms and simulators, for various benchmark instances with up to 600 variables. Combining both of these innovations, we demonstrate the QTG's potential practical quantum advantage for large-scale problems, indicating an effective approach for combinatorial optimisation problems.

U2 - 10.48550/arXiv.2310.06623

DO - 10.48550/arXiv.2310.06623

M3 - Preprint

BT - A quantum algorithm for the solution of the 0-1 Knapsack problem

ER -

By the same author(s)