Hybrid Quantum Search Algorithm for Solving the Multi-Dimensional Knapsack Problem
Gordon Cui, Rei Sato, Kazuhiro Saito, Rodney Van Meter, Hideyuki Kawashima · 2024
The Multi-Dimensional Knapsack Problem (MDKP) is a strongly NP-Hard combinatorial optimization problem that extends the Knapsack Problem (KP) to multiple constraints. While effective heuristic classical MDKP algorithms have been studied, there remains no optimal exact classical algorithm and only few contributions using quantum algorithms exist. In this study, we leverage Grover's search and pre-processing techniques to propose an iterative quantum search algorithm and circuit design that integrates classical adjustments to the oracle, progressively refining solutions until optimal. Evaluations show that our method reduces depth, width, iterations, and runtime.