{"id":"0ddadb2a-31a6-4892-8891-24a7222db951","arxiv_id":"2506.14250","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"Adaptive graph shrinking with constraint-aware merging and a spectral stopping rule reduces QUBO size for MDKP, MIS, and QAP, improving simulated VQE solution quality on the shrunken instances.","lead":"A classical preprocessing step shrinks large optimization problems before a quantum solver runs, merging variables that look correlated and avoiding merges that would break constraints. Tests on knapsack, independent set, and assignment benchmarks show that solving the reduced problems with simulated quantum circuits gives better or comparable solutions than solving them directly.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The paper's own Appendix B data contradict the Section VIII.D claim that adaptive shrinking preserves solution quality: for MDKP hp2 and pb5, direct VQE on the full QUBO beats VQE on the adaptively shrunk instance (12.34% vs 16.61%, 4.25% vs 12.53%), with only modest size reductions.","rationale":"The Reader's verdict is CONDITIONAL, and I retain that verdict, but for a more concrete reason than the SDP-dominance assumption identified by the Reader. The load-bearing point is empirical: the method's advertised benefit—quality preservation under shrinkage—is falsifiable from the paper's own tables. Two of twelve MDKP instances show direct VQE on the full problem outperforming the adaptive-shrinking pipeline, even though the size reduction is small. If those numbers are reproducible, the broad claim in the abstract and Section VIII.D is overclaimed; if they are not reproducible, the paper lacks the code and experimental detail needed to resolve the discrepancy. Either way, the current manuscript should be accepted only with revisions that report per-instance paired results, error bars, and explicit repair-complexity metrics. I do not call for rejection because the method is plausible and most instances do show improvement; the issue is the scope of the empirical claim, not an obvious flaw in the algorithmic idea. This differs from the Reader's weakest assumption (Eq. 25/spectral stopping), though both point to the same central risk: the shrinking heuristic may not preserve the optimization landscape it is supposed to.","tokens_in":44201,"tokens_out":10124,"duration_ms":104935,"concrete_test":"Re-run the paired comparison from Appendix B Tables I and II with identical VQE settings (optimizer, shots, ansatz depth) on (a) the full QUBO and (b) each shrunken QUBO, including the constraint-aware variant, and compute per-instance optimality-gap differences. Specifically verify hp2 (67→57: direct 12.34% vs shrunk 16.61%) and pb5 (116→95: direct 4.25% vs shrunk 12.53%). If these differences persist with fixed seeds and error bars, the 'preserves solution quality' conclusion must be restricted to instances where it holds, and the 'otherwise intractable' claim should be removed for instances the direct solver already handled.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim of Section VIII.D—'Adaptive shrinking significantly reduces problem size while preserving solution quality'—is contradicted by the paper's own baseline data in Appendix B, Table I. For MDKP hp2, direct VQE on the full 67-variable QUBO achieves a 12.34% optimality gap, while VQE after adaptive shrinking (57 variables) achieves 16.61%. For pb5, direct VQE on the 116-variable QUBO achieves 4.25%, while the adaptively shrunk 95-variable instance achieves 12.53%; the constraint-aware variant in Table VIII gives the same 12.53%, so the discrepancy is not explained by the CA/non-CA distinction. The reductions are also modest (67→57 and 116→95, about 15–18%), and final sizes remain far above current hardware qubit limits, which weakens the 'otherwise intractable instances' claim. Separately, the abstract asserts reduced repair complexity, but no repair-complexity metric is reported anywhere; all tables only give binary feasibility, which the repair step guarantees by construction.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a hybrid classical–quantum pipeline for constrained combinatorial optimization in which a QUBO instance is mapped to a weighted Max-Cut graph, iteratively reduced by merging variables with strong SDP-derived correlations under a constraint-aware penalty, solved by VQE or CPLEX on the reduced instance, and reconstructed with a greedy repair step. The method is applied to three benchmark families (MDKP, MIS, QAP), with adaptive correlation recalculation and a spectral stopping criterion as secondary contributions. The central empirical claims are that the approach improves feasibility, reduces repair complexity, and enhances quantum solution quality on hardware-limited instances.","tokens_in":44509,"tokens_out":14585,"duration_ms":145072,"significance":"The constraint-aware merging idea is reasonable, and the ablation structure (fixed-ratio versus adaptive shrinking; constraint-aware versus non-constraint-aware QUBO formulations) is a genuine strength. The paper also provides the full shrinking algorithm as pseudocode (Algorithm 1) and per-instance circuit resource counts (Appendix D), which aid reproducibility. On the reported evidence, the constraint-aware variant improves VQE quality on a majority of instances (e.g., MDKP hp1 gap from 15.77% to 5.76%, pet3 from 17.06% to 2.49%; MIS 1tc.64 RSQ from 90% to 95%), and adaptive shrinking beats direct full-QUBO VQE on most MDKP and MIS instances. However, the headline claims exceed the evidence: two MDKP instances contradict the quality-preservation claim, no repair-complexity metric is reported anywhere, the VQE runs are single-shot with no error bars, and the final reduced sizes (37–128 variables) remain far above near-term hardware capacity while all results come from a noiseless simulator. The significance of the contribution as stated is therefore not yet established, although the underlying method is defensible and improvable.","major_comments":[{"comment":"The headline claim that adaptive shrinking 'significantly reduces problem size while preserving solution quality' is not supported for two of the twelve MDKP instances. For hp2, direct VQE on the full 67-variable QUBO reaches a 12.34% gap while VQE on the adaptively shrunk 57-variable instance reaches 16.61%; for pb5 the figures are 4.25% on 116 variables versus 12.53% on 95 variables, and the constraint-aware variant in Table VIII also gives 12.53%. These size reductions (15–18%) are representative of the whole table, so final sizes remain 37–128 variables, which undercuts the 'otherwise intractable instances' and 'hardware-limited' framing. Moreover, Figures 3–5 compare only shrunken-instance solvers; the unshrunk VQE baseline essential to the preservation claim appears only in Appendix B. The preservation claim should be restated per instance or confined to the majority of instances where shrinking helps.","section":"VIII.D and Appendix B, Tables I–II"},{"comment":"The claims of 'reduces repair complexity' (abstract) and 'improves pre-repair feasibility rates' (Section VI.A.5) are asserted without any supporting measurement. All tables (Tables III–X) report only final feasibility, which is True by construction because the repair step is applied to every solution; no table reports the number of repaired variables, repair iterations, pre-repair violations, or the fraction of runs requiring repair. Either a repair-complexity metric must be reported, or these claims should be removed from the abstract and Section VI.A.5.","section":"Abstract and Section VI.A.5"},{"comment":"The experiments are not reproducible as reported. The penalty factor λ is discussed in the sensitivity analysis (Section VIII.C), but the specific λ, spectral threshold α, recalculation interval r, change-detection threshold δ, correlation threshold τ, and QUBO penalty weights P_j used for the main benchmark runs are never stated. The VQE results are single runs with no seeds, shots, or variance, so small differences such as MDKP pet5 (12.66% non-CA versus 14.11% CA) and QAP scr12 (1.51% versus 4.99%) cannot be distinguished from optimizer noise. The ansatz family, circuit depth schedule, and optimizer used for VQE are not specified in the main text. These omissions should be corrected before the comparative claims can be evaluated.","section":"Section VIII and Appendices C–D"},{"comment":"The condition min constraint edges |w_ij| >> max objective edges |w_ij| is the stated justification for why SDP-derived correlations encode feasibility structure, but the paper never verifies this condition for the MDKP, MIS, or QAP benchmarks, and it is not obvious that it holds for QAP, where the objective contributes quadratic terms F_ik D_jl that can be comparable in magnitude to the penalized constraint terms. Because the entire merging heuristic rests on this assumption, the paper should either verify the condition numerically for the benchmark instances or present an ablation showing that merge decisions are insensitive to it.","section":"Section IV.B, Eq. (25)"},{"comment":"The spectral stopping rule is underspecified. The paper orders eigenvalues as λ_1 ≤ ... ≤ λ_n and defines Energy_k = (Σ_{i≤k} λ_i)/(Σ_i λ_i) over the smallest eigenvalues, while simultaneously referring to the 'top k eigenmodes'; it is unclear whether the retained modes are the lowest- or highest-frequency ones, and the reported final sizes (e.g., 50 of 60 for hp1, 95 of 116 for pb5) are not reconciled with any stated α value. Without the α values used and a clarification of the ordering convention, Contribution 3 cannot be reproduced or checked.","section":"Section V.B.e"}],"minor_comments":[{"comment":"References [22] ('A. Author and B. Author') and [24] ('John Smith and Jane Doe') appear to be placeholder citations and should be replaced with real references or removed.","section":"References"},{"comment":"Table X omits the constraint-aware row for tai12b, so the QAP comparison between constraint-aware and non-constraint-aware shrinking is incomplete.","section":"Appendix C, Table X"},{"comment":"Typos include 'perofrmance' in Section VIII.D and 'targetted' in Section I; these should be corrected.","section":"Throughout"},{"comment":"The sensitivity analysis reports that λ ∈ [1.0, 2.0] is robust but does not give the value used for the main experiments; the chosen values for λ and α should be stated alongside the results.","section":"Section VIII.C"},{"comment":"Section VII.B mentions QAOA and CVaR-VQE as downstream solvers, but Section VIII reports only 'VQE'; the actual solver and objective function used in the experiments should be specified.","section":"Section VII.B"},{"comment":"The statement that constraint-aware shrinking improves solution quality 'across all benchmarks' is contradicted by QAP scr12 (1.51% non-CA versus 4.99% CA) and tai12a (9.99% versus 10.27%) and by MDKP pet5 (12.66% versus 14.11%); the wording should be softened to 'on most instances.'","section":"Section VIII.D"}],"recommendation":"major_revision","confidential_remarks":"The placeholder references and the absence of error bars and hyperparameter reporting suggest the manuscript is not yet at publication standard; I would ask for the experimental code, seeds, and full parameter configuration as part of the revision. The 'otherwise intractable instances' framing also stretches the evidence, since the final reduced sizes (37–128 variables) are themselves beyond near-term hardware and all results are from a noiseless simulator. The core idea is publishable after revision if the claims are scaled back and the missing metrics are added."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this paper packages a plausible heuristic pipeline—SDP-based graph shrinking with constraint-aware penalties, adaptive correlation updates, and a spectral stopping rule—for reducing QUBO size before quantum optimization, and tests it on MDKP, MIS, and QAP. The new pieces are the adaptive recalculation strategies, the spectral stopping criterion, and the problem-specific merge penalties. Those are real additions over the prior shrinking literature, and the ablation in Appendix B comparing fixed-ratio vs adaptive shrinking is the most useful part of the paper. Credit where it is earned: the authors explicitly say they are not the first to use graph contractions, and they discuss the risk of over-penalizing merges in Section VI.A.5. That is upfront.\n\nThe problem is the abstract and Section VIII.D claim that adaptive shrinking 'preserves solution quality' and 'reduces repair complexity.' The paper's own Table I in Appendix B shows the opposite for two MDKP instances: on hp2, direct VQE on the full 67-variable QUBO gives a 12.34% gap, while VQE on the adaptively shrunk 57-variable instance gives 16.61%; on pb5, direct VQE gives 4.25% vs 12.53% after shrinking. The reductions are only 15–18% on those instances, so calling them 'otherwise intractable' is shaky. And no repair-complexity metric appears anywhere; every table reports final feasibility, which the repair step guarantees by construction, so that claim is untestable from the paper as written.\n\nThere are also standard experimental holes: VQE results are single runs with no error bars or shot statistics; no code or data are released; the dominance condition in Eq. 25 is asserted but never checked for the benchmark instances; the spectral stopping criterion is a heuristic with only a passing sensitivity comment. These are not fatal, but they are necessary to fix.\n\nDespite all that, I would not desk-reject this. The method is sensible, the benchmark set is non-trivial, and the failures I listed are addressable with experiments and artifacts rather than conceptual dead ends. The right move is to send it to referees with a clear ask: add direct VQE/CPLEX comparisons on full instances, report error bars, define and report repair complexity (e.g., repair iterations or removed variables), and release code. If those arrive, the paper becomes a solid contribution for people building quantum preprocessing tools. For now, the central claim is over-stated but not hollow.","headline":"A sensible QUBO preprocessing heuristic whose headline claims about solution quality and repair complexity overreach its own Appendix B data; worth refereeing with required revisions.","tokens_in":44986,"tokens_out":2944,"would_cite":false,"duration_ms":29240,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that adaptive graph shrinking, guided by SDP correlations and constraint-aware merge penalties, makes constrained combinatorial optimization tractable for near-term quantum hardware by shrinking the QUBO before the…","keywords":["graph shrinking","QUBO","Max-Cut","SDP relaxation","constraint-aware merging","VQE","QAOA","constrained combinatorial optimization"],"falsifier":"Take a benchmark instance where constraint-derived and objective-derived edge weights are comparable in magnitude, violating the condition in Eq. 25, and compare the adaptive-shrinking reconstructed objective against the known optimum; if solution quality drops systematically on such instances, the merging signal depends on that dominance condition rather than on generic structure preservation.","tokens_in":44034,"feed_emoji":"⚛️","tokens_out":11625,"duration_ms":112523,"temperature":0.7,"pith_summary":"Quantum optimization algorithms such as QAOA and VQE are limited on current hardware by qubit counts, circuit depth, and noise, so constrained combinatorial problems often cannot be encoded directly. This paper proposes a hybrid classical–quantum pipeline that first maps a constrained QUBO (quadratic unconstrained binary optimization) instance into a weighted Max-Cut graph, uses an SDP relaxation to identify strongly correlated variables, and iteratively merges them while penalizing merges that would break feasibility. After a quantum solver runs on the shrunken graph, the solution is lifted back to the original variables and repaired by problem-specific greedy heuristics. The paper reports that on multidimensional knapsack, maximum independent set, and quadratic assignment benchmarks, the pipeline yields feasible solutions, cuts the qubit demand, and achieves better or competitive optimality gaps compared with direct quantum solving on hardware-limited instances.","feed_headline":"Graph shrinking tames constrained optimization for quantum hardware","feed_subtitle":"Reduced QUBOs keep MDKP, MIS, and QAP instances feasible on limited qubits, with repair restoring validity.","key_machinery":"The carrying object is the constraint-aware shrinking loop. A QUBO instance is first mapped to a weighted Max-Cut graph, and the Max-Cut SDP relaxation supplies a Gram matrix $X$ whose entries estimate spin correlations between variables. Supernodes (groups of original variables that shrink into one unit) are merged by maximizing the score $S(C_i,C_j)=E_{u\\in C_i,v\\in C_j}[X_{uv}] - \\lambda\\,\\Pi(C_i,C_j)$, where $\\Pi$ penalizes merges that would violate the problem's feasibility constraints, and $\\lambda$ balances structural exploration against constraint safety. An adaptive spectral criterion—cumulative retained Laplacian eigenvalue energy above a threshold $\\alpha$—sets how far the graph shrinks, and the recorded merge history is replayed in reverse to reconstruct the full solution after the quantum solve.","core_discovery":"The central claim is that graph shrinking can serve as a standalone preprocessing step for constrained QUBO problems, not just as a circuit-cutting or decomposition aid. The authors argue that once a QUBO is converted to an equivalent weighted Max-Cut graph, the SDP relaxation's correlation structure encodes feasibility information, especially when constraint-derived edge weights dominate objective-derived edge weights; merging the most correlated supernodes therefore preserves the landscape that matters. Solving the reduced QUBO with VQE, then reconstructing and repairing the solution, produces feasible answers on the tested MDKP, MIS, and QAP instances, including cases where direct quantum solvers fail on qubit or memory limits. The paper presents this as a scalable pathway for near-term quantum algorithms, with the explicit caveat that shrinking is heuristic and carries no optimality guarantee.","pith_inferences":["Because the pipeline only needs a QUBO formulation and a constraint-violation oracle, the same shrinking-plus-repair recipe should apply to other constrained combinatorial problems, such as vehicle routing or graph coloring, provided the dominance condition of Eq. 25 is checked on each new family.","A direct way to test the paper's explanation is to measure how often the constraint-dominance condition actually holds on the benchmark instances; if shrinking still works when it fails, the repair phase rather than the SDP guidance may be doing the heavy lifting.","The spectral stopping rule is heuristic; a sharper version would try to bound the reconstructed objective's error in terms of the discarded Laplacian energy, which would turn the empirical claim into a formal one."],"forward_implications":["Instances that direct quantum solvers cannot encode because of qubit limits or memory errors can be run after shrinking, since the reduced graph is what gets encoded into the quantum circuit.","Embedding constraint awareness into the shrinking and the QUBO formulation improves the quality of VQE solutions relative to the non-constraint-aware version, while lowering the repair effort needed afterward.","Adaptive shrinking, using the spectral energy criterion, gives a better quality-versus-size trade-off than fixed reductions to two-thirds or one-half of the original instance.","The framework is solver-agnostic: any QUBO-oriented quantum algorithm, such as QAOA, VQE, or QRAO, can be plugged into the reduced-problem stage."],"supporting_citations":[{"why":"Supplies the reduction from a QUBO to an equivalent weighted Max-Cut graph on n+1 nodes, the entry point of the shrinking pipeline.","marker":"[10]"},{"why":"Provides the base correlation-guided shrinking procedure whose static policies this paper extends with adaptive updates.","marker":"[9]"},{"why":"Gives the SDP relaxation of Max-Cut whose Gram matrix yields the correlations used for merging decisions.","marker":"[32]"},{"why":"Sets the penalty-strength condition that makes constraint violations energetically unfavorable in the QUBO encodings.","marker":"[30]"},{"why":"Defines QAOA, one of the quantum algorithms the pipeline is designed to feed.","marker":"[5]"},{"why":"Defines VQE, the solver used on the shrunk instances in the experiments.","marker":"[6]"},{"why":"Supplies the multidimensional knapsack benchmark suite used for the reported optimality gaps.","marker":"[14]"},{"why":"Supplies the quadratic assignment benchmark instances with known optima used for the reported gaps.","marker":"[16]"}],"fun_headline_variants":["Graph shrinking as quantum preprocessing for hard constrained problems","Shrink QUBO graphs to keep quantum solvers feasible on limited qubits","Constraint-aware graph shrinking cuts repair cost in quantum optimization","Adaptive graph shrinking makes constrained QUBOs quantum-ready","Preprocessing graph merging enables near-term quantum COP solving"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that correlations from the relaxed Max-Cut graph, under the paper's condition that constraint-related edges are much heavier than objective edges, identify merges that preserve the original constrained problem's optimum closely enough; the paper does not verify that condition on its benchmarks.","fun_headline_variants_meta":{"raw":{"variants":["Graph shrinking as quantum preprocessing for hard constrained problems","Shrink QUBO graphs to keep quantum solvers feasible on limited qubits","Constraint-aware graph shrinking cuts repair cost in quantum optimization","Adaptive graph shrinking makes constrained QUBOs quantum-ready","Preprocessing graph merging enables near-term quantum COP solving"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000243,"raw_usage":{"total_tokens":1518,"prompt_tokens":923,"completion_tokens":595,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":539,"completion_tokens_details":{"reasoning_tokens":513}},"tokens_in":539,"tokens_out":595,"duration_ms":6758,"temperature":1.0,"reasoning_tokens":513,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T00:17:59.643927+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a benchmark instance where constraint-derived and objective-derived edge weights are comparable in magnitude, violating the condition in Eq. 25, and compare the adaptive-shrinking reconstructed objective against the known optimum; if solution quality drops systematically on such instances, the merging signal depends on that dominance condition rather than on generic structure preservation.","supporting_citations":[{"cited_title":"Experiments in quadratic 0–1 programming","cited_arxiv_id":null,"evidence_quote":"Supplies the reduction from a QUBO to an equivalent weighted Max-Cut graph on n+1 nodes, the entry point of the shrinking pipeline."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the base correlation-guided shrinking procedure whose static policies this paper extends with adaptive updates."},{"cited_title":"Improved approximation algorithms for maximum cut and satisfia- 24 bility problems using semidefinite programming.Journal of the ACM (JACM), 42(6):1115–1145, 1995","cited_arxiv_id":null,"evidence_quote":"Gives the SDP relaxation of Max-Cut whose Gram matrix yields the correlations used for merging decisions."},{"cited_title":"Ising formulations of many np problems","cited_arxiv_id":null,"evidence_quote":"Sets the penalty-strength condition that makes constraint violations energetically unfavorable in the QUBO encodings."},{"cited_title":"A quantum approximate optimization algorithm, 2014","cited_arxiv_id":null,"evidence_quote":"Defines QAOA, one of the quantum algorithms the pipeline is designed to feed."},{"cited_title":"A variational eigenvalue solver on a photonic quantum processor.Nature commu- nications, 5(1):4213, 2014","cited_arxiv_id":null,"evidence_quote":"Defines VQE, the solver used on the shrunk instances in the experiments."},{"cited_title":"Benchmark instances for the multidimen- sional knapsack problem","cited_arxiv_id":null,"evidence_quote":"Supplies the multidimensional knapsack benchmark suite used for the reported optimality gaps."},{"cited_title":"Burkard, Stefan E","cited_arxiv_id":null,"evidence_quote":"Supplies the quadratic assignment benchmark instances with known optima used for the reported gaps."}],"review_version":1}