arxiv: 2604.20088 · v1 · submitted 2026-04-22 · 🪐 quant-ph

Recognition: unknown

CVaR-Assisted Custom Penalty Function for Constrained Optimization

Xin Wei Lee , Hoong Chuin LAU

Authors on Pith no claims yet

Pith reviewed 2026-05-10 01:18 UTC · model grok-4.3

classification 🪐 quant-ph

keywords constrained optimizationQUBOcustom penalty functionCVaRvariational quantum algorithmsknapsack problemslack variables

0 comments

The pith

A slack-free nonlinear custom penalty with CVaR sampling reduces optimality gaps and improves consistency over slack-based QUBO for constrained quantum optimization.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a method to enforce inequality constraints in binary combinatorial problems for variational quantum algorithms without adding slack variables that enlarge the model and warp the landscape. It places a nonlinear custom penalty directly into the objective and approximates its value through finite sampling to keep evaluation tractable. Conditional Value-at-Risk is then used as the objective to steer the search toward higher-quality feasible regions. When tested on multi-dimensional knapsack instances, the resulting solutions show smaller optimality gaps and more stable performance than standard slack-augmented QUBO encodings. This matters for scaling quantum and hybrid solvers to real constrained problems in operations research where auxiliary variables quickly dominate qubit counts.

Core claim

The authors introduce a slack-free penalty formulation that uses a nonlinear custom penalty function to enforce inequality constraints directly in the objective. Finite sampling approximates the nonlinear term for use inside variational quantum algorithms, while integration of the Conditional Value-at-Risk objective improves robustness. On multi-dimensional knapsack benchmarks, the custom-penalty formulation combined with CVaR sampling produces improved optimality gaps and more consistent performance than conventional slack-based QUBO formulations.

What carries the argument

nonlinear custom penalty function evaluated via finite sampling under a CVaR objective

If this is right

The formulation removes the need for auxiliary slack variables, keeping the number of qubits and variables closer to the original problem size.
Feasibility structure of the input constraints is preserved more directly without additional post-processing or tuning.
The CVaR component focuses optimization effort on the tail of the solution distribution, yielding steadier high-quality outputs across repeated runs.
The same penalty construction applies to other constrained binary problems that currently rely on slack-augmented QUBO encodings.
Careful penalty design can limit distortion of the optimization landscape that quantum variational methods encounter.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The sampling-based treatment of nonlinear penalties may transfer to other variational or hybrid quantum-classical solvers facing similar constraint-handling costs.
If the accuracy of finite sampling holds at larger scales, the method could reduce the variable overhead that currently limits quantum approaches to modest-sized constrained instances.
Analogous slack-free penalties might benefit classical metaheuristics that also suffer from landscape distortion when constraints are encoded quadratically.
Testing the approach on problems with tighter feasibility margins would reveal whether the custom penalty maintains its consistency advantage when violation costs are higher.

Load-bearing premise

The finite-sampling approximation of the nonlinear custom penalty remains accurate enough during variational optimization to avoid bias or excessive variance that would erase the reported performance gains.

What would settle it

Running the same knapsack instances with the custom-penalty method and finding that final solutions violate the original constraints at a higher rate than slack-based runs, or that optimality gaps become equal or larger when the penalty is evaluated exactly rather than by sampling.

Figures

Figures reproduced from arXiv: 2604.20088 by Hoong Chuin LAU, Xin Wei Lee.

**Figure 2.** Figure 2: FIG. 2. Comparison between the mean optimality gaps between slack and custom penalty (non-slack) formulations. The [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 3.** Figure 3: FIG. 3. Comparison between the optimality gaps for different methods: finite sampling (FS) and Conditional Value-at-Risk [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

**Figure 4.** Figure 4: FIG. 4. Comparison between the probability of sampling [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗

**Figure 5.** Figure 5: FIG. 5. Comparison between the number of function evaluations for different methods: finite sampling (FS) and Conditional [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗

read the original abstract

Constrained combinatorial optimization problems are frequently reformulated as quadratic unconstrained binary optimization (QUBO) models in order to leverage emerging quantum optimization algorithms such as the Variational Quantum Eigensolver (VQE) and the Quantum Approximate Optimization Algorithm (QAOA). However, standard QUBO formulations enforce inequality constraints through slack variables and quadratic penalties, which can significantly increase the problem size and distort the optimization landscape. In this work, 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. 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a workable slack-free nonlinear penalty plus CVaR for quantum constrained QUBO, but the sampling approximation lacks the bias and variance checks needed to trust the reported gains.

read the letter

The main thing to know is that this work replaces slack variables with a custom nonlinear penalty that stays in the original variables, then uses CVaR on finite samples to make the whole thing tractable for VQE or QAOA. That removes the qubit overhead and some of the landscape distortion that slack penalties usually create, which matters for knapsack-sized instances. The authors test it on multi-dimensional knapsack benchmarks and say the combination gives tighter optimality gaps and steadier performance than the usual slack-augmented QUBO. The finite-sampling trick for the nonlinear term is a direct response to the exponential cost of exact expectation, and CVaR is a reasonable way to steer the optimizer toward the better tail of the distribution. Those pieces are new enough in the quantum-constrained-optimization literature to be worth noting. The soft spot is exactly where the stress-test note points: the nonlinear penalty estimator from bit-string samples is generally biased, yet the paper supplies no concentration bounds, bias-correction step, or shot-scaling curves. Without those, it is difficult to tell whether the consistency improvement is robust to realistic shot budgets or an artifact of the particular sample count and instance set chosen. The abstract claims the method “avoids exponential complexity,” but that is not the same as showing the approximation error stays small enough not to move the minimizers away from the feasible set. This paper is for people already working on penalty design and variational methods for operations-research problems on near-term hardware. A reader who needs concrete ideas for slack-free formulations will get something usable to prototype, though they will have to supply their own sampling analysis. It deserves a serious referee because the core formulation addresses a genuine scaling pain point and the empirical direction is clear, even if the current version needs tighter controls on the approximation quality before the performance claims can be taken at face value. I would send it out for review and ask the referees to focus on the bias-variance properties of the sampled penalty and to request explicit ablation tables on shot number versus gap.

Referee Report

2 major / 1 minor

Summary. The manuscript proposes a slack-free nonlinear custom penalty function to enforce inequality constraints directly in the objective for binary optimization problems, eliminating auxiliary slack variables that inflate QUBO size. It approximates this nonlinear penalty via finite sampling to enable use in variational quantum algorithms (VQE/QAOA) and augments the objective with Conditional Value-at-Risk (CVaR) sampling for robustness. The framework is evaluated on multi-dimensional knapsack instances, claiming reduced optimality gaps and more consistent performance relative to conventional slack-augmented QUBO formulations.

Significance. If the claimed performance gains are substantiated with quantitative evidence and sampling analysis, the approach could meaningfully reduce qubit overhead and landscape distortion in quantum solvers for constrained combinatorial problems common in operations research. The CVaR integration with a custom penalty offers a targeted way to prioritize feasible high-quality solutions under finite-shot variational optimization.

major comments (2)

[Abstract] Abstract: The claim that the custom-penalty formulation combined with CVaR sampling 'achieves improved optimality gaps and more consistent performance' supplies no quantitative results, error bars, baseline details, instance sizes, shot counts, or statistical comparisons. The central empirical assertion is therefore unsupported by evidence in the manuscript.
[Finite-sampling approximation] Finite-sampling section (Methods): The nonlinear custom penalty is approximated by finite sampling of the variational state, yet no bias or variance bounds, concentration inequality, or shot-scaling analysis with respect to constraint tightness or problem dimension is provided. Because the penalty involves nonlinear operations (e.g., max(0,·) or squared violations), the estimator is generally biased; without such analysis it is impossible to determine whether the reported gains remain valid under realistic sampling budgets or are artifacts of noise amplified by CVaR tail selection.

minor comments (1)

[Abstract] The abstract refers to 'the finite-sampling method that avoids the exponential complexity' without a citation or brief derivation showing how the sampling complexity scales.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive and detailed feedback. We address the major comments point by point below and will revise the manuscript accordingly to improve clarity and rigor.

read point-by-point responses

Referee: [Abstract] Abstract: The claim that the custom-penalty formulation combined with CVaR sampling 'achieves improved optimality gaps and more consistent performance' supplies no quantitative results, error bars, baseline details, instance sizes, shot counts, or statistical comparisons. The central empirical assertion is therefore unsupported by evidence in the manuscript.

Authors: We agree that the abstract would be strengthened by including key quantitative highlights from the experimental results. The full manuscript (Section IV) reports concrete comparisons on multi-dimensional knapsack instances, including optimality gap reductions, consistency metrics across multiple runs, instance sizes, and shot counts used in the VQE/QAOA simulations. We will revise the abstract to summarize these findings with specific numbers and baseline details while keeping it concise. revision: yes
Referee: [Finite-sampling approximation] Finite-sampling section (Methods): The nonlinear custom penalty is approximated by finite sampling of the variational state, yet no bias or variance bounds, concentration inequality, or shot-scaling analysis with respect to constraint tightness or problem dimension is provided. Because the penalty involves nonlinear operations (e.g., max(0,·) or squared violations), the estimator is generally biased; without such analysis it is impossible to determine whether the reported gains remain valid under realistic sampling budgets or are artifacts of noise amplified by CVaR tail selection.

Authors: The referee correctly identifies that the manuscript lacks explicit theoretical bounds on bias and variance for the finite-shot estimator of the nonlinear penalty. While empirical results demonstrate practical performance, we will add a new paragraph in the Methods section providing a basic bias analysis for the max(0,·) term, a Hoeffding-style concentration bound adapted to the sampled penalty, and a discussion of shot scaling with constraint tightness and problem size. This will help assess validity under realistic budgets. revision: yes

Circularity Check

0 steps flagged

No circularity: empirical comparison of custom penalty + CVaR against slack QUBO on knapsack instances is self-contained

full rationale

The paper introduces a slack-free nonlinear penalty, approximates it via finite sampling, augments with CVaR, and reports better optimality gaps on multi-dimensional knapsack benchmarks versus conventional slack-based QUBO. No derivation chain reduces a claimed result to its own fitted parameters or self-citations; the performance claims rest on direct experimental comparison rather than any self-definitional or tautological step. The finite-sampling approximation is presented as a practical necessity without being relabeled as an independent prediction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the effectiveness of a custom nonlinear penalty and finite-sampling approximation whose details are not specified; no free parameters or invented entities are explicitly introduced in the abstract.

axioms (1)

domain assumption Finite-sampling method approximates the nonlinear penalty expectation accurately enough for variational optimization to succeed
Invoked to avoid exponential complexity while evaluating the custom penalty in VQE/QAOA.

pith-pipeline@v0.9.0 · 5547 in / 1316 out tokens · 38888 ms · 2026-05-10T01:18:41.557422+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

30 extracted references · 13 canonical work pages · 2 internal anchors

[1]

A Quantum Approximate Optimization Algorithm

E. Farhi, J. Goldstone, and S. Gutmann, A quantum approximate optimization algorithm, arXiv:1411.4028 (2014), arXiv:arXiv:1411.4028 [quant-ph]

work page internal anchor Pith review Pith/arXiv arXiv 2014
[2]

Quantum Computation by Adiabatic Evolution

E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, Quantum computation by adiabatic evolution, (2000), arXiv:arXiv:quant-ph/0001106

work page Pith review arXiv 2000
[3]

Farhi and A

E. Farhi and A. W. Harrow, Quantum supremacy through the quantum approximate optimization algo- rithm (2019), arXiv:1602.07674 [quant-ph]

work page arXiv 2019
[4]

Tilly, H

J. Tilly, H. Chen, S. Cao, D. Picozzi, K. Setia, Y. Li, E. Grant, L. Wossnig, I. Rungger, G. H. Booth, and J. Tennyson, The variational quantum eigensolver: A re- view of methods and best practices, Physics Reports986, 1–128 (2022)

2022
[5]

X. Yan, X. Lee, D. Cai, and N. Asai, Comparison between the performances of general two-local ansatzes and qaoa in max-cut problem, IPSJ SIG Technical Report2024- QS-11, 1 (2024)

2024
[6]

Hadfield, Z

S. Hadfield, Z. Wang, B. O'Gorman, E. Rieffel, D. Ven- turelli, and R. Biswas, From the quantum approximate optimization algorithm to a quantum alternating opera- tor ansatz, Algorithms12, 34 (2019)

2019
[7]

Bartschi and S

A. Bartschi and S. Eidenbenz, Grover mixers for QAOA: Shifting complexity from mixer design to state prepara- tion, in2020 IEEE International Conference on Quan- tum Computing and Engineering (QCE)(IEEE, 2020)

2020
[8]

Golden, A

J. Golden, A. Bartschi, D. O’Malley, and S. Eidenbenz, Threshold-based quantum optimization, in2021 IEEE International Conference on Quantum Computing and 10 Engineering (QCE)(IEEE, 2021) p. 137–147

2021
[9]

F. G. Fuchs, K. O. Lye, H. Møll Nilsen, A. J. Stasik, and G. Sartor, Constraint preserving mixers for the quantum approximate optimization algorithm, Algorithms15, 202 (2022)

2022
[10]

Ni, L.-X

X.-H. Ni, L.-X. Li, Y.-Q. Song, Z.-P. Jin, S.-J. Qin, and F. Gao, Progressive quantum algorithm for maximum in- dependent set with quantum alternating operator ansatz, Chinese Physics B34, 070304 (2025)

2025
[11]

Li, Y.-L

H.-M. Li, Y.-L. Han, Z.-X. Wang, and S.-M. Fei, Vari- ational quantum algorithm for constrained combinato- rial optimization problems, Physical Review A113, 10.1103/ykxd-h19w (2026)

work page doi:10.1103/ykxd-h19w 2026
[12]

Yonaga, M

K. Yonaga, M. J. Miyama, and M. Ohzeki, Solving inequality-constrained binary optimization problems on quantum annealer (2020), arXiv:2012.06119 [quant-ph]

work page arXiv 2020
[13]

Takabayashi, T

T. Takabayashi, T. Goto, and M. Ohzeki, Subgradi- ent method using quantum annealing for inequality- constrained binary optimization problems, Journal of the Physical Society of Japan94, 10.7566/jpsj.94.054003 (2025)

work page doi:10.7566/jpsj.94.054003 2025
[14]

T. V. Le and V. Kekatos, Variational quantum eigen- solver with constraints (vqec): Solving constrained op- timization problems via vqe (2024), arXiv:2311.08502 [quant-ph]

work page arXiv 2024
[15]

Westerheim, J

H. Westerheim, J. Chen, Z. Holmes, I. Luo, T. Nuradha, D. Patel, S. Rethinasamy, K. Wang, and M. M. Wilde, Dual variational quantum eigensolver: A quantum algo- rithm to lower bound the ground-state energy, Physical Review A113, 10.1103/twrt-y691 (2026)

work page doi:10.1103/twrt-y691 2026
[16]

J. A. Monta˜ nez-Barrera, D. Willsch, A. Maldonado- Romo, and K. Michielsen, Unbalanced penalization: a new approach to encode inequality constraints of combi- natorial problems for quantum optimization algorithms, Quantum Science and Technology9, 025022 (2024)

2024
[17]

J. A. Monta˜ nez-Barrera, P. van den Heuvel, D. Willsch, and K. Michielsen, Improving performance in combina- torial optimization problems with inequality constraints: An evaluation of the unbalanced penalization method on d-wave advantage, in2023 IEEE International Confer- ence on Quantum Computing and Engineering (QCE) (IEEE, 2023) p. 535–542

2023
[18]

Bucher, J

D. Bucher, J. Stein, S. Feld, and C. Linnhoff- Popien, Penalty-free approach to accelerating con- strained quantum optimization, Physical Review A112, 10.1103/fb5m-cl9m (2025)

work page doi:10.1103/fb5m-cl9m 2025
[19]

Bucher, D

D. Bucher, D. Porawski, M. Janetschek, J. Stein, C. O’Meara, G. Cortiana, and C. Linnhoff-Popien, Effi- cient qaoa architecture for solving multi-constrained opti- mization problems (2025), arXiv:2506.03115 [quant-ph]

work page arXiv 2025
[20]

X. W. Lee and H. C. Lau, Implementing slack-free cus- tom penalty function for qubo on gate-based quantum computers, in2025 IEEE International Conference on Quantum Computing and Engineering (QCE), Vol. 01 (2025) pp. 2112–2119

2025
[21]

Kandala, A

A. Kandala, A. Mezzacapo, K. Temme, M. Takita, M. Brink, J. M. Chow, and J. M. Gambetta, Hardware- efficient variational quantum eigensolver for small molecules and quantum magnets, Nature549, 242 (2017)

2017
[22]

P. K. Barkoutsos, G. Nannicini, A. Robert, I. Tavernelli, and S. Woerner, Improving variational quantum opti- mization using cvar, Quantum4, 256 (2020)

2020
[23]

Kulik and H

A. Kulik and H. Shachnai, There is no eptas for two- dimensional knapsack, Inf. Process. Lett.110, 707–710 (2010)

2010
[24]

Beasly, Or-library,https://people.brunel.ac.uk/ ~mastjjb/jeb/orlib/mknapinfo.html(2018)

J. Beasly, Or-library,https://people.brunel.ac.uk/ ~mastjjb/jeb/orlib/mknapinfo.html(2018)

2018
[25]

Sharma and H

M. Sharma and H. C. Lau, A comparative study of quantum optimization techniques for solving com- binatorial optimization benchmark problems (2025), arXiv:2503.12121 [quant-ph]

work page arXiv 2025
[26]

X. Yan, X. Lee, N. Xie, Y. Saito, L. Kurosawa, N. Asai, D. Cai, and H. C. Lau, Light cone cancellation for vari- ational quantum eigensolver ansatz, arXiv:2404.19497 (2024), arXiv:2404.19497 [quant-ph]

work page internal anchor Pith review Pith/arXiv arXiv 2024
[27]

Shaydulin, P

R. Shaydulin, P. C. Lotshaw, J. Larson, J. Ostrowski, and T. S. Humble, Parameter transfer for quantum ap- proximate optimization of weighted maxcut (2022)

2022
[28]

Z. He, R. Shaydulin, S. Chakrabarti, D. Herman, C. Li, Y. Sun, and M. Pistoia, Alignment between initial state and mixer improves qaoa performance for constrained op- timization, npj Quantum Information9, 10.1038/s41534- 023-00787-5 (2023)

work page doi:10.1038/s41534- 2023
[29]

X. W. Lee and H. C. Lau, Solving constrained combi- natorial optimization problems with variational quan- tum imaginary time evolution, in2025 IEEE Interna- tional Conference on Quantum Computing and Engineer- ing (QCE), Vol. 01 (2025) pp. 1955–1964

2025
[30]

Larocca, S

M. Larocca, S. Thanasilp, S. Wang, K. Sharma, J. Bia- monte, P. J. Coles, L. Cincio, J. R. McClean, Z. Holmes, and M. Cerezo, Barren plateaus in variational quantum computing, Nature Reviews Physics7, 174 (2025)

2025