FET: Medium: Latch Ising Machines (LIM)

University Of California-Berkeley, Berkeley CA

Investigators

Abstract

Difficult computational (NP-complete) problems abound in today’s world, in areas as diverse as secure communications, protein folding, neural networks and healthcare. Large classes of these hard problems can be reduced to a form known as the Ising problem, which is closely related to the physics of ferromagnetic materials. The project team has devised a novel way of solving the Ising problem quickly and effectively in hardware, using networks of small, simple circuits, specifically, ``static'' memory cells, widely used in electronic devices of every kind. The concept significantly broadens the overall understanding of Ising machine schemes and their operational mechanisms. This project is developing this method (termed LIM) to practical fruition, including demonstration on real-world problems from communications. Being able to solve such real-world problems much more quickly and accurately than is currently practical can lead to broad benefits to society. The project's activities include a focus on students from traditionally disadvantaged backgrounds, as well as workshops for dissemination and interaction. More precisely, the team is showing that Ising machines, which have previously been realized using quantum/optical schemes as well as oscillator networks, can also be implemented using bi-stable elements such as CMOS-based latches. Unlike previous Ising machine approaches, which are large, expensive and ill-suited to low-cost mass production, the proposed approach is a purely classical scheme that does not rely on quantum phenomena or novel nano-devices. Using conventional CMOS electronics has many advantages: scalability/miniaturizability (i.e., very large numbers of spins in a physically small system), well-established design processes and tools that essentially guarantee first-time working hardware, very low power operation, seamless integration with control and I/O logic, easy programmability via standard interfaces like USB, and low cost mass production. Another key potential advantage stems from the continuous/analog nature of LIM (as contrasted with purely digital algorithms). The researchers are developing LIM theoretically and computationally, implementing it in hardware, and demonstrating it on benchmark Ising problems as well as Ising forms of difficult communications-related problems. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.