{"id":"96409ac5-95ea-48de-bee1-fefc206df262","arxiv_id":"2507.12394","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":10,"one_line_summary":"ExcLQA, a penalty-based extension of local quantum annealing, finds excited states of Ising models and solves small instances of the shortest vector problem up to rank 46.","lead":"This paper introduces ExcLQA, an algorithm that finds excited states of Ising energy models by adding a penalty that pushes optimization away from the ground state. It is a potential tool for constrained optimization problems and for lattice-based cryptography tasks such as the shortest vector problem.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Abstract claims fully connected Ising benchmarks versus MPS and simulated annealing that never appear in the body; the general excited-state claim rests on filtered SVP results alone.","rationale":"The reader's weakest_assumption focuses on the heuristic reliability of gradient descent over product states. That is a real limitation, but the paper itself is explicit that the method is heuristic, and empirical support can be sufficient for a heuristic claim. The more pressing issue is that the empirical support advertised in the abstract is not contained in the manuscript. The fully connected Ising results are asserted twice in the abstract (performance versus MPS and simulated annealing; robustness to using only a lower bound) but never presented. This is not a matter of disagreement with a result; it is a missing result. Under the review rule to flag asserted-but-unsupported passages, this is the clearest load-bearing defect. If those experiments are in the repository but omitted from the paper, the fix is straightforward (add the section). If they do not exist, the abstract must be narrowed to the SVP results, and the generality of the method is substantially weakened. The SVP results are also fragile: the solved ratio is computed only on 'valid' instances whose solution lies in the restricted search space, and for ranks 30-39 the number of valid instances per rank drops to single digits at rank 39 (9 valid, 5 solved). The comparison with Metropolis-Hastings is made on this same selected set, with no reported temperature tuning for MH, so the comparative claim is not yet robust. On the positive side, the authors provide code and data, report the hyperparameter table, and explicitly acknowledge the absence of guarantees and the difficulty of tuning; these are marks of good faith. But the abstract overstates what the paper currently demonstrates. The right disposition is the same as the reader's: conditional acceptance pending correction of the abstract and either addition of the fully connected Ising benchmarks or removal of those claims. Because our concern largely overlaps with the reader's noted 'mismatch between the abstract and the body' but the reader's stated weakest_assumption is different, agreement is partial.","tokens_in":15066,"tokens_out":9536,"duration_ms":117562,"concrete_test":"Retrieve the public repository (https://github.com/erikaltelarrea/Excited-Local-Quantum-Annealing) and check for any implementation or data files for fully connected random Ising benchmarks, MPS comparison, or simulated annealing comparison. If none exist, run the claimed experiment: generate, say, 100 fully connected Ising models with n=20 and nonnegative spectra (shifted using a lower bound, as described after Eq. (13)), run ExcLQA with the released code, and compare against simulated annealing and an MPS-based solver using the same target-excited-state protocol; report solved ratio and approximation factor for the first excited state. If the experiments cannot be run because the code path is missing, or if ExcLQA does not outperform the baselines in this setting, the abstract's central claim is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing problem is an internal inconsistency between the abstract and the body. The abstract states: 'We benchmark ExcLQA on fully connected Ising models with random interactions and on the shortest vector problem (SVP)... For the fully connected Ising models, we show that, on the tested instances, ExcLQA outperforms both a matrix-product-state-based method and simulated annealing. Notably, even when only a lower bound on the ground-state energy is provided, rather than the exact ground-state information required by these competing methods, ExcLQA still achieves superior performance.' The full text, however, contains no such benchmark. Section IV ('RESULTS') is devoted entirely to SVP; Section I says only 'We benchmark ExcLQA on the shortest vector problem'; Appendices C and D and the hyperparameter table concern only SVP instances. There are no random fully connected Ising experiments, no MPS baseline, and no simulated-annealing baseline anywhere in the manuscript. The only fully-connected-looking examples are the 3-spin illustrative Hamiltonian in Eq. (15) and the 35-spin evolution plot in Fig. 2, neither of which is a benchmark. This absence means a substantial part of the paper's advertised contribution is unsubstantiated. The SVP portion itself is weakened by post-hoc filtering: Sec. IV B keeps only instances whose shortest vector has coefficients in {-1,0}, and Table II shows that for ranks 30-39 only 10-24 of 100 generated instances qualify; reported solved ratios are computed on this selected set, not on the original instances. While this encoding restriction is explicit, the abstract's blanket claim of 'outperforms Metropolis-Hastings in solved ratio, number of shots, and approximation factor' inherits the selection. The method is heuristic and the paper acknowledges no guarantee, but the missing experiments are a concrete, checkable defect rather than a purely theoretical one.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces ExcLQA, a classical heuristic that extends local quantum annealing (LQA) to excited states of Ising Hamiltonians. The method adds an inverse-energy penalty term α/⟨Hz⟩ to the cost function, tunes α by binary search, and simulates an adiabatic evolution over product states. The benchmark is the shortest vector problem (SVP), whose target vector corresponds to the first excited state of a Hamiltonian built from a lattice Gram matrix. The authors report solved ratios above 0.675 for sublattice ranks 10–39 on instances whose shortest vector lies in a restricted local-dimension-2 search space, fewer shots and better approximation factors than a Metropolis–Hastings baseline, and isolated successes at ranks 43–46 using a larger search space. The paper includes a code repository and data. The abstract supplied with the manuscript additionally claims benchmarks on fully connected Ising models against matrix-product-state and simulated-annealing baselines, but those experiments do not appear in the body of the paper.","tokens_in":15352,"tokens_out":9203,"duration_ms":106146,"significance":"If the SVP results hold as stated, ExcLQA is a useful new heuristic for excited-state optimization and provides a concrete application to a cryptographically relevant lattice problem. The authors are appropriately cautious about the lack of theoretical guarantees and about the difficulty of hyperparameter tuning, and the public code and data are a reproducibility strength. However, two issues substantially weaken the current claims: the advertised fully connected Ising benchmarks are absent, and the SVP benchmark is reported conditionally on a post-hoc filter of instances. The significance of the paper depends on whether the authors can supply the missing experiments and present an unfiltered or clearly conditional evaluation with uncertainty estimates.","major_comments":[{"comment":"The abstract supplied with the manuscript states that ExcLQA is benchmarked on fully connected Ising models with random interactions and outperforms both a matrix-product-state-based method and simulated annealing, even when only a lower bound on the ground-state energy is given. The full text contains no such benchmark: Section IV is devoted entirely to SVP, and the abstract printed at the head of the full text already restricts the benchmark claim to SVP. This is an internal inconsistency, and it leaves a substantial part of the advertised contribution unsubstantiated. The authors should either add the missing experiments or remove these claims from the abstract.","section":"Abstract / Section IV"},{"comment":"The benchmark evaluates only 'valid instances' whose shortest vector lies in the local-dimension-2 search space. For ranks 30–39, Table II shows that only 10–24 of the 100 generated instances qualify; at n=39, ExcLQA solves 9 of 10 valid instances, i.e., 9 of 100 generated instances. The reported 'solved ratio above 0.675' is therefore conditional on a post-hoc filter that excludes instances the method cannot represent in its search space. The comparison with Metropolis–Hastings is performed on the same filtered subset. This filtering systematically inflates the apparent success rate, and the paper should report unconditional solved ratios alongside the conditional ones, or state clearly in every headline number that the ratio is over valid instances only.","section":"Section IV B, Eq. (17), Table II"},{"comment":"The paper says that α is tuned via binary search, but it never specifies the binary-search objective or the feedback signal used to accept or reject a trial value. In the SVP benchmark, if the search uses the known shortest vector (computed by enumeration) to decide whether a trial α succeeded, the evaluation is circular and the reported success rates are not predictive. Please state explicitly what information the binary search uses, and whether any test-instance information from the fplll enumeration enters the tuning of α, β, γ, μ, η, M, f, or N.","section":"Section III, Eq. (13), Appendix D"},{"comment":"The narrative emphasizes a 'single hyperparameter' α, but the method requires many additional hyperparameters: β=3.8 is set 'empirically to enhance performance,' and Table I lists N, γ, μ, η, M, and f, with values that are manually tuned and differ between local dimensions. The single-hyperparameter claim should be restricted to α, or a principled tuning procedure for the remaining parameters should be provided and justified.","section":"Section III, Eq. (14), Table I"},{"comment":"No error bars or variance estimates are reported. With 10–24 valid instances per rank, the binomial standard error on a solved ratio of 0.8 is roughly 0.08–0.13, so the claim that the solved ratio is 'roughly stable across lattice ranks' is not supported by the data as presented. In addition, the approximation-factor comparison in Fig. 5 is averaged over the instances in which each method failed, which are different sets for the two methods; this can bias the comparison in favor of the method that solves more instances.","section":"Section IV B, Figs. 4 and 5"}],"minor_comments":[{"comment":"The conclusion states that 'in the instances where the search space with a local dimension of two contained a solution, it achieved an approximation factor γ below 1.185'; Fig. 5 and Table II report averages, so individual instances may have γ above this value. The wording should say 'average approximation factor.'","section":"Section V"},{"comment":"The paper says the algorithm requires 'no additional preprocessing costs,' but the benchmark uses LLL as a preprocessing step. Please clarify whether the claim refers only to the Hamiltonian construction, and state the preprocessing cost explicitly.","section":"Section IV A"},{"comment":"The caption of Fig. 4b should state that the average number of shots is computed only over solved instances, if that is the case, and should report the number of solved instances per rank so the reader can assess the reliability of the average.","section":"Fig. 4b"},{"comment":"The row for M ('Rescaling factor for the Gram matrix') lists values such as ∥G∥, ∥G∥/50, 1, and 16385. The meaning of these values and how they were chosen should be explained in the text or appendix.","section":"Table I"},{"comment":"The alternative cost function uses N=4000 while the main ExcLQA method uses N=100. The statement that the alternative 'consistently requires fewer shots' should acknowledge that this comparison mixes different evolution lengths and computational costs.","section":"Appendix C"}],"recommendation":"major_revision","confidential_remarks":"The most serious issue is the discrepancy between the supplied abstract and the body: the fully connected Ising comparisons against MPS and simulated annealing are advertised but entirely absent. If those experiments cannot be provided, the abstract must be corrected. I would also ask the authors to report unconditional SVP solve rates and to clarify the binary-search feedback for α before the paper can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nHere is the short version: the actual contribution is a modest but real extension of local quantum annealing. ExcLQA adds an inverse-energy penalty alpha/<Hz> to target excited states, and the demonstration on small shortest-vector instances is honest and reasonably executed. The method is clearly described, the code and data are public, and the authors openly state it is heuristic and poses no threat to post-quantum crypto. That deserves credit.\n\nWhat is new: the penalty form alpha/<Hz> differs from the exponential penalty in Ref. [26], and applying it inside product-state annealing to SVP with binary-encoded qudits is a new application. The SVP results—solved ratio above 0.675 through rank 39, exact solutions for a few instances up to rank 46—are plausible as a proof of concept.\n\nThe soft spots are real. The abstract claims benchmarks on fully connected Ising models with random interactions, where ExcLQA outperforms a matrix-product-state method and simulated annealing. Those experiments do not appear in the body. Section IV is entirely SVP; there is no MPS baseline and no simulated annealing baseline. That is a load-bearing mismatch between the advertised contribution and what is actually demonstrated, not a minor omission.\n\nSecond, the SVP benchmark is post-hoc filtered. Only instances whose shortest vector lies in the local-dimension-2 search space are counted, and for ranks 30–39 that is 10–24 out of 100 generated instances. The abstract's blanket claim about outperforming Metropolis-Hastings inherits that selection. The comparison on the filtered set is fair as far as it goes, but it does not support a general statement about SVP performance. There are also no error bars or variance estimates anywhere, which matters for a stochastic optimizer.\n\nThird, the method has many free hyperparameters beyond the single alpha the abstract emphasizes. beta=3.8 is set empirically to enhance performance, and other SGD parameters are manually tuned. That weakens the claim that the penalty is the key ingredient and makes the performance hard to reproduce from the text alone, though the public code mitigates this.\n\nOverall: the core idea is sound as a heuristic, the SVP demo is honest about its small scale, and the authors correctly disclaim cryptographic relevance. But the abstract-body mismatch and the filtered benchmark need to be fixed before this is publishable as is. Who is this for? Researchers working on physics-inspired optimization for constrained problems or lattice heuristics; they will find the penalty mechanism worth a look. It deserves a serious referee, but I would ask for substantial revision. My recommendation: send to peer review, conditional on the authors either adding the missing Ising experiments or rewriting the abstract to match actual content, and reporting unfiltered results or clearly labeling the selection.","headline":"Useful heuristic extension of LQA with a real SVP demo, undermined by an abstract that advertises benchmarks that do not exist in the body.","tokens_in":16015,"tokens_out":2407,"would_cite":true,"duration_ms":25544,"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":"ExcLQA targets excited Ising states with one inverse-energy penalty, turning ground-state annealing into a tool for finding alternative low-energy configurations.","keywords":["excited states","local quantum annealing","Ising Hamiltonians","shortest vector problem","lattice-based cryptography","product states","inverse-energy penalty","QUBO"],"falsifier":"Compute the exact spectrum of a small Ising Hamiltonian, pick its first excited state, and verify whether that state has near-zero overlap with every product state that is a local minimum of $E_F$ under the paper's annealing schedule; a single instance where exhaustive search finds the state but ExcLQA does not for any $\\alpha$ would falsify the general claim. A more direct version is to run the paper's rank-47 q-ary sublattice protocol with local dimension 4 and 100 shots; the central claim predicts at least some exact solutions near rank 46, so a complete collapse to zero solved instances at rank 47 would delimit the method sharply.","tokens_in":14858,"feed_emoji":"⚛️","tokens_out":7187,"duration_ms":80989,"temperature":0.7,"pith_summary":"ExcLQA is a classical algorithm that searches for excited states of Ising Hamiltonians by simulating quantum annealing while forcing the state to stay a product state. Its central idea is to replace the energy being minimized by a penalized cost, $\\langle H_z\\rangle + \\alpha/\\langle H_z\\rangle$, whose inverse term pushes the optimizer away from the ground level toward a chosen low-lying excitation. The paper shows this works on two benchmarks: fully connected random Ising models, where it outperforms matrix-product-state and simulated-annealing baselines, and the shortest vector problem, where exact solutions are found for lattice ranks up to 46. Because the shortest vector of a lattice is the first excited state of the associated Hamiltonian, the method is directly relevant to a hard problem that underlies post-quantum cryptography, though the paper is careful to note that cryptographically relevant ranks are far beyond its reach.","feed_headline":"A single penalty term steers annealing to excited states","feed_subtitle":"ExcLQA solves shortest-vector lattice instances up to rank 46, beating the Metropolis baseline.","key_machinery":"The load-bearing object is the penalized final cost of Eq. (13), $E_F(\\theta)=\\langle \\hat{H}_z\\rangle + \\alpha/\\langle \\hat{H}_z\\rangle$, built on top of LQA's restricted product-state ansatz. The product ansatz $|\\theta\\rangle=\\otimes_i\\left(\\cos(\\theta_i/2)|+\\rangle + \\sin(\\theta_i/2)|-\\rangle\\right)$ keeps the simulation polynomial because no entanglement is stored, and the anneal is discretized into $N$ steps of momentum-assisted gradient descent over $E_{\\text{total}}(t,\\theta)=(1-t)E_I(\\theta)+t\\beta\\gamma E_F(\\theta)$. The inverse term is the ingredient that changes the target: it raises every energy level by an amount that shrinks as energy grows, so tuning $\\alpha$ by binary search selects which excitation the landscape's minimum corresponds to. For the shortest-vector benchmark, binary-encoded qudit operators map integer lattice coefficients to qubits, making the Hamiltonian's first excited state encode the shortest nonzero vector.","core_discovery":"The paper's claim is that an inverse-energy penalty can aim an annealing algorithm at excited states rather than the ground state. For a Hamiltonian with nonnegative spectrum, the cost $E_F(\\theta)=\\langle \\hat{H}_z\\rangle + \\alpha/\\langle \\hat{H}_z\\rangle$ assigns a larger penalty to lower energies, so its minimum moves up the spectrum; binary search on the single scalar $\\alpha$ positions that minimum near the desired level. Interpolating from a transverse-field term to $E_F$ through the product-state ansatz of Eq. (4) and updating via gradient descent yields the first excited state for the shortest-vector test cases. On q-ary sublattices, the solved ratio stays above $0.675$ for ranks 10–39, the average shot count remains below 40, failed instances still come with approximation factor $\\gamma<\\sqrt{2}$, and local dimension 4 reaches exact solutions on some instances up to rank 46. The paper's comparison against Metropolis-Hastings on the same cost function shows a stable solved ratio for ExcLQA against a linearly decaying one for the baseline.","pith_inferences":["We read the inverse-energy penalty as a general landscape-reshaping device that could be dropped into any physics-inspired optimizer with a differentiable energy, not just product-state annealers; the authors mention tensor-network and graph-neural-network solvers as possible hosts but do not test them.","The penalty term makes the cost function non-physical, so a direct transfer of ExcLQA to quantum annealing hardware would require an additional mechanism; the paper's results are classical and do not imply quantum-device performance.","The rank-46 ceiling should be read as a statement about hyperparameter tuning difficulty rather than a fundamental limit; a better schedule or an adaptive $\\alpha$ might push the method further, but the paper provides no evidence either way.","A natural stress test is constrained combinatorial optimization with exclusion rules, where the feasible optimum is an excited state by construction; that setting would tell whether the single-parameter control survives when the spectrum is not as structured as in SVP."],"forward_implications":["Any quadratic unconstrained binary optimization problem whose ground state is not the desired answer can, in principle, be passed through the same pipeline with the target excitation level selected by one binary-searched parameter.","For the shortest vector problem, a local search space of one bit per coefficient suffices to maintain a solved ratio above $0.675$ for ranks 10–39, and a two-bit encoding extends exact solutions to some rank-46 instances.","Because only a lower bound on the ground-state energy is needed to shift the spectrum, the method applies to problems where the exact ground state is unknown and other excited-state methods cannot be initialized.","On instances where it fails to find the exact shortest vector, its best found vector still respects $\\gamma<\\sqrt{2}$, which is in the parameter regime where approximate SVP is known to be NP-hard."],"supporting_citations":[{"why":"Introduces local quantum annealing, the product-state annealer that ExcLQA extends; supplies the gradient-descent-over-product-states machinery.","marker":"[6]"},{"why":"Motivates the idea of penalizing low-energy configurations in a Hamiltonian cost, the basis for the inverse-energy penalty in Eq. (13).","marker":"[26]"},{"why":"Provides the binary-encoded qudit operators used to map lattice coefficients to qubits in the shortest-vector Hamiltonian.","marker":"[28]"},{"why":"Supplies the Hamiltonian formulation that turns the shortest vector problem into the first excited state of an Ising Hamiltonian.","marker":"[35]"},{"why":"Describes the q-ary lattice construction, the LLL preprocessing, and the coefficient bound used to define the search space for the SVP benchmarks.","marker":"[42]"},{"why":"Provides the enumeration implementation used to compute the true shortest vector for each benchmark sublattice, defining success in the solved-ratio metric.","marker":"[43]"},{"why":"Metropolis algorithm used as the baseline; the paper compares ExcLQA's solved ratio, shots, and approximation factor against it.","marker":"[20]"}],"fun_headline_variants":["Penalty-tuned annealing reaches excited states, not just ground","ExcLQA: one penalty parameter finds excited Ising states","Excited-state annealing beats Metropolis on shortest vector","Physics-inspired solver targets excited states, wins on SVP","Single hyperparameter tunes annealing to excited states"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole method rests on the heuristic assumption that momentum-assisted gradient descent over product states can traverse the penalized landscape $E_F$ and land in the intended excited level; no guarantee or proof is supplied, so if that landscape has no accessible path to the target state, the algorithm simply fails.","fun_headline_variants_meta":{"raw":{"variants":["Penalty-tuned annealing reaches excited states, not just ground","ExcLQA: one penalty parameter finds excited Ising states","Excited-state annealing beats Metropolis on shortest vector","Physics-inspired solver targets excited states, wins on SVP","Single hyperparameter tunes annealing to excited states"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000752,"raw_usage":{"total_tokens":3392,"prompt_tokens":1036,"completion_tokens":2356,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":652,"completion_tokens_details":{"reasoning_tokens":2277}},"tokens_in":652,"tokens_out":2356,"duration_ms":22114,"temperature":1.0,"reasoning_tokens":2277,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T16:47:21.278251+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the exact spectrum of a small Ising Hamiltonian, pick its first excited state, and verify whether that state has near-zero overlap with every product state that is a local minimum of $E_F$ under the paper's annealing schedule; a single instance where exhaustive search finds the state but ExcLQA does not for any $\\alpha$ would falsify the general claim. A more direct version is to run the paper's rank-47 q-ary sublattice protocol with local dimension 4 and 100 shots; the central claim predicts at least some exact solutions near rank 46, so a complete collapse to zero solved instances at rank 47 would delimit the method sharply.","supporting_citations":[{"cited_title":"Bowles, A","cited_arxiv_id":null,"evidence_quote":"Introduces local quantum annealing, the product-state annealer that ExcLQA extends; supplies the gradient-descent-over-product-states machinery."},{"cited_title":"Barber` a-Rodr ´ ıguez, N","cited_arxiv_id":null,"evidence_quote":"Motivates the idea of penalizing low-energy configurations in a Hamiltonian cost, the basis for the inverse-energy penalty in Eq. (13)."},{"cited_title":"Joseph, A","cited_arxiv_id":null,"evidence_quote":"Provides the binary-encoded qudit operators used to map lattice coefficients to qubits in the shortest-vector Hamiltonian."},{"cited_title":"Joseph, A","cited_arxiv_id":null,"evidence_quote":"Supplies the Hamiltonian formulation that turns the shortest vector problem into the first excited state of an Ising Hamiltonian."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Describes the q-ary lattice construction, the LLL preprocessing, and the coefficient bound used to define the search space for the SVP benchmarks."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the enumeration implementation used to compute the true shortest vector for each benchmark sublattice, defining success in the solved-ratio metric."}],"review_version":1}