Discrete optimization: A quantum revolution?

Stefan Creemers and Luis Fernando Pérez Armas

European Journal of Operational Research, 2025, vol. 323, issue 2, 378-408

Abstract: We develop several quantum procedures and investigate their potential to solve discrete optimization problems. First, we introduce a binary search procedure and illustrate how it can be used to effectively solve the binary knapsack problem. Next, we introduce two other procedures: a hybrid branch-and-bound procedure that allows to exploit the structure of the problem and a random-ascent procedure that can be used to solve problems that have no clear structure and/or are difficult to solve using traditional methods. We explain how to assess the performance of these procedures and perform an elaborate computational experiment. Our results show that we can match the worst-case performance of the best classical algorithms when solving the binary knapsack problem. After improving and generalizing our procedures, we show that they can be used to solve any discrete optimization problem. To illustrate, we show how to solve the quadratic binary knapsack problem. For this problem, our procedures outperform the best classical algorithms. In addition, we demonstrate that our procedures can be used as heuristics to find (near-) optimal solutions in limited time Not only does our work provide the tools required to explore a myriad of future research directions, it also shows that quantum computing has the potential to revolutionize the field of discrete optimization.

Keywords: Quantum; Computing; Algorithm; Knapsack; Grover (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724009585
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:323:y:2025:i:2:p:378-408

DOI: 10.1016/j.ejor.2024.12.016

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().