Analog Computing System for Accelerating Combinatorial Optimization

OVERVIEW

Hybrid analog-digital system for quickly solving large combinatorial optimization problems.

• Achieves high adaptivity and scalability over previous accelerators while ensuring solution quality
• Logistics, chip design, resource allocation, network analysis, scheduling, machine learning, bioinformatics

BACKGROUND

Combinatorial optimization problems arise in diverse areas like logistics, chip design, and resource management. These problems, such as the classic MAX-CUT and various instances of NP-hard decision tasks, demand immense computational power since brute-force or traditional digital methods scale exponentially with system size. Historically, digital solvers and annealing-based algorithms (including simulated/digital annealing and Ising machines) have been developed to provide approximate solutions, but struggle to scale efficiently or to solve dense, fully connected graphs. Further, many analog accelerator approaches are highly specialized, limited to sparse problems, or are technically challenging to program and scale to larger problem instances due to device variations, interconnect limitations, or support for only a narrow class of topologies. Thus, there remains a strong need for a scalable, programmable, robust, and efficient hardware solution for large-scale combinatorial optimization across a wide variety of problem structures and types.

INNOVATION

Researchers at the University of Michigan have developed a programmable analog-digital accelerator employing a spin-network-inspired architecture, where analog variables are realized as electric charges on capacitors. By relaxing the computationally intense sinusoidal coupling required in earlier models to a simpler, piecewise-linear coupling function, the solution process maintains quality while greatly simplifying hardware realization and computational demands. The system comprises a scalable array of analog memory nodes, a shared computational unit for flexible problem encoding, and an optimized design for current superposition and simultaneous readout. Crucially, the analog-to-binary mapping for the final output is incorporated inherently into the network’s dynamics, ensuring optimal solution rounding in constant time. This architectural flexibility allows for rapid and high-quality solutions to arbitrary (including dense and fully connected) combinatorial optimization problems. Real-world impact spans large-scale logistics, VLSI circuit design, scheduling, complex network analysis, and advanced data science, offering polynomially scaling run-times and area/power efficiencies well beyond conventional digital, quantum, or prior analog accelerators.

ADDITIONAL INFORMATION

REFERENCES:

• "Custom CMOS Ising Machine Based on Relaxed Burer-Monteiro-Zhang Heuristic"
• "Scalable almost-linear dynamical Ising machines"

INTELLECTUAL PROPERTY:

Patent application pending.

KEYWORDS:

Lsing Machine, Analog Computing, Optimization, Accelerator