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:2503.21222 · EPJ Quantum Technology

A quantum constraint generation framework for binary linear programs

András Czégel, Boglárka G.-Tóth

Published May 19, 2025• 0 citations
arXivHTMLPDF

Abstract

Abstract We propose a new approach to utilize quantum computers for binary linear programming (BLP), which can be extended to general integer linear programs (ILP). Quantum optimization algorithms, hybrid or quantum-only, are currently general purpose, standalone solvers for ILP. However, to consider them practically useful, we expect them to overperform the current state of the art classical solvers. That expectation is unfair to quantum algorithms: in classical ILP solvers, after many decades of evolution, many different algorithms work together as a robust machine to get the best result. This is the approach we would like to follow now with our quantum ‘solver’ solutions. In this study we wrap any suitable quantum optimization algorithm into a quantum informed classical constraint generation framework. First we relax our problem by dropping all constraints and encode it into an Ising Hamiltonian for the quantum optimization subroutine. Then, by sampling from the solution state of the subroutine, we obtain information about constraint violations in the initial problem, from which we decide which coupling terms we need to introduce to the Hamiltonian. The coupling terms correspond to the constraints of the initial binary linear program. Then we optimize over the new Hamiltonian again, until we reach a feasible solution, or other stopping conditions hold. Since one can decide how many constraints they add to the Hamiltonian in a single step, our algorithm is at least as efficient as the (hybrid) quantum optimization algorithm it wraps. We support our claim with results on small scale minimum cost exact cover problem instances.

DOI
10.1140/epjqt/s40507-025-00364-z

Related papers

Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming

Friedrich Wagner, Jonas Nüßlein, Frauke Liers

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.

arXiv:2302.05493•ACM Transactions on Quantum Computing•Jan 13, 2025•2 citations

A quantum-classical hybrid branch & bound algorithm

András Czégel, Dávid Sipos, Boglárka G. -Tóth

We propose a complete quantum-classical hybrid branch-and-bound algorithm (QCBB) to solve binary linear programs with equality constraints. That includes bound calculation, convergence metrics and optimality guarantee to the quantum optimization based algorithm, which makes our method directly comparable to classical methods. Key aspects of the proposed algorithm are (i) encapsulation of the quantum optimization method, (ii) utilization of noisy samples for problem reduction, (iii) classical approximation based bound calculation, (iv) branch and bound traits like gap-based stopping criterion and monotonic increase in solution quality, (v) integrated composition of many different solutions that can be improved individually. We show numerical results on set partitioning problem instances and provide many details about the characteristics of the different steps of the algorithm.

quant-pharXiv:2511.19501•Nov 25, 2025•0 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

Hybrid Quantum–Classical Framework for Fuzzy 0–1 Integer Linear Programming: α-Level Trade-off Analysis via Quadratic Unconstrained Binary Optimization Reformulation

Hamed Fazlollahtabar, Hadi Gholizadeh

This paper addressed the computational challenges of solving large-scale fuzzy 0-1 Integer Linear Programming (ILP) problems by proposing a Fuzzy-Hybrid Quantum-Classical Optimization Algorithm (F-HQCOA).The novel approach employed α-cut based transformations to convert fuzzy ILP models into a family of crisp Quadratic Unconstrained Binary Optimization (QUBO) problems, which were then solved using hybrid quantumclassical techniques.Unlike multi-objective formulations, the proposed framework performed a parametric analysis over α-levels to generate a spectrum of solutions that reflected trade-offs between objective optimality and feasibility satisfaction under uncertainty.The degree of satisfaction (µ) was adopted as an evaluation metric to assess solution quality rather than as an independent optimization objective.The method was evaluated on fuzzy Multi-Dimensional Knapsack and Set Covering problems.Results showed that the proposed approach could efficiently handle larger instances and provided a diverse set of solutions across α-levels.While quantum-assisted methods demonstrated reduced Time-to-Solution (TTS) in certain settings, comparisons were presented with careful consideration of differences in computational paradigms.The proposed framework offers a practical decision-support tool for optimization under uncertainty and establishes a foundation for future extensions toward true multi-objective fuzzy quantum optimization.

Journal of Industrial Intelligence•Sep 2, 2025•0 citations

Quantum Speedups for Group Relaxations of Integer Linear Programs

Brandon Augustino, Dylan Herman, Guneykan Ozgul +5 more

Integer Linear Programs (ILPs) are a flexible and ubiquitous model for discrete optimization problems. Solving ILPs is \textsf{NP-Hard} yet of great practical importance. Super-quadratic quantum speedups for ILPs have been difficult to obtain because classical algorithms for many-constraint ILPs are global and exhaustive, whereas quantum frameworks that offer super-quadratic speedup exploit local structure of the objective and feasible set. We address this via quantum algorithms for Gomory's group relaxation. The group relaxation of an ILP is obtained by dropping nonnegativity on variables that are positive in the optimal solution of the linear programming (LP) relaxation, while retaining integrality of the decision variables. We present a competitive feasibility-preserving classical local-search algorithm for the group relaxation, and a corresponding quantum algorithm that, under reasonable technical conditions, achieves a super-quadratic speedup. When the group relaxation satisfies a nondegeneracy condition analogous to, but stronger than, LP non-degeneracy, our approach yields the optimal solution to the original ILP. Otherwise, the group relaxation tightens bounds on the optimal objective value of the ILP, and can improve downstream branch-and-cut by reducing the integrality gap; we numerically observe this on several practically relevant ILPs. To achieve these results, we derive efficiently constructible constraint-preserving mixers for the group relaxation with favorable spectral properties, which are of independent interest.

quant-pharXiv:2602.13494•Feb 17, 2026•0 citations
Abstract We propose a new approach to utilize quantum computers for binary linear programming (BLP), which can be extended to general integer linear programs (ILP). Quantum optimization algorithms, hybrid or quantum-only, are currently general purpose, standalone solvers for ILP. However, to consider them practically useful, we expect them to overperform the current state of the art classical solvers. That expectation is unfair to quantum algorithms: in classical ILP solvers, after many decades of evolution, many different algorithms work together as a robust machine to get the best result. This is the approach we would like to follow now with our quantum ‘solver’ solutions. In this study we wrap any suitable quantum optimization algorithm into a quantum informed classical constraint generation framework. First we relax our problem by dropping all constraints and encode it into an Ising Hamiltonian for the quantum optimization subroutine. Then, by sampling from the solution state of the subroutine, we obtain information about constraint violations in the initial problem, from which we decide which coupling terms we need to introduce to the Hamiltonian. The coupling terms correspond to the constraints of the initial binary linear program. Then we optimize over the new Hamiltonian again, until we reach a feasible solution, or other stopping conditions hold. Since one can decide how many constraints they add to the Hamiltonian in a single step, our algorithm is at least as efficient as the (hybrid) quantum optimization algorithm it wraps. We support our claim with results on small scale minimum cost exact cover problem instances.
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.
We propose a complete quantum-classical hybrid branch-and-bound algorithm (QCBB) to solve binary linear programs with equality constraints. That includes bound calculation, convergence metrics and optimality guarantee to the quantum optimization based algorithm, which makes our method directly comparable to classical methods. Key aspects of the proposed algorithm are (i) encapsulation of the quantum optimization method, (ii) utilization of noisy samples for problem reduction, (iii) classical approximation based bound calculation, (iv) branch and bound traits like gap-based stopping criterion and monotonic increase in solution quality, (v) integrated composition of many different solutions that can be improved individually. We show numerical results on set partitioning problem instances and provide many details about the characteristics of the different steps of the algorithm.
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.
This paper addressed the computational challenges of solving large-scale fuzzy 0-1 Integer Linear Programming (ILP) problems by proposing a Fuzzy-Hybrid Quantum-Classical Optimization Algorithm (F-HQCOA).The novel approach employed α-cut based transformations to convert fuzzy ILP models into a family of crisp Quadratic Unconstrained Binary Optimization (QUBO) problems, which were then solved using hybrid quantumclassical techniques.Unlike multi-objective formulations, the proposed framework performed a parametric analysis over α-levels to generate a spectrum of solutions that reflected trade-offs between objective optimality and feasibility satisfaction under uncertainty.The degree of satisfaction (µ) was adopted as an evaluation metric to assess solution quality rather than as an independent optimization objective.The method was evaluated on fuzzy Multi-Dimensional Knapsack and Set Covering problems.Results showed that the proposed approach could efficiently handle larger instances and provided a diverse set of solutions across α-levels.While quantum-assisted methods demonstrated reduced Time-to-Solution (TTS) in certain settings, comparisons were presented with careful consideration of differences in computational paradigms.The proposed framework offers a practical decision-support tool for optimization under uncertainty and establishes a foundation for future extensions toward true multi-objective fuzzy quantum optimization.
Integer Linear Programs (ILPs) are a flexible and ubiquitous model for discrete optimization problems. Solving ILPs is \textsf{NP-Hard} yet of great practical importance. Super-quadratic quantum speedups for ILPs have been difficult to obtain because classical algorithms for many-constraint ILPs are global and exhaustive, whereas quantum frameworks that offer super-quadratic speedup exploit local structure of the objective and feasible set. We address this via quantum algorithms for Gomory's group relaxation. The group relaxation of an ILP is obtained by dropping nonnegativity on variables that are positive in the optimal solution of the linear programming (LP) relaxation, while retaining integrality of the decision variables. We present a competitive feasibility-preserving classical local-search algorithm for the group relaxation, and a corresponding quantum algorithm that, under reasonable technical conditions, achieves a super-quadratic speedup. When the group relaxation satisfies a nondegeneracy condition analogous to, but stronger than, LP non-degeneracy, our approach yields the optimal solution to the original ILP. Otherwise, the group relaxation tightens bounds on the optimal objective value of the ILP, and can improve downstream branch-and-cut by reducing the integrality gap; we numerically observe this on several practically relevant ILPs. To achieve these results, we derive efficiently constructible constraint-preserving mixers for the group relaxation with favorable spectral properties, which are of independent interest.