Current research into optimization algorithms brings the added benefit of foresight into future computational challenges. By testing optimization techniques on tough problems, researchers can more deeply define what makes that problem difficult, and how that difficulty will impact scalability.

In his talk at Upgrade 2020, the NTT Research Summit, Dr. Hideo Mabuchi, Professor of Applied Physics at Stanford University, assessed the impacts of the effectiveness of optimization using the Ising machine problem. “We see that a critical frontier for cutting-edge academic research involves both the development of novel heuristic algorithms that deliver better performance with lower cost, and providing deep conceptual insight into what makes a given problem instance easy or hard for such algorithms,” he said.

Dr. Mabuchi explains that solving for the ground state of an Ising model represents a canonical problem in combinatorial optimization. That is, to find the ground state of an Ising model is to find an optimal configuration of its variables. The Ising model comprises a lattice of magnetic moments, or spins, with binary values. Each spin contributes to the total energy, by an amount that is impacted by interactions between these binary values, as well as a magnetic field acting upon each point.

Optimization problems of this kind represent a crucial frontier for the future of computing ­– the larger the lattice, the longer it takes to solve for the ground state. “Qualitatively speaking, this makes the Ising problem a representative of hard optimization problems,” Dr. Mabuchi said. “The runtime required by any computational algorithm to find exact solutions should asymptotically scale exponentially with the number of spins … for worst-case instances.” Detailed research on algorithms for the Ising problem contributes to our understanding of a broad class of hard optimization problems.

Exploring optimization techniques beyond conventional CPU algorithms not only reduces runtimes, it also makes the horizon of CPU limitations clearer. “As we talk about the end of Moore’s law, and speculate about a so-called second quantum revolution, it’s natural to talk not only about novel algorithms… but also about highly customized, special purpose hardware architectures on which we may run entirely unconventional algorithms,” he said.

It’s critical to approach this problem using not only electronic components, but a mix of analog, optical, and digital hardware. The integration of different physical and digital structures will drive research past the limitations of CPUs and help to not only define exactly why a problem takes so long to solve but which hardware innovations are most beneficial, Dr. Mabuchi said.

Dr. Mabuchi develops this perspective by considering the Coherent Ising Machine architecture based on optical parametric oscillators (OPOs). A network of OPOs are fed a pump of power from a starting point of 0. Individually, there exists a lasing threshold at which each OPO randomly chooses one of two phases, which can be associated with the binary values of an Ising spin. When the OPOs are coupled together, the effects of the fields created by each OPO modifies the collective threshold across the entire network.

To solve for the ground state of the coupled OPO network, viewed as a lattice of Ising spins, the pump is increased from 0 and the relative phases of the OPOs are observed when the minimum lasing threshold is reached. A fundamental research goal for Coherent Ising Machines is to pinpoint features of specific OPO-coupling patterns that can cause problems for this optimization strategy.  “We conjecture that such analysis can provide fundamental insight into what makes certain optimization instances hard or easy for coherent Ising machines, and hope that our approach can lead to both improvements of the basic CIM algorithm and pre-processing rubrics for rapidly assessing CIM suitability for a given optimization instance,” he concludes.

Searching for the ground state of an Ising model using innovative techniques like this is an example of how such optimization practices can unveil new perspectives on an old problem.

For the full transcript of Hideo Mabuchi’s presentation, click here.

Watch Hideo Mabuchi’s full presentation below.