Pith. sign in

REVIEW 3 major objections 6 minor 24 references

Analysis of Higher-Order Ising Hamiltonians

T0 review · 3 major / 6 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper establishes that symmetric higher-order Ising Hamiltonians can be evaluated in $O(|e|^2)$ time via convolution, and that two cumulative convolution passes make every exact partial derivative cost one additional convolution.

desk verdict Useful convolution trick and an honest empirical comparison, but the central gradient formula has an off-by-one index error and the Type II relaxation theorem only holds for p=1. read the letter →

arxiv 2412.13489 v1 pith:6XEYGQCG submitted 2024-12-18 cs.AI cond-mat.stat-mechphysics.comp-phquant-ph

Yunuo Cen , Zhiwei Zhang , Zixuan Wang , Yimin Wang , Xuanyao Fong This is my paper · ORCID
classification cs.AIcond-mat.stat-mechphysics.comp-phquant-ph
keywords higher-orderIsingmodelmachineWalsh-FourierexpansionsymmetricBooleanfunctionsconvolutionHamiltonianrelaxationparitylearningwitherrorgradientdescent
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

IsingSim is a simulator for higher-order Ising Hamiltonians, energy functions whose terms couple arbitrarily many binary spins at once, and this paper supplies the theoretical core that makes such simulation scalable. The central claim is that for symmetric constraints, the Walsh-Fourier expansion of a hyperedge can be evaluated by convolutions of two-term sequences, lowering the cost from $O(2^{|e|})$ to $O(|e|^2)$, and that the same convolution machinery yields exact partial derivatives with only one additional convolution after two cumulative passes. The paper further claims that the standard continuous relaxations of the Hamiltonian agree with the original Boolean problem at their global minima, so gradient descent on the relaxed landscape should find satisfying assignments, and that in experiments on parity learning with error, the plain hypercube relaxation outperforms the two physics-inspired relaxations. A sympathetic reader would care because higher-order Ising models encode industrial constraints compactly but lack efficient hardware or algorithms; this framework gives a way to study their behavior and a blueprint for building faster higher-order Ising machines.

What carries the argument

The carrying object is the Walsh-Fourier expansion of a Boolean hyperedge function, a unique multilinear polynomial that agrees with the function on all $\{-1,1\}$ assignments. For a symmetric constraint, the expansion's coefficients depend only on the size of the monomial, so the polynomial can be assembled as a weighted sum of elementary symmetric functions. The paper computes those elementary symmetric functions as a convolution of $|e|$ two-term sequences $[a_j, 1]$; retaining intermediate results in forward order, called $CC_{\text{seq}}$, and reverse order, called $CC_{\text{rev}}$, lets every partial derivative be read off as one more convolution. This two-pass cumulative convolution is the mechanism that makes $O(|e|^2)$ evaluation and near-free exact gradients possible.

What would settle it

Take a small symmetric constraint such as the four-variable cardinality constraint from the paper's Example 2, form the Type II relaxed Hamiltonian with $p = 1$, and numerically search for a point inside the box whose value is below $-\sum_e w_e - n$; finding one would refute the Type II relaxation theorem, while finding none on many random restarts would support it.

Watch

Extended reading notes

Core claim

The central claim is that a higher-order Ising Hamiltonian built from symmetric Boolean constraints can be simulated without exponential cost. Using the Walsh-Fourier expansion, each hyperedge becomes a unique multilinear polynomial; when the constraint is symmetric, the coefficients depend only on monomial size, so the evaluation reduces to a convolution of $|e|$ two-term sequences $[a_j, 1]$ and costs $O(|e|^2)$ instead of $O(2^{|e|})$ (Corollary 3). By keeping the intermediate convolution results in forward and reverse order, the partial derivative with respect to any one spin is obtained with a single additional convolution (Corollary 4), so exact gradient descent becomes computationally feasible. The paper also claims that the standard continuous relaxations, the hypercube, intrinsic locking, and injection locking, have global minima that match the Boolean satisfying assignments according to Theorem 2 and Corollaries 1 and 2, and reports experiments on parity learning with error showing that the hypercube relaxation has the highest success rate, with a weak-convexity explanation for that ranking.

Load-bearing premise

The framework assumes that the continuous relaxations' global minima coincide exactly with the Boolean satisfying assignments; if a relaxed Hamiltonian has an interior minimum lower than the discrete minimum, gradient descent can land on a point that is not a solution.

Editorial extensions

If this is right

  • Corollary 3 implies that any higher-order Ising simulator for symmetric constraints can replace exponential hyperedge evaluation with quadratic evaluation, so hyperedges with dozens of spins become practical to simulate.
  • Corollary 4 gives hardware designers a direct recipe: two cumulative convolution passes for the whole hyperedge, then one convolution per spin for the gradient, a structure that can be mapped to digital accelerators or analog arrays.
  • The relaxation theorems say that whenever the continuous minimum equals the Boolean minimum, gradient descent on any of the three landscapes is in principle a legitimate solver, not just a heuristic.
  • The weak-convexity analysis suggests a ranking of relaxation difficulty, with Type I easiest and Type III hardest, which can guide which physical Ising machine design is worth building for a given class of constraints.
  • The behavior of the proximal-style gradient estimator shows that global-minimum-finding gradients work on small problems but become impractical at higher dimensions, pointing toward hybrid local-global strategies at scale.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • One testable extension is to group nearly symmetric constraints into symmetric blocks; if the convolution speedup survives grouping, the practical range of hyperedge sizes could grow well beyond the paper's benchmarks.
  • Because the Type II relaxation argument depends on a linear combination of minima-preserving functions retaining those minima, checking this property on small random formulas would clarify exactly which relaxation guarantees hold beyond the paper's examples.
  • The reported Type I advantage suggests that hardware with simple hypercube coupling may be preferable to designs that add locking terms, an implication the paper leaves for designers to test on other benchmarks.
  • The framework's decoupling of spins from gradients means the same Hamiltonian could be simulated with new hardware-inspired update rules, such as noise-injected or analog-gradient rules, without changing the evaluation machinery.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. This paper proposes a theoretical and experimental framework, IsingSim, for simulating higher-order Ising Hamiltonians. It defines a higher-order Ising model whose hyperedges encode Boolean constraints, uses Walsh-Fourier expansions to obtain multilinear polynomial relaxations, and presents three continuous relaxation schemes: Type I (hypercube relaxation), Type II (DOPO-like intrinsic locking), and Type III (oscillator-based injection locking). The authors derive a symmetric-FE evaluation scheme using convolution (Corollary 3), a cumulative-convolution gradient scheme (Corollary 4), and a Moreau-envelope gradient estimator. Experiments on parity-learning-with-error instances compare three spin types and three gradient types, reporting success rates and model-size reductions. The paper concludes that the framework can guide higher-order Ising machine design.

Significance. The paper formalizes higher-order Ising Hamiltonians and gives a clean algebraic treatment of symmetric constraints; Corollary 3's O(|e|^2) evaluation via convolution is correct and useful, and the PLE benchmark comparison of three relaxation geometries is a reasonable proof-of-concept. The central acceleration and relaxation-equivalence claims, however, rest on Corollaries 1 and 4, both of which contain mathematical errors as written; because these corollaries are load-bearing for the paper's main claims, the current version does not establish the framework's validity. The paper would be significantly strengthened by correcting these statements and by providing runtime comparisons rather than only success rates.

major comments (3)
  1. [II-C, Corollary 1] Eq. (3) is false for p ≠ 1. The locking term a_i^4 − 2p a_i^2 has minimum −p^2 at a_i = ±√p, so the left side of Eq. (3) is generally not −Σ w_e − n: for example, with H = x1 x2, n = 2, p = 4, the point (2, −2) gives x1 x2 + (16−32) + (16−32) = −36, while the claimed minimum is −3. The proof's assertion that "a function retains the minima when it is a linear combination of the functions with the same minima" is false in general (e.g., x^2 and 2x^2 have the same global minimum, but x^2 − 2x^2 = −x^2 does not). For p = 1 the claim can be proved by a separate argument, since the locking term is then a nonnegative potential vanishing exactly on {±1}^n and the Type I relaxation already places the continuous minimum at the vertices; that argument is not given. The Type II relaxation as stated is therefore not a valid continuous relaxation except for p = 1.
  2. [II-E1, Corollary 4] Eq. (6) has an index-shift error. Differentiating f_e(a) = Σ_{i=0}^d \hat f_e(i) e_i(a) gives ∂f_e/∂a_j = Σ_{r=0}^{d−1} \hat f_e(r+1) e_r(a_{\ne j}); Eq. (6) instead sums \hat f_e(r) e_r(a_{\ne j}). The same error appears in the cumulative-convolution formula in the following paragraph. Concretely, for f(x1, x2) = x1 x2, the only nonzero coefficient is \hat f(2) = 1; Eq. (6) returns 0 for ∂f/∂x1, whereas the true derivative is x2. Thus the cumulative-convolution gradient formula does not compute gradients of the FE Hamiltonian as written, and the claimed bidirectional acceleration of gradient computation is not established. A corrected coefficient index may salvage the scheme, but the formal claim must be revised.
  3. [III and Abstract] The abstract and conclusion state that IsingSim "significantly accelerate[s] the simulation speed", but no runtime measurements or baselines are reported. Table I reports model sizes and Fig. 3 reports success rates, but there is no wall-clock comparison of the convolution-based evaluation against the naive O(2^{|e|}) evaluation, nor against other higher-order Ising solvers. The complexity reduction in Corollary 3 is theoretical; an empirical runtime comparison is needed to support the speed claim. In addition, the experimental section does not state how success rates are defined or provide error bars over the 100 trials per instance, which limits the strength of the performance conclusions.
minor comments (6)
  1. [II-C, Corollary 2] The proof says "minima of H(cos(a))" but the function in Eq. (4) is H(sin(a)); this typo should be corrected.
  2. [II-D, Corollary 3] The notation \bigcirc_{j∈e}[a_j,1] and the sentence "N denotes the convolution of |e| sequences" are not formally defined; please define the convolution operator and the indexing of the result entries explicitly.
  3. [Definition 1] The Boolean formula is written F = V_{c∈C} c; the conjunction symbol should be \wedge, and the term "hybrid constraint" should be explicitly defined.
  4. [III-A] The text says "type-II Ising spins at the same initial point will converge to a local minimum near (1, 1)", but for p = 1 the locking potential minima are at ±1; clarify the convergence points shown in Fig. 2b.
  5. [Table I] The columns |V_2| and |E_2| contain non-integer values; indicate whether these are averages over the generated instances.
  6. [References] Reference [14] is cited with a URL only; provide the publication status or a stable DOI if available.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the core derivations are algebraic and parameter-free, and the self-citations are attribution/background rather than load-bearing.

full rationale

IsingSim's derivation chain starts from the standard Walsh–Fourier expansion (Theorem 1, cited to O'Donnell) and Lemma 1, which defines the Boolean minimum of the Hamiltonian as -sum w_e. Corollary 3 is a regrouping of the Fourier expansion for symmetric constraints using convolution, and Corollary 4 is intended to be the derivative of Eq. (5); both are parameter-free algebraic identities, not fitted inputs renamed as predictions. The continuous-relaxation theorems cite [1] and [16], which include present authors, but the proof of Theorem 2 is explicitly by the maximum principle [17], an external mathematical fact, and the Type II/III locking terms are imported from external physics papers [10], [11]. Thus the self-citations do not supply the load-bearing content. The manuscript does contain formal gaps—Corollary 1's assertion that a linear combination of functions sharing the same minima retains those minima is false in general, and Eq. (6) appears to use \hat f_e(i) where differentiation of Eq. (5) requires \hat f_e(i+1)—but these are correctness/omitted-proof concerns, not circularity by construction. No self-definitional, fitted-input-called-prediction, uniqueness-imported-from-authors, or ansatz-smuggled-via-citation pattern is present.

Assumptions & free parameters 4 free parameters · 6 assumptions · 0 invented entities

The central efficiency claim rests on standard FE theory plus a new convolution trick; no fitted constants appear in the derivations. The main unexamined assumptions are the correctness of the relaxation equivalence for Type II with general p, the transfer from continuous gradient dynamics to physical Ising machines, and the heuristic weak-convexity explanation of performance ordering.

free parameters (4)
  • Type II locking strength p = 1
    Corollary 1 states p>0 but the RHS -sum w - n only matches the minimum value when p=1; experiments use p=1.
  • ADAM optimizer settings = lr=0.05 for gradient descent, lr=1 for Moreau gradient; beta1=0.9, beta2=0.999
    Chosen by hand; the learning rate change for the Moreau gradient is justified only by slower convergence, and no sensitivity analysis is reported.
  • Moreau envelope estimator parameters = alpha=delta=t=1; 1000 samples per gradient
    Chosen by hand; the paper notes sample count grows with problem size, so the n=8-only results are not directly comparable to larger instances.
  • Hyperedge weights = w_e = |e|
    Chosen by hand for PLE instances; no study of weight sensitivity, and weights affect the landscape and success rates.
assumptions (6)
  • standard math Walsh-Fourier expansion of a Boolean function into a unique multilinear polynomial exists (Theorem 1).
    Standard result in Boolean function analysis, cited to O'Donnell [15].
  • standard math A multilinear (harmonic) function on the hypercube attains its extrema on the boundary (maximum principle).
    Used in Theorem 2 proof and hence in all three relaxation equivalence claims.
  • ad hoc to paper A linear combination of functions with the same global minima has the same global minima.
    Stated in Corollary 1 proof; false in general, and the correct argument for p=1 (lower bounds H >= -sum w and second term >= -1) is not provided.
  • standard math The Moreau envelope gradient estimator (Proposition 1) provides a usable descent direction with finite samples.
    Taken from Osher, Heaton, Wu Fung [18]; its practical effectiveness for these Hamiltonians is only empirically tested on n=8.
  • domain assumption The weak-convexity parameters rho1 < rho2 < rho3 explain the observed performance ordering of Type I, II, III.
    The Hessian bounds are stated without derivation, and the interpretation that smaller rho implies better ADAM success is heuristic.
  • domain assumption Continuous gradient/ADAM dynamics on the relaxed Hamiltonian model the behavior of physical Ising machines.
    The paper's design guidance for hardware relies on this transfer, but no physical device or hardware model is validated.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Analysis of Higher-Order Ising Hamiltonians." pith.science (2026). https://pith.science/paper/6XEYGQCG

@misc{pith2026241213489,
  author       = {Pith},
  title        = {Pith review of: Analysis of Higher-Order Ising Hamiltonians},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6XEYGQCG}},
  note         = {Machine review of arXiv:2412.13489}
}
read the original abstract

It is challenging to scale Ising machines for industrial-level problems due to algorithm or hardware limitations. Although higher-order Ising models provide a more compact encoding, they are, however, hard to physically implement. This work proposes a theoretical framework of a higher-order Ising simulator, IsingSim. The Ising spins and gradients in IsingSim are decoupled and self-customizable. We significantly accelerate the simulation speed via a bidirectional approach for differentiating the hyperedge functions. Our proof-of-concept implementation verifies the theoretical framework by simulating the Ising spins with exact and approximate gradients. Experiment results show that our novel framework can be a useful tool for providing design guidelines for higher-order Ising machines.

Figures

Figures reproduced from arXiv: 2412.13489 by the authors.

Figure 1
Figure 1. Left. Encoding a combinatorial problem, e.g., parity learning with error problem, into a higher-order Ising model. Right. The overall flow of IsingSim. Example 1. Given a set of variables x ∈ {0, 1} 4 , and auxiliary variables y ∈ {0, 1} 3 . Finding an assignment that satisfies the cardinality x1 + x2 + x3 + x4 ≥ 2 can be encoded into solving the minima of a discrete function minx,y(y2+y3+y4−1)2+(2y2+3y3+4y4−x1−x2−x… view at source ↗
Figure 2
Figure 2. The gradient descent trajectories of two coupled [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 18 canonical work pages

  1. [1]

    Fouriersat: A fourier expansion-based algebraic framework for solving hybrid boolean constraints,

    A. Kyrillidis, A. Shrivastava, M. Vardi, and Z. Zhang, “Fouriersat: A fourier expansion-based algebraic framework for solving hybrid boolean constraints,” in Proceedings of the AAAI Conference on Artificial Intel- ligence, vol. 34, no. 02, 2020, pp. 1552–1560

    work page 2020

  2. [2]

    A scalable shannon entropy estimator,

    P. Golia, B. Juba, and K. S. Meel, “A scalable shannon entropy estimator,” in International Conference on Computer Aided Verification. Springer, 2022, pp. 363–384

    work page 2022

  3. [3]

    Fastpass: Fast pin access analysis with incremental sat solving,

    F. Wang, J. Liu, and E. F. Young, “Fastpass: Fast pin access analysis with incremental sat solving,” in Proceedings of the 2023 International Symposium on Physical Design , 2023, pp. 9–16

    work page 2023

  4. [4]

    Solving quantum-inspired perfect matching problems via tutte’s theorem-based hybrid boolean constraints,

    M. Y . Vardi and Z. Zhang, “Solving quantum-inspired perfect matching problems via tutte’s theorem-based hybrid boolean constraints,” arXiv preprint arXiv:2301.09833, 2023

    arXiv 2023

  5. [5]

    Ising formulations of many np problems,

    A. Lucas, “Ising formulations of many np problems,” Frontiers in physics, vol. 2, p. 5, 2014

    2014

  6. [6]

    Perspectives of quantum annealing: Methods and implementations,

    P. Hauke, H. G. Katzgraber, W. Lechner, H. Nishimori, and W. D. Oliver, “Perspectives of quantum annealing: Methods and implementations,” Reports on Progress in Physics , vol. 83, no. 5, p. 054401, 2020

    work page 2020

  7. [7]

    Integer factorization using stochastic magnetic tunnel junctions,

    W. A. Borders, A. Z. Pervaiz, S. Fukami, K. Y . Camsari, H. Ohno, and S. Datta, “Integer factorization using stochastic magnetic tunnel junctions,” Nature, vol. 573, no. 7774, pp. 390–393, 2019

    work page 2019

  8. [8]

    Massively parallel probabilistic computing with sparse ising machines,

    N. A. Aadit, A. Grimaldi, M. Carpentieri, L. Theogarajan, J. M. Martinis, G. Finocchio, and K. Y . Camsari, “Massively parallel probabilistic computing with sparse ising machines,” Nature Electronics, vol. 5, no. 7, pp. 460–468, 2022

    2022

Show all 24 references
  1. [9]

    Energy-efficient superparamagnetic ising machine and its application to traveling salesman problems,

    J. Si, S. Yang, Y . Cen, J. Chen, Y . Huang, Z. Yao, D.-J. Kim, K. Cai, J. Yoo, X. Fong et al., “Energy-efficient superparamagnetic ising machine and its application to traveling salesman problems,” Nature Communications, vol. 15, no. 1, p. 3457, 2024

    2024

  2. [10]

    Net- work of time-multiplexed optical parametric oscillators as a coherent ising machine,

    A. Marandi, Z. Wang, K. Takata, R. L. Byer, and Y . Yamamoto, “Net- work of time-multiplexed optical parametric oscillators as a coherent ising machine,” Nature Photonics, vol. 8, no. 12, pp. 937–942, 2014

    2014

  3. [11]

    Solving combinatorial optimisation problems using oscillator based ising machines,

    T. Wang, L. Wu, P. Nobel, and J. Roychowdhury, “Solving combinatorial optimisation problems using oscillator based ising machines,” Natural Computing, vol. 20, no. 2, pp. 287–306, 2021

    2021

  4. [12]

    Design framework for ising machines with bistable latch-based spins and all-to-all resistive coupling,

    Y . Wang, Y . Cen, and X. Fong, “Design framework for ising machines with bistable latch-based spins and all-to-all resistive coupling,” in 2024 IEEE International Symposium on Circuits and Systems (ISCAS). IEEE, 2024, pp. 1–5

    2024

  5. [13]

    Efficient optimization with higher-order ising machines,

    C. Bybee, D. Kleyko, D. E. Nikonov, A. Khosrowshahi, B. A. Olshausen, and F. T. Sommer, “Efficient optimization with higher-order ising machines,” Nature Communications, vol. 14, no. 1, p. 6033, 2023

    2023

  6. [14]

    Unified framework for efficient high-order ising machine hardware im- plementations,

    T. Bhattacharya, G. Hutchinson, and D. B. Strukov, “Unified framework for efficient high-order ising machine hardware im- plementations,” preprint, avaiable at: https://web. ece. ucsb. edu/˜ strukov/papers/2024/IM2024. pdf

    2024

  7. [15]

    Analysis of boolean functions,

    R. O’Donnell, “Analysis of boolean functions,” arXiv preprint arXiv:2105.10386, 2021

    2021 arXiv

  8. [16]

    Massively parallel continuous local search for hybrid sat solving on gpus,

    Y . Cen, Z. Zhang, and X. Fong, “Massively parallel continuous local search for hybrid sat solving on gpus,” arXiv preprint arXiv:2308.15020, 2023

    2023 arXiv

  9. [17]

    M. H. Protter and H. F. Weinberger, Maximum principles in differential equations. Springer Science & Business Media, 2012

    2012

  10. [18]

    A hamilton–jacobi-based proximal operator,

    S. Osher, H. Heaton, and S. Wu Fung, “A hamilton–jacobi-based proximal operator,” Proceedings of the National Academy of Sciences , vol. 120, no. 14, p. e2220469120, 2023

    2023

  11. [19]

    Adam: A method for stochastic optimization,

    D. P. Kingma, “Adam: A method for stochastic optimization,” arXiv preprint arXiv:1412.6980, 2014

    2014 arXiv

  12. [20]

    The minimal disagreement parity problem as a hard satisfiability problem,

    J. M. Crawford, M. J. Kearns, and R. E. Schapire, “The minimal disagreement parity problem as a hard satisfiability problem,” Compu- tational Intell. Research Lab and AT&T Bell Labs TR , 1994

    1994

  13. [21]

    Cryptography from learning parity with noise,

    K. Pietrzak, “Cryptography from learning parity with noise,” in In- ternational Conference on Current Trends in Theory and Practice of Computer Science. Springer, 2012, pp. 99–114

    2012

  14. [22]

    Satlib: An online resource for research on sat,

    H. H. Hoos and T. St ¨utzle, “Satlib: An online resource for research on sat,” Sat, vol. 2000, pp. 283–292, 2000

    2000

  15. [23]

    Mscg: Robust core- guided maxsat solving,

    A. Morgado, A. Ignatiev, and J. Marques-Silva, “Mscg: Robust core- guided maxsat solving,” Journal on Satisfiability, Boolean Modeling and Computation, vol. 9, no. 1, pp. 129–134, 2014

    2014

  16. [24]

    Global solutions to nonconvex problems by evolution of hamilton-jacobi pdes,

    H. Heaton, S. Wu Fung, and S. Osher, “Global solutions to nonconvex problems by evolution of hamilton-jacobi pdes,” Communications on Applied Mathematics and Computation, vol. 6, no. 2, pp. 790–810, 2024

    2024

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.