Field-Programmable Ising Machines (FPIM)

Patent Status

Patent Pending

Brief Description

Certain difficult optimization problems, such as the traveling salesman problem, can be solved using so-called analog Ising machines, in which electronic components (such as certain arrangements of diodes or electronic switches) implement an analog of a well-studied physical system known as an Ising machine. The problem is recast so that its solution can be read off from the lowest-energy configuration of the analog Ising machine, a state which the system will naturally evolve towards. While promising, this methodology suffers major drawbacks. Firstly, the number of subunits, known as “spins”, in the analog Ising machines, as well as the number of connections between these subunits, can grow substantially with problem size. Secondly, existing implementations of this principle rely on chip constructions which are optimized for one or a few problems, and are not sufficiently reprogrammable to be repurposed efficiently for other applications. 

To address these problems, researchers at UC Berkeley have developed a device known as a Field-programmable Ising machine which can be adapted to implement an analog Ising machine using a variety of hardware designs, such as the diodes and switches mentioned above. These Ising machines can be effectively reprogrammed to efficiently solve a wide array of problems across various domains. The inventors have shown that this design can be applied to SAT (“Satisfiability”) problems, a class known to be similar to the traveling salesman problem, in that the number of spins needed and their level of connectivity do not grow too quickly with problem size.

Suggested uses

This technology could lead to the development of practical, cost-effective special-purpose chips designed to solve complex combinatorial optimization problems such as SAT with performance far exceeding that achievable using traditional linear computing techniques. This could have a similarly revolutionary effect as GPUs, which are special-purpose chips which implement massively parallelizable linear algebraic problems that are traditionally computationally costly.

Advantages

Field-programmable Ising machines are fully reprogrammable and agnostic regarding the hardware implementation of the Ising spins, both of which make them much more flexible than previous approaches. A classical Ising analog, these devices can be made much smaller, less expensively, and more scalable than quantum computers designed for similar purposes. It has also been shown that for so-called SAT problems, which are closely related to many optimization problems of practical interest, the number of analog spins required and the connectivity of those spins can scale minimally with the size of the problem input, whereas for existing devices these quantities can scale quite rapidly. 

Related Materials