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:2103.15433 · Physical Review Applied

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

Marika Svensson, Martin Andersson, Mattias Grönkvist, Pontus Vikstål, Devdatt Dubhashi, Giulia Ferrini, Göran Johansson

Published Sep 26, 2023• 23 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physrevapplied.20.034062

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•13 citations

Quantum Subroutines in Branch-Price-and-Cut for Vehicle Routing

Friedrich Wagner, Frauke Liers

Motivated by recent progress in quantum hardware and algorithms, researchers have developed quantum heuristics for optimization problems, aiming for advantages over classical methods. To date, quantum hardware is still error-prone and limited in size such that quantum heuristics cannot be scaled to relevant problem sizes and are often outperformed by their classical counterparts. Moreover, if provably optimal solutions are desired, one has to resort to classical exact methods. As, however, quantum technologies may improve considerably in future, we demonstrate in this work how quantum heuristics with limited resources can be integrated in large-scale exact optimization algorithms for NP-hard problems. To this end, we consider vehicle routing as a prototypical NP-hard problem. We model the pricing and separation subproblems arising in a branch-price-and-cut algorithm as quadratic unconstrained binary optimization problems. This allows to use established quantum heuristics like quantum annealing or the quantum approximate optimization algorithm for their solution. A key feature of our algorithm is that it profits not only from the best solution returned by the quantum heuristic but from all solutions below a certain cost threshold, thereby exploiting the inherent randomness is quantum algorithms. Moreover, we reduce the requirements on quantum hardware since the subproblems, which are solved via quantum heuristics, are smaller than the original problem. We provide a proof-of-concept experimental study comparing quantum annealing to simulated annealing and to established classical algorithms in our framework. While our hybrid quantum-classical approach is still outperformed by purely classical methods, our results reveal that both pricing and separation may be well suited for quantum heuristics if quantum hardware improves.

arXiv:2412.15665•IEEE Transactions on Quantum Engineering•Jan 1, 2026•1 citation

Applying the Quantum Approximate Optimization Algorithm to the Tail-Assignment Problem

Pontus Vikstål, Mattias Grönkvist, Marika Svensson +3 more

Airlines today are faced with a number of large-scale scheduling problems. One such problem is the tail-assignment problem, which is the task of assigning individual aircraft to a given set of flights, minimizing the overall cost. Each aircraft is identified by the registration number on its tail fin. In this paper, we simulate the quantum approximate optimization algorithm (QAOA) applied to instances of this problem derived from real-world data. The QAOA is a variational hybrid quantum-classical algorithm recently introduced and likely to run on near-term quantum devices. The instances are reduced to fit on quantum devices with 8, 15, and 25 qubits. The reduction procedure leaves only one feasible solution per instance, which allows us to map the tail-assignment problem onto the exact-cover problem. We find that repeated runs of the QAOA identify the feasible solution with close to unit probability for all instances. Furthermore, we observe patterns in the variational parameters such that an interpolation strategy can be employed, which significantly simplifies the classical optimization part of the QAOA. Finally, we empirically find a relation between the connectivity of the problem graph and the single-shot success probability of the algorithm.

arXiv:1912.10499•Physical Review Applied•Sep 3, 2020•107 citations

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•7 citations

Flexible integration of classical and quantum techniques in the evolutionary path to quantum utility

Prashanti Priya Angara

This dissertation addresses fundamental challenges in solving constrained combinatorial optimization problems using hybrid quantum-classical computing approaches. Quantum computing shows promise for tackling computationally intractable problems, current approaches face significant limitations. The path forward in computing involves combining quantum and classical computing approaches. Quantum processing units (QPUs) will play a key role in accelerating algorithms in optimization, simulation, and machine learning applications beyond what classical computers can achieve on their own, similar to how graphical processing units (GPUs) have become integral to general-purpose computing. The current generation of quantum devices is limited by noise and circuit depth constraints, making it challenging to gain practical utility. Hybrid quantum-classical approaches, which combine quantum computing resources with classical computing resources, are essential for addressing these limitations on near-term devices. In the area of combinatorial optimization, current practical state-of-the-art hybrid approaches are variational in nature, relying on parameterized quantum circuits to encode solutions and classical optimization techniques to find optimal parameters. While the ultimate goal of solving computationally intractable problems is to find provably optimal solutions, practical constraints of real-world scenarios often necessitate focusing on efficiently obtaining high-quality, near-optimal solutions. The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical approach for tackling these challenging problems that are encoded using quadratic and higher-order unconstrained binary optimization problems (QUBO and HUBO). QAOA alternates between two operators: a problem-specific cost Hamiltonian that encodes the optimization objective, and a mixer Hamiltonian that explores the solution space. The algorithm's parameters are iteratively optimized using classical methods to maximize the probability of sampling high-quality solutions. However, these methods often struggle with solution feasibility, especially for problems where the solutions must satisfy specific constraints. Penalty-based encodings require careful parameter tuning and risk producing infeasible solutions, while feasibility-preserving methods demand deeper quantum circuits that are challenging to implement on near-term quantum devices. In this dissertation, we present novel strategies that reduce or omit dependency on penalty parameters while maintaining solution quality, effectively capturing both optimal and near-optimal solutions, and balancing the trade-offs between circuit depth and solution feasibility. We present SCOOP, a novel QAOA-based framework for solving constrained optimization problems. SCOOP transforms a constrained problem into an unconstrained counterpart, forming SCOOP problem twins. QAOA operates on the unconstrained twin to identify potential optimal and near-optimal solutions. Effective classical post-processing reduces the solution set to the constrained problem space. Our SCOOP approach is solution-enhanced, objective-function-compatible, and scalable. We demonstrate the effectiveness of the SCOOP framework on selected NP-hard problems, some of which can be encoded quadratically (such as Minimum Vertex Cover and Maximum Independent Set), and some that can be encoded using higher-order terms (such as Minimum Dominating Set, Minimum Maximal Matching, and Minimum Set Cover). We also apply our framework to constrained combinatorial optimization problems that can be solved in polynomial time, such as Minimum Edge Cover and Maximum Matching. Experimental results on full statevector simulators and tensor network simulators show that SCOOP significantly improves the probability of finding high-quality feasible solutions across various problem classes, on problems that can be encoded quadratically as well as problems that can be encoded using higher-order terms. We also demonstrate the effectiveness of SCOOP on real quantum hardware, specifically IBM Quantum Heron R2 processors with 156 qubits, showing that SCOOP can be applied to practical problems with current quantum hardware limitations. This work makes significant contributions toward achieving quantum utility by enabling systematic investigation of constrained optimization problems on quantum devices. While current quantum computing research primarily focuses on unconstrained problems like MaxCut, real-world applications typically involve constraints. SCOOP provides a scalable framework for encoding constrained problems, extending quantum computing's practical utility beyond simple unconstrained cases. By eliminating dependency on penalty parameters and providing natural problem formulations, SCOOP makes it feasible to explore quantum solutions for constrained problems where classical exact methods become intractable. This capability is crucial for identifying promising avenues for demonstrating quantum utility across diverse constrained optimization problems, advancing the practical applicability of quantum computing approaches.

•Jan 1, 2025•0 citations

A quantum constraint generation framework for binary linear programs

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

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.

arXiv:2503.21222•EPJ Quantum Technology•May 19, 2025•1 citation
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.
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.
Motivated by recent progress in quantum hardware and algorithms, researchers have developed quantum heuristics for optimization problems, aiming for advantages over classical methods. To date, quantum hardware is still error-prone and limited in size such that quantum heuristics cannot be scaled to relevant problem sizes and are often outperformed by their classical counterparts. Moreover, if provably optimal solutions are desired, one has to resort to classical exact methods. As, however, quantum technologies may improve considerably in future, we demonstrate in this work how quantum heuristics with limited resources can be integrated in large-scale exact optimization algorithms for NP-hard problems. To this end, we consider vehicle routing as a prototypical NP-hard problem. We model the pricing and separation subproblems arising in a branch-price-and-cut algorithm as quadratic unconstrained binary optimization problems. This allows to use established quantum heuristics like quantum annealing or the quantum approximate optimization algorithm for their solution. A key feature of our algorithm is that it profits not only from the best solution returned by the quantum heuristic but from all solutions below a certain cost threshold, thereby exploiting the inherent randomness is quantum algorithms. Moreover, we reduce the requirements on quantum hardware since the subproblems, which are solved via quantum heuristics, are smaller than the original problem. We provide a proof-of-concept experimental study comparing quantum annealing to simulated annealing and to established classical algorithms in our framework. While our hybrid quantum-classical approach is still outperformed by purely classical methods, our results reveal that both pricing and separation may be well suited for quantum heuristics if quantum hardware improves.
Airlines today are faced with a number of large-scale scheduling problems. One such problem is the tail-assignment problem, which is the task of assigning individual aircraft to a given set of flights, minimizing the overall cost. Each aircraft is identified by the registration number on its tail fin. In this paper, we simulate the quantum approximate optimization algorithm (QAOA) applied to instances of this problem derived from real-world data. The QAOA is a variational hybrid quantum-classical algorithm recently introduced and likely to run on near-term quantum devices. The instances are reduced to fit on quantum devices with 8, 15, and 25 qubits. The reduction procedure leaves only one feasible solution per instance, which allows us to map the tail-assignment problem onto the exact-cover problem. We find that repeated runs of the QAOA identify the feasible solution with close to unit probability for all instances. Furthermore, we observe patterns in the variational parameters such that an interpolation strategy can be employed, which significantly simplifies the classical optimization part of the QAOA. Finally, we empirically find a relation between the connectivity of the problem graph and the single-shot success probability of the algorithm.
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.
This dissertation addresses fundamental challenges in solving constrained combinatorial optimization problems using hybrid quantum-classical computing approaches. Quantum computing shows promise for tackling computationally intractable problems, current approaches face significant limitations. The path forward in computing involves combining quantum and classical computing approaches. Quantum processing units (QPUs) will play a key role in accelerating algorithms in optimization, simulation, and machine learning applications beyond what classical computers can achieve on their own, similar to how graphical processing units (GPUs) have become integral to general-purpose computing. The current generation of quantum devices is limited by noise and circuit depth constraints, making it challenging to gain practical utility. Hybrid quantum-classical approaches, which combine quantum computing resources with classical computing resources, are essential for addressing these limitations on near-term devices. In the area of combinatorial optimization, current practical state-of-the-art hybrid approaches are variational in nature, relying on parameterized quantum circuits to encode solutions and classical optimization techniques to find optimal parameters. While the ultimate goal of solving computationally intractable problems is to find provably optimal solutions, practical constraints of real-world scenarios often necessitate focusing on efficiently obtaining high-quality, near-optimal solutions. The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical approach for tackling these challenging problems that are encoded using quadratic and higher-order unconstrained binary optimization problems (QUBO and HUBO). QAOA alternates between two operators: a problem-specific cost Hamiltonian that encodes the optimization objective, and a mixer Hamiltonian that explores the solution space. The algorithm's parameters are iteratively optimized using classical methods to maximize the probability of sampling high-quality solutions. However, these methods often struggle with solution feasibility, especially for problems where the solutions must satisfy specific constraints. Penalty-based encodings require careful parameter tuning and risk producing infeasible solutions, while feasibility-preserving methods demand deeper quantum circuits that are challenging to implement on near-term quantum devices. In this dissertation, we present novel strategies that reduce or omit dependency on penalty parameters while maintaining solution quality, effectively capturing both optimal and near-optimal solutions, and balancing the trade-offs between circuit depth and solution feasibility. We present SCOOP, a novel QAOA-based framework for solving constrained optimization problems. SCOOP transforms a constrained problem into an unconstrained counterpart, forming SCOOP problem twins. QAOA operates on the unconstrained twin to identify potential optimal and near-optimal solutions. Effective classical post-processing reduces the solution set to the constrained problem space. Our SCOOP approach is solution-enhanced, objective-function-compatible, and scalable. We demonstrate the effectiveness of the SCOOP framework on selected NP-hard problems, some of which can be encoded quadratically (such as Minimum Vertex Cover and Maximum Independent Set), and some that can be encoded using higher-order terms (such as Minimum Dominating Set, Minimum Maximal Matching, and Minimum Set Cover). We also apply our framework to constrained combinatorial optimization problems that can be solved in polynomial time, such as Minimum Edge Cover and Maximum Matching. Experimental results on full statevector simulators and tensor network simulators show that SCOOP significantly improves the probability of finding high-quality feasible solutions across various problem classes, on problems that can be encoded quadratically as well as problems that can be encoded using higher-order terms. We also demonstrate the effectiveness of SCOOP on real quantum hardware, specifically IBM Quantum Heron R2 processors with 156 qubits, showing that SCOOP can be applied to practical problems with current quantum hardware limitations. This work makes significant contributions toward achieving quantum utility by enabling systematic investigation of constrained optimization problems on quantum devices. While current quantum computing research primarily focuses on unconstrained problems like MaxCut, real-world applications typically involve constraints. SCOOP provides a scalable framework for encoding constrained problems, extending quantum computing's practical utility beyond simple unconstrained cases. By eliminating dependency on penalty parameters and providing natural problem formulations, SCOOP makes it feasible to explore quantum solutions for constrained problems where classical exact methods become intractable. This capability is crucial for identifying promising avenues for demonstrating quantum utility across diverse constrained optimization problems, advancing the practical applicability of quantum computing approaches.
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.