EUVIMEDEUVIMED entdecken
Crossref

Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming

Friedrich Wagner, Jonas Nüßlein, Frauke Liers

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →