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

Operations Research, Systems Engineering and Industrial Engineering | Software Engineering

Research Areas

Intelligent Systems and Optimization

Publication

2024 IEEE International Conference on Quantum Computing and Engineering (QCE): Montreal, September 15-20: Proceedings

First Page

692

Last Page

698

ISBN

9798331541378

Identifier

10.1109/QCE60285.2024.00086

Publisher

IEEE

City or Country

Montreal, Canada

Copyright Owner and License

Authors

Creative Commons License

Creative Commons Attribution 4.0 International License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Additional URL

https://doi.org/10.1109/QCE60285.2024.00086

Download

Share

COinS