Discrete optimization: A quantum revolution?

Stefan Creemers and Luis Fernando Pérez Armas
Additional contact information
Stefan Creemers: Université catholique de Louvain, LIDAM/CORE, Belgium

No 3324, LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

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)
Pages: 31
Date: 2025-01-01
Note: In: European Journal of Operational Research, 2025, vol. 323 (2), p. 378-408
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:cor:louvrp:3324

DOI: 10.1016/j.ejor.2024.12.016

Access Statistics for this paper

More papers in LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().