Stress-Testing Memcomputing on Hard Combinatorial Optimization Problems.

Area of Science:

• * Computing paradigms and novel architectures
• * Computational complexity and optimization algorithms
• * Electronic circuit design and simulation

Background:

• * Memcomputing utilizes time non-local dynamical systems for in-memory computing.
• * Digital memcomputing machines (DMMs) are scalable and excel at combinatorial optimization.
• * DMMs can be realized using standard electronic circuits, described by ordinary differential equations.

Purpose of the Study:

• * To stress-test the scalability of digital memcomputing machines (DMMs) for large-scale optimization.
• * To validate linear time and memory resource scaling for DMM simulations beyond previous limits.
• * To compare DMM performance against state-of-the-art algorithms for hard problem instances.

Main Methods:

• * Simulation of DMMs using the commercial Falcon simulator.
• * Testing up to 64 million variables (approximately 1 billion literals) on a single CPU core.
• * Employing standard electronic circuits without quantum elements, described by ODEs.

Main Results:

• * DMM simulations exhibited linear scaling in both time and memory resources.
• * This linear scalability was maintained up to the largest tested problem size (64 million variables).
• * State-of-the-art algorithms required exponential resources for comparison.

Conclusions:

• * Memcomputing, particularly DMMs, offers significant advantages over traditional computing approaches for optimization.
• * The physics-based memcomputing approach demonstrates robust scalability for extremely large problems.
• * These findings reinforce the potential of DMMs for solving complex computational challenges efficiently.