Hard computational problems abound in today's world, from airline scheduling to healthcare. Large classes of these hard problems can be reduced to a form known as the Ising problem, which is closely related to the underlying physics of ferromagnetic materials. This project is based on a recently devised way to solve the Ising problem quickly and effectively in electronic hardware using networks of connected Complementary Metal Oxide Semiconductor (CMOS) oscillators, i.e., electronic equivalents of metronomes and grandfather clocks. Being able to solve large real-world problems much more quickly using this approach than what is currently possible will have broad and beneficially disruptive effects on society. The project's activities include course development, outreach to high-school students, yearly workshops for dissemination and interaction, and scientific and design tool infrastructure development.
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. It can be implemented using conventional CMOS electronics, which has many advantages: scalability / miniaturisability (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 advantage relates to variability, a significant problem in nanoscale CMOS. Unlike other schemes, where performance deteriorates due to variability, this approach can essentially eliminate variability by means of simple VCO-based calibration to bring all the oscillators to the same frequency. Yet another key potential advantage stems from the continuous/analog nature of the proposed scheme (as opposed to purely digital algorithms). Computational experiments indicate that the time the scheme takes to find good solutions of the Ising problem grows only very slowly with respect to the number of spins.This is a significant potential advantage over digital algorithms as hardware sizes scale up to large numbers of spins. In addition, virtually any type of nonlinear oscillator (not just CMOS) can be used to implement this scheme, including optical, micro-electronic mechanical systems, biochemical, spin torque device based, etc., oscillators.
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.
