betaFeedback

WorksPhysics and Astronomy

Vector Ising Spin Annealer for Minimizing Ising Hamiltonians

Abstract

We introduce the Vector Ising Spin Annealer (VISA), a framework in gain-based computing that harnesses light-matter interactions to solve complex optimization problems encoded in spin Hamiltonians. Traditional driven-dissipative systems often select excited states due to limitations in spin movement. VISA transcends these constraints by enabling spins to operate in a three-dimensional space, offering a robust solution to minimize Ising Hamiltonians effectively. Our comparative analysis reveals VISA's superior performance over conventional single-dimension spin optimizers, demonstrating its ability to bridge substantial energy barriers in complex landscapes. Through detailed studies on cyclic and random graphs, we show VISA's proficiency in dynamically evolving the energy landscape with time-dependent gain and penalty annealing, illustrating its potential to redefine optimization in physical systems.

Introduction

In pursuing advancements in digital computing, mainly aimed at addressing the complexities inherent in AI and large-scale optimization problems, the inherent limitations of the traditional von Neumann architecture come to the forefront. These limitations are characterized by the escalating costs required for incremental performance improvements, prompting a pivotal shift toward more sustainable computational paradigms [1]. In this evolving landscape, two primary paths have emerged: refining algorithms within the existing computational frameworks and exploring novel hardware paradigms grounded in physics principles, with a notable focus on exploiting light-matter interactions.

Algorithmic enhancements, while valuable, offer incremental improvements. In contrast, the exploration of alternative hardware paradigms holds the promise of a substantial shift, leveraging the fundamental principles of physics—such as minimizing entropy, energy, and dissipation [2]—and integrating quantum phenomena like superposition and entanglement [3]. This innovative approach aims to transcend the conventional computing model’s limitations, tapping into the intrinsic computational potential of physical systems to address complex optimization challenges currently beyond traditional methods’ reach.

Central to this innovative trajectory is the integration of analogue, physics-based algorithms and hardware, which involve translating complex optimization problems into universal spin Hamiltonians, like the classical Ising and XY models [4, 5, 6]. This translation process involves embedding the structure of the problem into the spin Hamiltonian’s coupling strengths and targeting the ground state as the solution, with the physical system tasked with discovering this state. The efficiency and accuracy of this mapping process are vital, as they ensure the scalability of computational efforts, enabling these problems to remain manageable despite increasing complexity [7].

Gain-based computing (GBC) using coupled light-matter emerges as a novel disruptive computing platform distinct from gate-based and quantum or classical annealing approaches. GBC combines optical light manipulations with advancements in laser technology and spatial light modulators, facilitating parallel processing across multiple channels with significant nonlinearities and high-energy efficiency. The operational principle of GBC—increasing pumping power (annealing), followed by symmetry breaking and gradient descent—relies on wave coherence and synchronization to lead the system to a state that minimizes losses naturally. Recent developments in physics-based hardware exploiting GBC principles have showcased diverse technologies. These range from optical parametric oscillator based coherent Ising machines (CIMs) [8, 9, 10, 11], memristors [12], and laser systems [13, 14, 15], to photonic simulators [16, 17], polaritons [5, 6], photon condensates [18], and novel computational architectures like Microsoft’s analogue iterative machine [19] and Toshiba’s simulated bifurcation machine [20]. These platforms have been instrumental in minimizing programmable spin Hamiltonians, demonstrating efficacy across a spectrum of complex optimization challenges, including machine learning [21], financial analytics [22], and biophysical modelling [23, 24].

The Ising Hamiltonian, originating from statistical physics, is a natural model that can be implemented in these platforms. It describes interactions between spins in a lattice, providing a fundamental model for understanding complex systems and can be written as

HI=−∑ijJijsisj−∑ihisi,(1)H_{\mathrm{I}}=-\sum_{ij}J_{ij}s_i s_j-\sum_i h_i s_i, \tag*{(1)}

where si=±1s_i=\pm1 represents the spin, and hih_i is the external magnetic field. JijJ_{ij} is the interaction strength between the ii-th and jj-th spins, and is encoded in the coupling matrix J\mathbf{J}. The Ising model’s exploration of ground states in physical systems parallels the search for minimum cost functions in optimization. At the same time, its energy landscapes mirror the loss landscapes in machine learning, offering a unique perspective on optimization problems.

At the core of the hardware representation of Ising Hamiltonians lies the utilization of scalar soft-spins within soft-spin Ising models, which effectively change energy barriers inherent in classical hard-spin Ising Hamiltonians, HIH_I. The transition from the hard-spin Ising Hamiltonians HIH_I to the soft-spin Ising models consists of considering binary spins sis_i as signs of continuous variables xix_i - amplitudes - that bifurcate from vacuum state x=0\mathbf{x} = 0 guided by the gain increase. While facilitating enhanced problem-solving capabilities, this approach occasionally encounters the obstacle of trajectory trapping within local minima due to the escalating energy barriers as gain increases.

Therefore, the challenge of navigating energy landscapes with numerous local minima, especially during amplitude bifurcation, necessitates an innovative approach to avoid the system being trapped in local minima. In this paper, we introduce the Vector Ising Spin Annealer (VISA), a model that integrates the benefits of multidimensional spin systems and soft-spin gain-based evolution. Unlike traditional single-dimension semi-classical spin models, VISA utilizes three soft modes to represent vector components of an Ising spin, allowing for movement in three dimensions and offering a robust framework for accurately determining ground states in complex optimization problems. Our comparative studies underscore the enhanced performance of VISA compared to established models with scalar spins, such as Hopfield-Tank networks, coherent Ising machines, and the spin-vector Langevin model (SVL). VISA showcases a notable ability to overcome significant energy barriers and effectively navigate through intricate energy landscapes. We illustrate VISA’s effectiveness by tackling Ising Hamiltonian problems across various graph structures. Our examples include analytically solvable 3-regular circulant graphs, more complex circulant graphs, and random graphs where minimizing the Ising Hamiltonian is known to be an NP-hard problem. In our discussions, when we refer to “solving a graph A” or “minimizing a graph A”, we use shorthand for the more detailed process of “finding the global minimum of the Ising Hamiltonian on graph A”. This terminology simplifies our reference to determining the lowest possible energy state for the Ising model applied to a specific graph structure.

Vector Ising Spin Annealer

The VISA model is a semi-classical, three-dimensional soft-spin Ising model. It employs annealing of the loss landscape, symmetry-breaking, bifurcation, gradient descent, and mode selection to drive the system toward the global minimum of the Ising Hamiltonian. Here, we represent Ising soft-spins as continuous vectors in three-dimensional space xi=(x1i,x2i,x3i)\mathbf{x}_i = (x_{1i}, x_{2i}, x_{3i}) that are free to move in that space. VISA may be physically realized using amplitudes of a network of coupled optical oscillators. In these optical-based Ising machines, vectors of Ising spins are represented by three soft-spin amplitudes. In total, 3N3N amplitudes are required to minimize an NN-spin Ising Hamiltonian. This approach is somewhat complimentary to the recently proposed “dimensionality annealing” where soft Ising amplitudes are considered as coordinates of the multidimensional spins such as XY or Heisenberg spins [25, 26]. While the main idea is to exploit the advantages of the higher dimensionality, VISA aims at the Ising minimization rather than hyper-dimensional spin systems [25, 26].

To formulate the Hamiltonian that is capable of representing the dynamics of the GBC, we incorporate the term that is convex and dominates when the effective gain (loss) is large and negative, the Ising term that is minimized when the gain is large and positive, and a term that aligns the spins at the end of the process so that their direction can be associated with the binary spin si=±1s_i = \pm1. We write, therefore, the VISA Hamiltonian as the sum of three terms HVISA=H1+H2+H3H_{\mathrm{VISA}} = H_1 + H_2 + H_3, where

H1=α4∑i=1N(γi(t)−∣xi∣2)2,(2)H_1 = \frac{\alpha}{4} \sum_{i=1}^{N} \left(\gamma_i(t) - \lvert x_i \rvert^2\right)^2, \tag*{(2)}
H2=−12∑i,j=1NJijxi⋅xj,(3)H_2 = -\frac{1}{2} \sum_{i,j=1}^{N} J_{ij}\mathbf{x}_i \cdot\mathbf{x}_j, \tag*{(3)}
H3=P(t)2∑i,j=1N∣xi×xj∣2,(4)H_3 = \frac{P(t)}{2} \sum_{i,j=1}^{N} \lvert\mathbf{x}_i \times\mathbf{x}_j \rvert^2, \tag*{(4)}

with hyperparameter α\alpha. As the effective gain γi(t)\gamma_i(t) increases with time tt from negative (effective losses) to positive (effective gain) values, H1H_1 anneals between a convex function with the minimum at xi=0\mathbf{x}_i = 0 to nonzero amplitudes. H2H_2 coincides with the Ising Hamiltonian when all xi\mathbf{x}_i have unit magnitude when projected along the same direction. Finally, H3H_3 is a penalty term with time-dependent magnitude P(t)P(t) to enforce collinearity between xi\mathbf{x}_i and xj\mathbf{x}_j at the end of the gain-induced landscape change. At which time, the condition on the amplitudes ∣xi∣=1\lvert\mathbf{x}_i \rvert= 1 is imposed by the feedback on the gain realised by γ˙i=ϵ(1−∣xi∣2)\dot{\gamma}_i = \epsilon(1 - \lvert\mathbf{x}_i \rvert^2) [27]. Analogously to CIM operation, as γi(t)\gamma_i(t) grows from negative to positive values, HVISAH_{\mathrm{VISA}} anneals from the dominant convex term H1H_1 that is minimized at xi=(0,0,0)\mathbf{x}_i = (0,0,0) for all ii, to the minimum of H2+H3H_2 + H_3 with ∣xi∣=1\lvert\mathbf{x}_i \rvert= 1 via symmetry-breaking bifurcation. Concurrently, as P(t)P(t) increases from P(0)=0P(0) = 0 to sufficiently large P(T)>0P(T) > 0, the soft-spins vectors become collinear. The Ising spins are calculated by projecting the three-dimensional vectors along the axis k\mathbf{k} they have centred around and taking signs of the resultant scalar si=sgn⁡(xi⋅k)s_i=\operatorname{sgn}(x_i\cdot k). At t=Tt=T, the target hard-spin Ising Hamiltonian HIH_{\mathrm{I}} is minimized.

The Hamiltonian HVISAH_{\mathrm{VISA}} is 4-local due to the H3H_3 term. Some optical hardware can directly encode such interactions [28]. At the same time, it is possible to reduce the 4-local Hamiltonian to quadratic Hamiltonian by substituting the product of two variables with a new one while adding the appropriate penalty terms. For instance, the quartic interaction term xixjxkxmx_i x_j x_k x_m can be reduced to a triplet by introducing a new variable yy instead of xkxmx_k x_m and the term qkm(y)=Q(xkxm−2xky−2xmy+3y)q_{km}(y)=Q(x_kx_m-2x_ky-2x_my+3y) (known as Rosenberg polynomial [29]) in the Hamiltonian where Q>0Q>0 is the penalty constant. Note that qkm=0q_{km}=0 if and only if xkxm=yx_kx_m=y and is strictly positive otherwise. The reduction of the triplet xixjyx_ix_jy is done similarly by replacing xixjx_ix_j with a new spin variable zz and introducing the penalty term qij(z)q_{ij}(z) in the Hamiltonian [30].

The governing equations x˙i=−∇iHVISA\dot{x}_i=-\nabla_iH_{\mathrm{VISA}} represent the gradient descent combined with the temporal change of annealing parameters γi(t)\gamma_i(t) and P(t)P(t) as

x˙i=αxi(γi(t)−∣xi∣2)+∑j=1NJijxj+P(t)(xi∑j=1N∣xj∣2−∑j=1Nxj(xi⋅xj)).(5)\begin{aligned} \dot{x}_i &= \alpha x_i\left(\gamma_i(t)-\lvert x_i\rvert^2\right)+\sum_{j=1}^{N}J_{ij}x_j\\ &\quad+P(t)\left(x_i\sum_{j=1}^{N}\lvert x_j\rvert^2-\sum_{j=1}^{N}x_j(x_i\cdot x_j)\right). \tag*{(5)} \end{aligned}

where in the last two terms, the vector triple product has been invoked. The operation of VISA, therefore, relies on the gradient descent of a gain-driven losses landscape.

We illustrate a toy model of VISA for two dimensions in Figure 1, demonstrating how the energy landscape evolves as the gain γi(t)\gamma_i(t) and penalty P(t)P(t) are evolved, and how the minimizers x∗x^* and minima of HVISAH_{\mathrm{VISA}} change during this process.

Energy landscape of components of the two-dimensional VISA Hamiltonian

Figure 1. Energy landscape of components of the two-dimensional VISA Hamiltonian for N=2N=2 with spin-spin coupling terms J11=J22=0J_{11}=J_{22}=0 and J12=J21=−1J_{12}=J_{21}=-1. The normalized minimizer is x1=(1,−1)/2x_1=(1,-1)/\sqrt{2} and x2=(−1,1)/2x_2=(-1,1)/\sqrt{2}, and therefore in this illustration we choose state vectors x1=(x,y)x_1=(x,y) while setting x2=(−1,1)/2x_2=(-1,1)/\sqrt{2}. Snapshots of the self-interacting term H1H_1 through the annealing schedule are shown in (a)-(c) for α=4\alpha=4 and γi=γ=−0.5\gamma_i=\gamma=-0.5 (a), 0.50.5 (b), and 11 (c), illustrating the symmetry-breaking as the gain increases. H1+H2H_1+H_2 is shown in (d)-(f) which seek to minimise interaction energy between soft spins; in (f) the minimum is achieved as the angle between vectors x1x_1 and x2x_2 is π\pi; in a more general coupling matrix the vector spins will tend to adjust the angles as to minimise the pairwise interactions. H1+H2+H3H_1+H_2+H_3 is shown in (g)-(i) for the same gain parameter as in (a)-(c) and P(t)=1.0P(t)=1.0 (g), 1.51.5 (h), and 2.02.0 (i). The vector spins are forced to be collinear with the direction that can be identified with the hard Ising spins in (i).

Numerical Evolution of Vector Ising Spin Annealers

We consider two popular models to introduce the concept of a scalar-based GBC against which VISA will be benchmarked. (A) Hopfield-Tank (HT) neural networks [31, 32] have energy landscape given by the Lyapunov function

EHT=−p(t)∑i=1N∫0vig−1(x) dx−12∑i,j=1NJijvivj,(6)E_{\mathrm{HT}}=-p(t)\sum_{i=1}^{N}\int_{0}^{v_i}g^{-1}(x)\,\mathrm{d}x-\frac{1}{2}\sum_{i,j=1}^{N}J_{ij}v_iv_j, \tag*{(6)}

with nonlinear activation function vi=g(xi)v_i=g(x_i) and real soft-spin variables xi(t)x_i(t) describing the network state. At any time tt, the Ising state can be obtained from xix_i by associating spins sis_i with the sign of the soft-spin variables si=sgn⁡(xi)s_i=\operatorname{sgn}(x_i). The governing equation for HT neural networks is x˙i=p(t)xi+∑jJijvj\dot{x}_i=p(t)x_i+\sum_jJ_{ij}v_j with annealing parameter p(t)p(t). This first-order equation can be momentum-enhanced and replaced with the second-order equation

leading to Microsoft analogue iterative machine [19] or Toshiba bifurcation machine [33]. We will use these enhancements below. (B) CIM using the degenerate optical parametric oscillators has an energy function

ECIM=14∑i=1N(p(t)−xi2)2−α2∑i,j=1NJijxixj,(7)E_{\mathrm{CIM}}=\frac{1}{4}\sum_{i=1}^{N}\left(p(t)-x_i^2\right)^2-\frac{\alpha}{2}\sum_{i,j=1}^{N}J_{ij}x_ix_j, \tag*{(7)}

where xix_i, p(t)p(t), and JijJ_{ij} represent degenerate optical parametric oscillator quadrature, effective laser pumping power, and coupling strength, respectively. The system evolves as

x˙i=p(t)xi−xi3+α∑jJijxj,(8)\dot{x}_i=p(t)x_i-x_i^3+\alpha\sum_jJ_{ij}x_j, \tag*{(8)}

where α\alpha is a hyperparameter chosen to maximize solution quality. In the scalar-based GBC models, as the gain p(t)p(t) increases from negative values (representing effective losses) to large positive values (large effective gain), the amplitudes undergo Hopf bifurcation and reach xi=±p(T)x_i=\pm\sqrt{p(T)} as t→Tt\to T, p(t)=p(T)=constp(t)=p(T)=\mathrm{const} for t>Tt>T. At the fixed point, the second term in Eq. (6) dominates, which is the target Ising Hamiltonian scaled by p(T)p(T).

The energy landscapes during amplitude bifurcation have many local minima from the increased degrees of freedom of the soft-mode systems. Moreover, the ground state of the soft-mode system may correspond to the excited state of the hard-spin Ising model. At the bifurcation, the system trajectories may get trapped at these minima and could not transition to the correct global minimum at higher gains, especially when global cluster spin flips are required [34]. By enhancing the dimensionality of the energy landscape, VISA may allow the system to evolve from the global minimum of the soft-spin Ising model to the global minimum of the classical hard-spin Ising Hamiltonians, as we now illustrate.

J-Möbius Ladder Graph

First, we examine the Ising Hamiltonian minimization on simple cyclic graphs. These graphs offer analytically solvable benchmarks with distinct and identifiable obstacles in finding ground states. The process of finding Ising ground states on such graphs is significantly influenced by the eigenvalues of the coupling matrix J\mathbf{J}, especially the relationship between the eigenvectors’ component signs and the Ising Hamiltonian’s global minimum [34]. For instance, HT networks adjust spin amplitudes to favour the principle eigenvector component signs [35].

We start by using a Möbius ladder-type graph, a cyclic structure with an even number of vertices NN arranged in a ring, featuring variable couplings between adjacent and opposite vertices. To explore non-trivial ground states, we introduce equal antiferromagnetic couplings (Jij=−1J_{ij}=-1) among nearest neighbors and variable cross-ring antiferromagnetic couplings (Jij=−JJ_{ij}=-J). We refer to the Möbius graphs with these couplings as JJ-Möbius graph. Following Ref. [34], we define S0S_0 as the alternating spin state around the ring and S1S_1 as the state with spins alternating except at two opposite ring points with frustrated spins, as depicted in Figure 5(a) and (b). When N/2N/2 is even, the energies and principal eigenvalues of S0S_0 and S1S_1 intersect at Jcrit≡4/NJ_{\mathrm{crit}}\equiv4/N and Je≡1−cos⁡(2π/N)J_{\mathrm{e}}\equiv1-\cos(2\pi/N), respectively. In the range Je<J<JcritJ_{\mathrm{e}<J<J_{\mathrm{crit}}}, S0S_0’s largest eigenvalues are smaller than those of S1S_1, with an eigenvalue gap

J-Möbius ladder graphs and ground state probabilities

Figure 5. N=8N = 8 JJ-Möbius ladder graphs with circle (blue) and cross-circle (red) couplings for the (a) S0S_0 and (b) S1S_1 configurations. (c) Ground state probability for VISA, SVL, ME-HT, CIM, and BFGS for an N=8N = 8 JJ-Möbius ladder graph with varying cross-circle couplings JJ. One thousand runs are used to calculate the probability of finding the ground state pGSp_{\mathrm{GS}} for each value of JJ. Dashed lines corresponding to JeJ_{\mathrm{e}} (black) and JcritJ_{\mathrm{crit}} (red) show the values of JJ for which the leading eigenvalue changes and the ground state configuration changes, respectively. For VISA, ε=0.02\varepsilon= 0.02, γi(0)=−0.5\gamma_i(0) = -0.5, and P(t)=αtP(t) = \alpha t. For SVL, m=1.0m = 1.0, ξ∼N(μ=0,σ=0.1)\xi\sim N(\mu= 0,\sigma= 0.1), and γ=0.99\gamma= 0.99. For momentum-enhanced HT, m=1.0m = 1.0, and γ=0.99\gamma= 0.99. For CIM we used p(t)=(1−p0)tanh⁡(εt)+p0p(t) = (1-p_0)\tanh(\varepsilon t)+p_0 with p0=J−2p_0 = J^{-2}, and ε=0.003\varepsilon= 0.003. For each value of JJ, optimal values of α\alpha and β(0)\beta(0) are chosen based on sets of preliminary runs in which they are varied. Inset (d) illustrates the structure of Möbius ladder coupling matrices J\mathbf{J} with Jij=0J_{ij} = 0 (white), −1-1 (blue), −J-J (red).

Δ=2cos⁡(2π/N)+2J−2\Delta= 2\cos(2\pi/N) + 2J - 2

even though S0S_0 represents the ground state with lower energy. The dynamics of semi-classical soft-spin models, including these considerations, are juxtaposed with quantum annealing approaches in the minimization of the Ising Hamiltonian on JJ-Möbius ladder graphs, as detailed in Ref. [34].

The presence of amplitude heterogeneities enables the soft-spin model to acquire and maintain its state achieved at the bifurcation even when it diverges from the classical hard-spin Ising Hamiltonian ground state, potentially complicating the optimization process when Je<J<JcritJ_{\mathrm{e}}<J<J_{\mathrm{crit}}. To mitigate this issue, the manifold reduction CIM (MR-CIM) technique was developed, incorporating an additional feedback mechanism to regulate soft spin amplitudes, ensuring they remain close to their mean value [34]. The amplitude adjustment after each update at time step tt is governed by

xi→(1−δ)xi+δR(x)xi∣xi∣,(9)x_i \rightarrow(1-\delta)x_i+\delta\frac{R(\mathbf{x})x_i}{\lvert x_i\rvert}, \tag*{(9)}

where 0<δ<10<\delta<1. This adjustment draws the spins nearer to the mean, with the average defined by the squared radius of the quadrature R(x)=∑ixi2/NR(\mathbf{x})=\sum_i x_i^2/N, thus aligning the local and global minima of the soft and hard spin models more closely. Comparative analyses between various CIM modes and quantum annealing have been conducted, demonstrating that, despite quantum annealing’s ability to utilize quantum entanglement and inter-spin correlations to identify ground states, it exhibits heightened sensitivity to diminishing energy gaps near JcritJ_{\mathrm{crit}}. Consequently, quantum annealing demands longer annealing schedules to accurately determine ground state solutions as JJ nears JcritJ_{\mathrm{crit}} [34].

Figure 2 illustrates the application of VISA to a JJ-Möbius ladder graph instance characterized by cross-circle couplings where Je<J<JcritJ_{\mathrm{e}}<J<J_{\mathrm{crit}}. The continuous spin components experience an Aharonov-Hopf bifurcation during the process, exploiting the minimal energy barriers inherent in soft-spin models. We particularly focus on the intermediary time t1t_1 following the bifurcation, noting that at this time, the spin amplitudes have yet to achieve unit magnitude, and the spins are not collinear. By a later time t2>t1t_2 > t_1, the spin vectors stabilize as the minimization of the VISA Hamiltonian progresses. These soft-spin vectors then exhibit Ising spin characteristics, including unit magnitude and (anti-)parallel alignment, while the coupling term H2H_2 guarantees identifying the target Ising Hamiltonian’s ground state.

Evolution of the VISA model in an N = 8 J-Möbius ladder network

Figure 2. Evolution of the VISA model in an N=8N=8 JJ-Möbius ladder network with coupling strength J=0.4J=0.4, as governed by Eq. (5). This figure illustrates the dynamics of VISA’s soft-spin components: x1=x1ix_1=x_{1i} (a), x2=x2ix_2=x_{2i} (b), and x3=x3ix_3=x_{3i} (c), with vertical dashed lines indicating the changes at times t1t_1 and t2t_2. Panels (d) and (e) depict the corresponding spin vectors, highlighting the orientation at t1t_1—influenced by H1+H2H_1+H_2—and at t2t_2, where spins align in a unified direction due to a high P(t2)P(t_2), revealing the hard-spin Ising Hamiltonian’s global minimum. The final orientation of the vectors at t2t_2 is spontaneous; thus, the vectors are adjusted such that the zz-axis aligns with this direction. Panel (f) shows the trajectory of the VISA Hamiltonian, HVISAH_{\mathrm{VISA}}, over time as it converges to the ground state. The numerical integration of Eq. (5) utilized the following parameters: ε=0.03\varepsilon=0.03, γi(0)=−0.5\gamma_i(0)=-0.5, P(t)=t/200P(t)=t/200, α=4\alpha=4, and initial conditions xij(0)x_{ij}(0) uniformly distributed within [−0.01,0.01][-0.01,0.01]. The fourth-order Runge-Kutta method with fixed time step Δt=0.1\Delta t=0.1 was employed for solving Eq. (5).

In Figure 3, we depict typical trajectories of VISA vectors on Bloch spheres, drawing a parallel to similar quantum representations. We orient the spontaneously aligning spins along the zz-axis to facilitate visualisation. With a fixed interaction strength where Je<J<JcritJ_{\mathrm{e}} < J < J_{\mathrm{crit}} and considering N=8N = 8, we demonstrate the bifurcation dynamics originating from the center. This visualization shows how the three-dimensional nature of VISA allows spins to traverse paths that connect various minima, ultimately converging on the ground state S0S_0. The final vector states are indicated by black arrows, while red points mark the terminal positions of spin vectors at sequential time steps tt. These trajectories elucidate the process by which spins increasingly satisfy collinearity and unit magnitude constraints through external annealing of P(t)P(t) and the feedback mechanism on γi\gamma_i, steering the spin magnitudes to the threshold value of ∣xi∣=1\lvert x_i\rvert= 1.

Evolution of VISA spins for an $N = 8$ $J$-Möbius graph

Figure 3. Evolution of VISA spins for an N=8N = 8 JJ-Möbius graph with coupling constant J=0.4J = 0.4. The spins reach final states adhering to the Ising model’s collinear and unit magnitude constraints. The spontaneous orientation of vectors at time t2t_2 leads to an adjustment of the spin vectors, aligning the zz-axis with the resultant direction. Parameters used are ε=0.04\varepsilon= 0.04, γi(0)=−0.5\gamma_i(0) = -0.5, P(t)=t/25P(t) = t/25, α=4\alpha= 4, and initial conditions xpi(0)x_{pi}(0) uniformly distributed within [−0.01,0.01][-0.01, 0.01].

In Figure 4, we compare VISA with CIM under equivalent starting conditions, highlighting that while CIM cannot find the ground state within the range Je<J<JcritJ_{\mathrm{e}} < J < J_{\mathrm{crit}}, VISA excels by leveraging the dynamics of spins in three dimensions to identify the global minimum. Soft-spins contribute to this success in both models by facilitating the escape from local minima through reduced energy barriers, a feature not present in hard-spin models.

Comparison of VISA and CIM trajectories and energy landscapes

Figure 4. Panel (a) compares the trajectory evolution of VISA (blue) and CIM (red) on an N=8N = 8 JJ-Möbius ladder graph with a coupling constant J=0.35J = 0.35. Here, VISA successfully reaches the ground state S0S_0, while CIM remains in an excited state S1S_1. Both systems start from the same initial conditions, with CIM beginning at xi(0)=ax_i(0) = a and VISA at xi(0)=(a,b,b)x_i(0) = (a,b,b), where aa and bb are uniformly chosen from the ranges [−0.01,0.01][-0.01, 0.01] and [−0.0001,0.0001][-0.0001, 0.0001] respectively. Panels (b)-(d) for CIM and (e)-(g) for VISA show the spin states at three different times t1t_1, t2t_2, and t3t_3, marked by vertical dashed lines in panel (a), illustrating CIM’s inability to overcome the energy barrier to reach the ground state, in contrast to VISA’s effective navigation in three-dimensional space. Panel (h) compares the VISA Hamiltonian HVISAH_{\mathrm{VISA}} against the CIM energy ECIME_{\mathrm{CIM}} as calculated from Eq. (7), while panel (i) focuses on the Ising energy, with the ground state S0S_0 indicated by a black dashed line. Lastly, panel (j) outlines the regions in the γ\gamma-PP space that correspond to different global minima of HVISAH_{\mathrm{VISA}} for N=8N = 8, showing S1S_1 in blue and S0S_0 in varying colors (yellow, orange, red) for JJ values of 0.35, 0.40, and 0.45, respectively.

els. Unlike CIM, constrained by the principal eigenvalue of J\mathbf{J} to an excited state, VISA uses its multidimensional advantage to bridge minima unreachable by CIM’s one-dimensional approach. Additionally, VISA’s mechanism allows for spin flipping at energy costs lower than that required by CIM, thanks to its ability to navigate through three-dimensional space to find the most energy-efficient path to the global minimum. Figures (4)(a)-(i) depict how VISA effectively minimizes Ising energy, contrasting with CIM’s stagnation in an excited state. For Je<J<JcritJ_{\mathrm{e}} < J < J_{\mathrm{crit}}, and as the gain γi\gamma_i and penalty P(t)P(t) increase, VISA goes towards the ground state S0S_0, aligning with the lowest energy state indicated by the hard-spin Ising Hamiltonian, as shown in Figure 4(j). Nonetheless, it’s important to note that increasing spin amplitudes too fast may also inadvertently heighten energy barriers, potentially impeding state transitions. Further insight into the structure of the VISA energy landscape and its comparison with the energy landscape of the scalar models can be gained by analysing the critical points (see Supplementary Information). The VISA energy landscape shows much-diminished energy barriers.

We compare VISA to two second-order scalar networks methods, namely (i) momentum-enhanced Hopfield-Tank (ME-HT), and (ii) spin-vector Langevin. With rigorous hyper-parameter exploration phases, ME-HT outperforms parallel tempering, simulated annealing, and commercial solver Gurobi at various QUBO benchmarks [19]. The ME-HT governing equation is

mx¨i+γx˙i−β(t)xi−α∂H(g(x))∂xi=0,(10)m\ddot{x}_i+\gamma\dot{x}_i-\beta(t)x_i-\alpha\frac{\partial H(g(\mathbf{x}))}{\partial x_i}=0, \tag*{(10)}

with effective mass mm, momentum term γ∈[0,1)\gamma\in[0,1), and hyperparameters α\alpha and β(t)\beta(t), the latter of which undergoes an annealing protocol given by β(t)=β0(1−t/T)\beta(t)=\beta_0(1-t/T). Equation (10) combines gradient descent with annealed non-conservative dissipation, and the addition of momentum distinguishes it from regular first-order HT networks with energy landscape Eq. (6). Momentum, or the heavy-ball method, aims to overcome the pitfalls of pathological curvature in deep learning and accelerates standard gradient descender optimizers [36, 37].

VISA can be further compared and contrasted with the spin-vector Langevin (SVL) model that was proposed as a classical analogue of quantum annealing description using stochastic Langevin time evolution governed by the fluctuation-dissipation theorem [38]. SVL is based on the time-dependent Hamiltonian used in quantum annealing H(t)=A(t)H0+B(t)HPH(t)=A(t)H_0+B(t)H_P, where initial Hamiltonian H0=∑iσixH_0=\sum_i\sigma_i^x, and problem Hamiltonian HP=−∑i,jJijσizσjzH_P=-\sum_{i,j}J_{ij}\sigma_i^z\sigma_j^z, with Pauli operator σi\sigma_i acting on the ii-th variable. Real annealing functions satisfy boundary conditions A(0)=B(T)=1A(0)=B(T)=1 and A(T)=B(0)=0A(T)=B(0)=0, where TT is the temporal length of the annealing schedule. If the rate of change of the functions is slow enough, the system stays in the ground state of the instantaneous Hamiltonian so that the Ising Hamiltonian is minimised at t=Tt=T. Quantum annealing has shown competitive results in quadratic unconstrained binary optimization (QUBO) problems such as subset sum, vertex cover, graph coloring, and travelling salesperson [39]. The SVL model replaces Pauli operators with real functions of continuous angle σiz→sin⁡θi\sigma_i^z \to\sin\theta_i, σix→cos⁡θi\sigma_i^x \to\cos\theta_i, and is therefore a classical annealing Hamiltonian using continuous-valued spins sin⁡θi\sin\theta_i. SVL dynamics is described by a system of coupled stochastic equations

mθ¨i+γθ˙i+α∂H(θ)∂θi+ξi(t)=0,(11)m\ddot{\theta}_i+\gamma\dot{\theta}_i+\alpha\frac{\partial H(\theta)}{\partial\theta_i}+\xi_i(t)=0, \tag*{(11)}

where mm is the effective mass, γ\gamma is the damping constant, α\alpha is a hyperparameter, and ξi(t)\xi_i(t) is an iid Gaussian noise. For long annealing times, the minima of HSIHs are obtained through the transformation si=sgn⁡(sin⁡θi)s_i=\operatorname{sgn}(\sin\theta_i). The gradient term in Eq. (11) is

∂H(θ)∂θi=−B(t)∑j=1NJijcos⁡θisin⁡θj+A(t)sin⁡θi,(12)\frac{\partial H(\theta)}{\partial\theta_i}=-B(t)\sum_{j=1}^{N}J_{ij}\cos\theta_i\sin\theta_j+A(t)\sin\theta_i, \tag*{(12)}

which in conjunction with fluctuation-dissipation relations ⟨ξi(t)⟩=0\langle\xi_i(t)\rangle=0 and ⟨ξi(t)ξj(t′)⟩=δijδ(t−t′)\langle\xi_i(t)\xi_j(t')\rangle=\delta_{ij}\delta(t-t'), give 2N2N stochastic differential equations: dθi=(pi/m)dt\mathrm{d}\theta_i=(p_i/m)\mathrm{d}t and

dpi=(∂H(θ)∂θi+γmpi)dt+dWi,(13)\mathrm{d}p_i=\left(\frac{\partial H(\theta)}{\partial\theta_i}+\frac{\gamma}{m}p_i\right)\mathrm{d}t+\mathrm{d}W_i, \tag*{(13)}

where dWi\mathrm{d}W_i represents a real-valued continuous-time stochastic Wiener process [38]. The characteristic amplitude bifurcation of scalar spins according to ME-HT and SVL are given in Supplementary Information.

The key feature distinguishing VISA from the discussed models lies in its novel gain-based and dimensionality annealing strategy applied across multiple dimensions. In the analysis of JJ-Möbius ladder graphs, as shown in Figure 5, we compute the ground state probability for VISA alongside SVL, ME-HT, CIM, and the Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm [40]. Within the range Je<J<JcritJ_{\mathrm{e}} < J < J_{\mathrm{crit}}, VISA consistently identifies the ground state S0S_0 with a higher probability pGSp_{\mathrm{GS}} compared to the other models.

Cyclic Graphs

Next we consider the J−GJ-G cyclic graphs that are a variant of JJ-Möbius ladder graphs that include additional couplings, connecting each vertex ii to vertices i±ki\pm k with a weight of −G-G, where 1<k<N/21<k<N/2. This modification aims to explore more complex interaction patterns and their impact on the system’s ground state behavior and eigenvalue distributions, particularly focusing on how these factors evolve in optimization and the search for ground states in varied graph structures. The interaction strength range is expanded to accommodate both ferromagnetic and antiferromagnetic interactions, with −1≤J,G≤1-1\leq J,G\leq1. This yields a 5-regular circulant graph characterized by weights Jij∈{−1,−J,−G}J_{ij}\in\{-1,-J,-G\}, depicted in Figure 6. Cyclic graphs maintain their local and global topological properties under rotational transformations, encapsulating all connectivity information within any row of J\mathbf{J}. By selecting the first row J1,jJ_{1,j}, we compute eigenvalues as λn=∑j=1NJ1,jcos⁡[2πn(j−1)/N]\lambda_n=\sum_{j=1}^{N}J_{1,j}\cos[2\pi n(j-1)/N], leading to λn=−2cos⁡(2πn/N)−J(−1)n−2Gcos⁡(2πkn/N)\lambda_n = -2\cos(2\pi n/N) - J(-1)^n - 2G\cos(2\pi kn/N) [41]. We then deduce boundaries by observing eigenvalues in the J−GJ-G plane, identifying where leading eigenvalues and corresponding eigenvectors change their correspondence with the ground and excited states. The ground state boundaries are identified within the J−GJ-G space in the Supplementary Information. Figure 6 depicts regions where the global minimum diverges from the hypercube corner of the projected eigenvector with the highest eigenvalue.

J-G cyclic graphs and coupling matrix

Figure 6. J−GJ-G cyclic graphs for N=8N = 8 with couplings (a) k=2k = 2, and (b) k=3k = 3. Panel (c) depicts the matrix structure J\mathbf{J} for k=3k = 3, where the color coding represents Jij=0J_{ij} = 0 (white), −1-1 (blue), −J-J (red), and −G-G (green). The ground states and leading eigenvalue states for k=2k = 2 are displayed in panels (d) and (e) within the J−GJ-G space, respectively. Panel (f) delineates the energy and eigenvalue boundaries, with the pink region indicating discrepancies between ground and maximal eigenvalue states. The sequence from panels (g) to (i) extends this analysis to k=3k = 3, highlighting the ground state probabilities across easy-hard transitions in the J−GJ-G space, indicated by solid red lines in panels (f) and (i).

We investigate ground state probabilities pGSp_{\mathrm{GS}} over transition regions in these graphs with both JJ and GG cross-circle couplings. We choose values in J−GJ-G parameter space that demonstrate transitions between regions in which the eigenvector corresponding to the leading eigenvalue does not match the ground state solution (exact calculations of these regions are presented in Supp. Inf.). Ground state probabilities for VISA, SVL, ME-HT, CIM, and BFGS are illustrated in Figure 7. Four cases are analyzed, split into two sets: k=2k = 2 and k=3k = 3. We consider perpendicular lines in the two-dimensional J−GJ-G space for each set. Specifically, we vary (fix) JJ and fix (vary) GG. For k=2k = 2 and G=0.5G = 0.5, an easy-hard-easy transition emerges as JJ increases, akin to JJ-Möbius ladder previously studied.

Ground state probability plots for VISA, SVL, ME-HT, CIM, and BFGS

Figure 7. Ground state probability for VISA, SVL, ME-HT, CIM, and BFGS for N=8N = 8 J−GJ-G cyclic graphs with varying cross-circle couplings JJ and GG. (a) k=2k = 2, J∈[−0.5,0.5]J \in[-0.5, 0.5], and G=0.5G = 0.5. (b) k=2k = 2, J=0.5J = 0.5, and G∈[0,1]G \in[0, 1]. (c) k=3k = 3, J∈[−1,0.5]J \in[-1, 0.5], and G=−0.8G = -0.8. (d) k=3k = 3, J=−0.5J = -0.5, and G∈[−1,0]G \in[-1, 0]. One thousand runs are used to calculate the probability of finding the ground state pGSp_{\mathrm{GS}} for each value of JJ. Dashed red and black lines show where the ground state energies and leading eigenvalues change, respectively. For VISA, ε=0.04\varepsilon= 0.04, γi(0)=−0.5\gamma_i(0) = -0.5, and P(t)=αtP(t) = \alpha t. For SVL, m=1.0m = 1.0, ξ∼N(μ=0,σ=0.1)\xi\sim N(\mu= 0, \sigma= 0.1), and γ=0.99\gamma= 0.99. For momentum-enhanced HT, m=1.0m = 1.0, and γ=0.99\gamma= 0.99. The general annealing protocol for CIM is used with p0=J−2p_0 = J - 2 and ε=0.003\varepsilon= 0.003. For each value of JJ, optimal values of α\alpha and β(0)\beta(0) are chosen based on sets of preliminary runs in which they are varied.

Indeed, for Je<J<JcritJ_{\mathrm{e}} < J < J_{\mathrm{crit}}, pGSp_{\mathrm{GS}} decreases as the eigenvalue gap Δ\Delta increases. If, instead, we fix J=−0.5J = -0.5, a transition occurs, centred at the change between ground states given by Gcrit=0.5G_{\mathrm{crit}} = 0.5. Here, the hard region is bounded by eigenvalue crossing points Ge1=−2/2G_{\mathrm{e}_1} = -\sqrt{2}/2 and Ge2=1/2G_{\mathrm{e}_2} = 1/\sqrt{2}. For k=3k = 3, pGSp_{\mathrm{GS}} is less sensitive to the magnitude of Δ\Delta for regions where S3S_3 is the ground state. This is due to the proximity between the leading eigenvalue state S1S_1 and ground solution S3S_3 in topological spin space. More precisely, the transformation from S1S_1 to S3S_3 requires only a single spin flip, representing a nominal energy barrier for soft-spin models. Therefore, hardness in J−GJ-G cyclic graphs derives not just from the eigenvalue gap magnitude but additionally from the distance between hypercube corners of the ground and leading eigenvalue states.

Random Graphs

We extend VISA’s evaluation to QUBO instances renowned for their computational intensity as they scale: dense fully connected graphs and sparse threeregular graphs with customarily distributed random couplings JijJ_{ij}, representing Sherrington-Kirkpatrick (SK) and weighted three-regular Max-Cut problems, respectively. These models are pivotal for benchmarking physical simulators [42, 43, 44, 45] and are categorized under the NP-hard complexity class [4, 46]. Unlike cyclic graphs, these instances do not have analytically known ground states, necessitating using the Gurobi optimization suited for ground state estimations. Gurobi employs advanced pre-processing and heuristic enhancements to expedite branch-and-bound algorithms [47]. Figure 8(a) compares the ground state approximations achieved by Gurobi with those by VISA for N=100N = 100 SK and weighted three-regular Max-Cut graphs. Alongside, we include comparisons with SVL, MR-CIM, and CIM, where MR-CIM and CIM adapt their laser intensities following a general pumping scheme p(t)=(1−p0)tanh⁡(εt)+p0p(t) = (1-p_0)\tanh(\varepsilon t) + p_0. MR-CIM further applies an additional feedback mechanism as per Eq. (9) on top of Eq. (8), controlling soft-spin amplitudes and the dimensionality landscape. We define the quality improvement of VISA over another method X in terms of objective values OO as (OVISA−OX)/OVISA(O_{\mathrm{VISA}} - O_X)/O_{\mathrm{VISA}}, showcasing these metrics for SK and three-regular problems in Figure 8(b), where X represents the best-performing competing method for each instance.

Proximity gap and quality improvement for VISA, SVL, MR-CIM, and CIM

Figure 8. (a) The proximity gap, defined as the ratio of the found objective to the Gurobi objective, for VISA, SVL, manifold reduction CIM, and CIM methods. Gurobi was given a 30-second time limit for each of the 100 problem instances with size N=100N = 100. The instances are divided equally between two graph topologies: dense, fully connected, and sparse three-regular graphs. In both cases, the matrix weight elements are drawn from the Gaussian distribution with zero mean and unit variance, resulting in instances belonging to the Sherrington-Kirkpatrick and weighted 3-regular Max-Cut problems. (b) Violin plots demonstrate the distribution of VISA’s quality improvement performance compared to the best solution found by competing methods {SVL, MR-CIM, CIM} across the SK and 3-Regular QUBO benchmarks.

Conclusions

This paper introduces the Vector Ising Spin Annealer (VISA). This model capitalizes on the advantages of multidimensional spin systems, gain-based operation and soft-spin annealing techniques to optimize Ising Hamiltonians on various graph structures. VISA distinguishes itself by enabling more efficient navigation through the solution space, enhancing spin mobility in higher-dimensional spaces, and providing a robust framework for connecting local minima and reducing energy barriers.

A key focus of VISA is its ability to recover ground states effectively, even in scenarios where these states do not correspond to the principal eigenvector of the coupling matrix. The model’s performance was numerically evaluated against other methods, demonstrating its superior ability to find ground states across different graph types and complex QUBO instances. Thus, it highlights its potential to address NP-hard problems.

Future research could explore the role of defects in spin models, such as topological defects, domain walls, and vortex rings and their role in achieving the ground state during gain-based operation. Vortices may exhibit more efficient annihilation properties in higher-dimensional systems, such as those utilized by VISA. This is potentially due to the additional spatial degrees of freedom, which could facilitate the merging or cancellation of vortices and anti-vortices, a phenomenon less constrained than in two-dimensional spaces. This enhanced annihilation could lead to a smoother energy landscape, aiding the system in avoiding local minima and more effectively converging to the ground state.

By leveraging multidimensional spins, VISA opens new avenues for developing analogue optimization machines, potentially incorporating quantum effects to enhance computational capabilities. The prospects of applying dimensionality annealing techniques in optical-based Ising machines suggest an exciting future for speed-of-light computation and accurate ground state recovery, marking a significant advancement in optimization technologies.

ACKNOWLEDGEMENTS

J.S.C. acknowledges the PhD support from the EPSRC. N.G.B. acknowledges the support from the Julian Schwinger Foundation Grant No. JSF-19-02-0005, the HORIZON EIC-2022-PATHFINDERCHALLENGES-01 HEISINGBERG project 101114978, and Weizmann-UK Make Connection grant 142568. Both authors are grateful to Dr Fernando Gómez-Ruiz for valuable discussions.

SUPPLEMENTARY INFORMATION

Critical Points of VISA Hamiltonian

To determine the critical points of HVISAH_{\mathrm{VISA}}, we set ∂E∂xi=0\frac{\partial E}{\partial x_i}=0 for all ii, where ii ranges from 1 to NN. Figure 9 depicts these critical points, with the minima corresponding to the states S0S_0 and S1S_1 emphasized. As the gain γi(t)\gamma_i(t) and the collinearity penalty P(t)P(t) are systematically increased, a transition in the ground state from S1S_1 to S0S_0 is observed. Notably, there is an infinite continuum of (γi,P)(\gamma_i,P) pairs where S0S_0 and S1S_1 share the same energy level. This continuum forms a demarcation line in the γ−P\gamma-P space, illustrated in Figure 4(j). At a specific point on this boundary, as depicted in Figure 9(c), both S0S_0 and S1S_1 emerge as ground states. Furthermore, Figure 9 quantifies the average Euclidean distance Δd\Delta d that each soft-spin xpix_{pi} needs to traverse to transition from the local minimum S1S_1 to the global minimum S0S_0, passing through the nearest saddle point. In every scenario analyzed, the VISA model demonstrates a shorter requisite distance compared to the analogous CIM model, underscoring its efficiency in navigating the energy landscape.

Critical points of the VISA Hamiltonian

Figure 9. Critical points of HVISAH_{\mathrm{VISA}} for N=8N=8 JJ-Möbius ladder graph with J=0.4J=0.4. Each point is characterized by its energy EE and Euclidean distance from the origin dd. The number of soft spins normalizes distance dd. Blue and red circles denote minima for states S1S_1 and S0S_0, respectively, while black circles indicate other minima and saddle points of HVISAH_{\mathrm{VISA}}. The closest saddle point (SP) to excited state S1S_1 is highlighted in green. Progressing from figures (a) to (f), we systematically increase the gain γi=γ\gamma_i=\gamma for all ii and the penalty PP, following a typical annealing schedule. Notably, at (c), with γ=−0.087\gamma=-0.087 and P=0.32P=0.32, we reach a critical juncture that delineates the transition between global minima S0S_0 and S1S_1, as illustrated in Figure 4(j), where S0S_0 and S1S_1 attain equal energy levels EE. Adjacent bars to the main plots list distance Δd\Delta d for journey S1→SP→S0S_1 \to\mathrm{SP} \to S_0 for VISA (blue) and CIM (red), where for CIM we take p=γp=\gamma.

Basins of Attraction

Figure 10 illustrates the basins of attraction for a range of gain γi=γ∀i\gamma_i=\gamma\forall i and penalty PP values on JJ-Möbius ladder graphs with J=0.4J=0.4. Panels (a) to (f) in the figure show the evolution of these basins as γ\gamma and PP are incrementally increased, following a typical gain-based and penalty annealing schedule in the VISA model. The basins of attraction are defined by the initial states xpi(0)x_{pi}(0), uniformly distributed across the interval [−1,1][-1,1], which converge to distinct minima through gradient descent. Initially, at (γ,P)=(−0.5,0)(\gamma,P)=(-0.5,0), the global minimum is S1S_1, which has the largest basin of attraction, capturing all initial states towards S1S_1. However, as γ\gamma and PP progressively increase, the attraction basin associated with the excited state S0S_0 expands. Beyond the critical threshold in the γ−P\gamma-P parameter space, demonstrated in Figure 4(j), S0S_0 transitions to become the new ground state. Further annealing of γ\gamma and PP beyond this threshold reveals additional higher-energy states through the process of gradient descent.

Basins of attraction of the VISA model landscape on J-Möbius ladder graph

Figure 10. Basins of attraction of the VISA model landscape on JJ-Möbius ladder graph. We take N=8N = 8 and J=0.4J = 0.4 with various gains γi=γ∀i\gamma_i = \gamma\forall i and penalties PP as they anneal in the VISA method. Four thousand randomly distributed starting points xpi(0)x_{pi}(0) in [−1,1][-1,1] are plotted with colors corresponding to minima reached via gradient descent using Newton’s method. (γ,P)(\gamma, P) (a) (−0.5,0)(-0.5,0), (b) (−0.25,0.15)(-0.25,0.15), (c) (−0.087,0.32)(-0.087,0.32), (d) (0.25,0.5)(0.25,0.5), (e) (0.5,0.75)(0.5,0.75), and (f) (0.75,1.0)(0.75,1.0). To characterize points, the magnetization magnitude ∣m∣=mx2+my2+mz2|\mathbf{m}| = \sqrt{m_x^2 + m_y^2 + m_z^2} and correlation magnitude ∣Xcorr∣=Xx2+Xy2+Xz2|\mathbf{X}_{\mathrm{corr}}| = \sqrt{X_x^2 + X_y^2 + X_z^2} are used, where mp=∑ixpi/Nm_p = \sum_i x_{pi}/N and Xp=∑i(xpi−mp)(xp(i+1)−mp)/∑i(xpi−mp)2X_p = \sum_i(x_{pi}-m_p)(x_{p(i+1)}-m_p)/\sum_i(x_{pi}-m_p)^2 are the average magnetization and correlations along the pp-axis, respectively. For small γ\gamma and PP, the basin of attraction is dominated by the S1S_1 state. As γ\gamma and PP grow, the volume of the basin of attraction for state S0S_0 increases. For γ\gamma and PP, which lie on the critical boundary, shown here in (c), both S0S_0 and S1S_1 states have the same energy. As γ\gamma and PP increase further, S0S_0 becomes the ground state. This is indicated by the switch between excited (red) and ground (blue) states.

Second-Order Scalar Networks Minimizing the Ising Hamiltonian on JJ-Möbius Ladder Graphs

Figure 11 illustrates the Aharonov-Hopf bifurcation in soft-spins within the ME-HT model. For each time step tt, we apply a clipping function [xi]t=sgn⁡([xi]t)[x_i]_t = \operatorname{sgn}([x_i]_t) when ∣[xi]t∣>1|[x_i]_t| > 1, alongside a nonlinear activation function g(xi)=tanh⁡(xi)g(x_i) = \tanh(x_i). The parameter α\alpha is adjusted according to the largest positive eigenvalue λmax⁡\lambda_{\max} of the adjacency matrix JJ. Concurrently, Figure 12 displays the temporal evolution of scalar amplitudes as dictated by the SVL model, applied to the same Möbius graph with J=1J = 1.

Evolution of momentum enhanced Hopfield-Tank method for an N = 8 J-Möbius ladder network with J = 1

Figure 11. Evolution of momentum enhanced Hopfield-Tank method for an N=8N = 8 JJ-Möbius ladder network with J=1J = 1. (a) The amplitudes connected by the frustrated edges are lower than in the rest of the system and are shown in red. (b) The corresponding Ising Hamiltonian decreases in time, and the ground state is found, with energy given by the dashed red line. (c) Schematic representation of state S1S_1 realised by the soft-spin momentum enhanced HT model. Here, m=1.0m = 1.0, α=2.5/λmax⁡\alpha= 2.5/\lambda_{\max}, β=1.5(1−t/T)\beta= 1.5(1-t/T), γ=0.7\gamma= 0.7, and xi(0)x_i(0) is chosen uniformly at random from the range [−0.01,0.01][-0.01,0.01]. Fourth order Runge-Kutta is used with fixed time step Δt=0.1\Delta t = 0.1 to solve Eq. (10).

Evolution of the spin-vector Langevin (SVL) model

Figure 12. Evolution of the spin-vector Langevin (SVL) model. Applying the SVL model on an N=8N = 8 JJ-Möbius ladder network with coupling strength J=1J = 1. (a) depicts the amplitudes connected by frustrated edges, shown in red, which are lower than those in the rest of the system. (b) illustrates the real annealing functions A(t)A(t) in blue and B(t)B(t) in red, satisfying the boundary conditions A(0)=B(T)=1A(0) = B(T) = 1 and A(T)=B(0)=0A(T) = B(0) = 0, over an annealing period T=100T = 100. (c) shows the total Hamiltonian H(t)=A(t)H0+B(t)HPH(t) = A(t)H_0+B(t)H_P dynamics: it decreases initially as the ground state of H0H_0 is reached, then increases as A(t)A(t) and B(t)B(t) are annealed. Post a critical juncture, the SVL model aims to minimize the problem Hamiltonian HPH_P, identifying the ground state of the JJ-Möbius ladder, indicated by the dashed red line. Parameters used are m=1.0m = 1.0, α=1/λmax⁡\alpha= 1/\lambda_{\max}, γ=1.0\gamma= 1.0, and noise ξ=0\xi= 0. Annealing schedules are defined as A(t)=1−t/TA(t) = 1-t/T and B(t)=t/TB(t) = t/T. Initial phases θi(0)\theta_i(0) are randomly selected from [−π/2,π/2][-\pi/2, \pi/2]. Equation (11) is solved using a fourth-order Runge-Kutta method with a fixed time step of Δt=0.1\Delta t = 0.1.

Eigenvalues, Eigenvectors, and Ground States of J−GJ-G Cyclic Graphs

Here we refer to J−GJ-G cyclic graph defined in the main text, and illustrated in Figure 6(a)-(b) for N=8N = 8. For general NN with couplings Jij∈{−1,−J,−G}J_{ij} \in\{-1,-J,-G\}, the NN eigenvalues are given by

λn=−2cos⁡(2πn/N)−J(−1)n−2Gcos⁡(2πkn/N),(14)\lambda_n = -2\cos(2\pi n/N) - J(-1)^n - 2G\cos(2\pi kn/N), \tag*{(14)}

where n=1,2,…,Nn = 1,2,\ldots,N. Equation (14) follows from substituting J1,jJ_{1,j} into the general form of matrix eigenvalues for cyclic graphs given in the main text. As JJ and GG

vary within [−1,1][-1,1], the leading eigenvalue changes. Constrained to this domain, for N=8N = 8 and k=2k = 2, the leading eigenvalues are given by n=4,5,6n = 4,5,6. Substituting these values into Eq. (14) and equating each pair gives three boundaries defined by J=1−2/2−GJ = 1-\sqrt{2}/2-G, J=G−1/2J = G-1/\sqrt{2}, and G=1/2G = 1/2. Similarly for k=3k = 3, we obtain two unique leading eigenvalues (n=4,5)(n = 4,5) in the J−GJ-G domain, with boundary J=1−2/2+(1+1/2)GJ = 1-\sqrt{2}/2+(1+1/\sqrt{2})G. Eigenvectors corresponding to leading eigenvalues are used to deduce analogous Ising states by projecting the eigenvector onto the nearest hypercube corner [−1,1]N[-1,1]^N. These Ising states are given in Figure 6(e) and (h). Gurobi is used to obtain ground states in J−GJ-G space. Four unique configurations are found with N=8N = 8: namely S0S_0, S1S_1, and S2S_2 for k=2k = 2, and S0S_0, S1S_1, and S3S_3 for k=3k = 3. S2S_2 and S3S_3 are defined as the configurations of Ising spins given by S2=(1,1,−1,−1,1,1,−1,−1)S_2 = (1,1,-1,-1,1,1,-1,-1) and S3=(1,1,−1,1,1,−1,1,−1)S_3 = (1,1,-1,1,1,-1,1,-1). For even N/2N/2, these four states have energies

E0(J,G)=(J−2−2G(−1)k+1)N/2,(15)E_0(J,G) = (J-2-2G(-1)^{k+1})N/2, \tag*{(15)}
E1(J,G)=4−(J+2)N/2+(−1)k(N−4k)G,(16)E_1(J,G) = 4-(J+2)N/2+(-1)^k(N-4k)G, \tag*{(16)}
E2(J,G)=((−1)N/4J+(1+(−1)k)(−1)dG)N/2,(17)E_2(J,G) = ((-1)^{N/4}J+(1+(-1)^k)(-1)^dG)N/2, \tag*{(17)}
E3(J,G)=4−N+(2−N/2)J+(−1)k(N−4k)G,(18)E_3(J,G) = 4-N+(2-N/2)J+(-1)^k(N-4k)G, \tag*{(18)}

where d=k/2d = k/2 if kk is even, and 0 otherwise. Equating the relevant energies for k=2k = 2 gives three boundaries defined by separators J=1/2−GJ = 1/2-G, J=G−1/2J = G-1/2, and G=1/2G = 1/2. Similarly for k=3k = 3, the boundary edges are given by J=1/2+3/2GJ = 1/2+3/2G, J=3/2+2GJ = 3/2+2G, and J=0J = 0. Eigenvalues and ground states for J−GJ-G cyclic graphs are shown in Figure 13 for values of JJ and GG considered in the main text.

Eigenvalues of N = 8 J − G cyclic graphs

Figure 13. Eigenvalues of N=8N = 8 J−GJ-G cyclic graphs as functions of JJ and GG. Each plot corresponds to one of the red lines in Figure 6(f) and (i). Ground state probabilities are calculated on these lines in J−GJ-G space for various methods in the main text. (a) k=2k = 2 and G=0.5G = 0.5. (b) k=2k = 2 and J=0J = 0. (c) k=3k = 3 and G=−0.8G = -0.8. (d) k=3k = 3 and J=−0.5J = -0.5. Vertical dashed red and black lines show where ground state energies and leading eigenvalues change, respectively. Background colors denote ground states in specific regions, with states and corresponding colors listed in the key.

Supplementary Information: Vector Ising Spin Annealer for Minimizing Ising Hamiltonians

James S. Cummins; Natalia G. Berloff

Critical Points of VISA Hamiltonian

To determine the critical points of HVISAH_{\mathrm{VISA}}, we set ∂E∂xi=0\frac{\partial E}{\partial x_i}=0 for all ii, where ii ranges from 1 to NN. Figure S1 depicts these critical points, with the minima corresponding to the states S0S_0 and S1S_1 emphasized. As the gain γi(t)\gamma_i(t) and the collinearity penalty P(t)P(t) are systematically increased, a transition in the ground state from S1S_1 to S0S_0 is observed. Notably, there is an infinite continuum of (γi,P)(\gamma_i,P) pairs where S0S_0 and S1S_1 share the same energy level. This continuum forms a demarcation line in the γ−P\gamma-P space, illustrated in Fig. (??)(j). At a specific point on this boundary, as depicted in Figure S1(c), both S0S_0 and S1S_1 emerge as ground states. Furthermore, Figure S1 quantifies the average Euclidean distance Δd\Delta d that each soft-spin xpix_{pi} needs to traverse to transition from the local minimum S1S_1 to the global minimum S0S_0, passing through the nearest saddle point. In every scenario analyzed, the VISA model demonstrates a shorter requisite distance compared to the analogous CIM model, underscoring its efficiency in navigating the energy landscape.

Critical points of $H_{\mathrm{VISA}}$ for the $N=8$ $J$-Möbius ladder graph

Figure S1. Critical points of HVISAH_{\mathrm{VISA}} for N=8N = 8 JJ-Möbius ladder graph with J=0.4J = 0.4. Each point is characterized by its energy EE and Euclidean distance from the origin dd. The number of soft spins normalizes distance dd. Blue and red circles denote minima for states S1S_1 and S0S_0 respectively, while black circles indicate other minima and saddle points of HVISAH_{\mathrm{VISA}}. The closest saddle point (SP) to excited state S1S_1 is highlighted in green. Progressing from figures (a) to (f), we systematically increase the gain γi=γ\gamma_i = \gamma for all ii and the penalty PP, following a typical annealing schedule. Notably, at (c), with γ=−0.087\gamma= -0.087 and P=0.32P = 0.32, we reach a critical juncture that delineates the transition between global minima S0S_0 and S1S_1, as illustrated in Fig. (??)(j), where S0S_0 and S1S_1 attain equal energy levels EE. Adjacent bars to the main plots list distance Δd\Delta d for journey S1→SP→S0S_1 \to\mathrm{SP} \to S_0 for VISA (blue) and CIM (red), where for CIM we take p=γp = \gamma.

Basins of Attraction

Figure S2 illustrates the basins of attraction for a range of gain γi=γ ∀i\gamma_i=\gamma\ \forall i and penalty PP values on JJ-Möbius ladder graphs with J=0.4J=0.4. Panels (a) to (f) in the figure show the evolution of these basins as γ\gamma and PP are incrementally increased, following a typical gain-based and penalty annealing schedule in the VISA model. The basins of attraction are defined by the initial states xpi(0)x_{pi}(0), uniformly distributed across the interval [−1,1][-1,1], which converge to distinct minima through gradient descent. Initially, at (γ,P)=(−0.5,0)(\gamma,P)=(-0.5,0), the global minimum is at S1S_1, which has the largest basin of attraction, capturing all initial states towards S1S_1. However, as γ\gamma and PP are progressively increased, the basin of attraction associated with the excited state S0S_0 expands. Beyond the critical threshold in the γ−P\gamma-P parameter space, demonstrated in Fig. (??)(j), S0S_0 transitions to become the new ground state. Further annealing of γ\gamma and PP beyond this threshold reveals additional higher-energy states through the process of gradient descent.

Basins of attraction of the VISA model landscape on J-Möbius ladder graph

Figure S2. Basins of attraction of the VISA model landscape on JJ-Möbius ladder graph. We take N=8N = 8 and J=0.4J = 0.4 with various gains γi=γ∀i\gamma_i = \gamma\forall i and penalties PP as they anneal in the VISA method. 4000 randomly distributed starting points xpi(0)x_{pi}(0) in [−1,1][-1,1] are plotted with colors corresponding to minima reached via gradient descent using Newton’s method. (γ,P)(\gamma, P) (a) (−0.5,0)(-0.5,0), (b) (−0.25,0.15)(-0.25,0.15), (c) (−0.087,0.32)(-0.087,0.32), (d) (0.25,0.5)(0.25,0.5), (e) (0.5,0.75)(0.5,0.75), and (f) (0.75,1.0)(0.75,1.0). To characterize points, the magnetization magnitude ∣m∣=mx2+my2+mz2|\mathbf{m}| = \sqrt{m_x^2 + m_y^2 + m_z^2} and correlation magnitude ∣Xcorr∣=Xy2+Xy2+Xz2|\mathbf{X}_{\mathrm{corr}}| = \sqrt{X_y^2 + X_y^2 + X_z^2} are used, where mp=∑ixpi/Nm_p = \sum_i x_{pi}/N and Xp=∑i(xpi−mp)(xp(i+1)−mp)/∑i(xpi−mp)2X_p = \sum_i(x_{pi} - m_p)(x_{p(i+1)} - m_p)/\sum_i(x_{pi} - m_p)^2 are the average magnetization and correlations along the pp-axis, respectively. For small γ\gamma and PP, the basin of attraction is dominated by the S1S_1 state. As γ\gamma and PP grow, the volume of the basin of attraction for state S0S_0 increases. For γ\gamma and PP which lie on the critical boundary, shown here in (c), both S0S_0 and S1S_1 states have the same energy. As γ\gamma and PP increase further, S0S_0 becomes the ground state. This is indicated by the switch between excited (red) and ground (blue) states.

References

  1. [1]N. C. Thompson and S. Spanuth, Communications of the ACM 64, 64 (2021).
  2. [2]S. K. Vadlamani, T. P. Xiao, and E. Yablonovitch, Proceedings of the National Academy of Sciences 117, 26639 (2020).
  3. [3]E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser, arXiv preprint quant-ph/0001106 (2000).
  4. [4]A. Lucas, Frontiers in physics 2, 5 (2014).
  5. [5]N. G. Berloff, M. Silva, K. Kalinin, A. Askitopoulos, J. D. Töpfer, P. Cilibrizzi, W. Langbein, and P. G. Lagoudakis, Nature materials (2017).
  6. [6]K. P. Kalinin, A. Amo, J. Bloch, and N. G. Berloff, Nanophotonics 9, 4127 (2020).
  7. [7]G. De las Cuevas and T. S. Cubitt, Science 351, 1180 (2016).
  8. [8]P. L. McMahon, A. Marandi, Y. Haribara, R. Hamerly, C. Langrock, S. Tamate, T. Inagaki, H. Takesue, S. Utsunomiya, K. Aihara, et al., Science 354, 614 (2016).
  9. [9]T. Inagaki, Y. Haribara, K. Igarashi, T. Sonobe, S. Tamate, T. Honjo, A. Marandi, P. L. McMahon, T. Umeki, K. E. Eubutsu, et al., Science 354, 603 (2016).
  10. [10]Y. Yamamoto, K. Aihara, T. Leleu, K.-i. Kawarabayashi, S. Kako, M. Fejer, K. Inoue, and H. Takesue, npj Quantum Information 3, 1 (2017).
  11. [11]hara, et al., Science advances 7, eabh0952 (2021).
  12. [12]F. Cai, S. Kumar, T. Van Vaerenbergh, X. Sheng, R. Liu, C. Li, Z. Liu, M. Foltin, S. Yu, Q. Xia, et al., Nature Electronics 3, 409 (2020).
  13. [13]M. Babaeian, D. T. Nguyen, V. Demir, M. Akbulut, P.-A. Blanche, Y. Kaneda, S. Guha, M. A. Neifeld, and N. Peyghambarian, Nature communications 10, 1 (2019).
  14. [14]V. Pal, S. Mahler, C. Tradonsky, A. A. Friesen, and N. Davidson, Physical Review Research 2, 033008 (2020).
  15. [15]M. Parto, W. Hayenga, A. Marandi, D. N. Christodoulides, and M. Khajavikhan, Nature materials 19, 725 (2020).
  16. [16]D. Pierangeli, G. Marcucci, and C. Conti, Physical review letters 122, 213902 (2019).
  17. [17]C. Roques-Carmes, Y. Shen, C. Zanoci, M. Prabhu, F. Atieh, J. Ding, T. Dubček, C. Mao, M. R. Johnson, V. Čeperić, et al., Nature communications 11, 249 (2020).
  18. [18]M. Vretenar, B. Kassenberg, S. Bissesar, C. Toebes, and J. Klaers, Physical Review Research 3, 023167 (2021).
  19. [19]K. Kalinin, G. Mourgias-Alexandris, H. Ballani, N. G. Berloff, J. H. Clegg, D. Cletheroe, C. Gkantsidis, I. Haller, V. Lyutsarev, F. Parmigiani, L. Pickup, et al., arXiv preprint arXiv:2304.12594 (2023).arxiv.org/abs/2304.12594
  20. [20]H. Goto, K. Endo, M. Suzuki, Y. Sakai, T. Kanao, Y. Hamakawa, R. Hidaka, M. Yamasaki, and K. Tatsumura, Science Advances 7, eabe7953 (2021).
  21. [21]P. Date, D. Arthur, and L. Pusey-Nazzaro, Scientific reports 11, 10029 (2021).
  22. [22]M. Gilli, D. Maringer, and E. Schumann, Numerical methods and optimization in finance (Academic Press, 2019).
  23. [23]N. A. Pierce and E. Winfree, Protein engineering 15, 779 (2002).
  24. [24]K. A. Dill, S. B. Ozkan, M. S. Shell, and T. R. Weikl, Annu. Rev. Biophys. 37, 289 (2008).
  25. [25]M. Calvanese Strinati and C. Conti, Nature Communications 13, 7248 (2022).
  26. [26]M. C. Strinati and C. Conti, Physical Review Letters 132, 017301 (2024).
  27. [27]K. P. Kalinin and N. G. Berloff, New Journal of Physics 20, 113023 (2018).
  28. [28]N. Stroev and N. G. Berloff, Physical Review Letters 126, 050504 (2021).
  29. [29]I. G. Rosenberg, (1975).
  30. [30]E. Boros and P. L. Hammer, Discrete applied mathematics 123, 155 (2002).
  31. [31]J. J. Hopfield, Proceedings of the national academy of sciences 79, 2554 (1982).
  32. [32]J. J. Hopfield and D. W. Tank, Biological cybernetics 52, 141 (1985).
  33. [33]H. Goto, Scientific reports 6, 1 (2016).
  34. [34]J. S. Cummins, H. Salman, and N. G. Berloff, arXiv preprint arXiv:2311.17359 (2023).DOI
  35. [35]K. P. Kalinin and N. G. Berloff, Communications Physics 5, 20 (2022).
  36. [36]A. Orvieto and A. Lucchi, Advances in Neural Information Processing Systems 32 (2019).
  37. [37]S. Saab Jr, S. Phoha, M. Zhu, and A. Ray, Machine Learning 111, 3245 (2022).
  38. [38]D. Subires, F. J. Gómez-Ruiz, A. Ruiz-García, D. Alonso, and A. Del Campo, Physical Review Research 4, 023104 (2022)
  39. [39]J.-R. Jiang and C.-W. Chu, in 2022 IEEE 4th ECICE (IEEE, 2022) pp. 406–411.
  40. [40]The BFGS algorithm is implemented with minimizer FindMinimum in Wolfram Mathematica. VISA Hamiltonian H_VISA is subject to BFGS with fixed γ_i = γ = 1.0Vi and P = 0.8.
  41. [41]J. Gancio and N. Rubido, Chaos, Solitons & Fractals 158, 112001 (2022).
  42. [42]Y. Haribara, H. Ishikawa, S. Utsunomiya, K. Aihara, and Y. Yamamoto, Quantum Science and Technology 2, 044002 (2017).
  43. [43]R. Hamerly, T. Inagaki, P. L. McMahon, D. Venturelli, A. Marandi, T. Onodera, E. Ng, C. Langrock, K. Inaba, T. Honjo, et al., Science advances 5, eaau0823 (2019).
  44. [44]M. P. Harrigan, K. J. Sung, M. Neeley, K. J. Satzinger, F. Arute, K. Arya, J. Atalaya, J. C. Bardin, R. Barends, S. Boixo, et al., Nature Physics 17, 332 (2021).
  45. [45]F. Böhm, G. Verschaffelt, and G. Van der Sande, Nature communications 10, 1 (2019).
  46. [46]S. Arora, E. Berger, H. Elad, G. Kindler, and M. Safra, in 46th Annual IEEE FOCS Symposium (IEEE, 2005) pp. 206–215.
  47. [47]Gurobi Optimization, LLC, “Gurobi Optimizer Reference Manual,” (2023).

Paper details

vlnc:W_q645zj9c
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents