{"id":"d30d35f5-78fb-40eb-9a19-433d749e4373","arxiv_id":"2512.20613","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"Quantum-inspired product/matrix-product-state annealing embedded in iterated local search reports better MaxCut approximations than the ILS, LQA, GCS, and QAOA baselines tested, on graphs up to 50,000 vertices.","lead":"The paper combines quantum-inspired variational states with iterated local search, creating two solvers for maximum-cut problems that they benchmark on graphs up to 50,000 variables. The authors report both solvers outperform their chosen baselines—including classical ILS, other quantum-inspired schemes, and published QAOA results—with a GPU-parallel version offering an order-of-magnitude speedup on a 20,000-variable instance.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Per-instance λ tuning for QiILS versus fixed baselines threatens the reported Gset advantage; hyperparameter inconsistencies make the protocol non-reproducible.","rationale":"The reader's conditional verdict identifies precisely the weakest point: QiILS is given per-instance hyperparameter tuning while the baselines are not, so the reported Gset advantage may reflect tuning effort rather than algorithmic merit. This concern is load-bearing because the central claim is an empirical superiority claim, and the Gset results are the main large-instance evidence. The specific fix—charge tuning overhead and tune baselines fairly, then evaluate on held-out initializations—is concrete and would settle the issue. I do not think this warrants rejection; the algorithm is clearly specified, the variational updates are exact, and the random-instance benchmarks with globally selected λ provide some supporting evidence. However, the hyperparameter inconsistencies (e.g., Fig. 3(b) λ=0.75 vs Table S2 λ=0.65; sweeps 80 vs 200) and the lack of released code/data mean the conditional verdict is the right call. My read does not change the verdict, so I recommend UNCHANGED rather than a different category.","tokens_in":16761,"tokens_out":7380,"duration_ms":90982,"concrete_test":"On G1–G10, split random initial states into a tuning set (10 seeds, 50 iterations per candidate) and a held-out evaluation set (10 fresh seeds, 1000 iterations). Use the tuning set to select each method's hyperparameters per instance with the same grid and budget (λ,p for QiILS; p for ILS; γ,η for LQA; analogous for GCS), then report held-out average/best solution values and total wall-clock time including tuning. Also run QiILS with a single fixed λ across all G instances to quantify the contribution of per-instance tuning. If QiILS still outperforms per-instance-tuned baselines on held-out seeds, the concern is resolved; if the margin shrinks or reverses, the superiority claim requires qualification.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central empirical claim that QiILS outperforms established classical heuristics rests on the Gset comparisons, but those comparisons are not made on equal footing. Supplemental Sec. IV states that optimal λ values for the Gset calculations were found using 10 random initializations and 50 iterations on each graph, and Table S2 lists distinct λ per instance (e.g., G1=0.38, G2=0.41, G6=0.42). Meanwhile, ILS, LQA, and GCS are run with fixed hyperparameters (Table I caption). Since Fig. 2(a) shows that performance varies by orders of magnitude with λ, per-instance tuning of only QiILS can explain a substantial part of the apparent advantage. The conclusion also calls ILS, LQA, and GCS 'state-of-the-art classical heuristics,' which is not supported: LQA and GCS are quantum-inspired variational methods, and ILS is a basic metaheuristic; no comparison to leading MaxCut solvers is provided. The protocol is further weakened by inconsistencies: main text Fig. 3(b) reports λ=0.75 and p=0.3, while Table S2 lists λ=0.65 and p=0.5; Table I says sweeps=80 for QiILS, while Table S2 says 200. Without code/data or a clarified, internally consistent protocol, the reported margins cannot be independently verified. The algorithms themselves are clearly described and the PS update equations are exact, so the concern is about the empirical comparison, not the core construction.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces quantum-inspired variational algorithms for MaxCut based on product-state (PS) and matrix-product-state (MPS) ansätze, embedded in iterated local search (ILS). The single-site PS update is derived exactly (Eqs. 4–6), and MPS versions are implemented with DMRG. The authors also introduce QiIGS, a parallel gradient-descent variant, and benchmark these methods on random regular graphs, Gset instances up to 800 vertices, and one 20,000-vertex instance (G81). The paper claims that QiILS outperforms classical ILS, local quantum annealing (LQA), generalized coherent states (GCS), and QAOA on the tested instances, and that QiIGS offers an order-of-magnitude speedup over QiILS on G81.","tokens_in":17145,"tokens_out":5557,"duration_ms":53889,"significance":"If the empirical claims are robust, the paper would make a useful contribution: the exact PS updates are simple, the algorithms are classically scalable, and the idea of combining quantum-inspired variational evolution with ILS is natural and interesting. The derivation is transparent, and the numerical study is extensive, including hyperparameter exploration and a large-scale GPU comparison. However, the reported advantage over baselines rests on a comparison in which QiILS's key hyperparameter λ is tuned per target instance, while the baselines use fixed hyperparameters. This, together with internal inconsistencies in the reported hyperparameters and an overstated characterization of the baselines, substantially weakens the central claim as currently presented.","major_comments":[{"comment":"The Gset comparison is not on equal footing: per-instance λ values for QiILS (e.g., G1=0.38, G2=0.41, G6=0.42) were selected using 10 random initializations and 50 iterations on the same graph being evaluated (Supplemental Sec. IV), while LQA and GCS use fixed hyperparameters. Since Fig. 2(a) shows that performance varies by orders of magnitude with λ, the advantage in Table I and Fig. 1 may reflect per-instance selection rather than algorithmic superiority. Please provide a train/validation split, held-out instances, or explicitly charge the tuning cost to QiILS; without this, the main empirical claim is not established.","section":"Supplemental Sec. IV, Table S2; Table I; Fig. 2(a)"},{"comment":"The reported hyperparameters are internally inconsistent. The Fig. 3(b) caption states λ=0.75, p=0.3, while Table S2 lists λ=0.65, p=0.5; the Fig. 2(b) caption says λ=0.4, while Table S2 says λ=0.5; and Table I says QiILS uses sweeps=80, while Table S2 lists sweeps=200 for G1–G10. These discrepancies make the protocol non-reproducible and must be reconciled before the results can be used to support the conclusions.","section":"Fig. 3(b) vs Table S2; Fig. 2(b) vs Table S2; Table I vs Table S2"},{"comment":"The conclusions call ILS, LQA, and GCS 'state-of-the-art classical heuristics.' This is overstated: ILS is a generic metaheuristic, LQA and GCS are quantum-inspired variational methods, and no leading classical MaxCut solvers (e.g., Breakout Local Search, simulated annealing, or commercial solvers) are compared. The competitive claim should be scoped to the tested baselines, not to the state of the art in combinatorial optimization.","section":"Conclusions"}],"minor_comments":[{"comment":"The abbreviations u3R and w3R are used in figures but not defined; the text defines udR and wdR. Use consistent notation.","section":"Background and Figs. 2, 5"},{"comment":"The rounding rule maps θ_j to bits, but the relation between the bit b_j and the spin value (±1) used in the Hamiltonian is not explicitly stated; clarify to avoid ambiguity.","section":"Eq. (8)"},{"comment":"The Supplemental Material is referenced only by a '[URL will be inserted by publisher]' placeholder; a working link or an included supplemental PDF is needed for reproducibility.","section":"Supplemental Sec. IV"},{"comment":"The table's 'iterations' column is not consistently defined for all rows; for example, Fig. 2(a) lists 1,2,4,8 while Fig. 4 lists 10,000. Clarify whether these are iteration counts or iteration indices.","section":"Table S2"}],"recommendation":"major_revision","confidential_remarks":"The reader's main concern is valid: the per-instance tuning of λ for QiILS while keeping baseline hyperparameters fixed undermines the headline comparison. The paper's core algorithmic derivation is sound, and the inconsistency in hyperparameter reporting is fixable, but the empirical claims need to be reworked with a fair evaluation protocol (e.g., held-out instances or tuning-cost accounting) before the paper can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First off: the paper is worth reading. The core idea—embedding fixed-lambda (M)PS annealing sweeps in an iterated-local-search loop—is a sensible combination, and the dedicated chi=1 product-state version with the closed-form angle update (Eqs. 4–6) is a genuine, useful algorithmic contribution. The QiIGS gradient variant and the GPU benchmark up to 50,000 variables are also new and interesting. The authors are transparent about the fact that hyperparameters were tuned: Figure 1's caption explicitly notes the offset from extra tuning sweeps, and the supplement describes the lambda-selection procedure. That transparency deserves credit.\n\nThe soft spot is the empirical core. On Gset, QiILS's lambda (and p) are selected per graph using 10 random initializations and 50 iterations on that same graph, while the baselines use fixed hyperparameters chosen more coarsely. Given that Figure 2(a) shows performance varies by orders of magnitude with lambda, some—possibly much—of the reported advantage is selection bias. A train/test split or charging the tuning cost to QiILS would settle the question, but that hasn't been done. Additionally, calling ILS, LQA, and GCS \"state-of-the-art classical heuristics\" overstates the comparison: LQA/GCS are quantum-inspired variational methods, and ILS is a simple metaheuristic. No comparison to leading MaxCut solvers (e.g., Breakout Local Search or well-tuned simulated annealing) is given.\n\nThere are also direct reproducibility issues. The main text (Fig. 3(b) caption) says lambda=0.75, p=0.3, while Table S2 says 0.65 and 0.5 for the same figure. Table I's caption says sweeps=80 for QiILS in the Gset benchmark, but Table S2 says 200. No code or data is provided. These are easily fixed, but as written, the protocol is not self-consistent.\n\nThe PS update derivation is exactly correct, and the QiIGS speedup curve is a fair demonstration of GPU parallelization. So the construction is sound; it's the benchmarking protocol that needs a revision. I'd send this to a serious referee—it deserves review—but I'd expect the verdict to be major revision, with code release, held-out tuning validation, and a rewritten conclusion that doesn't oversell the baselines. Right now I'd treat the qualitative claim (this family can beat plain ILS and LQA on these instances) as plausible, and the quantitative margins as unverified.","headline":"A clearly-constructed tensor-network heuristic whose headline Gset advantage is not yet trustworthy because the comparison is per-instance tuned and the reported hyperparameters are inconsistent.","tokens_in":17624,"tokens_out":4010,"would_cite":false,"duration_ms":41517,"reading_group":"maybe","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 argues that variational matrix product state methods, when wrapped in iterated local search, outperform both classical heuristics like ILS and quantum algorithms like QAOA on large MaxCut problems.","keywords":["MaxCut","matrix product states","iterated local search","quantum-inspired optimization","variational methods","combinatorial optimization","GPU parallelization","QAOA"],"falsifier":"Take a collection of unseen Gset instances, choose λ once on a separate training set (e.g., via golden-section search), then run QiILS and ILS with that fixed λ and charge all tuning time to QiILS. If QiILS no longer achieves consistently lower relative error than ILS, the paper's main advantage claim is falsified.","tokens_in":16634,"feed_emoji":"⚛️","tokens_out":2656,"duration_ms":29430,"temperature":0.7,"pith_summary":"The authors show that combining variational product-state or matrix-product-state minimization of a quantum-annealing Hamiltonian with iterated local search yields a solver, QiILS, that finds better MaxCut solutions than standard ILS, LQA, GCS, and QAOA on instances up to 50,000 variables. A parallel variant, QiIGS, achieves comparable accuracy while running an order of magnitude faster on a 20,000-variable graph. A sympathetic reader would care because the result suggests that classical, quantum-inspired tensor-network heuristics remain strong competitors to near-term quantum optimization algorithms.","feed_headline":"Quantum-inspired MPS solver beats ILS and QAOA on MaxCut","feed_subtitle":"New iterated local search with product states solves MaxCut up to 50,000 variables, with a GPU-parallel variant an order of magnitude faster","key_machinery":"The central object is the interpolating Hamiltonian H(λ) = (1-λ)Hi + λHf, where Hi is a transverse-field Hamiltonian and Hf encodes the MaxCut objective. The QiILS algorithm alternates between variational energy minimization of this Hamiltonian at a fixed λ and random spin flips (perturbations), with the product-state variant updating each angle θj via a closed-form formula. QiIGS replaces those sequential updates with parallel gradient descent, enabling GPU acceleration.","core_discovery":"The paper's central claim is that optimizing a quantum annealing interpolation Hamiltonian with DMRG-style sweeps, followed by random spin perturbations, produces a strictly generalized form of ILS that systematically improves approximation ratios on MaxCut. The authors report that the unentangled product-state version (bond dimension 1) with many iterations outperforms higher bond dimensions on large instances, and that QiILS beats ILS, LQA, GCS, and QAOA on Gset benchmarks. They further claim that QiIGS, which replaces sequential angle updates with parallel gradient descent, scales nearly independently of problem size on GPU hardware and provides an order-of-magnitude speedup over QiILS on","pith_inferences":["The reported advantage of QiILS over ILS depends on per-instance tuning of λ (and perturbation strength p); if tuning overhead is charged to QiILS or λ is fixed by a held-out selection, the margins in Table I and Fig. 1 could shrink.","The strong performance of the product-state (χ=1) version suggests that entanglement captured by larger bond dimensions is not the driver of the gains; the annealing path plus ILS perturbation loop may carry most of the benefit.","These quantum-inspired solvers could serve as a stronger classical baseline for future demonstrations of quantum optimization advantage, since they already outperform a popular variational quantum algorithm on tested instances."],"forward_implications":["QiILS recovers standard ILS at λ=1, so any improvement must come from the annealing-like intermediate states sampled at λ<1.","On unweighted 3-regular graphs, QiILS with χ=1 solves all 1000 tested instances within 15 iterations, a performance the authors compare favorably to QAOA's required circuit depth.","Per-sweep wall-clock time of QiILS matches that of ILS, while LQA is roughly 7× slower and GCS roughly 9000× slower on the G12 benchmark.","QiIGS's parallel gradient updates allow near-constant per-iteration time as the problem grows to 50,000 variables.","The same recipe—annealing interpolation plus iterated local search—could be applied to other binary optimization problems beyond MaxCut."],"fun_headline_variants":["MPS variational solver beats ILS and QAOA on MaxCut","Quantum-inspired MPS solver wins MaxCut benchmarks up to 50k vars","GPU-parallel MPS solver speeds up MaxCut by 10x","Variational MPS trounces classical ILS on MaxCut instances","Product-state ILS outperforms QAOA on large MaxCut"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that per-instance hyperparameter tuning (especially λ) is a fair part of the method's cost and that the tuned values generalize; if a held-out evaluation with fixed hyperparameters erases the gap over ILS, the central performance claim collapses.","fun_headline_variants_meta":{"raw":{"variants":["MPS variational solver beats ILS and QAOA on MaxCut","Quantum-inspired MPS solver wins MaxCut benchmarks up to 50k vars","GPU-parallel MPS solver speeds up MaxCut by 10x","Variational MPS trounces classical ILS on MaxCut instances","Product-state ILS outperforms QAOA on large MaxCut"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000168,"raw_usage":{"total_tokens":1035,"prompt_tokens":619,"completion_tokens":416,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":363,"completion_tokens_details":{"reasoning_tokens":322}},"tokens_in":363,"tokens_out":416,"duration_ms":3911,"temperature":1.0,"reasoning_tokens":322,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T14:19:22.235791+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a collection of unseen Gset instances, choose λ once on a separate training set (e.g., via golden-section search), then run QiILS and ILS with that fixed λ and charge all tuning time to QiILS. If QiILS no longer achieves consistently lower relative error than ILS, the paper's main advantage claim is falsified.","supporting_citations":[],"review_version":1}