A Continuous Energy Ising Machine Leveraging Difference-of-Convex Programming

• URL: http://arxiv.org/abs/2509.01928v1
• Date: Tue, 02 Sep 2025 03:51:51 GMT
• Title: A Continuous Energy Ising Machine Leveraging Difference-of-Convex Programming
• Authors: Debraj Banerjee, Santanu Mahapatra, Kunal Narayan Chaudhury,
• Abstract summary: We implement our Ising solver across a range of GPU platforms.<n>We demonstrate it consistently outperforms existing solvers across problem sizes ranging from small ($103$ spins) to ultra-large ($108$ spins)
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many combinatorial optimization problems can be reformulated as the task of finding the ground state of a physical system, such as the Ising model. Most existing Ising solvers are inspired by simulated annealing. Although annealing techniques offer scalability, they lack convergence guarantees and are sensitive to the cooling schedule. We propose to solve the Ising problem by relaxing the binary spins to continuous variables and introducing a potential function (attractor) that steers the solution toward binary spin configurations. The resulting Hamiltonian can be expressed as a difference of convex functions, enabling the design of efficient iterative algorithms that require a single matrix-vector multiplication per iteration and are backed by convergence guarantees. We implement our Ising solver across a range of GPU platforms: from edge devices to high-performance computing clusters and demonstrate that it consistently outperforms existing solvers across problem sizes ranging from small ($10^3$ spins) to ultra-large ($10^8$ spins).

Related papers

• DInf-Grid: A Neural Differential Equation Solver with Differentiable Feature Grids [73.28614344779076]
  We present a differentiable grid-based representation for efficiently solving differential equations (DEs)<n>Our results demonstrate a 5-20x speed-up over coordinate-based methods, solving differential equations in seconds or minutes while maintaining comparable accuracy and compactness.
  arXiv  Detail & Related papers  (2026-01-15T18:59:57Z)
• Fast, Convex and Conditioned Network for Multi-Fidelity Vectors and Stiff Univariate Differential Equations [0.0]
  Accuracy in neural PDE solvers often breaks down due to poor optimisation caused by ill-conditioning.<n>We show that components in governing equations can produce highly ill-conditioned activation vectors.<n>We introduce Shifted Gaussian, a simple yet effective activation filtering step that increases matrix rank and expressivity while preserving convexity.
  arXiv  Detail & Related papers  (2025-08-08T00:51:38Z)
• Efficient Optimization Accelerator Framework for Multistate Ising Problems [0.0]
  Ising machines are a prominent class of hardware architectures that aim to solve NP-hard optimization problems.<n>We model the spin interactions as a generalized logic function to significantly reduce the exploration space.<n>We also design a 1024-neuron all-to-all connected probabilistic Ising accelerator that shows up to 10000x performance acceleration.
  arXiv  Detail & Related papers  (2025-05-26T17:23:47Z)
• $\ell_0$-Regularized Quadratic Surface Support Vector Machines [0.0]
  Kernel-free quadratic surface support vector machines have recently gained traction due to their flexibility in modeling nonlinear decision boundaries without relying on kernel functions.<n>We propose a sparse variant of the QSVM by enforcing a cardinality constraint on the model parameters.<n>We validate our approach on several real-world datasets, demonstrating its ability to reduce overfitting while maintaining strong classification performance.
  arXiv  Detail & Related papers  (2025-01-20T04:26:34Z)
• Limitations of tensor network approaches for optimization and sampling: A comparison to quantum and classical Ising machines [0.0]
  We develop a tensor network (TN) based algorithm to reveal the low-energy spectrum of Ising spin-glass systems.<n>Our deterministic approach combines a branch-and-bound search strategy with an approximate calculation of marginals via TN contractions.<n>We benchmark our approach on random problems defined on Pegasus and Zephyr graphs with up to a few thousand spins.
  arXiv  Detail & Related papers  (2024-11-25T14:35:14Z)
• Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching [53.91395791840179]
  We present Unified Spectral Bundling with Sketching (USBS), a provably correct, fast and scalable algorithm for solving massive SDPs. USBS provides a 500x speed-up over the state-of-the-art scalable SDP solver on an instance with over 2 billion decision variables.
  arXiv  Detail & Related papers  (2023-12-19T02:27:22Z)
• Differentiable and accelerated spherical harmonic and Wigner transforms [7.636068929252914]
  Modelling and analysis of spherical data requires efficient computation of gradients for machine learning or other differentiable programming tasks.<n>We develop novel algorithms for accelerated and differentiable computation of generalised Fourier transforms on the sphere.<n>We observe up to a 400-fold acceleration when benchmarked against alternative C codes.
  arXiv  Detail & Related papers  (2023-11-24T18:59:04Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching [55.28394191394675]
  We develop an adaptive inexact Newton method for equality-constrained nonlinear, nonIBS optimization problems. We demonstrate the superior performance of our method on benchmark nonlinear problems, constrained logistic regression with data from LVM, and a PDE-constrained problem.
  arXiv  Detail & Related papers  (2023-05-28T06:33:37Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  In many applications, we need algorithms which can align partially overlapping point sets are invariant to the corresponding corresponding RPM algorithm. We first show that the objective is a cubic bound function. We then utilize the convex envelopes of trilinear and bilinear monomial transformations to derive its lower bound. We next develop a branch-and-bound (BnB) algorithm which only branches over the transformation variables and runs efficiently.
  arXiv  Detail & Related papers  (2021-01-19T04:24:23Z)
• Provably Convergent Working Set Algorithm for Non-Convex Regularized Regression [0.0]
  This paper proposes a working set algorithm for non-regular regularizers with convergence guarantees. Our results demonstrate high gain compared to the full problem solver for both block-coordinates or a gradient solver.
  arXiv  Detail & Related papers  (2020-06-24T07:40:31Z)
• Kernel methods through the roof: handling billions of points efficiently [94.31450736250918]
  Kernel methods provide an elegant and principled approach to nonparametric learning, but so far could hardly be used in large scale problems. Recent advances have shown the benefits of a number of algorithmic ideas, for example combining optimization, numerical linear algebra and random projections. Here, we push these efforts further to develop and test a solver that takes full advantage of GPU hardware.
  arXiv  Detail & Related papers  (2020-06-18T08:16:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.