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:2507.12159

Cutting Slack: Quantum Optimization with Slack-Free Methods for Combinatorial Benchmarks

Monit Sharma, Hoong Chuin Lau

Published Jul 16, 2025• 0 citations
arXivHTMLPDF

Abstract

Constraint handling remains a key bottleneck in quantum combinatorial optimization. While slack-variable-based encodings are straightforward, they significantly increase qubit counts and circuit depth, challenging the scalability of quantum solvers. In this work, we investigate a suite of Lagrangian-based optimization techniques including dual ascent, bundle methods, cutting plane approaches, and augmented Lagrangian formulations for solving constrained combinatorial problems on quantum simulators and hardware. Our framework is applied to three representative NP-hard problems: the Travelling Salesman Problem (TSP), the Multi-Dimensional Knapsack Problem (MDKP), and the Maximum Independent Set (MIS). We demonstrate that MDKP and TSP, with their inequality-based or degree-constrained structures, allow for slack-free reformulations, leading to significant qubit savings without compromising performance. In contrast, MIS does not inherently benefit from slack elimination but still gains in feasibility and objective quality from principled Lagrangian updates. We benchmark these methods across classically hard instances, analyzing trade-offs in qubit usage, feasibility, and optimality gaps. Our results highlight the flexibility of Lagrangian formulations as a scalable alternative to naive QUBO penalization, even when qubit savings are not always achievable. This work provides practical insights for deploying constraint-aware quantum optimization pipelines, with applications in logistics, network design, and resource allocation.

DOI
10.48550/arxiv.2507.12159

Related papers

Lagrangian duality in quantum optimization: Overcoming QUBO limitations for constrained problems

Einar Gabbassov, Gili Rosenberg, Artur Scherer

We propose an approach to solving constrained combinatorial optimization problems based on embedding the concept of Lagrangian duality into the framework of adiabatic quantum computation. Within the setting of circuit-model fault-tolerant quantum computation, we demonstrate that this approach achieves a quadratic improvement in circuit depth and maintains a constraint-independent circuit width in contrast with the prevalent approach of solving constrained problems via reformulations based on the quadratic unconstrained binary optimization (QUBO) framework. In this study, we include a detailed review of the limitations encountered when using QUBO for constrained optimization. We show that the proposed method overcomes these limitations by encoding the optimal solution at an energetically elevated level of a simpler problem Hamiltonian, which results in substantially more resource-efficient quantum circuits. We consolidate our strategy with a detailed analysis on how the concepts of Lagrangian duality such as duality gap and complementary slackness relate to the success probability of sampling the optimal solution. Our findings are illustrated by benchmarking the Lagrangian dual approach against the QUBO approach using the NP-complete binary knapsack problem.

arXiv:2310.04542•Physical Review Research•May 23, 2025•5 citations

Implementing Slack-Free Custom Penalty Function for QUBO on Gate-Based Quantum Computers

Xin Lee, Hoong Chuin Lau

Solving NP-hard constrained combinatorial optimization problems using quantum algorithms remains a challenging yet promising avenue toward quantum advantage. Variational Quantum Algorithms (VQAs), such as the Variational Quantum Eigensolver (VQE), typically require constrained problems to be reformulated as unconstrained ones using penalty methods. A common approach introduces slack variables and quadratic penalties in the QUBO formulation to handle inequality constraints. However, this leads to increased qubit requirements and often distorts the optimization landscape, making it harder to find high-quality feasible solutions. To address these issues, we explore a slack-free formulation that directly encodes inequality constraints using custom penalty functions, specifically the exponential function and the Heaviside step function. These steplike penalties suppress infeasible solutions without introducing additional qubits or requiring finely tuned weights. Inspired by recent developments in quantum annealing and thresholdbased constraint handling in gate-based algorithms, we implement and evaluate our approach on the Multiple Knapsack Problem (MKP). Experimental results show that the step-based formulation significantly improves feasibility and optimality rates compared to unbalanced penalization, while reducing overall qubit overhead.

arXiv:2504.12611•IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•1 citation

Unbalanced penalization: a new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms

J. A. Montañez-Barrera, Dennis Willsch, Alberto Maldonado-Romo +1 more

Abstract Solving combinatorial optimization problems of the kind that can be codified by quadratic unconstrained binary optimization (QUBO) is a promising application of quantum computation. Some problems of this class suitable for practical applications such as the traveling salesman problem (TSP), the bin packing problem (BPP), or the knapsack problem (KP) have inequality constraints that require a particular cost function encoding. The common approach is the use of slack variables to represent the inequality constraints in the cost function. However, the use of slack variables considerably increases the number of qubits and operations required to solve these problems using quantum devices. In this work, we present an alternative method that does not require extra slack variables and consists of using an unbalanced penalization function to represent the inequality constraints in the QUBO. This function is characterized by larger penalization when the inequality constraint is not achieved than when it is. We evaluate our approach on the TSP, BPP, and KP, successfully encoding the optimal solution of the original optimization problem near the ground state cost Hamiltonian. Additionally, we employ D -Wave Advantage and D -Wave hybrid solvers to solve the BPP, surpassing the performance of the slack variables approach by achieving solutions for up to 29 items, whereas the slack variables approach only handles up to 11 items. This new approach can be used to solve combinatorial problems with inequality constraints with a reduced number of resources compared to the slack variables approach using quantum annealing or variational quantum algorithms.

arXiv:2211.13914•Quantum Science and Technology•Mar 20, 2024•57 citations

From Circuits to Hardware: Benchmarking Standard and Qubit-Efficient Quantum Optimization on Real Hardware

Monit Sharma, Hoong Chuin Lau

Despite rapid progress in quantum optimization, broad real-hardware benchmarks comparing multiple algorithmic families across diverse combinatorial problems under a common protocol remain limited. We benchmark gate-based quantum optimization on four NP-hard problems: multi-dimensional knapsack (MDKP), maximum independent set (MIS), quadratic assignment (QAP), and market-share (MSP). We study VQE, CVaR-VQE, standard, multi-angle, and warm-start QAOA, together with qubit-efficient PCE and QRAO, on IBM Heron r1/r2 processors using resilience-level-2 mitigation. To our knowledge, this includes the first real-hardware QRAO results and the first multi-problem PCE hardware benchmark. Across 247 method-instance combinations, we report transpiled circuit size, hardware outcomes, and an independent-error gate-count fidelity proxy, $F_{\mathrm{est}}$. For MDKP and MIS, an empirical operating point near $F_{\mathrm{est}}\approx 0.1$, corresponding to about 770 two-qubit gates at the median Heron-r2 CZ error rate, marks the onset of noise-dominated execution. QAP exposes a separate bottleneck: dense one-hot encodings and an exponentially sparse feasible manifold, with feasible fraction $10!/2^{100}$ at $n=10$; no tested hardware method produces a feasible assignment. Compiled QAOA-family circuits are generally noise dominated, and a matched uniform-random control shows that most feasible low-fidelity outcomes fall within the random range, apart from one finite-sample MIS warm-start exception. A SWAP-aware, fractional-gate, Nighthawk-topology compilation counterfactual reduces two-qubit counts but leaves all circuits below $F_{\mathrm{est}}=10^{-3}$. These conclusions apply to the tested implementations rather than QAOA in general. Qubit-efficient methods extend runnable instance sizes, but only within the empirical fidelity budget.

quant-pharXiv:2607.11637•Quantum Science and Technology•Jul 14, 2026•0 citations

Quantum Approaches to NP-Hard Combinatorial Optimization Problems: A Review

Charan Karnati, P. Venkata Subba Reddy

NP-hard problems are one of the most computationally intensive challenges in computer science, appearing in many domains such as logistics, cybersecurity, drug design, and financial modelling. Classical algorithms become impractical as problem size increases due to combinatorial explosion. This paper presents a structured framework for analysing quantum algorithms targeting NP-hard optimization problems, like the Traveling Salesman Problem (TSP), Max-Cut, and Boolean Satisfiability (SAT). We have developed a taxonomy which categorizes quantum approaches—quantum annealing, variational algorithms (QAOA/VQE), and Grover-based search—based on problem encoding strategies, resource requirements, and theoretical guarantees. From the comparative analysis of existing literature, we: 1) Map algorithm classes to problem domains (e.g., QAOA for Max-Cut, annealing for TSP) 2) Identify performance trade-offs between solution quality, qubit counts, and circuit depth 3) Analyse hardware compatibility constraints across NISQ platforms 4) Reveal fundamental scalability barriers including noise susceptibility and embedding overhead The framework establishes implementation guidelines for near- term quantum hardware and proposes hybrid quantum-classical pathways to bridge theoretical potential and practical deployment. This systematic analysis prioritizes research directions for achieving quantum advantage in combinatorial optimization.

•Aug 5, 2025•0 citations

Improving Performance in Combinatorial Optimization Problems with Inequality Constraints: An Evaluation of the Unbalanced Penalization Method on D-Wave Advantage

J. A. Montañez-Barrera, Pim van den Heuvel, Dennis Willsch +1 more

Combinatorial optimization problems are one of the target applications of current quantum technology, mainly because of their industrial relevance, the difficulty of solving large instances of them classically, and their equivalence to Ising Hamiltonians using the quadratic unconstrained binary optimization (QUBO) formulation. Many of these applications have inequality constraints, usually encoded as penalization terms in the QUBO formulation using additional variables known as slack variables. The slack variables have two disadvantages: (i) these variables extend the search space of optimal and suboptimal solutions, and (ii) the variables add extra qubits and connections to the quantum algorithm. Recently, a new method known as unbalanced penalization has been presented to avoid using slack variables. This method offers a trade-off between additional slack variables to ensure that the optimal solution is given by the ground state of the Ising Hamiltonian, and using an unbalanced heuristic function to penalize the region where the inequality constraint is violated with the only certainty that the optimal solution will be in the vicinity of the ground state. This work tests the unbalanced penalization method using real quantum hardware on D-Wave Advantage for the traveling salesman problem (TSP). The results show that the unbalanced penalization method outperforms the solutions found using slack variables and sets a new record for the largest TSP solved with quantum technology.

arXiv:2305.18757•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•16 citations
Constraint handling remains a key bottleneck in quantum combinatorial optimization. While slack-variable-based encodings are straightforward, they significantly increase qubit counts and circuit depth, challenging the scalability of quantum solvers. In this work, we investigate a suite of Lagrangian-based optimization techniques including dual ascent, bundle methods, cutting plane approaches, and augmented Lagrangian formulations for solving constrained combinatorial problems on quantum simulators and hardware. Our framework is applied to three representative NP-hard problems: the Travelling Salesman Problem (TSP), the Multi-Dimensional Knapsack Problem (MDKP), and the Maximum Independent Set (MIS). We demonstrate that MDKP and TSP, with their inequality-based or degree-constrained structures, allow for slack-free reformulations, leading to significant qubit savings without compromising performance. In contrast, MIS does not inherently benefit from slack elimination but still gains in feasibility and objective quality from principled Lagrangian updates. We benchmark these methods across classically hard instances, analyzing trade-offs in qubit usage, feasibility, and optimality gaps. Our results highlight the flexibility of Lagrangian formulations as a scalable alternative to naive QUBO penalization, even when qubit savings are not always achievable. This work provides practical insights for deploying constraint-aware quantum optimization pipelines, with applications in logistics, network design, and resource allocation.
We propose an approach to solving constrained combinatorial optimization problems based on embedding the concept of Lagrangian duality into the framework of adiabatic quantum computation. Within the setting of circuit-model fault-tolerant quantum computation, we demonstrate that this approach achieves a quadratic improvement in circuit depth and maintains a constraint-independent circuit width in contrast with the prevalent approach of solving constrained problems via reformulations based on the quadratic unconstrained binary optimization (QUBO) framework. In this study, we include a detailed review of the limitations encountered when using QUBO for constrained optimization. We show that the proposed method overcomes these limitations by encoding the optimal solution at an energetically elevated level of a simpler problem Hamiltonian, which results in substantially more resource-efficient quantum circuits. We consolidate our strategy with a detailed analysis on how the concepts of Lagrangian duality such as duality gap and complementary slackness relate to the success probability of sampling the optimal solution. Our findings are illustrated by benchmarking the Lagrangian dual approach against the QUBO approach using the NP-complete binary knapsack problem.
Solving NP-hard constrained combinatorial optimization problems using quantum algorithms remains a challenging yet promising avenue toward quantum advantage. Variational Quantum Algorithms (VQAs), such as the Variational Quantum Eigensolver (VQE), typically require constrained problems to be reformulated as unconstrained ones using penalty methods. A common approach introduces slack variables and quadratic penalties in the QUBO formulation to handle inequality constraints. However, this leads to increased qubit requirements and often distorts the optimization landscape, making it harder to find high-quality feasible solutions. To address these issues, we explore a slack-free formulation that directly encodes inequality constraints using custom penalty functions, specifically the exponential function and the Heaviside step function. These steplike penalties suppress infeasible solutions without introducing additional qubits or requiring finely tuned weights. Inspired by recent developments in quantum annealing and thresholdbased constraint handling in gate-based algorithms, we implement and evaluate our approach on the Multiple Knapsack Problem (MKP). Experimental results show that the step-based formulation significantly improves feasibility and optimality rates compared to unbalanced penalization, while reducing overall qubit overhead.
Abstract Solving combinatorial optimization problems of the kind that can be codified by quadratic unconstrained binary optimization (QUBO) is a promising application of quantum computation. Some problems of this class suitable for practical applications such as the traveling salesman problem (TSP), the bin packing problem (BPP), or the knapsack problem (KP) have inequality constraints that require a particular cost function encoding. The common approach is the use of slack variables to represent the inequality constraints in the cost function. However, the use of slack variables considerably increases the number of qubits and operations required to solve these problems using quantum devices. In this work, we present an alternative method that does not require extra slack variables and consists of using an unbalanced penalization function to represent the inequality constraints in the QUBO. This function is characterized by larger penalization when the inequality constraint is not achieved than when it is. We evaluate our approach on the TSP, BPP, and KP, successfully encoding the optimal solution of the original optimization problem near the ground state cost Hamiltonian. Additionally, we employ D -Wave Advantage and D -Wave hybrid solvers to solve the BPP, surpassing the performance of the slack variables approach by achieving solutions for up to 29 items, whereas the slack variables approach only handles up to 11 items. This new approach can be used to solve combinatorial problems with inequality constraints with a reduced number of resources compared to the slack variables approach using quantum annealing or variational quantum algorithms.
Despite rapid progress in quantum optimization, broad real-hardware benchmarks comparing multiple algorithmic families across diverse combinatorial problems under a common protocol remain limited. We benchmark gate-based quantum optimization on four NP-hard problems: multi-dimensional knapsack (MDKP), maximum independent set (MIS), quadratic assignment (QAP), and market-share (MSP). We study VQE, CVaR-VQE, standard, multi-angle, and warm-start QAOA, together with qubit-efficient PCE and QRAO, on IBM Heron r1/r2 processors using resilience-level-2 mitigation. To our knowledge, this includes the first real-hardware QRAO results and the first multi-problem PCE hardware benchmark. Across 247 method-instance combinations, we report transpiled circuit size, hardware outcomes, and an independent-error gate-count fidelity proxy, FestF_{\mathrm{est}}Fest​. For MDKP and MIS, an empirical operating point near Fest≈0.1F_{\mathrm{est}}\approx 0.1Fest​≈0.1, corresponding to about 770 two-qubit gates at the median Heron-r2 CZ error rate, marks the onset of noise-dominated execution. QAP exposes a separate bottleneck: dense one-hot encodings and an exponentially sparse feasible manifold, with feasible fraction 10!/210010!/2^{100}10!/2100 at n=10n=10n=10; no tested hardware method produces a feasible assignment. Compiled QAOA-family circuits are generally noise dominated, and a matched uniform-random control shows that most feasible low-fidelity outcomes fall within the random range, apart from one finite-sample MIS warm-start exception. A SWAP-aware, fractional-gate, Nighthawk-topology compilation counterfactual reduces two-qubit counts but leaves all circuits below Fest=10−3F_{\mathrm{est}}=10^{-3}Fest​=10−3. These conclusions apply to the tested implementations rather than QAOA in general. Qubit-efficient methods extend runnable instance sizes, but only within the empirical fidelity budget.
NP-hard problems are one of the most computationally intensive challenges in computer science, appearing in many domains such as logistics, cybersecurity, drug design, and financial modelling. Classical algorithms become impractical as problem size increases due to combinatorial explosion. This paper presents a structured framework for analysing quantum algorithms targeting NP-hard optimization problems, like the Traveling Salesman Problem (TSP), Max-Cut, and Boolean Satisfiability (SAT). We have developed a taxonomy which categorizes quantum approaches—quantum annealing, variational algorithms (QAOA/VQE), and Grover-based search—based on problem encoding strategies, resource requirements, and theoretical guarantees. From the comparative analysis of existing literature, we: 1) Map algorithm classes to problem domains (e.g., QAOA for Max-Cut, annealing for TSP) 2) Identify performance trade-offs between solution quality, qubit counts, and circuit depth 3) Analyse hardware compatibility constraints across NISQ platforms 4) Reveal fundamental scalability barriers including noise susceptibility and embedding overhead The framework establishes implementation guidelines for near- term quantum hardware and proposes hybrid quantum-classical pathways to bridge theoretical potential and practical deployment. This systematic analysis prioritizes research directions for achieving quantum advantage in combinatorial optimization.
Combinatorial optimization problems are one of the target applications of current quantum technology, mainly because of their industrial relevance, the difficulty of solving large instances of them classically, and their equivalence to Ising Hamiltonians using the quadratic unconstrained binary optimization (QUBO) formulation. Many of these applications have inequality constraints, usually encoded as penalization terms in the QUBO formulation using additional variables known as slack variables. The slack variables have two disadvantages: (i) these variables extend the search space of optimal and suboptimal solutions, and (ii) the variables add extra qubits and connections to the quantum algorithm. Recently, a new method known as unbalanced penalization has been presented to avoid using slack variables. This method offers a trade-off between additional slack variables to ensure that the optimal solution is given by the ground state of the Ising Hamiltonian, and using an unbalanced heuristic function to penalize the region where the inequality constraint is violated with the only certainty that the optimal solution will be in the vicinity of the ground state. This work tests the unbalanced penalization method using real quantum hardware on D-Wave Advantage for the traveling salesman problem (TSP). The results show that the unbalanced penalization method outperforms the solutions found using slack variables and sets a new record for the largest TSP solved with quantum technology.