Quantum Computing Techniques for Multi-Knapsack Problems

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.

arXiv comment20 pages

References in corpus (16)

• A variational eigenvalue solver on a quantum processor
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• The Variational Quantum Eigensolver: a review of methods and best practices
• Perspectives of quantum annealing: Methods and implementations
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Quantum Annealing for Industry Applications: Introduction and Review
• Warm-starting quantum optimization
• Efficient measure for the expressivity of variational quantum algorithms
• Quantum Algorithms for Mixed Binary Optimization applied to Transaction Settlement
• QUARK: A Framework for Quantum Computing Application Benchmarking
• Building an iterative heuristic solver for a quantum annealer
• Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
• Qubit-efficient encoding schemes for binary optimisation problems
• Quantum Image Segmentation Based on Grayscale Morphology

Cited by in corpus (8)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing Problem
• Approximating under the Influence of Quantum Noise and Compute Power
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Quantum Approximation Optimization Algorithm for the Trellis based Viterbi Decoding of Classical Error Correcting Codes
• Symmetry-based quantum algorithms for open-shop scheduling with hard constraints
• Predict and Conquer: Navigating Algorithm Trade-offs with Quantum Design Automation
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems