RECORD
Quantum Computing Techniques for Multi-Knapsack Problems
Quantum Physics · Submitted 13 Jan 2023
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim In addition to the high demand for better quantum hardware, our results also emphasize the necessity of more and better quantum optimization algorithms, especially for multi-knapsack problems.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Optimization problems are ubiquitous in various industrial settings, and multi-knapsack optimization is one recurrent task faced daily by several industries. The advent of quantum computing has opened a new paradigm for computationally intensive tasks, with promises of delivering better and faster solutions for specific classes of problems. This work presents a comprehensive study of quantum computing approaches for multi-knapsack problems, by investigating some of the most prominent and state-of-the-art quantum algorithms using different quantum software and hardware tools. The performance of the quantum approaches is compared for varying hyperparameters. We consider several gate-based quantum algorithms, such as QAOA and VQE, as well as quantum annealing, and present an exhaustive study of the solutions and the estimation of runtimes. Additionally, we analyze the impact of warm-starting QAOA to understand the reasons for the better performance of this approach. We discuss the implications of our results in view of utilizing quantum optimization for industrial applications in the future. In addition to the high demand for better quantum hardware, our results also emphasize the necessity of more and better quantum optimization algorithms, especially for multi-knapsack problems.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Optimization problems are ubiquitous in various industrial settings, and multi-knapsack optimization is one recurrent task faced daily by several industries. | background 1.00 | 0.03 | 0.02 | asserted 1.00 |
| s1 | The advent of quantum computing has opened a new paradigm for computationally intensive tasks, with promises of delivering better and faster solutions for specific classes of problems. | background 1.00 | 0.04 | 0.03 | hedged possibility 0.57 |
| s2 | This work presents a comprehensive study of quantum computing approaches for multi-knapsack problems, by investigating some of the most prominent and state-of-the-art quantum algorithms using different quantum software and hardware tools. | contribution 1.00 | 0.90 | 0.05 | asserted 0.98 |
| s3 | The performance of the quantum approaches is compared for varying hyperparameters. | method 0.90 | 0.88 | 0.04 | asserted 0.95 |
| s4 | We consider several gate-based quantum algorithms, such as QAOA and VQE, as well as quantum annealing, and present an exhaustive study of the solutions and the estimation of runtimes. | method 0.71 | 0.93 | 0.06 | asserted 0.98 |
| s5 | Additionally, we analyze the impact of warm-starting QAOA to understand the reasons for the better performance of this approach. | contribution 0.62 | 0.93 | 0.08 | asserted 0.71 |
| s6 | We discuss the implications of our results in view of utilizing quantum optimization for industrial applications in the future. | interpretation 0.94 | 0.53 | 0.14 | unclear 0.49 |
| s7 | In addition to the high demand for better quantum hardware, our results also emphasize the necessity of more and better quantum optimization algorithms, especially for multi-knapsack problems. | interpretation 0.68 | 0.58 | 0.60 | asserted 0.96 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Optimization problems are ubiquitous in various industrial settings, and multi-knapsack optimization is one recurrent task faced daily by several industries. The advent of quantum computing has opened a new paradigm for computationally intensive tasks, with promises of delivering better and faster solutions for specific classes of problems. This work presents a comprehensive study of quantum computing approaches for multi-knapsack problems, by investigating some of the most prominent and state-of-the-art quantum algorithms using different quantum software and hardware tools. The performance of the quantum approaches is compared for varying hyperparameters. We consider several gate-based quantum algorithms, such as QAOA and VQE, as well as quantum annealing, and present an exhaustive study of the solutions and the estimation of runtimes. Additionally, we analyze the impact of warm-starting QAOA to understand the reasons for the better performance of this approach. We discuss the implications of our results in view of utilizing quantum optimization for industrial applications in the future. In addition to the high demand for better quantum hardware, our results also emphasize the necessity of more and better quantum optimization algorithms, especially for multi-knapsack problems.
Human review
How the literature uses it
3 arXiv papers cite this in 6 sentences
Papers citing it · 3 sentences without a confident label
Cites it as support 1 paper
-
However, the QAOA solutions suffer from a low feasible solution ratio for constrained problems whose $F⫋{0,1}^n$, with several experimental studies illustrating this limitation even in toy examples [ref] .
A Feasibility-Preserved Quantum Approximate Solver for the Capacitated Vehicle Routing Problem · Introduction · 0.97
Cites it as background 2 papers
-
The QUBO forms of the MKP and the TSP are discussed in detail in [ref] .
A Feasibility-Preserved Quantum Approximate Solver for the Capacitated Vehicle Routing Problem · Related Work · 0.92
-
In [ref] , a comprehensive study of quantum computing approaches for multi-knapsack problems is proposed by investigating some of the most prominent and state-of-the-art quantum algorithms using different quantum software and hardware tools.
Enhancing Knapsack-based Financial Portfolio Optimization Using Quantum Approximate Optimization Algorithm · Related Work · 0.91
What it cites · 2 sentences without a confident label
Cites as background 2 papers
-
Two techniques that are built upon the quantum approximate optimization algorithm (QAOA) are introduced in [ref] : one of them “warm-starts” the quantum optimization algorithm by seeding it with an initial solution using a greedy classical method, and the other uses special mixing Hamiltonians to improve the exploration of the solution space.
Quantum Optimization Heuristics with an Application to Knapsack Problems · Introduction · 0.93
-
The QAOA is a popular variational algorithm inspired by the adiabatic theorem, devised to produce approximate solutions for combinatorial optimization problems [ref] .
A Quantum Approximate Optimization Algorithm · Quantum Approximate Optimization Algorithm (QAOA) · 0.94
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.