Destabilization of Local Minima in Analog Spin Systems by Correction of Amplitude Heterogeneity

The relaxation of binary spins to analog values has been the subject of much debate in the field of statistical physics, neural networks, and more recently quantum computing, notably because the benefits of using an analog state for finding lower energy spin configurations are usually offset by the negative impact of the improper mapping of the energy function that results from the relaxation. We show that it is possible to destabilize trapping sets of analog states that correspond to local minima of the binary spin Hamiltonian by extending the phase space to include error signals that correct amplitude inhomogeneity of the analog spin states and controlling the divergence of their velocity. Performance of the proposed analog spin system in finding lower energy states is competitive against state-of-the-art heuristics.

Figure 1

Bifurcation diagram in the space $\{\theta =[a/1-p],{\mu }_j(\mathit{\sigma })\}$ at configuration $\mathit{\sigma }$. Thick lines correspond to the sets where $\mathrm{Re}[{\lambda }_j^{\pm }]=0$, i.e., $\theta =0$, $-1$, or $F({\mu }_j)$ with ${\mathrm{\Delta }}_j<0$, and dotted lines correspond to the sets where $\theta =G_{\pm }(\beta ,{\mu }_j)$. In the regions marked 1 and 2, the pair of eigenvalues ${\lambda }_j^{+}$ and ${\lambda }_j^{-}$ are complex conjugate with negative real parts and positive real parts, respectively, whereas in regions 3–5, they are both real with both, none, and one of their real parts being negative, respectively. $\beta =0.2$. Andronov-Hopf bifurcation (AH).

Figure 2

Control of the divergence in the auxiliary subspace. (a) Divergence $\mathrm{div}\mathit{g}$ in the auxiliary subspace vs normalized simulation time $t$. After some transient behavior, the divergence is constant and approximately described by its analytical value $\mathrm{div}\mathit{g}\approx \kappa$. (b) Divergence $\mathrm{div}\mathit{g}$ and average time $⟨t_{\mathrm{sol}}⟩$ for finding the ground state of the Ising Hamiltonian with a probability superior to 99% with $t_{\mathrm{sol}}=⟨t_0⟩[\log (0.1)/\log (1-P_0)]$ for $P_0<0.99$, and $t_{\mathrm{sol}}=⟨t_0⟩$ otherwise, with $P_0$ and $⟨t_0⟩$ (see inset) the probability of finding the ground state during a single run and averaged time to solution for successful runs, respectively.

Figure 3

Proportion $p_0(t)$ of instances unsolved, i.e., for which a ground-state configuration has not been found, after the CPU time $t$ in seconds of the SK problems of size $N=80$, 100, 150, and 200 shown in (a)–(d), respectively, for the proposed scheme and the BLS algorithm [38] in the logarithmic scale. The 95% confidence interval shown by dotted lines is calculated using 20 runs per instance.