Quantum relaxation for solving multiple knapsack problems

• Main Authors: SHARMA, Monit, YAN, Jin, LAU, Hoong Chuin, RAYMOND, Rudy
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2024
• Subjects: Constrained optimization; Knapsack constraints; Quantum Hamiltonians; Quantum random access code; Linear relaxation; Computer Engineering; Software Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/9969; https://ink.library.smu.edu.sg/context/sis_research/article/10969/viewcontent/2404.19474v2__1_.pdf
• Institution: Singapore Management University

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.