Pith. sign in

REVIEW 3 major objections 4 minor 2 cited by

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

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Slack-free Lagrangian encodings can match QUBO solution quality with far fewer qubits.

desk verdict Qubit savings are real, but Algorithm 7 makes the MDKP "quantum" step a trivial linear thresholding, so the central performance claim is unsupported as written. read the letter →

arxiv 2507.12159 v3 pith:VDSU46OW submitted 2025-07-16 quant-ph

Monit Sharma , Hoong Chuin Lau This is my paper
classification quant-ph MSC 90C2790C1081P68
keywords quantumoptimizationQUBOLagrangianrelaxationslackvariablescombinatorialtravellingsalesmanproblemmultidimensionalknapsackmaximumindependentset
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper tries to establish that Lagrangian relaxation can replace slack-variable encodings in quantum combinatorial optimization, cutting qubit counts for MDKP and TSP without sacrificing solution quality, and that even for MIS, where slack elimination gives no qubit saving, principled multiplier updates improve feasibility and objective quality. If true, this matters because slack variables are a major scalability bottleneck on noisy intermediate-scale quantum hardware: they inflate qubit counts and circuit depth. The paper benchmarks dual averaging, stochastic subgradient, bundle, cutting-plane, and augmented-Lagrangian updates against a slack-based QUBO baseline on TSP, MDKP, and MIS instances, in simulation and on a gate-model superconducting QPU, and reports lower or comparable optimality gaps for the Lagrangian methods on most instances. The authors position the result as a hybrid pipeline: tune multipliers classically, then solve the final relaxed QUBO once with a quantum solver.

What carries the argument

The central mechanism is Lagrangian relaxation with classical dual updates followed by a single quantum QUBO solve. Hard constraints $h(x) \le 0$ are replaced by linear penalty terms $\lambda h(x)$; the multipliers $\lambda$ are updated by subgradient, dual-averaging, bundle, cutting-plane, or augmented-Lagrangian rules until the relaxed solution is close to feasible; and the resulting relaxed objective is converted to a QUBO and solved once with a variational quantum eigensolver. For TSP the relaxed subproblem is the minimum-cost 1-tree of the Held-Karp relaxation, for MDKP it is an item-by-item threshold choice, and for MIS it is vertex selection with weights reduced by adjacent-edge penalties.

What would settle it

Recompute the MDKP results in Tables V and VI using the closed-form rule from Algorithm 7, $x_i = 1$ exactly when $p_i - \sum_j \lambda_j^* w_{ji} > 0$, and compare the gaps with the reported VQE gaps; if they coincide, the quantum solve is not doing the work, and if they diverge, the published encoding omits terms that the experiments actually used.

Watch

Extended reading notes

Core claim

The paper claims that problems with inequality or degree constraints can be dualized into Lagrange multipliers to produce a slack-free QUBO that uses far fewer qubits while keeping solution quality competitive. For TSP it uses the Held-Karp relaxation, dualizing degree constraints so the subproblem is a minimum-cost 1-tree and residual subtours are handled by classical post-processing. For MDKP it dualizes the resource-capacity constraints, yielding a separable item-choice subproblem and a final QUBO with no slack variables. For MIS the edge constraints are dualized as well, and although the qubit count is the same with or without slack, iterative multiplier updates raise the relative solution quality, with several instances above 90 percent. Across simulator and hardware runs, the Lagrangian methods, especially subgradient and bundle updates, report lower or comparable gaps than the slack-QUBO baseline on most instances.

Load-bearing premise

The load-bearing premise is that the classically tuned Lagrangian objective, once encoded as a QUBO, still represents the original constrained problem well enough that solving that QUBO on a quantum device is a meaningful test of solution quality; the MDKP case carries extra weight because the paper's Algorithm 7 makes the final objective linear in the binary variables.

Editorial extensions

If this is right

  • MDKP and TSP instances that exceed hardware qubit limits under slack encodings can be executed in slack-free form; MDKP pb5 drops from 116 to 20 qubits, and several slack-based instances that hit the qubit limit run successfully without slack.
  • Subgradient and bundle multiplier updates give the most consistent quality gains, so they are the natural defaults for a Lagrangian quantum optimization pipeline.
  • The hybrid workflow keeps iterative constraint handling classical and sends only a compact relaxed QUBO to the quantum device once, which is the practical way to fit constrained problems on near-term hardware.
  • For MIS, the qubit counts are identical between slack and slack-free encodings, so the reported improvements in relative solution quality come from the multiplier-update dynamics rather than from encoding compactness.
  • The paper claims no quantum advantage; classical solvers still resolve the benchmark instances faster, so the contribution is formulation compactness and hybrid feasibility.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the final MDKP QUBO in Algorithm 7 is genuinely linear in the binary variables, the quantum solve reduces to a classical threshold rule; a direct classical recomputation of the reported gaps would reveal whether the gains come from the Lagrangian relaxation itself rather than from the quantum subroutine.
  • A fairer benchmark would hold the classical multiplier-tuning budget fixed and compare the final QUBO solution with and without a quantum solve, since most of the constraint-handling work happens before the quantum device is used.
  • The same slack-free Lagrangian encodings could be tested inside classical local-search or branch-and-bound solvers; if they help there too, the benefit would be formulation-level rather than quantum-specific.
  • For MIS, the lesson is that multiplier dynamics, not qubit reduction, drive the improvement, which suggests that tuned penalties can help any QUBO-based solver even when the encoding cannot be made more compact.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proposes slack-free Lagrangian-relaxation-based encodings for three NP-hard combinatorial problems (TSP, MDKP, and MIS) and benchmarks them against slack-variable QUBO baselines on quantum simulators and on Rigetti's Ankaa-3 QPU. The authors apply classical dual-update methods (dual averaging, stochastic subgradient, bundle method, cutting plane, and augmented Lagrangian) to tune Lagrange multipliers, then map the final relaxed objective to a QUBO solved by VQE. They report qubit savings and optimality gaps or relative solution quality across tables and claim that Lagrangian formulations are a scalable alternative to naive QUBO penalization.

Significance. If the central claim were fully validated, the paper would offer practically useful guidance on encoding inequality and degree constraints in near-term quantum optimization. The benchmark instances are external with known optima, the scope explicitly avoids claiming quantum advantage, and the hybrid classical-quantum pipeline is a sensible architecture. However, the significance is critically contingent on the reported quantum runs actually solving nontrivial QUBO instances; the manuscript as written does not establish this, because the MDKP final objective is linear and the TSP final Hamiltonian is unspecified.

major comments (3)
  1. [Appendix A, Algorithm 7, step 12] The final MDKP objective defined in step 12 is min_{x∈{0,1}^n} −∑_i (p_i −∑_j λ*_j w_ji) x_i +∑_j λ*_j b_j, which is affine in the binary variables. Minimizing a linear binary function is classically trivial (set x_i = 1 iff the coefficient is positive), so the subsequent VQE run does not solve a nontrivial QUBO. The reported MDKP optimality gaps in Tables V and VI are therefore attributable to the classical multiplier optimization, not to the quantum solver. The manuscript must specify the actual quadratic Hamiltonian (including any penalty terms from the augmented Lagrangian or other regularizers) that was executed on the simulator/QPU, or explicitly state that the MDKP experiments are classical.
  2. [Section III.A.1] The Held-Karp Lagrangian relaxation for TSP dualizes the degree constraints, but the resulting subproblem is a minimum-cost 1-tree solvable in polynomial time. The text does not provide the QUBO/Ising Hamiltonian that is finally solved by the quantum device. If the quantum step simply optimizes the relaxed objective with fixed multipliers (without subtour-elimination constraints), the problem remains classically polynomial, and the hardware results in Table IV do not demonstrate quantum benefit. Please give the explicit final Hamiltonian, explain how subtour violations are handled in the quantum solution, and describe the circuit ansatz and number of layers used.
  3. [Section IV.C and abstract] The abstract's claim of 'significant qubit savings without compromising performance' is not established as a quantum result. Since the MDKP final objective is linear and the TSP encoding is unspecified, the comparison against the slack-based QUBO baseline is not a fair evaluation of quantum solvers: the baseline solves a genuine quadratic problem on the device, while the Lagrangian methods may effectively solve a classically trivial problem and delegate only the multiplier tuning to classical algorithms. The paper needs to ensure that the quantum step solves a nontrivial quadratic objective and to provide evidence (e.g., circuit-depth, sampling counts, or a comparison against classical thresholding) that the QPU execution affects the reported gaps.
minor comments (4)
  1. [Section III.A.2 and Appendix A] The notation for resource capacities is inconsistent: Section III.A.2 uses c_j for capacities, while Algorithm 7 and Table II use b_j; please unify the notation.
  2. [Section II.A, Eq. (3)] The symbol m is used for both the number of slack bits in Eq. (3) and the number of constraints elsewhere (e.g., MDKP), which is confusing; consider using a different symbol for the slack precision.
  3. [Figures 1-6] The figures are referenced in the text and captions but are not visible in the submitted manuscript, so the scatter plots and qubit-scaling comparisons cannot be evaluated; please include the actual figures.
  4. [Section IV] The hyperparameters for the dual updates (step size α_k, bundle parameter β, augmented Lagrangian penalty μ) and the VQE settings (ansatz, number of layers, optimizer, shots) are not reported; these details are necessary for reproducibility.

Circularity Check

1 steps flagged · score 6.0 of 10

MDKP 'quantum' results reduce to classical thresholding: Algorithm 7's final QUBO is affine, so its optimum is the same Lagrangian-subproblem solution used to fit the multipliers.

  1. self definitional [Appendix A, Algorithm 7, step 12 (with step 3); see also Section III.B.1]
    "F ormulate QUBO: Insert λ∗ into the Lagrangian-relaxed objective to define min_{x∈{0,1}^n} −( Σ_i [ p_i − Σ_j λ∗_j w_ji ] x_i + Σ_j λ∗_j b_j )."

    Step 3 solves the Lagrangian subproblem by the closed-form rule x_i(λ)=1 iff p_i − Σ_j λ_j w_ji > 0. The step-12 'QUBO' is an affine function of x: minimizing it over binary variables sets x_i=1 iff the coefficient −(p_i − Σ_j λ∗_j w_ji) is negative, i.e. iff p_i − Σ_j λ∗_j w_ji > 0. Hence the final solution returned after the VQE step is identical, by construction, to the classical subproblem solution used to compute the dual function and subgradients that produced λ∗. The MDKP optimality gaps in Tables V and VI are therefore the outputs of the classical thresholding heuristic, not of a quantum optimization that adds new information; the quantum solver cannot change an affine optimum.

full rationale

The paper is benchmarked against external instances (SAC-94, Sloane graphs, Euclidean TSP instances) and known optima, and the self-citations [23,26] appear only as background context, so no load-bearing self-citation chain is present. The 'significant qubit savings' of slack-free encodings is a definitional consequence of omitting slack variables rather than a derived empirical prediction; this is a framing observation, not a circular derivation. The one substantive circularity is the MDKP pipeline: Algorithm 7 specifies the final objective as affine, making the VQE result equal to the same thresholding used to fit the multipliers, so the central MDKP performance claim reduces by construction to a classical heuristic. The manuscript does not give an explicit final QUBO for the TSP or MIS variants, so no analogous reduction can be exhibited for them from the text; that missing derivation is an auditability gap rather than a demonstrated circularity. Because one of the three central problem results is forced by construction, the overall circularity score is 6 rather than higher.

Assumptions & free parameters 5 free parameters · 3 assumptions · 0 invented entities

The ledger is dominated by unreported hyperparameters and standard optimization assumptions. No new physical or mathematical entities are introduced. The most consequential item is the assumption that the final relaxed QUBO can be solved meaningfully by a quantum device; the appendix text casts doubt on whether the quantum subproblem is nontrivial at all.

free parameters (5)
  • subgradient step size alpha_k = not reported
    Controls the pace of multiplier updates in dual averaging and subgradient methods; results depend on its schedule.
  • bundle method QP stabilization parameter beta = not reported
    Stabilizes the quadratic program in the bundle method; value affects convergence and final multipliers.
  • augmented Lagrangian penalty parameter mu = not reported
    The paper states performance is 'highly sensitive to penalty coefficient tuning' and a tuning failure led to a gap over 50% on pet6.
  • VQE hyperparameters = not reported
    Circuit depth, ansatz type, optimizer, learning rate, and number of shots are not specified, despite being central to the quantum results.
  • iteration count K and tolerance epsilon = not reported
    Termination criteria for the classical dual-update loop are not given.
assumptions (3)
  • standard math The Lagrangian dual function is concave and the chosen subgradient/bundle/cutting-plane updates converge to a near-optimal dual solution.
    Invoked in Section III.B without proof; standard result under technical conditions not checked for the discrete subproblems.
  • domain assumption The Hamiltonian or QUBO derived from the Lagrangian-relaxed objective faithfully represents the original constrained problem for the quantum solver.
    The paper assumes the relaxed QUBO, when solved by VQE, produces solutions relevant to the original constraints. This is load-bearing and not established; Appendix Algorithm 7 suggests a linear objective for MDKP.
  • domain assumption The selected benchmark instances (SAC-94, synthetic TSP, coding-theory graphs) are representative of classically hard instances for the conclusions drawn.
    The paper generalizes from a small set of instances; representative-ness is assumed rather than demonstrated.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Cutting Slack: Quantum Optimization with Slack-Free Methods for Combinatorial Benchmarks." pith.science (2026). https://pith.science/paper/VDSU46OW

@misc{pith2026250712159,
  author       = {Pith},
  title        = {Pith review of: Cutting Slack: Quantum Optimization with Slack-Free Methods for Combinatorial Benchmarks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VDSU46OW}},
  note         = {Machine review of arXiv:2507.12159}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2507.12159 by the authors.

Figure 1
Figure 1. FIG. 1: Comparison of qubit requirements across problem formulations. [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. FIG. 2: Performance analysis of various optimization methods on the TSP instances. Each plot compares simulator [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. FIG. 3: Performance analysis of various optimization methods on the MDKP instances. Each plot compares [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: FIG. 4: Performance analysis of various optimization methods on the MIS instances. Each plot compares simulator [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]
Figure 5
Figure 5. Figure 5: FIG. 5 [PITH_FULL_IMAGE:figures/full_fig_p013_5.png]
Figure 6
Figure 6. Figure 6: FIG. 6 [PITH_FULL_IMAGE:figures/full_fig_p013_6.png]
Figure 7
Figure 7. Figure 7: FIG. 7: Integration of Lagrangian Relaxation with [PITH_FULL_IMAGE:figures/full_fig_p017_7.png]

Discussion (0). Sign in to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Hardware-Aware QUBO Reformulation of Constrained Binary Optimization via the Walsh-Fourier Transform

    quant-ph 2026-07 conditional novelty 6.0 of 10

    A Walsh-Fourier least-squares projection of constraint penalties onto hardware-supported quadratic terms gives chain-free QUBO encodings that, on tested MDKP benchmarks, often beat full-pairwise projections and unbala...

  2. Resource-Efficient Quantum Optimization via Higher-Order Encoding

    quant-ph 2025-11 conditional novelty 5.0 of 10

    HUBO encodings reduce qubit counts from n*m to n*ceil(log2 m) and cut CNOT counts by 89.6-100% in QAOA benchmarks on gate assignment, max k-colorable subgraph, and integer programming instances.

Reference graph

Works this paper leans on

76 extracted references · 75 canonical work pages · cited by 2 Pith papers

  1. [33]

    Financial optimization

    Stavros A Zenios. Financial optimization. Cambridge university press, 1993

    work page 1993

  2. [1]

    Slack-Based Approaches:Introducing auxiliary variables to transform inequalities into equalities

    work page

  3. [2]

    Penalty-Based Methods: Employing quadratic penalties or asymmetric penalty functions to penal- ize constraint violations without additional slack variables

    work page

  4. [3]

    This section systematically reviews these approaches, comparingtheirtheoreticalunderpinnings, empiricalper- formance, and computational trade-offs

    Lagrangian Relaxation: Reformulating con- straints via dual variables and solving the relaxed problem iteratively. This section systematically reviews these approaches, comparingtheirtheoreticalunderpinnings, empiricalper- formance, and computational trade-offs. A. Slack-Based Approaches to Constraint Handling A standard technique for encoding inequality ...

    work page

  5. [4]

    Acceptthestepifthefunctionimprovessufficiently; otherwise, take a null step. Cutting Plane Method The Cutting Plane Method [44] iteratively refines a piecewise-linear approximation of the dual function by adding linear constraints (cuts) based on subgradients, systematically narrowing down the feasible region. Algorithm Steps:

    work page

  6. [5]

    It asks for the shortest possible route that visits each city exactly once and returns to the ori- gin city

    Travelling Salesman Problem (TSP) The Travelling Salesman Problem (TSP) is a founda- tional problem in combinatorial optimization and oper- 5 ations research. It asks for the shortest possible route that visits each city exactly once and returns to the ori- gin city. The TSP arises in logistics, circuit design, and computational biology, and is known to b...

    work page

  7. [6]

    It arises in diverse domains such as resource allocation, portfolio optimization, and logistics

    Multi-Dimensional Knapsack Problem (MDKP) The Multi-Dimensional Knapsack Problem (MDKP) is a generalization of the classical knapsack problem where multiple resource constraints must be satisfied simulta- neously. It arises in diverse domains such as resource allocation, portfolio optimization, and logistics. Let there ben items andm resource constraints....

    work page

  8. [7]

    The Lagrangian relaxation leads to a problem that is separable across items and easier to optimize

    The Lagrangian becomes: L(x, λ) = nX i=1 pixi − mX j=1 λj nX i=1 wjixi − cj ! (19) Rewriting: L(x, λ) = nX i=1  pi − mX j=1 λjwji   xi + mX j=1 λjcj (20) The dual variablesλj adjust the effective profit of each item based on its resource usage, guiding the optimiza- tion towards feasibility. The Lagrangian relaxation leads to a problem that is separab...

    work page

Show all 76 references
  1. [8]

    This problem is central to combinatorics 6 and finds applications in scheduling, wireless communi- cation, and register allocation

    Maximum Independent Set (MIS) The Maximum Independent Set (MIS) problem seeks the largest subset of vertices in a graph such that no two are adjacent. This problem is central to combinatorics 6 and finds applications in scheduling, wireless communi- cation, and register alloca...

  2. [9]

    Unlike traditional methods that solve the entire constrained problem on a quantum device, our approach decouples the dual and primal updates

    Integration of Lagrangian Relaxation with Quantum Solvers In our framework, we employ Lagrangian relaxation to embed the constraints directly into the objective func- tion through Lagrange multipliers,λ. Unlike traditional methods that solve the entire constrained problem on a...

  3. [10]

    These methods are crucial for ensuring convergence while balancing compu- tational efficiency

    Lagrangian Dual Optimization: Update Methods To efficiently solve the dual problem in Lagrangian re- laxation, various update methods are employed to op- timize the Lagrange multipliers λ. These methods are crucial for ensuring convergence while balancing compu- tational effic...

  4. [11]

    Solve the Lagrangian subproblem to compute the function value gk and subgradient sk at λk

  5. [12]

    Store the triplet(λk, gk, sk) in a bundle

  6. [13]

    Solve a Quadratic Program (QP): min λ ˆg(λ) + 1 2 ∥λ − λk∥2 (39) where ˆg(λ) is a piecewise linear model of the dual function

  7. [14]

    Shortcuts to adiabaticity by counter- diabatic driving.Physical review letters, 111(10):100502,

    Adolfo Del Campo. Shortcuts to adiabaticity by counter- diabatic driving.Physical review letters, 111(10):100502,

  8. [15]

    Solve the Lagrangian subproblem to evaluate the function value gk and subgradient sk

  9. [16]

    Introduce a new linear constraint (cut): g(λ) ≥ gk + s⊤ k (λ − λk). (40)

  10. [17]

    Solve a Linear Program (LP) to determineλk+1

  11. [18]

    Repeat until convergence criteria are met. Augmented Lagrangian Method The Augmented Lagrangian Method [45, 46] enhances the standard Lagrangian by adding a quadratic penalty term to improve constraint handling and convergence. Augmented Lagrangian Function: LA(x, λ, µ) = f (x...

  12. [19]

    Primal Update: Minimize the augmented La- grangian with respect to the primal variablesx: xk+1 = arg min x LA(x, λk, µk). (42)

  13. [20]

    Dual Update: Adjust the Lagrange multipliers based on constraint violations: λk+1 j = λk j + µk bj − nX i=1 wjixk+1 i ! . (43) 8

  14. [21]

    Table II provides a comprehensive comparison of dif- ferent update strategies employed in Lagrangian dual op- timization

    Penalty Parameter Update: Optionally, update µ to balance contributions from multipliers and penalties. Table II provides a comprehensive comparison of dif- ferent update strategies employed in Lagrangian dual op- timization. Each method is evaluated based on its up- date rule...

  15. [22]

    This increase is due to the explicit introduction of auxiliary variables that handles 14 inequality constraints

    Qubit Efficiency and Resource Constraints As observed in Tables III–VII, the slack-based (S) for- mulations consistently require more qubits than their slack-free (NS) counterparts. This increase is due to the explicit introduction of auxiliary variables that handles 14 inequa...

  16. [23]

    Direct QUBO- based formulations, especially the slack-based QUBO, of- ten yield the highest optimization gaps

    Optimization Method Comparison Across all three problem classes, MDKP, MIS, and TSP-we observe consistent trends regarding the effective- ness of various optimization strategies. Direct QUBO- based formulations, especially the slack-based QUBO, of- ten yield the highest optimi...

  17. [24]

    The Subgradient method stands out as a robust approach across all problems, achieving low optimization gaps in TSP, strong convergence in MDKP, and high RSQ in MIS

    Unified Observations Across Problem Types WhencomparingperformanceacrossMDKP,MIS,and TSP, slack-free methods (NS) consistently demonstrate superiorqubitefficiencyandcompetitivesolutionquality. The Subgradient method stands out as a robust approach across all problems, achievin...

  18. [25]

    Even moderate-size MDKP instances push hardware con- straints, particularly under slack-based formulations

    Scalability on Near-Term Devices The qubit limit annotations in Table VI illustrate the scalability challenges of NISQ-era devices. Even moderate-size MDKP instances push hardware con- straints, particularly under slack-based formulations. The NS approach, by minimizing qubit ...

  19. [26]

    quantum optimization strategies that scale toward real-world deployment. The remainder of this paper is structured as follows: Section Ireviews related work on constraint handling in quantum optimization.Section IIdetails the methodol- ogy for formulating MDKP using Lagrangian...

  20. [27]

    Slack-free encodings help mit- igate these issues, enabling shallower circuits and im- proved optimization dynamics

    Trainability and Hybrid Optimization Quantum solvers like VQE rely on parameterized cir- cuits, whosetrainabilityisadverselyaffectedbyincreased qubit count and depth. Slack-free encodings help mit- igate these issues, enabling shallower circuits and im- proved optimization dyn...

  21. [28]

    However, realizing this potential requires careful atten- tion to encoding strategies, qubit efficiency, and hybrid scheme design

    Industry-Relevant Applications Our findings suggest that domains such as logistics, re- source allocation, and portfolio optimization, which can be modeled via knapsack or independent set structures, can benefit from quantum optimization in the near term. However, realizing th...

  22. [29]

    Springer Science & Business Media, 1998

    Dingzhu Du and Panos M Pardalos.Handbook of com- binatorial optimization, volume 4. Springer Science & Business Media, 1998. 1

    1998

  23. [30]

    A review of simheuristics: Extending metaheuristics to deal with stochastic com- binatorial optimization problems

    Angel A Juan, Javier Faulin, Scott E Grasman, Markus Rabe, and Gonçalo Figueira. A review of simheuristics: Extending metaheuristics to deal with stochastic com- binatorial optimization problems. Operations Research 16 Perspectives, 2:62–72, 2015

    2015

  24. [31]

    Ma- chine learning for combinatorial optimization: a method- ological tour d’horizon.European Journal of Operational Research, 290(2):405–421, 2021

    Yoshua Bengio, Andrea Lodi, and AntoineProuvost. Ma- chine learning for combinatorial optimization: a method- ological tour d’horizon.European Journal of Operational Research, 290(2):405–421, 2021

    2021

  25. [32]

    A robust optimization model for stochastic logistic problems

    Chian-Son Yu and Han-Lin Li. A robust optimization model for stochastic logistic problems. International journal of production economics, 64(1-3):385–397, 2000

    2000

  26. [34]

    Springer Science & Business Media, 2008

    Mauricio GC Resende and Panos M Pardalos.Handbook of optimization in telecommunications. Springer Science & Business Media, 2008. 1

    2008

  27. [35]

    From the quantum approximate optimization algorithm to a quantum alternating operator ansatz

    Stuart Hadfield, Zhihui Wang, Bryan O’gorman, Eleanor G Rieffel, Davide Venturelli, and Rupak Biswas. From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. Algorithms, 12(2):34, 2019. 1, 3

    2019

  28. [36]

    Egger, Jakub Mareček, and Stefan Woerner

    Daniel J. Egger, Jakub Mareček, and Stefan Woerner. Warm-starting quantum optimization.Quantum, 5:479, June 2021

    2021

  29. [37]

    Multi-angle quan- tum approximate optimization algorithm.Scientific Re- ports, 12(1):6781, 2022

    Rebekah Herrman, Phillip C Lotshaw, James Ostrowski, Travis S Humble, and George Siopsis. Multi-angle quan- tum approximate optimization algorithm.Scientific Re- ports, 12(1):6781, 2022

    2022

  30. [38]

    Nakanishi, Kosuke Mitarai, and Keisuke Fujii

    Ken M. Nakanishi, Kosuke Mitarai, and Keisuke Fujii. Subspace-search variational quantum eigensolver for ex- cited states. Physical Review Research, 1(3), October 2019

    2019

  31. [39]

    Variational quantum computation of excited states

    Oscar Higgott, Daochen Wang, and Stephen Brier- ley. Variational quantum computation of excited states. Quantum, 3:156, July 2019

    2019

  32. [40]

    Barkoutsos, Giacomo Nannicini, Anton Robert, Ivano Tavernelli, and Stefan Woerner

    Panagiotis Kl. Barkoutsos, Giacomo Nannicini, Anton Robert, Ivano Tavernelli, and Stefan Woerner. Improving variational quantum optimization using cvar.Quantum, 4:256, April 2020

    2020

  33. [41]

    Prospects for quantum en- hancement with diabatic quantum annealing.Nature Re- views Physics, 3(7):466–489, 2021

    EJ Crosson and DA Lidar. Prospects for quantum en- hancement with diabatic quantum annealing.Nature Re- views Physics, 3(7):466–489, 2021

    2021

  34. [42]

    Mathematical foundation of quantum annealing.Journal of Mathemat- ical Physics, 49(12), 2008

    Satoshi Morita and Hidetoshi Nishimori. Mathematical foundation of quantum annealing.Journal of Mathemat- ical Physics, 49(12), 2008. 1

    2008

  35. [43]

    Love, Alán Aspuru- Guzik, and Jeremy L

    Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man- Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru- Guzik, and Jeremy L. O’Brien. A variational eigenvalue solver on a photonic quantum processor. Nature Com- munications, 5:4213, 2014. 1

    2014

  36. [44]

    Multidimensional Knapsack Problems, pages 235–283

    Hans Kellerer, Ulrich Pferschy, and David Pisinger. Multidimensional Knapsack Problems, pages 235–283. Springer Berlin Heidelberg, Berlin, Heidelberg, 2004. 1

    2004

  37. [45]

    On the hamiltonian game (a traveling salesman problem)

    Julia Robinson. On the hamiltonian game (a traveling salesman problem). Technical report, 1949. 1

    1949

  38. [46]

    The traveling salesman problem: a computational study, volume 17

    David L Applegate. The traveling salesman problem: a computational study, volume 17. Princeton university press, 2006. 1

    2006

  39. [47]

    Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85–103. Plenum Press, 1972. 1

    1972

  40. [48]

    Ising formulations of many np problems

    Andrew Lucas. Ising formulations of many np problems. Frontiers in Physics, 2, 2014. 1

    2014

  41. [49]

    Quantum computing in the nisq era and beyond

    John Preskill. Quantum computing in the nisq era and beyond. Quantum, 2:79, 2018. 1

    2018

  42. [50]

    A comparative study of quantum optimization techniques for solving combinatorial optimization benchmark problems.arXiv preprint arXiv:2503.12121, 2025

    Monit Sharma and Hoong Chuin Lau. A comparative study of quantum optimization techniques for solving combinatorial optimization benchmark problems.arXiv preprint arXiv:2503.12121, 2025. 1

    2025 arXiv

  43. [51]

    The lagrangian relaxation method for solving integer programming problems.Management science, 27(1):1–18, 1981

    Marshall L Fisher. The lagrangian relaxation method for solving integer programming problems.Management science, 27(1):1–18, 1981. 1, 3

    1981

  44. [52]

    The traveling- salesman problem and minimum spanning trees.Opera- tions research, 18(6):1138–1162, 1970

    Michael Held and Richard M Karp. The traveling- salesman problem and minimum spanning trees.Opera- tions research, 18(6):1138–1162, 1970. 1, 5

    1970

  45. [53]

    Adaptive graph shrinking for quantum optimization of constrained com- binatorial problems

    Monit Sharma and Hoong Chuin Lau. Adaptive graph shrinking for quantum optimization of constrained com- binatorial problems. arXiv preprint arXiv:2506.14250,

    arXiv

  46. [54]

    A subgradient ap- proach for constrained binary optimization via quantum adiabatic evolution, 2017

    Sahar Karimi and Pooya Ronagh. A subgradient ap- proach for constrained binary optimization via quantum adiabatic evolution, 2017. 2, 3

    2017

  47. [55]

    J. A. Montañez-Barrera, Pim van den Heuvel, Dennis Willsch, and Kristel Michielsen. Improving performance in combinatorial optimization problems with inequality constraints: An evaluation of the unbalanced penaliza- tion method on d-wave advantage. In2023 IEEE Inter- national ...

    2023

  48. [56]

    Unbalanced penaliza- tion: a new approach to encode inequality constraints of combinatorial problems for quantum optimization algo- rithms

    J A Montañez-Barrera, Dennis Willsch, A Maldonado- Romo, and Kristel Michielsen. Unbalanced penaliza- tion: a new approach to encode inequality constraints of combinatorial problems for quantum optimization algo- rithms. Quantum Science and Technology, 9(2):025022, April 2024. 3

    2024

  49. [57]

    Implementing slack- free custom penalty function for qubo on gate-based quantum computers

    Xin Wei Lee and Hoong Chuin Lau. Implementing slack- free custom penalty function for qubo on gate-based quantum computers. In 2025 IEEE International Con- ference on Quantum Computing and Engineering (QCE). IEEE, 2025. 2

    2025

  50. [58]

    Solving constrained quadratic binary problems via quan- tum adiabatic evolution, 2018

    Pooya Ronagh, Brad Woods, and Ehsan Iranmanesh. Solving constrained quadratic binary problems via quan- tum adiabatic evolution, 2018. 3

    2018

  51. [59]

    Subgradient method using quantum annealing for inequality-constrained binary optimization problems

    Taisei Takabayashi, Takeru Goto, and Masayuki Ohzeki. Subgradient method using quantum annealing for inequality-constrained binary optimization problems. arXiv preprint arXiv:2411.06901, 2024. 3

    2024 arXiv

  52. [60]

    Variational quantum eigensolver with constraints (vqec): Solving constrained optimization problems via vqe, 2024

    Thinh Viet Le and Vassilis Kekatos. Variational quantum eigensolver with constraints (vqec): Solving constrained optimization problems via vqe, 2024. 3

    2024

  53. [61]

    Knapsack problems

    David Pisinger and Paolo Toth. Knapsack problems. Handbook of Combinatorial Optimization: Volume1–3, pages 299–428, 1998. 3, 4

    1998

  54. [62]

    Anewalgorithmforthe 0-1 knapsack problem.Management Science, 34(5):633– 644, 1988

    SilvanoMartelloandPaoloToth. Anewalgorithmforthe 0-1 knapsack problem.Management Science, 34(5):633– 644, 1988

    1988

  55. [63]

    Core problems in knapsack algorithms

    David Pisinger. Core problems in knapsack algorithms. Operations Research, 47(4):570–575, 1999. 3, 4

    1999

  56. [64]

    Learning la- grangian multipliers for the travelling salesman problem

    Augustin Parjadis, Quentin Cappart, Bistra Dilkina, Aaron Ferber, and Louis-Martin Rousseau. Learning la- grangian multipliers for the travelling salesman problem. arXiv preprint arXiv:2312.14836, 2023. 3

    2023 arXiv

  57. [65]

    Problem complexity and method efficiency in op- timization

    Arkadij Semenovič Nemirovskij and David Borisovich Yudin. Problem complexity and method efficiency in op- timization. 1983. 7 17

    1983

  58. [66]

    Minimization methods for non- differentiable functions, volume 3

    Naum Zuselevich Shor. Minimization methods for non- differentiable functions, volume 3. Springer Science & Business Media, 2012

    2012

  59. [67]

    Dual averaging method for regularized stochas- tic learning and online optimization.Advances in Neural Information Processing Systems, 22, 2009

    Lin Xiao. Dual averaging method for regularized stochas- tic learning and online optimization.Advances in Neural Information Processing Systems, 22, 2009. 7

    2009

  60. [68]

    A stochastic ap- proximation method.The annals of mathematical statis- tics, pages 400–407, 1951

    Herbert Robbins and Sutton Monro. A stochastic ap- proximation method.The annals of mathematical statis- tics, pages 400–407, 1951. 7

    1951

  61. [69]

    Robust stochastic approximation ap- proach to stochastic programming.SIAM Journal on op- timization, 19(4):1574–1609, 2009

    Arkadi Nemirovski, AnatoliJuditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation ap- proach to stochastic programming.SIAM Journal on op- timization, 19(4):1574–1609, 2009. 7

    2009

  62. [70]

    Approximations in proximal bundle methods and decomposition of convex programs.Journal of Optimization Theory and applications, 84(3):529–548,

    Krzysztof C Kiwiel. Approximations in proximal bundle methods and decomposition of convex programs.Journal of Optimization Theory and applications, 84(3):529–548,

  63. [71]

    The cutting-plane method for solving convex programs

    James E Kelley, Jr. The cutting-plane method for solving convex programs. Journal of the society for Industrial and Applied Mathematics, 8(4):703–712, 1960. 7

    1960

  64. [72]

    Multiplier and gradient meth- ods

    Magnus R Hestenes. Multiplier and gradient meth- ods. Journal of optimization theory and applications, 4(5):303–320, 1969. 7

    1969

  65. [73]

    A method for nonlinear constraints in minimization problems.Optimization, pages 283–298,

    Michael JD Powell. A method for nonlinear constraints in minimization problems.Optimization, pages 283–298,

  66. [74]

    Wood, Jake Lishman, Julien Gacon, Si- mon Martiel, Paul D

    Ali Javadi-Abhari, Matthew Treinish, Kevin Krsulich, Christopher J. Wood, Jake Lishman, Julien Gacon, Si- mon Martiel, Paul D. Nation, Lev S. Bishop, Andrew W. Cross, Blake R. Johnson, and Jay M. Gambetta. Quan- tum computing with Qiskit, 2024. 8

    2024

  67. [75]

    Benchmark instances for the multidimen- sional knapsack problem, 01 2015

    John Drake. Benchmark instances for the multidimen- sional knapsack problem, 01 2015. 8

    2015

  68. [76]

    N. J. A. Sloane. Challenge problems: Independent sets in graphs, 2000. Accessed: January 14, 2025. 8 Appendix A: Algorithms FIG. 7: Integration of Lagrangian Relaxation with Quantum Optimization Require: MKP instance data, initial Lagrange multipliers λ(0), maximum iterationsK...

    2000

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.