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

• URL: http://arxiv.org/abs/2507.12159v2
• Date: Thu, 17 Jul 2025 06:09:17 GMT
• Title: Cutting Slack: Quantum Optimization with Slack-Free Methods for Combinatorial Benchmarks
• Authors: Monit Sharma, Hoong Chuin Lau,
• Abstract summary: Constraint handling remains a key bottleneck in quantum optimization.<n>We investigate a suite of Lagrangian-based optimization techniques for solving constrained problems on quantum simulators and hardware.<n>Our results highlight the flexibility of Lagrangian formulations as a scalable alternative to QUBO penalization.
• Score: 4.266376725904727
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Adaptive Graph Shrinking for Quantum Optimization of Constrained Combinatorial Problems [4.266376725904727]
  We propose a hybrid classical--quantum framework based on graph shrinking to reduce the number of variables and constraints in QUBO formulations of optimization problems.<n>Our approach improves solution feasibility, reduces repair complexity, and enhances quantum optimization quality on hardware-limited instances.
  arXiv  Detail & Related papers  (2025-06-17T07:11:48Z)
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems [3.757262277494307]
  This paper proposes a novel combination of constraint encoding methods for the Quantum Approximate Optimization Ansatz.<n>One-hot constraints are enforced through $XY$-mixers that restrict the search space to the feasible sub-space naturally.<n>Since $XY$-mixers restrict the search space, specific state vector entries are always zero and can be omitted from the simulation, saving valuable memory and computing resources.
  arXiv  Detail & Related papers  (2025-06-03T17:46:53Z)
• Implementing Slack-Free Custom Penalty Function for QUBO on Gate-Based Quantum Computers [4.266376725904727]
  Variational Quantum Algorithms (VQAs) typically require constrained problems to be reformulated as unconstrained ones using penalty methods.<n>A common approach introduces slack variables and quadratic penalties in the QUBO formulation to handle inequality constraints.<n>We explore a slack-free formulation that directly encodes inequality constraints using custom penalty functions.<n>These step-like penalties suppress infeasible solutions without introducing additional qubits or requiring finely tuned weights.
  arXiv  Detail & Related papers  (2025-04-17T03:20:02Z)
• A Comparative Study of Quantum Optimization Techniques for Solving Combinatorial Optimization Benchmark Problems [4.266376725904727]
  We introduce a comprehensive benchmarking framework designed to evaluate quantum optimization techniques against well-established NP-hard problems.<n>Our framework focuses on key problem classes, including the Multi-Dimensional Knapsack Problem (MDKP), Maximum Independent Set (MIS), Quadratic Assignment Problem (QAP), and Market Share Problem (MSP)
  arXiv  Detail & Related papers  (2025-03-15T13:02:22Z)
• Reconfigurable Intelligent Surface (RIS)-Assisted Entanglement Distribution in FSO Quantum Networks [62.87033427172205]
  Quantum networks (QNs) relying on free-space optical (FSO) quantum channels can support quantum applications in environments where establishing an optical fiber infrastructure is challenging and costly. A reconfigurable intelligent surface (RIS)-assisted FSO-based QN is proposed as a cost-efficient framework providing a virtual line-of-sight between users for entanglement distribution.
  arXiv  Detail & Related papers  (2024-01-19T17:16:40Z)
• Achieving Constraints in Neural Networks: A Stochastic Augmented Lagrangian Approach [49.1574468325115]
  Regularizing Deep Neural Networks (DNNs) is essential for improving generalizability and preventing overfitting. We propose a novel approach to DNN regularization by framing the training process as a constrained optimization problem. We employ the Augmented Lagrangian (SAL) method to achieve a more flexible and efficient regularization mechanism.
  arXiv  Detail & Related papers  (2023-10-25T13:55:35Z)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  We present an alternative method that does not require extra slack variables. We evaluate our approach on the traveling salesman problem, the bin packing problem, and the knapsack problem. This new approach can be used to solve problems with inequality constraints with a reduced number of resources.
  arXiv  Detail & Related papers  (2022-11-25T06:05:18Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  In this paper, we develop a simple yet efficient approach for the problem of comparing uncertain quantities. We recast inner optimization in the Lagrangian as a learning problem for surrogate approximation, which bypasses apparent intractability. The proposed light-SD demonstrates superior performance on several representative problems ranging from finance to supply chain management.
  arXiv  Detail & Related papers  (2022-11-14T21:54:31Z)
• Exploiting In-Constraint Energy in Constrained Variational Quantum Optimization [7.541345730271882]
  In general, such constraints cannot be easily encoded in the circuit, and the quantum circuit measurement outcomes are not guaranteed to respect the constraints. We propose a new approach for solving constrained optimization problems with unimplement, easy-to-constrained quantum ansatze. We implement our method in QVoice, a Python package that interfaces with Qiskit for quick prototyping in simulators and on quantum hardware.
  arXiv  Detail & Related papers  (2022-11-13T20:58:00Z)
• Constrained Optimization via Quantum Zeno Dynamics [23.391640416533455]
  We introduce a technique that uses quantum Zeno dynamics to solve optimization problems with multiple arbitrary constraints, including inequalities. We show that the dynamics of quantum optimization can be efficiently restricted to the in-constraint subspace on a fault-tolerant quantum computer.
  arXiv  Detail & Related papers  (2022-09-29T18:00:40Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.