bSB and dSB algorithms
The Ising problem is to find a spin configuration minimizing the Ising energy, defined as
(1)where si denotes the ith spin taking 1 or −1, N is the number of spins, Ji,j is the coupling coefficient between the ith and jth spins (Ji,j = Jj,i and Ji,i = 0), and hi is the local field on the ith spin. Since introducing an ancillary spin reduces the Ising problem to the one without local fields (see section S1), here, we focus on the Ising problem with no local fields (hi = 0).
To solve the Ising problem, QbM uses quantum-mechanical nonlinear oscillators called Kerr-nonlinear parametric oscillators (KPOs), each of which can generate a Schrödinger cat state, i.e., a quantum superposition of two oscillating states, via a quantum-mechanical bifurcation (31). Such a KPO has recently been realized experimentally using superconducting circuits (45, 46). However, the realization of a large-scale QbM will require a long time. On the other hand, it was found that a classical-mechanical model corresponding to QbM, referred to as a classical bifurcation machine (CbM), also works as an Ising machine (31, 33). In this case, we can efficiently simulate such a classical machine using present digital computers, instead of building real machines. [This is not the case for QbM, because QbM can also be used as a universal quantum computer (47, 48), which is classically unsimulatable.] This simulation approach paves the way for large-scale Ising machines with all-to-all connectivity.
By modifying the equations of motion for CbM such that computational costs are reduced and the symplectic Euler method (49) is applicable, we obtain the following Hamiltonian equations of motion for aSB (30)
(5)where xi and yi are, respectively, the position and momentum of a particle corresponding to the ith spin, dots denote time derivatives, a(t) is a control parameter increased from zero, a0 and c0 are positive constants, and VaSB is the potential energy in aSB.
To qualitatively explain the operation principle of aSB, we show an example of the dynamics in aSB in Fig. 1 (A and B), where the ferromagnetic two-spin Ising problem (J1,2 = J2,1 = 1) with solutions s1 = s2 = ± 1 is solved as the simplest problem. All positions and momenta are randomly set around zero at the initial time. The initial potential has a single local minimum at the origin (top and middle of Fig. 1B), so the particles circulate around the origin (Fig. 1A and middle of Fig. 1B). When a(t) becomes sufficiently large, bifurcations occur, that is, multiple local minima of the potential appear. Then, the particles adiabatically follow one of the minima. Consequently, each xi bifurcates to a positive or negative value (Fig. 1A and bottom of Fig. 1B). Since two local minima corresponding to the two solutions have lower energies and appear earlier than the other two local minima, the particles successfully find one of the solutions. Last, the sign of xi, sgn(xi), gives the ith spin, si, for the solution of the Ising problem. It has been empirically found that aSB works well for much larger-scale and more complex problems (30).