{"id":"396a6edf-cfce-434a-ab0e-6fc292ff93b9","arxiv_id":"2507.12159","paper_version":3,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":5,"one_line_summary":"Using Lagrangian multiplier updates instead of slack variables reduces qubit counts and sometimes improves solution quality on small quantum optimization benchmarks.","lead":"The paper tests classical Lagrangian-based methods that replace slack variables with iteratively updated multipliers to cut qubit counts in quantum optimization. The authors benchmark five such techniques on TSP, knapsack, and independent-set problems using simulators and a Rigetti quantum processor.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 7 reduces the MDKP final objective to a linear binary problem, making the reported VQE results classically trivial; the claimed performance of slack-free methods over slack QUBO is not established as a quantum result.","rationale":"The central assertion of the paper is that slack-free Lagrangian formulations reduce qubit counts without compromising performance in quantum optimization. The qubit-count reduction is straightforward and supported by the reported resource numbers, so that part is not under attack. The load-bearing condition for the rest of the claim is that the final Lagrangian-relaxed objective, after classical multiplier updates, is a genuine QUBO whose solution is being sought by a quantum solver and whose quality reflects the original constrained problem. The manuscript's own Algorithm 7 contradicts this condition for MDKP: the final objective is linear in the binary variables, so a VQE run on it is solving a classically trivial problem, and any reported optimality gap is essentially the output of the classical subgradient/dual procedure, not of quantum optimization. If the experiments actually used additional quadratic penalties or a different encoding, those details are missing, making the tables uninterpretable and unreproducible. The same structural issue applies to TSP, where the Held-Karp relaxation is described in terms of 1-trees, but the actual QUBO encoding of the 1-tree constraint is never given. This is an internal inconsistency rather than a mere disagreement with the field's consensus: the paper's own algorithm makes the central empirical comparison invalid as evidence for quantum advantage or even for quantum utility. A concrete check—inspecting the recorded final Hamiltonian—would settle the question: if quadratic terms are absent, the main performance claims must be revised; if present, the authors should provide them so the results can be evaluated. As written, the central claim is not adequately supported.","tokens_in":17192,"tokens_out":3382,"duration_ms":42743,"concrete_test":"Obtain the exact QUBO/Ising matrix used in the VQE runs for Tables III–VI (e.g., from the authors' code or by instrumenting the pipeline to log the final Hamiltonian after the classical multiplier loop). Check whether any off-diagonal quadratic coefficient is nonzero. For MDKP, if all quadratic coefficients are zero, the VQE stage solves a linear thresholding problem, and the reported gaps measure a classical subroutine rather than quantum optimization, invalidating the comparison against the slack QUBO baseline.","verdict_should_be":"REJECT","load_bearing_attack":"The load-bearing empirical claim is that Lagrangian-based slack-free methods achieve competitive or better optimality gaps than slack-based QUBO on quantum hardware. The manuscript's own Algorithm 7 (Appendix A, step 12) defines the final MDKP objective as min_x [ -sum_i (p_i - sum_j lambda*_j w_ji) x_i + sum_j lambda*_j b_j ], an affine function of the binary variables with no quadratic term. Minimizing a linear binary function is classically trivial: set x_i = 1 iff the coefficient is positive. If the reported VQE runs used this objective, the 'quantum' step reduces to thresholding, so the optimality gaps in Tables V and VI are classical results of the multiplier optimization, not evidence about quantum solvers. If the runs instead added quadratic penalty or regularization terms (e.g., from the augmented Lagrangian), those terms are absent from the manuscript and the reported qubit counts, circuit depths, and gaps cannot be independently reproduced or interpreted. The same concern threatens the TSP results unless the Held-Karp relaxation is encoded with explicit 1-tree or subtour-elimination constraints in the QUBO, which the paper does not provide. Thus the central performance claim rests on an unverified and internally contradicted encoding.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":17410,"tokens_out":5652,"duration_ms":64433,"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":[{"comment":"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.","section":"Appendix A, Algorithm 7, step 12"},{"comment":"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.","section":"Section III.A.1"},{"comment":"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.","section":"Section IV.C and abstract"}],"minor_comments":[{"comment":"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.","section":"Section III.A.2 and Appendix A"},{"comment":"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.","section":"Section II.A, Eq. (3)"},{"comment":"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.","section":"Figures 1-6"},{"comment":"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.","section":"Section IV"}],"recommendation":"reject","confidential_remarks":"The central issue is that the appendix explicitly defines the MDKP final objective as linear, which makes the quantum step classically trivial. If the authors actually used a quadratic QUBO in the experiments, the missing specification is a serious reporting gap; if they used the linear form, the quantum claims are vacuous. Either way, the current manuscript does not support its main conclusion, and the problem is at the scope level rather than a local fix. The paper could potentially be rewritten with full encoding details and new experiments, but as submitted it is not acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing you should know: the qubit savings in this paper are real and easy to verify, but the main performance claim is not. The manuscript's own Algorithm 7 reduces the MDKP final objective to a linear binary function, which makes the reported VQE step classically trivial, and the TSP and MIS encodings are under-specified.\n\nWhat the paper does well: it benchmarks standard instances (SAC-94, Sloane graphs) on both simulator and a real Rigetti QPU, and it compares several Lagrangian multiplier-update schemes—subgradient, bundle, cutting plane, dual averaging, augmented Lagrangian—side by side. The resource-count tables clearly show that slack-free formulations use far fewer qubits. The authors also do not overclaim quantum advantage; they explicitly say classical solvers are faster.\n\nThe soft spot is load-bearing, not cosmetic. Algorithm 7, step 12, defines the final MDKP objective as min_x [ -sum_i (p_i - sum_j lambda*_j w_ji) x_i + sum_j lambda*_j b_j ]. That is an affine function of the binary variables. The optimum is obtained by thresholding each x_i independently. So unless the experiments secretly added quadratic penalties or regularization, the MDKP gaps in Tables V and VI are classical results of the multiplier search, not evidence about the quantum solver. The appendix offers no alternative QUBO, and the main text does not supply the Hamiltonian used on hardware. The same problem menaces the TSP results: the Held-Karp 1-tree relaxation is described in words, but the actual QUBO, the subtour handling, and the mapping to qubits are never written down. MIS has more detail, but still no ansatz, no hyperparameters, and no error bars.\n\nThe novelty is also modest. Lagrangian relaxation with subgradient updates already appears in the quantum annealing papers cited as [27,31], and [33] integrates Lagrangian ideas into VQE. The contribution here is mostly an engineering benchmark of dual-update heuristics, not a new method.\n\nAll that said, the reader's rejection is fair in substance but perhaps harsh in framing. The qubit-count story is a useful data point for people designing NISQ pipelines. I would send this to peer review rather than desk reject, because a serious referee could force the authors to provide exact QUBO matrices, circuit details, and code—or to reposition the MDKP results as a classical Lagrangian study. As written, I would not cite or trust the optimality-gap numbers.","headline":"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.","tokens_in":17996,"tokens_out":4577,"would_cite":false,"duration_ms":54273,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","90C10","81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"Slack-free Lagrangian encodings can match QUBO solution quality with far fewer qubits.","keywords":["quantum optimization","QUBO","Lagrangian relaxation","slack variables","combinatorial optimization","travelling salesman problem","multidimensional knapsack problem","maximum independent set"],"falsifier":"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.","tokens_in":16928,"feed_emoji":"⚛️","tokens_out":12370,"duration_ms":121735,"temperature":0.7,"pith_summary":"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.","feed_headline":"Slack-free encodings cut qubit counts without loss of quality","feed_subtitle":"MDKP pb5 falls from 116 to 20 qubits; MIS still gains from tuned multipliers.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the slack-variable Ising/QUBO encoding that serves as the baseline for qubit-count and optimality-gap comparisons.","marker":"[21]"},{"why":"Supplies the classical Lagrangian relaxation machinery that the paper ports into the quantum setting.","marker":"[24]"},{"why":"Defines the Held-Karp 1-tree relaxation used to make the TSP formulation slack-free.","marker":"[25]"},{"why":"Provides the subgradient multiplier-update rule used to push relaxed solutions toward feasibility.","marker":"[27]"},{"why":"Shows how to embed Lagrangian relaxation inside a VQE loop, the pattern adapted for the final QUBO solve.","marker":"[33]"},{"why":"Supplies the standard MDKP benchmark instances used in the experiments.","marker":"[48]"},{"why":"Supplies the error-correcting-code graphs used as MIS benchmark instances.","marker":"[49]"}],"fun_headline_variants":["Slack-free method drops MDKP qubits from 116 to 20","Lagrangian tricks cut slack, save qubits in quantum optimization","Quantum optimization gets lean: no slack, same quality","Held-Karp style dualization reduces qubit count for TSP and MDKP","Slack-free reformulations shrink quantum circuits, keep answers"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Slack-free method drops MDKP qubits from 116 to 20","Lagrangian tricks cut slack, save qubits in quantum optimization","Quantum optimization gets lean: no slack, same quality","Held-Karp style dualization reduces qubit count for TSP and MDKP","Slack-free reformulations shrink quantum circuits, keep answers"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00028,"raw_usage":{"total_tokens":1666,"prompt_tokens":958,"completion_tokens":708,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":574,"completion_tokens_details":{"reasoning_tokens":617}},"tokens_in":574,"tokens_out":708,"duration_ms":7605,"temperature":1.0,"reasoning_tokens":617,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T16:52:42.382037+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Table II provides a comprehensive comparison of dif- ferent update strategies employed in Lagrangian dual op- timization","cited_arxiv_id":null,"evidence_quote":"Defines the slack-variable Ising/QUBO encoding that serves as the baseline for qubit-count and optimality-gap comparisons."},{"cited_title":"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","cited_arxiv_id":null,"evidence_quote":"Supplies the classical Lagrangian relaxation machinery that the paper ports into the quantum setting."},{"cited_title":"Even moderate-size MDKP instances push hardware con- straints, particularly under slack-based formulations","cited_arxiv_id":null,"evidence_quote":"Defines the Held-Karp 1-tree relaxation used to make the TSP formulation slack-free."},{"cited_title":"Slack-free encodings help mit- igate these issues, enabling shallower circuits and im- proved optimization dynamics","cited_arxiv_id":null,"evidence_quote":"Provides the subgradient multiplier-update rule used to push relaxed solutions toward feasibility."},{"cited_title":"Financial optimization","cited_arxiv_id":null,"evidence_quote":"Shows how to embed Lagrangian relaxation inside a VQE loop, the pattern adapted for the final QUBO solve."},{"cited_title":"Ising formulations of many np problems","cited_arxiv_id":null,"evidence_quote":"Supplies the standard MDKP benchmark instances used in the experiments."},{"cited_title":"Quantum computing in the nisq era and beyond","cited_arxiv_id":null,"evidence_quote":"Supplies the error-correcting-code graphs used as MIS benchmark instances."}],"review_version":1}