Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming
ACM Transactions on Quantum Computing · 30.06.2025 · 6 (2) · 1-28
DOI: 10.1145/3711935 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Quantum Computing, online erschienen am 13.02.2025. Verfasst von Friedrich Wagner und 2 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 79 Literaturangaben. Gefördert von: Hightech Agenda Bayern, Federal Ministry for Economic Affairs and Climate Action on the basis of a decision by the German Bundestag through project QuaST.
Abstract (Originalsprache)
To date, research in quantum computation promises potential for outperforming classical heuristics in combinatorial optimization. However, when aiming at provable optimality, one has to rely on classical exact methods like integer programming. State-of-the-art integer programming algorithms can compute strong relaxation bounds even for hard instances, but may have to enumerate a large number of subproblems for determining an optimum solution. If the potential of quantum computing is realized, it can be expected that in particular finding high-quality solutions for hard problems can be done fast. Still, near-future quantum hardware considerably limits the size of treatable problems. In this work, we go one step into integrating the potentials of quantum and classical techniques for combinatorial optimization. We propose a hybrid heuristic for the weighted maximum-cut problem and for quadratic unconstrained binary optimization. The heuristic employs a linear programming relaxation, rendering it well-suited for integration into exact branch-and-cut algorithms. For large instances, we reduce the problem size according to a linear relaxation such that the reduced problem can be handled by quantum machines of limited size. Moreover, we improve the applicability of depth-1 QAOA, a parameterized quantum algorithm, by deriving a parameter estimate for arbitrary instances. We present numerous computational results from real quantum hardware.
Förderung
- Hightech Agenda Bayern
- Federal Ministry for Economic Affairs and Climate Action on the basis of a decision by the German Bundestag through project QuaST
Zitieren
APA
Wagner, F., Nüßlein, J., & Liers, F. (2025). Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming. ACM Transactions on Quantum Computing, 6(2), 1-28. https://doi.org/10.1145/3711935
Vancouver
Wagner F, Nüßlein J, Liers F. Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming. ACM Transactions on Quantum Computing. 2025;6(2):1-28. doi:10.1145/3711935
BibTeX
@article{Wagner2025,
author = {Wagner, Friedrich and Nüßlein, Jonas and Liers, Frauke},
title = {Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming},
journal = {ACM Transactions on Quantum Computing},
year = {2025},
volume = {6},
number = {2},
pages = {1--28},
doi = {10.1145/3711935}
}
EUVIMED