Efficient combinatorial optimization by quantum-inspired parallel annealing in analogue memristor crossbar.

Area of Science:

• Computer Science
• Materials Science
• Physics

Background:

• Combinatorial optimization problems are computationally intensive, posing challenges for exact solutions due to rapid increases in complexity with problem size.
• Specialized hardware, like memristor-based analog Ising machines, offers potential solutions but has not fully leveraged inherent parallelism and analog capabilities.
• Existing simulated annealing approaches on these platforms are limited in exploiting the full potential of memristor crossbar arrays.

Purpose of the Study:

• To propose and validate a quantum-inspired parallel annealing method for memristor-based Ising machines.
• To enhance the solution quality and efficiency of solving complex combinatorial optimization problems.
• To demonstrate the advantages of exploiting memristor technology's natural parallelism and analog features.

Main Methods:

• Developed a quantum-inspired parallel annealing algorithm tailored for memristor crossbar arrays.
• Implemented the algorithm on an integrated memristor chip.
• Experimentally solved benchmark problems including Max-Cut (weighted and unweighted) and the Traveling Salesman Problem.

Main Results:

• The proposed method achieved full parallelism, leading to significant speed and energy improvements.
• Experimental results demonstrated superior time- and energy-efficiency compared to previous simulated annealing and other Ising machine implementations.
• The approach effectively utilized memristor parallelism, analog states, and all-to-all connectivity.

Conclusions:

• The quantum-inspired parallel annealing method significantly enhances the performance of memristor-based Ising machines.
• This approach offers a promising pathway for efficiently solving complex combinatorial optimization problems.
• Memristor technology's unique features are effectively leveraged for advanced computational tasks.