CVaR-Assisted Custom Penalty Function for Constrained Optimization
arXiv:2604.20088
The paper introduces a slack‑free, nonlinear penalty function for constrained binary optimization and combines it with a CVaR‑based objective to improve the performance of quantum algorithms like VQE and QAOA on problems such as the multi‑dimensional knapsack.
Abstract
We propose a slack-free penalty formulation for constrained binary optimization that eliminates auxiliary slack variables and preserves the feasibility structure of the original problem. The proposed approach introduces a nonlinear custom penalty function to enforce inequality constraints directly in the objective function. To address the computational challenges associated with evaluating nonlinear penalties in variational quantum algorithms, we employ the finite-sampling method that avoids the exponential complexity required by exact expectation computation. Furthermore, we integrate the Conditional Value-at-Risk (CVaR) objective to improve optimization robustness and guide the search toward high-quality solutions. The proposed framework is evaluated on instances of the multi-dimensional knapsack problem, a classical benchmark in combinatorial optimization. We showcase that the proposed custom-penalty formulation combined with CVaR sampling achieves improved optimality gaps and more consistent performance compared with conventional slack-based QUBO formulations. We also tested our method on the Quantinuum H2 quantum hardware, demonstrating the possibilities of training small-sized VQE on noisy trapped-ion quantum computers. The results suggest that careful penalty design can play a critical role in enabling quantum and hybrid quantum-classical algorithms for constrained optimization problems that arise in operations research.
13 pages, 7 figures, 2 tables