Moderate exponential-time quantum dynamic programming across the subsets for scheduling problems

Camille Grange, Michael Poss, Eric Bourreau, T’kindt, Vincent and Olivier Ploton

European Journal of Operational Research, 2025, vol. 320, issue 3, 516-526

Abstract: Grover Search is currently one of the main quantum algorithms leading to hybrid quantum–classical methods that reduce the worst-case time complexity for some combinatorial optimization problems. Specifically, the combination of Quantum Minimum Finding (obtained from Grover Search) with dynamic programming has proved particularly efficient in improving the complexity of NP-hard problems currently solved by classical dynamic programming. For these problems, the classical dynamic programming complexity in O∗(cn), where O∗ denotes that polynomial factors are ignored, can be reduced by a hybrid algorithm to O∗(cquantn), with cquantKeywords: Discrete optimization; Quantum computing; Scheduling; Dynamic programming (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724006969
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:320:y:2025:i:3:p:516-526

DOI: 10.1016/j.ejor.2024.09.005

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 ().