Feasibility-driven QAOA with penalty scheduling

• URL: http://arxiv.org/abs/2606.25117v1
• Date: Tue, 23 Jun 2026 19:44:00 GMT
• Title: Feasibility-driven QAOA with penalty scheduling
• Abstract summary: Most available quantum algorithms address constrained optimization problems by treating constraints as soft penalty terms within a QUBO formulation.<n>We introduce two extensions of standard linear-ramp QAOA tailored to problems with multiple heterogeneous constraints.<n>We show that piecewise-ramp QAOA consistently outperforms lr-QAOA and $$-lr-QAOA across circuit depths and system sizes.
• Score: 1.4519462317941787
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Most available quantum algorithms address constrained optimization problems by treating constraints as soft penalty terms within a QUBO formulation. This approach requires careful adjustment of the penalty coefficients, which scales poorly with the number of constraints and lacks a proper strategy to balance feasibility and solution quality. In this work, we introduce two extensions of standard linear-ramp QAOA (lr-QAOA) tailored to problems with multiple heterogeneous constraints. We first construct $Λ$-lr-QAOA, in which each penalty term is assigned its own linear-ramp schedule, promoting penalty weights from external hyperparameters to internal variational parameters of QAOA, similarly to the objective and mixer parameters. By optimizing all schedules jointly in a single run, this approach eliminates nested penalty tuning and scales more efficiently to multiple constraints. The optimization is guided by a feasibility-driven loss function that pushes the quantum state towards high-quality feasible solutions. As a further refinement, we introduce piecewise-ramp QAOA, in which the linear ramps are replaced by two-segment piecewise schedules, enhancing the expressiveness of the Ansatz at the cost of a small parameter overhead independent of the circuit depth. We benchmark both methods on Earth-observation satellite mission planning tasks formulated as budget-constrained Maximum Weight Independent Set problems. Numerical results show that piecewise-ramp QAOA consistently outperforms lr-QAOA and $Λ$-lr-QAOA across circuit depths and system sizes. Furthermore, both $Λ$-lr-QAOA and piecewise-ramp QAOA exhibit a high feasibility rate, which is crucial in industrial applications. Our analysis highlights an intrinsic feasibility-optimality trade-off, which we address by introducing a filtered variant of the loss providing a single hyperparameter to tune this balance.

Related papers

• A Hybrid Classical-Quantum Approach for Multi-Constrained Location Optimization Problem [0.19573380763700712]
  The Maximal Covering Location Problem (MCLP) aims to determine the optimal facility placements that maximize total coverage.<n>It is characterized by both equality and inequality constraints, which ensure correct coverage but significantly increase the complexity of exploring the solution space as instance size grows.<n>In this work, the MCLP is formulated as a Quadratic Unconstrained Binary Optimization model, where constraint embedding plays a critical role in solution quality.
  arXiv  Detail & Related papers  (2026-07-08T19:44:55Z)
• Linear-Core Surrogates: Smooth Loss Functions with Linear Rates for Classification and Structured Prediction [42.67092904252001]
  We propose a new family of convex loss functions that resolve this tension by stitching a linear core to a smooth tail.<n>We prove that these surrogates are differentiable everywhere while retaining strict linear $H$-consistency bounds.
  arXiv  Detail & Related papers  (2026-04-30T11:32:25Z)
• EQE-QAOA: An Equivalence-Preserving Qubit Efficient Framework for Combinatorial Optimization [54.05451096499336]
  Existing techniques rely on qubit reduction at the cost of information loss, leading to degraded computational performance.<n>We propose the Equivalence-preserving Qubit Efficient QAOA, which significantly reduces the required number of qubits without degrading performance.<n>We show that it is broadly applicable to large-scale optimization problems, excluding only unconstrained problems with completely independent variables.
  arXiv  Detail & Related papers  (2026-04-20T13:57:49Z)
• Improving Feasibility in Quantum Approximate Optimization Algorithm for Vehicle Routing via Constraint-Aware Initialization and Hybrid XY-X Mixing [2.204918347869259]
  Vehicle Routing Problem (VRP) is a core problem in logistics and transportation.<n> conventional Pauli-$X$ mixer can disrupt partial solution structures that satisfy key local constraints.<n>We propose a constraint-aware QAOA framework with two complementary components.
  arXiv  Detail & Related papers  (2026-04-08T15:39:22Z)
• Design and Analysis of an Improved Constrained Hypercube Mixer in Quantum Approximate Optimization Algorithm [0.0]
  In the Noisy Intermediate-Scale Quantum (NISQ) era, QAOA is not suited for constrained problems.<n>One way to incorporate certain types of constraints is to restrict the mixing operator to the feasible subspace.<n>We present a modification that generates circuits with fewer gates for a broad class of constrained problems.
  arXiv  Detail & Related papers  (2026-03-05T13:57:15Z)
• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• Constrained Dynamic Gaussian Splatting [47.982650444869336]
  Constrained Dynamic Gaussian Splatting (CDGS) is a novel framework that formulates dynamic scene reconstruction as a budget-constrained optimization problem.<n>We show that CDGS delivers optimal rendering quality under varying capacity limits, achieving over 3x compression compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2026-02-03T13:53:29Z)
• QTIS: A QAOA-Based Quantum Time Interval Scheduler [0.22940141855172033]
  The proposed method integrates an ancilla-assisted quantum circuit to dynamically detect and penalize overlapping tasks.<n>Results confirm the efficiency of QTIS in scheduling tasks with fixed temporal windows while minimizing conflicts.
  arXiv  Detail & Related papers  (2025-11-19T16:29:14Z)
• PT$^2$-LLM: Post-Training Ternarization for Large Language Models [52.4629647715623]
  Large Language Models (LLMs) have shown impressive capabilities across diverse tasks, but their large memory and compute demands hinder deployment.<n>We propose PT$2$-LLM, a post-training ternarization framework tailored for LLMs.<n>At its core is an Asymmetric Ternary Quantizer equipped with a two-stage refinement pipeline.
  arXiv  Detail & Related papers  (2025-09-27T03:01:48Z)
• Cutting Slack: Quantum Optimization with Slack-Free Methods for Combinatorial Benchmarks [4.266376725904727]
  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.
  arXiv  Detail & Related papers  (2025-07-16T11:39:47Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  This paper examines a crucial subset of problems where both the objective and constraint functions are weakly convex.<n>Existing methods often face limitations, including slow convergence rates or reliance on double-loop designs.<n>We introduce a novel single-loop penalty-based algorithm to overcome these challenges.
  arXiv  Detail & Related papers  (2025-04-21T17:15:48Z)
• STORM+: Fully Adaptive SGD with Momentum for Nonconvex Optimization [74.1615979057429]
  We investigate non-batch optimization problems where the objective is an expectation over smooth loss functions. Our work builds on the STORM algorithm, in conjunction with a novel approach to adaptively set the learning rate and momentum parameters.
  arXiv  Detail & Related papers  (2021-11-01T15:43:36Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)

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.