Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming

Wagner F, Nublein J, Liers F (2025)

Publication Type: Journal article

Publication year: 2025

Journal

ACM Transactions on Quantum Computing Association for Computing Machinery (ACM)

Book Volume: 6

Article Number: 12

Journal Issue: 2

DOI: 10.1145/3711935

Abstract

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.

Authors with CRIS profile

Frauke Liers-Bergmann Professur für Optimization under Uncertainty & Data Analysis

Involved external institutions

Fraunhofer-Institut für Integrierte Schaltungen (IIS) DE Germany (DE)

How to cite

APA:

Wagner, F., Nublein, J., & Liers, F. (2025). Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming. ACM Transactions on Quantum Computing, 6(2). https://doi.org/10.1145/3711935

MLA:

Wagner, Friedrich, Jonas Nublein, and Frauke Liers. "Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming." ACM Transactions on Quantum Computing 6.2 (2025).

BibTeX: Download