Publication Type
Conference Proceeding Article
Version
acceptedVersion
Publication Date
9-2024
Abstract
Combinatorial problems are a common challenge in business, requiring finding optimal solutions under specified constraints. While significant progress has been made with variational approaches such as QAOA, most problems addressed are unconstrained (such as Max-Cut). In this study, we investigate a hybrid quantum-classical method for constrained optimization problems, particularly those with knapsack constraints that occur frequently in financial and supply chain applications. Our proposed method relies firstly on relaxations to local quantum Hamiltonians, defined through commutative maps. Drawing inspiration from quantum random access code (QRAC) concepts, particularly Quantum Random Access Optimizer (QRAO), we explore QRAO's potential in solving large constrained optimization problems. We employ classical techniques like Linear Relaxation as a presolve mechanism to handle constraints and cope further with scalability. We compare our approach with QAOA and present the final results for a real-world procurement optimization problem: a significant sized multi-knapsack-constrained problem.
Keywords
Constrained optimization, Knapsack constraints, Quantum Hamiltonians, Quantum random access code, Linear relaxation
Discipline
Computer Engineering | Software Engineering
Research Areas
Information Systems and Management
Publication
Proceedings of the IEEE International Conference on Quantum Computing and Engineering (QCE 2024) : Montreal, Quebec, Canada, September 15-20
City or Country
Montreal, Canada
Citation
SHARMA, Monit; YAN, Jin; LAU, Hoong Chuin; and RAYMOND, Rudy.
Quantum relaxation for solving multiple knapsack problems. (2024). Proceedings of the IEEE International Conference on Quantum Computing and Engineering (QCE 2024) : Montreal, Quebec, Canada, September 15-20.
Available at: https://ink.library.smu.edu.sg/sis_research/9969
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
