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

Monit Sharma, Hoong Chuin LauarXiv 2025 · DOI · arXiv

TL;DR

This paper introduces a "slack-free" framework for quantum combinatorial optimization that bypasses the need for resource-heavy slack variables. By leveraging classical Lagrangian relaxation techniques to handle constraints, the authors demonstrate significant qubit savings and improved solution quality on both quantum simulators and real-world hardware (Rigetti’s Ankaa-3) for NP-hard problems like the Traveling Salesman Problem and the Multi-Dimensional Knapsack Problem.

What Problem Does This Paper Address?

In the current "Noisy Intermediate-Scale Quantum" (NISQ) era, qubits are a precious and scarce resource. Most real-world combinatorial optimization problems involve hard inequality constraints (e.g., "the total weight must be less than $C$"). The standard method to map these to a Quadratic Unconstrained Binary Optimization (QUBO) model—the "language" of most quantum solvers—is to add slack variables.

However, slack variables come with a heavy price:

  1. Qubit Overhead: They significantly increase the number of qubits required, often pushing even modest problems beyond the limits of current hardware.
  2. Circuit Complexity: More variables lead to deeper, noisier circuits.
  3. Optimization Challenges: They enlarge the search space, making it harder for variational algorithms like QAOA or VQE to converge.

The authors seek to eliminate this "qubit bloat" by using Lagrangian-based methods that move constraints into the objective function without adding auxiliary variables.

Methods

The core idea is to use Lagrangian Relaxation. Instead of enforcing a hard constraint $h(x) \le 0$ with extra qubits, the constraint is "dualized" into the objective function as a penalty term $\lambda \cdot h(x)$, where $\lambda$ is a Lagrange multiplier.

The authors propose a hybrid classical-quantum workflow:

  • Classical Subroutine: Iteratively updates the multipliers ($\lambda$) using various dual optimization techniques.
  • Quantum Subroutine: Solves the resulting unconstrained (or simplified) subproblem to find the best binary solution $x$ for the current $\lambda$.

The paper benchmarks five specific dual update strategies:

  1. Subgradient Method / Dual Averaging: Simple, iterative updates based on constraint violations.
  2. Bundle Method: Uses a history of past gradients to stabilize updates.
  3. Cutting Plane Method: Refines a piecewise-linear approximation of the dual function.
  4. Augmented Lagrangian: Adds a quadratic penalty term to the linear Lagrangian to improve convergence and feasibility.
  5. Held-Karp Relaxation: A specialized relaxation specifically for the Traveling Salesman Problem (TSP) that handles degree constraints without slacks.

Datasets

The framework was evaluated on three canonical NP-hard problems:

  • Traveling Salesman Problem (TSP): Synthetic metric instances ranging from 5 to 10 cities.
  • Multi-Dimensional Knapsack Problem (MDKP): Instances from the SAC-94 dataset, derived from real-world industrial problems.
  • Maximum Independent Set (MIS): Benchmark graphs sourced from error-correcting code datasets.

Key Insights and Ideas

  • Massive Qubit Savings: For the Knapsack problem (MDKP), the slack-free approach reduced qubit requirements by up to 80% (e.g., from 116 qubits down to 20 for one instance), making previously "unrunnable" problems feasible on an 84-qubit QPU.
  • Dynamic vs. Static Penalties: Traditional QUBO uses fixed penalty weights. Lagrangian methods "learn" the right penalty level through iteration, which the authors found leads to much better feasibility and lower optimality gaps.
  • Problem-Specific Benefits: While MDKP and TSP saw huge qubit reductions, the Maximum Independent Set (MIS) problem doesn't inherently use slack variables. However, the Lagrangian framework still improved MIS solution quality by providing a more principled way to update penalties compared to naive QUBO.
  • The Hybrid Advantage: By decoupling the constraint handling (classical) from the combinatorial search (quantum), the system respects the limitations of NISQ hardware while utilizing the strengths of classical optimization.

Key Results

  • Performance on Hardware: On Rigetti’s Ankaa-3 QPU, the Subgradient method consistently outperformed the standard slack-based QUBO. For one MDKP instance (pb2), the optimality gap dropped from 22.7% (slack) to 10.7% (subgradient).
  • TSP Efficiency: For a 10-city TSP, the slack-based model required 100 qubits (exceeding hardware limits), while the slack-free Held-Karp formulation required only 45 qubits and achieved a 45.5% optimality gap on hardware.
  • Simulation Success: In simulators, the Augmented Lagrangian and Bundle methods frequently achieved Relative Solution Quality (RSQ) scores exceeding 90% for MIS instances, significantly better than the 40% achieved by naive slack-based QUBO.

Limitations and Future Work

  • Iterative Overhead: While slack-free methods save qubits, they require multiple iterations (runs) to tune the multipliers. This increases the total "wall-clock" time compared to a single-shot QUBO run.
  • Hyperparameter Tuning: Methods like the Augmented Lagrangian are sensitive to the initial choice of penalty parameters and step sizes.
  • Future Directions: The authors suggest integrating machine learning (e.g., Graph Neural Networks) to predict near-optimal Lagrange multipliers, further reducing the number of iterations needed. They also aim to test these formulations on alternative architectures like neutral-atom quantum processors.

Summary updated

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.
BibTeX
@misc{sharma2025cutting,
  author = {Monit Sharma and Hoong Chuin Lau},
  title = {{Cutting Slack: Quantum Optimization with Slack-Free Methods for Combinatorial Benchmarks}},
  year = {2025},
  eprint = {2507.12159},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2507.12159},
  howpublished = {arXiv},
}
Figure