Abstract: Ising machines are an unconventional computing paradigm that consists in determining the solution to hard computational problems by finding the energy minimum of an Ising model. Out of the possible implementations, probabilistic Ising machine rely on the p-bit, a bistable, tunable, stochastic unit that can be easily implemented by physical systems like spintronic diodes. To maximize the performance of such a system, it is necessary to work on three levels: the encoding, the energy minimization schedule and the implementation.
Encoding a problem into an Ising model means transforming a given formulation of a task into a quadratic Hamiltonian. One way to simplify and automate this procedure is to define small Ising models that function as building blocks and a way to join them. This is the strategy of invertible logic gates, which act as omni-directional Boolean operators that make it possible to design probabilistic circuits. A problem like factorization can, for instance, be designed as multiplier circuit run in reverse. Even a complex combinatorial optimization problem like the maximum satisfiability problem can be intuitively implemented into a sparse graph using this encoding paradigm.
Having a correct encoding of a problem is often not enough to maximize the probability (or improving the time) to find its solution. Large problems have enough variables that a complete mapping of the solution space (2N, with N being the number of p-bits/spins of the system) is unfeasible. In these cases, it is necessary to act on a scaling hyperparameter, usually known as the pseudo-temperature B. While straightforward energy minimization schedules like simulated annealing operate by linearly increasing B from a low value to a high one, effectively freezing the system, more advanced algorithms add additional degrees of freedom and operators. Parallel tempering, for instance, avoids local minima by employing several copies of the system (replicas) running at different Bs that can swap their states according to their energy. Simulated quantum annealing uses replicas with a quantum-inspired transverse field that forces a collapse into a single low-energy state.
The implementation of the Ising machine is what establishes the working speed, and thus the performance, of the system. Moreover, different hardware may impose limitations that also affect the compatible encodings and energy minimization schedules. Field-programmable gate arrays, for instance, allow for highly parallelizable computation, but require sparse graph topologies.
One of the technologies with the most potential for Ising machines is spintronics. Devices like magnetic tunnel junctions are intrinsically compatible with implementing an Ising spin in several ways. The parallel and anti-parallel state may encode the up and down state of the p-bit, or the phase of an oscillating magnetization of a spin-torque nano oscillator can be discretized using injection-locking to obtain the spin of an oscillatory Ising machine. These systems are incredibly compact and energy efficient, on top of being characterized by high working speed and CMOS compatibility, making them excellent candidates for future applications geared towards the solution of computational problems in dedicated hardware.
Bio: Andrea Grimaldi achieved his Ph.D. in Physics at the University of Messina with the Petaspin group led by Giovanni Finocchio, focusing mainly on spintronics and probabilistic computing. He is currently employed as a post-doctoral researcher at the Politecnico di Bari.