acceptodds
Under review as a conference paper at ICLR 2027

Scalable Continuous-Energy Ising Solvers Leveraging Difference-of-Convex Programming

Abstract

Optimizing the Ising model to its ground state is a central NP-hard combinatorial problem arising across physics, materials science, machine learning, and operations research. Practical solvers often rely on heuristic annealing methods, which can scale effectively but require cooling schedules and parameter tuning and typically provide limited convergence guarantees. At the other end of the spectrum, continuous relaxations such as semidefinite programming offer rigorous guarantees but become computationally prohibitive as problem size grows. We propose a continuous relaxation in which the discrete spin space is extended to . A separable quartic attractor replaces the hard constraint; its minimizers are exactly the vertices of a scaled hypercube . After solving the resulting continuous problem, a discrete solution is obtained via a componentwise sign mapping. The sum of the Ising energy and the attractor admits a difference-of-convex polynomial structure. This yields the Difference-of-Convex Hamiltonian (DOCH), which requires one matrix-vector multiplication and a componentwise cube-root update. Using the analytic nature of the Hamiltonian and the Łojasiewicz gradient inequality, we prove that DOCH converges to a critical point in this parameter regime and, under a nonzero-coordinate and Jacobian-stability condition, that the limit is a strict local minimum, enjoying linear convergence. For accelerated DOCH (ADOCH), we prove finite-window envelope descent and an best-iterate stationarity bound in the strict DC regime, together with full-sequence convergence when the look-back window is set to zero () from some finite iteration onward. We implement the proposed solvers on GPU platforms ranging from edge devices to high-performance computing clusters. Across MAX-CUT and spin-glass benchmarks, matched-budget comparisons with annealing, physics-inspired, and recent sampling-based solvers show favorable runtime-quality trade-offs from to spins.

Primary area:
optimization
Keywords:
Combinatorial Optimization, Non-Convex Optimization, Ising Model, First-Order Optimization, Iterative Convergence

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_c9YnOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper relaxes the Ising problem to a difference of convex objective functions. Two solver variants DOCH, and ADOCH that leverage the difference of convex structure are proposed and analyzed. Extensive numerical results are provided that highlight the performance of DOCH and ADOCH on various problem sizes ranging up 10^7 spins.

Critical strengths

The paper proposes a continuous quartic relaxation of Ising as a difference of convex problem, which is elegant and appears to be novel. (Caveat: I am not an expert on Ising, so I cannot relate the solution approach to the literature and earlier relaxation attempts.)

The convergence analysis (convergence to critical points of the relaxed problem) are rather routine and follow the literature. The results and claimed rates agree with the literature and appear to be sound, although I have not analyzed the proofs line-by-line. The key innovation of the paper is the relaxation as difference of convex and the empirical performance.

Critical weaknesses

There seems to be an issue with Fig. 3, b. The update step of DOCH is homogenous, so the iterates at different \beta values from the same initial condition match up to scaling. The same applies to the rounded iterates. Yet, Figure 3, (b) appears to show how the Ising energy changes with changing beta parameter. Can the authors clarify what is going on?

Looking at Table 8: it seems that there can be a large discrepancy between the average case result (mean E) and the best result (smallest E). Is such a discrepancy also present in corresponding baselines? Maybe the key results/tables could be augmented with success probabilities/restarts of both DOCH, ADOCH, and baselines?

Questions for authors

Please address the two points listed as weakness.

2 comments

We sincerely thank the reviewer for the encouraging assessment, particularly for recognizing the simplicity of the difference-of-convex formulation, the convergence analysis, and the large-scale experimental evaluation.


W1. Apparent dependence of the Ising energy on β\beta in Figure 3b.

We agree with the reviewer that, for fixed JJ and α\alpha and an identical initialization, changing β\beta only rescales the DOCH iterates by a positive factor. Consequently, their signs and the corresponding discrete Ising energies remain unchanged.

The key clarification concerns the experimental protocol in Figure 3b. Although the 100-spin SK coupling matrix JJ is fixed, we use independent random initializations for each value of γ\gamma. Moreover, we select α\alpha separately for each γ\gamma using the adaptive energy-based tuning procedure in Appendix M (Algorithm 9), and set β=nγ∣∣J+αI∣∣∞\beta=n^\gamma||J+\alpha I||_\infty.

Thus, the experiments differ not only in β\beta, but also in their initializations and potentially in α\alpha. The homogeneity argument therefore does not imply identical finite-sample average Ising energies across these experiments. The observed differences can arise from initialization variability and changes in the adaptively selected α\alpha.

We agree that Figure 3b should not be interpreted as showing a direct dependence of the rounded Ising energy on β\beta. For fixed α\alpha and identical initialization, this energy is invariant to β\beta in exact arithmetic. The figure instead reflects the combined effects of independent initializations and adaptive parameter selection in a practical setting.

We have now clarified this distinction in the figure caption and revised Remark G.2 to avoid attributing the observed energy variation directly to β\beta.


W2. Discrepancy between mean and best performance in Table 8.

As discussed in W6 of Reviewer v1pn, Table 8 shows substantial mean-best variability for ADOCH on the planted rank-one signed-bipartite instances. In contrast, DOCH recovers the certified optimum in all runs at n=100n=100 and achieves a mean energy within 1% of the optimum at n=1000n=1000. This variability is less pronounced on broader Ising and MAX-CUT benchmarks (Tables 4 and 5), where ADOCH achieves mean objective ratios of 0.984 to 0.994 over 100 independent runs.

Regarding the baselines, Tables 4 and 5 already report mean and best energies over 100 independent runs for DOCH, ADOCH, QQA, and iSCO on broader Ising and MAX-CUT benchmarks. ADOCH achieves mean objective ratios of 0.9840.984 to 0.9940.994, indicating considerably more consistent performance on these instances. Figures 5, 17, and 18 also present histograms and statistical summaries from 100 runs.

Thank you for the additional clarification and the revision. I maintain my positive score.

Reviewer_nuUuOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposed Ising solvers based on a difference of convex formulation of a continuous soft-spin Hamiltonian. The method avoids step-size tuning and provides convergence guarantees in a specific parameter regime. Numerical results are performed on various Ising benchmarks, including very large instances.

Critical strengths
  • The method avoids the need to define a step size in soft-spin Ising relaxation by using a difference of convex optimization formulation.

  • The benchmark includes a good range of problem instances and relevant competing methods.

Critical weaknesses
  • Equation (4) is essentially the standard quartic double-well potential used in soft-spin Ising models. This is a very well established construction rather than a new decomposition.

  • Several propositions, particularly in section 2, state rather elementary properties with limited relevance to the actual optimization problem. For instance, proposition 2.3 assume that the minimum of the relaxed potential lies exactly on the binary hypercube, which is generally not expected.

  • The PSD condition required for convergence analysis imposes a large self-gain in the soft-spin Hamiltonian. This can favor a strongly multistable regime with many local minima corresponding to suboptimal configurations. The relevance of this convergence regime for finding good Ising solutions is therefore unclear.

  • The method does not provide any guarantee for escaping local minima, which is one of the main difficulties in soft-spin optimization.

  • Table 2 reports approximate ranges, making it difficult to assess whether the proposed methods consistently outperform competing methods. More detailed comparisons are available in appendix but are fragmented across different tables and figures.

Questions for authors
  • Do the best numerical results actually satisfy the strict DC condition required by the convergence proofs? How does solution quality change when crossing this threshold?

  • Does the large self-gain in the strict DC regime suppress spin flips and favor trapping in suboptimal local minima?

  • Beyond avoiding step-size tuning, what is the advantage over standard gradient descent with adaptive step size or implicit integration?

  • On the very large instances, are the benchmarks in a regime where simple gradient descent on the soft-spin Hamiltonian would already perform well ?

  • Could the authors provide a per instance-comparison with precise energies, runtimes, and statistical variability?

2 comments

We thank the reviewer for the detailed assessment and for recognizing the value of avoiding explicit step-size selection and evaluating the solver over a broad range of Ising problems.


W1. The quartic double-well potential is well established.

We agree that the quartic double-well potential in Equation (4) is well established in soft-spin Ising models, as acknowledged in Appendix D. We do not claim novelty for the potential or DCA itself. As discussed in W1 of Reviewer v1pn:

Our contribution is its computational specialization to Ising optimization. The DC formulation yields an exactly solvable separable convex subproblem, leading to an explicit cube-root update requiring only one matrix-vector multiplication and componentwise operations per iteration. Unlike numerical integration of continuous dynamics, DOCH requires no inner iterations, integration step-size tuning, or cooling schedule, and supports efficient GPU implementation.

We have now clarified that the novelty lies in the resulting algorithmic specialization, convergence analysis, and large-scale performance, rather than in the underlying potential or DC decomposition.


W2. Elementary propositions and the assumption in Proposition 2.3.

We agree that Propositions 2.1 and 2.2 establish elementary properties of the relaxation. Proposition 2.3 is a conditional result: it characterizes the relation to the discrete optimum when a global minimizer of the relaxed potential lies on the scaled binary hypercube. We do not assume or claim that this condition holds in general.

Our main theoretical contributions lie in Section 4 and Appendix F. We establish full-sequence convergence of DOCH (Theorem 4.5) and derive the sharp Lojasiewicz exponent θ=1/2\theta=1/2 under the stability conditions of Proposition 4.6, yielding linear convergence. For the nonmonotone ADOCH scheme, we establish finite-window stationarity and convergence guarantees (Proposition 4.7 and Theorem 4.8) using the quartic structure and finite critical set.

We have distinguished these main convergence results more clearly from the preliminary properties in Section 2 and clarified the conditional nature of Proposition 2.3 in the revised manuscript.


W3. Strict DC condition, large self-gain, and multistability.

We agree that excessively large self-gain can increase multistability and favor suboptimal local minima. However, the strict DC condition J+αI≻0J+\alpha I\succ0 only requires α>−λmin⁡(J)\alpha>-\lambda_{\min}(J), allowing α\alpha to remain close to the spectral threshold. Also, DOCH still permits spin flips when the coupling term (Jx)i(Jx)_i opposes and outweighs the self-gain αxi\alpha x_i.

The convergence regime is therefore not necessarily incompatible with good Ising solutions. Our small and moderate benchmarks, including Biq Mac instances, use parameters within the strict DC regime. Table 8 also demonstrates exact ground-state recovery with η>1\eta>1 on small planted instances, while showing good recovery with η=0.5\eta=0.5 outside this regime. Thus, the conditions that ensure convergence and those that favor solution quality need not coincide.

For large instances, accurate estimation of λmin⁡(J)\lambda_{\min}(J) is challenging. We therefore tune η\eta adaptively (Algorithm 9), using the spectral estimate in Appendix G (Eq. 82), rather than imposing excessive self-gain. Propositions F.2 and F.3 also establish boundedness outside the DC regime, while Proposition 4.6 provides a local stability criterion.


W4. No guarantee of escaping local minima.

We agree that DOCH does not guarantee escape from suboptimal local minima. Our convergence results establish convergence to critical points of the continuous Hamiltonian, not necessarily global Ising optima. This limitation is shared by other heuristic Ising solvers.

In practice, we address this through multiple random initializations and adaptive parameter tuning (Algorithm 9). Unlike annealing-based methods, DOCH requires no step-size or cooling-schedule tuning and primarily adjusts a single parameter η\eta, with β\beta determined by Eq. (81). Tables 4 and 5 demonstrate lower tuning costs than QQA and iSCO while maintaining competitive solution quality.

Thus, our contribution is not guaranteed escape from local minima, but a computationally efficient, easily tunable solver with convergence guarantees and favorable empirical runtime–quality trade-offs. We have clarified this limitation in the revised manuscript.

W5. Table 2 is too approximate, and the results are fragmented.

We agree that the approximate ranges in Table 2 limit direct comparison, while the detailed results are scattered across the appendix.

To improve clarity, we have now organized the results into (i) comparisons against certified or independently established reference values, (ii) equal-budget comparisons across solvers, and (iii) large-scale scalability experiments.

We will also move the most relevant per-instance results from the appendix to the main paper, enabling a clearer assessment of solution quality, runtime, and consistency across methods.


Q1. Do the best numerical results satisfy the strict DC condition? How does quality vary across the threshold?

As discussed in W3, the strict DC condition requires α>−λmin⁡(J)\alpha>-\lambda_{\min}(J). For small and moderate instances, including Biq Mac benchmarks, we compute the spectral threshold accurately, and the tuned η>1\eta>1 places the solver within the strict DC regime, where Theorem 4.5 applies. For ultra-large instances, however, we use a Wigner-inspired spectral estimate (Appendix G, Eq. 82), whose error may shift the actual threshold. We therefore cannot claim that all best numerical results satisfy the strict DC condition.

Regarding solution quality, Table 8 shows exact ground-state recovery both within the DC regime (η>1\eta>1) and outside it (η=0.5\eta=0.5). Thus, the convergence condition is sufficient for theoretical guarantees but not necessary for obtaining good discrete solutions. Propositions F.2 and F.3 also establish boundedness outside the DC regime.


Q2. Can large self-gain suppress spin flips and favor trapping?

We agree that excessive self-gain can suppress spin flips and increase trapping in suboptimal local minima. But, the strict DC condition does not prevent spin flips: the DOCH update permits a sign change whenever the opposing coupling term (Jx)i(Jx)_i outweighs the self-gain αxi\alpha x_i.

As discussed in W3 and Q1, we adaptively tune α\alpha through η\eta (Appendix G and Algorithm 9) to avoid unnecessarily large self-gain. Combined with multiple random initializations, this helps explore different solutions, although it does not guarantee escape from local minima.

Q3. What is the advantage over adaptive gradient descent or implicit integration?

DOCH's main advantage is its explicit, exactly solvable DC update. Each iteration requires only one matrix-vector multiplication and componentwise cube-root operations, with no inner optimization or line search. Adaptive gradient descent may require additional gradient evaluations, while implicit integration typically requires solving nonlinear equations. DOCH thus has a predictable per-iteration cost, with monotone descent and full-sequence convergence in the strict DC regime (Theorem 4.5) and local linear convergence under Proposition 4.6.

Figure 20 and Table 2 compare DOCH against GD and Adam on K2000K_{2000}, showing favorable runtime-quality trade-offs and substantially lower tuning costs (≈5\approx 5 s versus 1.3×1031.3\times10^3 s and 1.6×1031.6\times10^3 s, respectively). Comparisons with bSB and SimCIM (Figures 5 and 17) provide additional context.

Thus, the advantage extends beyond avoiding step-size tuning to computational efficiency, exact surrogate updates, and convergence guarantees.


Q4. Would simple gradient descent already perform well on the ultra-large instances?

We agree that GD may perform well on some structured ultra-large instances. However, the soft-spin Hamiltonian has a non-globally Lipschitz gradient (Section 3), making GD sensitive to step-size selection. In contrast, DOCH solves each convex surrogate exactly, requiring one matrix-vector multiplication and componentwise cube-root operations per iteration, without step-size tuning or inner optimization.

Figure 20 and Table 2 compare DOCH/ADOCH with GD and Adam on K2000K_{2000}, demonstrating favorable runtime–quality trade-offs and substantially lower tuning costs.

Reviewer_v1pnOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes DOCH, which is a GPU solver for Ising ground-state problems. It also proposes an accelerated variant, ADOCH. The spins are relaxed to real numbers, and a quartic term is added that pulls each variable toward a fixed magnitude. The paper proves convergence to a critical point of the relaxed function when a parameter exceeds a threshold set by the smallest eigenvalue of the coupling matrix. It reports favorable time–quality trade-offs against simulated annealing (SA), simulated bifurcation (bSB), simulated coherent Ising machines (SimCIM), QQA, iSCO and others on instances with 10³ to 10⁸ spins.

Critical strengths

The method is simple and it only needs one matrix-vector product per step. It is also implemented at impressive scales, up to a sparse 10⁸-spin instance on two GPUs. The paper is careful about the limits of its theory. The evaluations are relatively comprehensive, which includes an optimized SA comparison at equal time budget. The comparisons with the official QQA and FEM implementations are also included.

Critical weaknesses
  1. The core algorithm is not new. The relaxed function is the simulated-bifurcation potential at a fixed pump (Appendix D). DOCH is the standard difference-of-convex algorithm, and ADOCH is Algorithm 1 of Phan et al. (2018). The Łojasiewicz convergence argument follows known DCA results (e.g., Le Thi, Huynh and Pham Dinh, 2018).

  2. The β ablation contradicts the update rule. In DOCH, scaling β only rescales the iterates by a positive factor. So the signs and the fixed-point Jacobian do not depend on β, which is also confirmed in Fig. 3c. The β dependence claimed in Fig. 3b and Remark G.2 therefore needs further clarifications.

  3. The SA baseline is not fairly evaluated to be a meaningful comparison. As written, Algorithm 3 flips one random spin per iteration and recomputes the full energy after each flip, so its 1,000 iterations on K2000 do not even finish an entire sweep. On the two 10⁷- spin instances, its energy stays at zero for 17 hours (Fig. 6c) and over the whole run in Fig. 16. But Table 2 still reports these runs as SA’s results (e.g., “SA ≈ 0” at 10⁷ spins), which understates what a standard SA with full sweeps would achieve.

  4. The paper does not show how close DOCH gets to the best known solutions. Most results are only ratios to the best solver within the same comparison. Even when best known solutions are used, for example on G-set (Fig. 18), DOCH reaches only 90–94% of the best known values and is not consistently better than SimCIM or bSB.

  5. The timing of the largest run needs clarification. In Fig. 6c the curves end at about 8 hours for DOCH, 17 hours for the baselines and 25 hours for ADOCH. However, the text describes an 11-hour test. The curves can still be compared at common times, but the final energies are not equal-budget results. Furthermore, many comparisons stop after 100 iterations or about 0.1 s. The advantage could be shown at several common budgets, with each annealing schedule tuned for its budget.

  6. The performance is weak in some cases. On the planted 1,000-spin instance, ADOCH's best ratio is 1.000. But its mean energy is −5,000 against a ground state of −250,000. At 100 spins its mean is −680 against −2,500 (Table 8). Also, the success probabilities across starts could be reported alongside best ratios.

Questions for authors

Which η and q were used in each experiment? How do the methods perform when the theorems apply?

What explains the β dependence in Fig. 3b?

How do the results change with a properly configured SA and bSB, and against a strong Max- Cut heuristic?

What distribution defines the SK instances?

4 comments

We sincerely thank the reviewer for the careful and technically detailed assessment of our work, and particularly for recognizing the simplicity of the proposed solver, its scalability to 10810^8 spins, and the breadth of the benchmarking effort.


W1. Novelty of the Hamiltonian, DCA, ADOCH, and convergence analysis.

We agree that the quartic double-well potential, standard DCA, accelerated DCA, and Lojasiewicz-based convergence analysis are established ideas. We acknowledge these connections in Appendix D and Sections 3 and 4 and do not claim novelty for these individual ingredients.

Our contribution lies in their specialization to Ising optimization, the resulting computational efficiency, and the associated convergence guarantees. In particular:

  1. Efficient updates: Exploiting the separable quartic potential within the DC framework yields an explicit cube-root update requiring only one matrix-vector multiplication and component-wise operations per DOCH iteration. The update requires neither inner optimization nor tuning of step size or the cooling schedule, making it suitable for GPU parallelization.

  2. Convergence analysis: Beyond applying standard DCA results, we establish full-sequence convergence of DOCH (Theorem 4.5) and derive the sharp Lojasiewicz exponent θ=1/2\theta=1/2 under the stability conditions of Proposition 4.6, yielding linear convergence. For ADOCH, we establish finite-window stationarity and convergence guarantees (Proposition 4.7 and Theorem 4.8), using the quartic structure and finite critical set, with full-sequence convergence under the stated monotone-window condition.

  3. Large-scale performance: Our experiments demonstrate competitive solution quality and runtime on Ising problems with up to 10810^8 spins, highlighting the practical value of the resulting solver.

Thus, we do not claim that the underlying potential or DC algorithms are new. Rather, our contribution is an efficient Ising solver that combines explicit updates, problem-specific convergence analysis, efficient parameter tuning, and demonstrated large-scale performance. We have made this distinction clearer in the revised manuscript.


W2. Dependence on β\beta in Figure 3b and Remark G.2.

We agree that for fixed JJ, α\alpha, and identical initialization, varying β\beta only rescales the DOCH iterates, leaving their signs and the resulting Ising energies unchanged. In Figure 3b, however, although JJ is fixed, each value of γ\gamma uses independent random initializations and a separately tuned α\alpha (Algorithm 9). Thus, the observed energy variation arises from differences in initialization and adaptive parameter selection, not from an intrinsic dependence of the rounded Ising energy on β\beta. We have addressed this in detail in W1 of Reviewer c9Yn and have clarified the experimental protocol and interpretation of Figure 3b and Remark G.2 in the revised manuscript.


W3. Fairness of the simulated annealing (SA) baseline.

We agree that Algorithm 3, adapted from the CIM work of Inagaki et al. (2016), uses individual spin-flip attempts rather than full sweeps and does not represent optimized simulated annealing (SA). Its inclusion was intended primarily for comparison with CIM, not as a definitive SA benchmark.

To address this concern, we also evaluated the optimized SA implementation of Isakov et al. (2015) under equal wall-clock budgets. As reported in Appendix M.3 (Table 6), optimized SA completes approximately 21,500–44,000 full sweeps, compared with 2,700–3,600 DOCH updates. Despite this, DOCH achieves better objective values on all five tested instances. Table 7 further shows that DOCH achieves faster single-run recovery of certified global optima.

Regarding Table 2, the entry “SA ≈0\approx 0” reflects coarse rounding rather than an actual zero energy. The reported energies are scaled by 101010^{10}, while the SA energy is of order 10810^8, giving a normalized magnitude of approximately 10−210^{-2}. We have reported these values with greater precision to avoid confusion.

We acknowledge that the original SA results on ultra-large instances should not be taken as representative of optimized SA performance. We have clarified this limitation and distinguished the original CIM-oriented comparison from the optimized, equal-budget SA benchmarks in Tables 6 and 7, which provide a more meaningful assessment of DOCH's performance.

W4. Comparison with best-known solutions and strong MAX-CUT heuristics.

We agree that closeness to independently established best-known solutions is an important measure of solution quality. Our solver-relative ratios are intended to compare methods under common computational budgets, not to provide approximation guarantees or to claim proximity to global optima.

Figure 18 already uses known approximation guarantees or to claim G-set cut values (Ma & Hao, 2017) and reports mean performance over 100 random initializations after 5, 10, and 100 iterations. The reported 90–94% ratios therefore reflect average performance under limited iteration budgets, rather than the best cuts attainable by DOCH. We also acknowledge that DOCH and ADOCH do not consistently outperform bSB or SimCIM on these instances.

Our primary contribution is a general-purpose, step-size-independent, and scalable Ising solver with competitive runtime–quality trade-offs across diverse problem classes, rather than a specialized MAX-CUT method. We have clarified the distinction and the limitations of the G-set results in the revised manuscript.


W5. Clarification of large-scale runtime and equal-budget comparisons.

We acknowledge that Figure 6c presents runs with different stopping times, with a nominal budget of approximately 17 hours for the 10710^7-spin experiment. DOCH saturated within approximately 8 hours, while ADOCH was extended to 25 hours to assess longer-term behavior. We have clarified these runtimes in the revised manuscript.

Performance comparisons are appropriately made at common wall-clock times rather than at the curve endpoints. The annealing schedules were configured for the 17-hour budget, whereas DOCH/ADOCH require neither cooling schedules nor step-size tuning.

Tables 6 and 7 and Figures 7, 8, and 17 already provide complementary comparisons across computational budgets, including equal-wall-clock evaluations against optimized SA. We have also clarified the computational budgets in the short-run experiments and emphasized common-time comparisons in Figure 6c. We acknowledge that evaluating annealing baselines with schedules tuned separately for multiple budgets would provide a stronger assessment.

Our main empirical claim is therefore favorable runtime-solution-quality trade-offs and rapid convergence, rather than superiority based on unequal-budget final energies.


W6. Discrepancy between best and mean performance on planted instances.

We agree that ADOCH exhibits substantial variability on the planted rank-one signed-bipartite instances in Table 8. Although it reaches the certified optimum in its best run, its mean energies of −680-680 and −5,000-5,000 at n=100n=100 and n=1000n=1000, respectively, are far from the corresponding ground-state energies. Thus, a best ratio of 1.000 does not imply reliable recovery across random initializations.

This behavior contrasts with DOCH on the same instances. DOCH recovers the certified optimum in every run at n=100n=100 and achieves a mean energy of −247,499.84-247,499.84 against the optimum of −250,000-250,000 at n=1000n=1000. On the broader Ising and MAX-CUT benchmarks (Tables 4 and 5), ADOCH also shows more consistent performance, with mean objective ratios of 0.984–0.994 over 100 independent runs. Nevertheless, these results do not diminish the poor average performance observed in Table 8.

Q1. Which η\eta and qq were used, and when do the theorems apply?

As detailed in Appendix G (Eq. 81), we set α=ηλ^−\alpha=\eta\widehat{\lambda}_{-}, with η∈(0,2]\eta\in(0,2] selected by adaptive tuning (Algorithm 9). For ADOCH, we use q=2q=2 in the ultra-large experiments (Figures 6c, 6d, and 16), q≤5q\leq5 for other instances with n≥104n\geq10^4, and q∈{2,…,10}q\in\{2,\ldots,10\} for smaller instances.

Regarding performance within the theoretical regime, small and moderate instances, including Biq Mac benchmarks, use η>1\eta>1 with accurately computed spectral thresholds, ensuring the strict DC condition. Table 7 demonstrates rapid recovery of certified optima on small benchmarks. For ultra-large instances, we use a Wigner-inspired spectral estimate (Appendix G, Eq. 82), whose error may place some tuned settings outside the strict DC regime.

Theorem 4.5 guarantees DOCH convergence within the DC regime. For ADOCH, Proposition 4.7 establishes finite-window stationarity, while Theorem 4.8 guarantees full-sequence convergence under its q=0q=0 condition. Outside the DC regime, Propositions F.2 and F.3 establish boundedness, and Proposition 4.6 provides a local stability criterion.


Q2. What explains the β\beta-dependence?

As explained in W2 and (in detail) in W1 of Reviewer c9Yn, the variation in Figure 3b arises from independent random initializations and separate adaptive tuning of α\alpha for each γ\gamma, not from an intrinsic dependence of the sign-rounded Ising energy on β\beta. We have clarified this in the revised manuscript.


Q3. How do the methods compare with properly configured SA, bSB, and a strong MAX-CUT heuristic?

We addressed the SA concern by adding optimized SA (Isakov et al., 2015) under equal wall-clock budgets (0.50.5–22 s). As shown in Table 6, DOCH outperforms optimized SA on all five instances, achieving higher objective ratios despite using only 2,7002,700 to 3,6003,600 updates, compared with 21,50021,500 to 44,00044{,}000 SA sweeps. Table 7 further shows that DOCH recovers certified optima faster.

For bSB, SimCIM, and SIA, we use adaptive parameter tuning (Algorithm 9) and validate our implementations against published K2000K_{2000} results, with deviations of approximately 0.50.5–3%3\%. Figure 18 compares G-set performance against published best-known cuts, where DOCH does not consistently outperform specialized methods.

We acknowledge that direct comparisons with stronger MAX-CUT heuristics would further strengthen the evaluation. Our contribution is a general-purpose, step-size-independent Ising solver with competitive runtime-quality trade-offs, rather than consistent superiority over specialized MAX-CUT methods.


Q4. What distribution defines the SK instances?

We confirm that the supplied SK generator uses J=(G+G⊤)/2J=(G+G^\top)/2, where GG has independent standard Gaussian entries, with Jii=0J_{ii}=0. Thus, Jij∼N(0,1/2)J_{ij}\sim\mathcal N(0,1/2) for i≠ji\neq j, rather than the conventional N(0,1/n)\mathcal N(0,1/n) normalization. We have explicitly stated the coupling normalization used in each experiment and clarified this distinction in the revised manuscript.

Reviewer_v1pnOpenReview ↗

Thanks and sorry for the delay

Thank you for the response. However, my major concerns remain. Table 8 uses η of 0.5 and 0.01, which is outside the region of the theorem. Also, every ADOCH run uses q > 0, but Theorem 4.8 requires q = 0. The basic SA rows in Table 2 are still not informative enough, and there is no comparison with the best-known values or a strong Max-Cut heuristic. I choose to keep my score.

Comments on the paper

2 comments

We thank the reviewer for the thoughtful assessment and appreciate the acknowledgment that several earlier concerns have been clarified. We appreciate the remaining concerns regarding novelty, theoretical relevance, and empirical performance, and would like to clarify the scope of our contributions.


1. Regarding novelty, we agree that the quartic double-well potential and the underlying steady-state equations are well established. Our contribution lies in an efficient optimization scheme tailored to Ising structure, rather than a new physical model. DOCH exploits the DC formulation to obtain an explicit, exactly solvable update requiring only one matrix-vector multiplication and component-wise cube-root operations per iteration, without inner optimization, integration step-size tuning, or cooling schedules. Importantly, the resulting computational efficiency, simple parameter tuning, and adaptive termination constitute key practical advantages over conventional numerical integration and annealing-based approaches.


2. Regarding theoretical relevance, we acknowledge that the Lojasiewicz exponent θ=1/2\theta=1/2 is standard near nondegenerate local minima. Establishing this exponent under explicit stability conditions yields local linear convergence, providing a sharper rate than a general asymptotic convergence guarantee. Together with full-sequence convergence of DOCH (Theorem 4.5) and finite-window stationarity guarantees for ADOCH (Proposition 4.7), these results characterize the convergence behavior of the proposed iterations.


3. Regarding local minima, we agree that ensuring high-quality local solutions remains challenging, as it does for other heuristic Ising solvers, particularly the annealing-based methods. In practice, hyperparameter tuning is an important means of addressing this challenge. However, annealing-based methods typically require repeated runs with varying cooling schedules when tuning parameters, whereas DOCH primarily tunes a single parameter, η\eta, making the search substantially more efficient (Tables 4 and 5). The strict DC condition permits α\alpha close to the spectral threshold, and our adaptive tuning balances solution quality with the theoretical convergence regime. Figure 3d demonstrates an efficient relative-error stopping criterion that allows DOCH to detect saturation without a predetermined runtime budget or repeated explicit Ising-energy evaluations, unlike methods that require a fixed cooling schedule.


4. Regarding empirical performance, we agree that G-set results do not establish superiority over specialized MAX-CUT solvers, including dSBM. However, our broader benchmarks demonstrate competitive and, in several tested instances, superior runtime-quality trade-offs compared with established solvers. In particular, DOCH achieves better objective values than optimized SA on all five equal-budget instances (Table 6), with faster certified-optimum recovery (Table 7). Comparisons with GD, Adam, QQA, iSCO, bSB, and SimCIM provide further evidence of computational efficiency, while scalability experiments extend to 10810^8 spins.


Thus, our central contribution is not merely another numerical method for the same steady-state equations, but a computationally efficient, easily tunable, and adaptively terminating Ising solver with rigorous convergence properties and demonstrated large-scale performance.

The authors acknowledge some of our concerns about novelty, relevance of the theory, and limits of performance against SOTA, so we will maintain our score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.