A quantum algorithm for solving 0-1 Knapsack problems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914024630779904 |
|---|---|
| author | Wilkening, Sören Lefterovici, Andreea-Iulia Binkowski, Lennart Perk, Michael Fekete, Sándor Osborne, Tobias J. |
| author_facet | Wilkening, Sören Lefterovici, Andreea-Iulia Binkowski, Lennart Perk, Michael Fekete, Sándor Osborne, Tobias J. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_06623 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A quantum algorithm for solving 0-1 Knapsack problems Wilkening, Sören Lefterovici, Andreea-Iulia Binkowski, Lennart Perk, Michael Fekete, Sándor Osborne, Tobias J. Quantum Physics Data Structures and Algorithms 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. |
| title | A quantum algorithm for solving 0-1 Knapsack problems |
| topic | Quantum Physics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2310.06623 |