Memristor-based hardware and algorithms for higher-order Hopfield optimization solver outperforming quadratic Ising machines

arXiv (Cornell University)

Abstract

Ising solvers offer a promising physics-based approach to tackle the challenging class of combinatorial optimization problems. However, typical solvers operate in a quadratic energy space, having only pair-wise coupling elements which already dominate area and energy. We show that such quadratization can cause severe problems: increased dimensionality, a rugged search landscape, and misalignment with the original objective function. Here, we design and quantify a higher-order Hopfield optimization solver, with 28nm CMOS technology and memristive couplings for lower area and energy computations. We combine algorithmic and circuit analysis to show quantitative advantages over quadratic Ising Machines (IM)s, yielding 48x and 72x reduction in time-to-solution (TTS) and energy-to-solution (ETS) respectively for Boolean satisfiability problems of 150 variables, with favorable scaling.

Authors 9

1. Mohammad Hizzani Aachen

   Forschungszentrum Jülich · RWTH Aachen University

   Affiliation as printed

   Forschungszentrum Jülich GmbH , Jülich , Germany

   RWTH Aachen University , Aachen , Germany

2. Arne Heittmann

   Forschungszentrum Jülich

   Affiliation as printed

   Forschungszentrum Jülich GmbH , Jülich , Germany

3. George A. Hutchinson

   University of California, Santa Barbara

   Affiliation as printed

   University of California , Santa Barbara , Santa Barbara , CA , USA

4. Dmitrii Dobrynin Aachen

   Forschungszentrum Jülich · RWTH Aachen University

   Affiliation as printed

   Forschungszentrum Jülich GmbH , Jülich , Germany

   RWTH Aachen University , Aachen , Germany

5. Thomas Van Vaerenbergh

   Hewlett Packard Enterprise (United States) · Hewlett Packard Enterprise (Ireland)

   Affiliation as printed

   Hewlett Packard Enterprise , Brussels , Belgium

6. Tinish Bhattacharya

   University of California, Santa Barbara

   Affiliation as printed

   University of California , Santa Barbara , Santa Barbara , CA , USA

7. Adrien Renaudineau

   Université Paris-Saclay

   Affiliation as printed

   Université Paris-Saclay , Paris , France

8. Dmitri B. Strukov

   University of California, Santa Barbara

   Affiliation as printed

   University of California , Santa Barbara , Santa Barbara , CA , USA

9. John Paul Strachan Aachen

   Forschungszentrum Jülich · RWTH Aachen University

   Affiliation as printed

   Forschungszentrum Jülich GmbH , Jülich , Germany

   RWTH Aachen University , Aachen , Germany