Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2302.05493 · ACM Transactions on Quantum Computing

Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming

Friedrich Wagner, Jonas Nüßlein, Frauke Liers

Published Jan 13, 2025• 2 citations
arXivHTMLPDF

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.

DOI
10.1145/3711935

Related papers

Faster exact solution of sparse MaxCut and QUBO problems

Daniel Rehfeldt, Thorsten Koch, Yuji Shinano

Abstract The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems—by using mathematical programming techniques. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse maximum-cut and quadratic unconstrained binary optimization instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.

Mathematical Programming Computation•Apr 15, 2023•38 citations

Hybrid Quantum-Classical Heuristic to Solve Large-Scale Integer Linear Programs

Marika Svensson, Martin Andersson, Mattias Grönkvist +4 more

We present a method that integrates any quantum algorithm capable of finding solutions to integer linear programs into the branch-and-price algorithm, which is regularly used to solve large-scale integer linear programs with a specific structure. The role of the quantum algorithm is to find integer solutions to subproblems appearing in branch-and-price. Obtaining optimal or near-optimal integer solutions to these subproblems can increase the quality of solutions and reduce the depth and branching factor of the branch-and-price algorithm and hence reduce the overall running time. We investigate the viability of the approach by considering the tail assignment problem and the quantum approximate optimization algorithm (QAOA). Here, the master problem is the optimization problem set partitioning or its decision version exact cover and can be expressed as finding the ground state of an Ising spin glass Hamiltonian. For exact cover, our numerical results indicate that the required algorithm depth decreases with the number of feasible solutions for a given success probability of finding a feasible solution. For set partitioning, on the other hand, we find that for a given success probability of finding the optimal solution, the required algorithm depth can increase with the number of feasible solutions if the Hamiltonian is balanced poorly, which in the worst case is exponential in the problem size. We therefore address the significance of properly balancing the objective and constraint parts of the Hamiltonian. We empirically find that the approach is viable with QAOA if polynomial algorithm depth can be realized on quantum devices.

Physical Review Applied•Sep 26, 2023•9 citations

A Hybrid Quantum-Classical Heuristic to solve large-scale Integer Linear Programs

Marika Svensson, Andersson, Martin, Mattias Grönkvist +4 more

We present a method that integrates any quantum algorithm capable of finding solutions to integer linear programs into the Branch-and-Price algorithm, which is regularly used to solve large-scale integer linear programs with a specific structure. The role of the quantum algorithm is to find integer solutions to subproblems appearing in Branch-and-Price. Obtaining optimal or near-optimal integer solutions to these subproblems can increase the quality of solutions and reduce the depth and branching factor of the Branch-and-Price algorithm and hence reduce the overall running time. We investigate the viability of the approach by considering the Tail Assignment problem and the Quantum Approximate Optimization Algorithm (QAOA). Here, the master problem is the optimization problem Set Partitioning or its decision version Exact Cover and can be expressed as finding the ground state of an Ising spin glass Hamiltonian. For Exact Cover, our numerical results indicate that the required algorithm depth decreases with the number of feasible solutions for a given success probability of finding a feasible solution. For Set Partitioning, on the other hand, we find that for a given success probability of finding the optimal solution, the required algorithm depth can increase with the number of feasible solutions if the Hamiltonian is balanced poorly, which in the worst case is exponential in the problem size. We therefore address the importance of properly balancing the objective and constraint parts of the Hamiltonian. We empirically find that the approach is viable with QAOA if polynomial algorithm depth can be realized on quantum devices.

arXiv:2103.15433•Mar 29, 2021•1 citation

Performance enhancing of hybrid quantum-classical Benders approach for MILP optimization

Sergio López-Baños, Elisabeth Lobe, Ontje Lünsdorf +1 more

Mixed-integer linear programming problems are extensively used in industry for a wide range of optimization tasks. However, as they get larger, they present computational challenges for classical solvers within practical time limits. Quantum annealers can, in principle, accelerate the solution of problems formulated as quadratic unconstrained binary optimization instances, but their limited scale currently prevents achieving practical speedups. Quantum-classical algorithms have been proposed to take advantage of both paradigms and to allow current quantum computers to be used in larger problems. In this work, a hardware-agnostic Benders' decomposition algorithm and a series of enhancements with the goal of taking the most advantage of quantum computing are presented. The decomposition consists of a master problem with integer variables, which is reformulated as a quadratic unconstrained binary optimization problem and solved with a quantum annealer, and a linear subproblem solved by a classical computer. The enhancements consist, among others, of different embedding processes that substantially reduce the pre-processing time of the embedding computation without compromising solution quality, a conservative handling of cut constraints, and a stopping criterion that accounts for the limited size of current quantum computers and their heuristic nature. The proposed algorithm is benchmarked against classical approaches using a D-Wave quantum annealer for a scalable family of transmission network expansion planning problems.

quant-pharXiv:2601.14024•Jan 21, 2026•0 citations

Faster exact solution of sparse MaxCut and QUBO problems

Daniel Rehfeldt, Thorsten Koch, Yuji Shinano

The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems -- by using mathematical programming techniques on digital computers. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse MaxCut and QUBO instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.

arXiv:2202.02305•Feb 4, 2022•1 citation

Quantum Approximate Optimization of Integer Graph Problems and Surpassing Semidefinite Programming for Max-k-Cut

Anuj Apte, Sami Boulebnane, Yuwei Jin +3 more

Quantum algorithms for binary optimization problems have been the subject of extensive study. However, the application of quantum algorithms to integer optimization problems remains comparatively unexplored. In this paper, we study the Quantum Approximate Optimization Algorithm (QAOA) applied to integer problems on graphs, with each integer variable encoded in a qudit. We derive a general iterative formula for depth-$p$ QAOA expectation on high-girth $d$-regular graphs of arbitrary size. The cost of evaluating the formula is exponential in the QAOA depth $p$ but does not depend on the graph size. Evaluating this formula for Max-$k$-Cut problem for $p\leq 4$, we identify parameter regimes ($k=3$ with degree $d \leq 10$ and $k=4$ with $d \leq 40$) in which QAOA outperforms the Frieze-Jerrum semi-definite programming (SDP) algorithm, which provides the best worst-case guarantee on the approximation ratio. To strengthen the classical baseline, we introduce a new heuristic algorithm based on the degree-of-saturation that achieves strong results on the \texttt{GSet} benchmark with quasi-linear runtime in the number of edges. It empirically outperforms both the Frieze-Jerrum algorithm and shallow-depth QAOA on regular graphs. Nevertheless, we provide numerical evidence that QAOA may overtake this heuristic at depth $p\leq 20$. Our results show that moving beyond binary to integer optimization problems can open up new avenues for quantum advantage.

quant-pharXiv:2602.05956•Feb 6, 2026•0 citations
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.
Abstract The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems—by using mathematical programming techniques. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse maximum-cut and quadratic unconstrained binary optimization instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.
We present a method that integrates any quantum algorithm capable of finding solutions to integer linear programs into the branch-and-price algorithm, which is regularly used to solve large-scale integer linear programs with a specific structure. The role of the quantum algorithm is to find integer solutions to subproblems appearing in branch-and-price. Obtaining optimal or near-optimal integer solutions to these subproblems can increase the quality of solutions and reduce the depth and branching factor of the branch-and-price algorithm and hence reduce the overall running time. We investigate the viability of the approach by considering the tail assignment problem and the quantum approximate optimization algorithm (QAOA). Here, the master problem is the optimization problem set partitioning or its decision version exact cover and can be expressed as finding the ground state of an Ising spin glass Hamiltonian. For exact cover, our numerical results indicate that the required algorithm depth decreases with the number of feasible solutions for a given success probability of finding a feasible solution. For set partitioning, on the other hand, we find that for a given success probability of finding the optimal solution, the required algorithm depth can increase with the number of feasible solutions if the Hamiltonian is balanced poorly, which in the worst case is exponential in the problem size. We therefore address the significance of properly balancing the objective and constraint parts of the Hamiltonian. We empirically find that the approach is viable with QAOA if polynomial algorithm depth can be realized on quantum devices.
We present a method that integrates any quantum algorithm capable of finding solutions to integer linear programs into the Branch-and-Price algorithm, which is regularly used to solve large-scale integer linear programs with a specific structure. The role of the quantum algorithm is to find integer solutions to subproblems appearing in Branch-and-Price. Obtaining optimal or near-optimal integer solutions to these subproblems can increase the quality of solutions and reduce the depth and branching factor of the Branch-and-Price algorithm and hence reduce the overall running time. We investigate the viability of the approach by considering the Tail Assignment problem and the Quantum Approximate Optimization Algorithm (QAOA). Here, the master problem is the optimization problem Set Partitioning or its decision version Exact Cover and can be expressed as finding the ground state of an Ising spin glass Hamiltonian. For Exact Cover, our numerical results indicate that the required algorithm depth decreases with the number of feasible solutions for a given success probability of finding a feasible solution. For Set Partitioning, on the other hand, we find that for a given success probability of finding the optimal solution, the required algorithm depth can increase with the number of feasible solutions if the Hamiltonian is balanced poorly, which in the worst case is exponential in the problem size. We therefore address the importance of properly balancing the objective and constraint parts of the Hamiltonian. We empirically find that the approach is viable with QAOA if polynomial algorithm depth can be realized on quantum devices.
Mixed-integer linear programming problems are extensively used in industry for a wide range of optimization tasks. However, as they get larger, they present computational challenges for classical solvers within practical time limits. Quantum annealers can, in principle, accelerate the solution of problems formulated as quadratic unconstrained binary optimization instances, but their limited scale currently prevents achieving practical speedups. Quantum-classical algorithms have been proposed to take advantage of both paradigms and to allow current quantum computers to be used in larger problems. In this work, a hardware-agnostic Benders' decomposition algorithm and a series of enhancements with the goal of taking the most advantage of quantum computing are presented. The decomposition consists of a master problem with integer variables, which is reformulated as a quadratic unconstrained binary optimization problem and solved with a quantum annealer, and a linear subproblem solved by a classical computer. The enhancements consist, among others, of different embedding processes that substantially reduce the pre-processing time of the embedding computation without compromising solution quality, a conservative handling of cut constraints, and a stopping criterion that accounts for the limited size of current quantum computers and their heuristic nature. The proposed algorithm is benchmarked against classical approaches using a D-Wave quantum annealer for a scalable family of transmission network expansion planning problems.
The maximum-cut problem is one of the fundamental problems in combinatorial optimization. With the advent of quantum computers, both the maximum-cut and the equivalent quadratic unconstrained binary optimization problem have experienced much interest in recent years. This article aims to advance the state of the art in the exact solution of both problems -- by using mathematical programming techniques on digital computers. The main focus lies on sparse problem instances, although also dense ones can be solved. We enhance several algorithmic components such as reduction techniques and cutting-plane separation algorithms, and combine them in an exact branch-and-cut solver. Furthermore, we provide a parallel implementation. The new solver is shown to significantly outperform existing state-of-the-art software for sparse MaxCut and QUBO instances. Furthermore, we improve the best known bounds for several instances from the 7th DIMACS Challenge and the QPLIB, and solve some of them (for the first time) to optimality.
Quantum algorithms for binary optimization problems have been the subject of extensive study. However, the application of quantum algorithms to integer optimization problems remains comparatively unexplored. In this paper, we study the Quantum Approximate Optimization Algorithm (QAOA) applied to integer problems on graphs, with each integer variable encoded in a qudit. We derive a general iterative formula for depth-ppp QAOA expectation on high-girth ddd-regular graphs of arbitrary size. The cost of evaluating the formula is exponential in the QAOA depth ppp but does not depend on the graph size. Evaluating this formula for Max-kkk-Cut problem for p≤4p\leq 4p≤4, we identify parameter regimes (k=3k=3k=3 with degree d≤10d \leq 10d≤10 and k=4k=4k=4 with d≤40d \leq 40d≤40) in which QAOA outperforms the Frieze-Jerrum semi-definite programming (SDP) algorithm, which provides the best worst-case guarantee on the approximation ratio. To strengthen the classical baseline, we introduce a new heuristic algorithm based on the degree-of-saturation that achieves strong results on the \texttt{GSet} benchmark with quasi-linear runtime in the number of edges. It empirically outperforms both the Frieze-Jerrum algorithm and shallow-depth QAOA on regular graphs. Nevertheless, we provide numerical evidence that QAOA may overtake this heuristic at depth p≤20p\leq 20p≤20. Our results show that moving beyond binary to integer optimization problems can open up new avenues for quantum advantage.