1. Analog Iterative Machine (AIM): using light to solve quadratic optimization problems with mixed variables
- Author
-
Kalinin, Kirill P., Mourgias-Alexandris, George, Ballani, Hitesh, Berloff, Natalia G., Clegg, James H., Cletheroe, Daniel, Gkantsidis, Christos, Haller, Istvan, Lyutsarev, Vassily, Parmigiani, Francesca, Pickup, Lucinda, and Rowstron, Antony
- Subjects
Computer Science - Emerging Technologies ,Mathematics - Optimization and Control ,Physics - Applied Physics - Abstract
Solving optimization problems is challenging for existing digital computers and even for future quantum hardware. The practical importance of diverse problems, from healthcare to financial optimization, has driven the emergence of specialised hardware over the past decade. However, their support for problems with only binary variables severely restricts the scope of practical problems that can be efficiently embedded. We build analog iterative machine (AIM), the first instance of an opto-electronic solver that natively implements a wider class of quadratic unconstrained mixed optimization (QUMO) problems and supports all-to-all connectivity of both continuous and binary variables.Beyond synthetic 7-bit problems at small-scale, AIM solves the financial transaction settlement problem entirely in analog domain with higher accuracy than quantum hardware and at room temperature. With compute-in-memory operation and spatial-division multiplexed representation of variables, the design of AIM paves the path to chip-scale architecture with 100 times speed-up per unit-power over the latest GPUs for solving problems with 10,000 variables. The robustness of the AIM algorithm at such scale is further demonstrated by comparing it with commercial production solvers across multiple benchmarks, where for several problems we report new best solutions. By combining the superior QUMO abstraction, sophisticated gradient descent methods inspired by machine learning, and commodity hardware, AIM introduces a novel platform with a step change in expressiveness, performance, and scalability, for optimization in the post-Moores law era., Comment: Main sections plus supplementa material for a total of 41 pages. 7 figures
- Published
- 2023