Analog Iterative Machine (AIM): using light to solve quadratic optimization problems with mixed variables
Kirill kalinin, George Mourgias-Alexandris, Hitesh Ballani, Natalia G. Berloff, James Clegg, Daniel Cletheroe, Christos Gkantsidis, Istvan Haller, Vassily Lyutsarev, Francesca R. Parmigiani, L. Pickup, Antony I.T. Rowstron
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.
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.
Many real-world engineering problems involve hard combinatorial optimizations. Heuristic algorithms, trading off accuracy for time-to-solution, are crucial for their solvability. However, as the problem size increases, time becomes the critical factor and solving these problems motivates the development of more elaborate techniques. In my thesis, I adopt the approach of synergistic co-design of heuristics and computing platforms. I postulate that for scalability, besides providing competitive quality of solution in polynomial time, such deeply custom optimizing machines should be characterized by simplicity, homogeneity and parallelizability of operations and the independence from external computing resources. Bearing these features, I propose a novel class of custom computing machines aimed at solving large quadratic unconstrained binary optimization (QUBO) problems via continuous relaxation. The machines are simultaneously designed at the heuristic and hardware levels, and implementable using the accessible VLSI CMOS technology. At the heuristic level, I approximately solve the QUBO form of max-cut through its relaxed reformulation as two relatively tractable sub-problems. First, the binary constraint on the QUBO variables is relaxed, leading to a system of coupled 2D vectors that evolve to maximize a quantity closely related to the cut. The terminal states are generally non-binary and therefore must be rounded. Optimal rounding, the second sub-problem, is non-trivial as existing parametric rounding algorithms, due to their sequential nature, become the bottleneck. Along the directions of these problems, this work presents two QUBO machines. First, I present an analog QUBO machine that solves a relaxed problem using analog computing methods. The entire machine is designed at the circuit level to implement a network of almost-linearly coupled continuous spins. The analog variables are realized using capacitors and their coupling using a digital-to-analog converter. However, our reliance on external computing resources for optimal rounding and non-idealities inherent to analog computing limits the size of the problem that could be solved by the machine. In the second part of the work, I overcome these challenges and present a digital QUBO machine prototyped on a multi-FPGA system. The machine provides high quality solutions to arbitary 1024-node weighted or 2048-node unweighted QUBO problem by simultaneously solving the relaxed QUBO problem and implementing an optimal rounding procedure in massively parallel fashion. To the best of our knowledge, this is the first self-contained scalable relaxation-based machine that directly solves the problem of optimal rounding.
With the growing demand for efficient computing to tackle complex real-world challenges like combinatorial optimization, both academia and industry are exploring alternative computing paradigms. The Ising machine (IM) is one such approach, solving optimization problems by mapping their cost functions onto the Ising model. In this framework, finding the optimal solution equates to determining the Ising spin configuration corresponding to the ground state of the Ising Hamiltonian. Analog IMs, relying on artificial spins that can take analogue rather than binary values, have shown great potential in reaching this ground at high speeds. Optical implementations, such as the opto-electronic IM developed within our research group, are particularly promising due to their higher bandwidth, energy efficiency, and lower latency compared to electronic IMs. However, scaling remains a challenge for large problems. To overcome this, we propose a novel analog optical IM utilizing a spatial light modulator (SLM). Our design differs from other IMs relying on SLMs by employing analog spin variables instead of binary ones and leveraging gradient descent-based feedback rather than a computer-driven Metropolis–Hastings sampling process. By exploiting the inherent parallelism of light, this SLM-based IM is expected to efficiently handle optimization problems with millions of spins while still maintaining high energy efficiency. At the conference, we will also offer more insight into the performance of these analogue IMs and will delve deeper in the bit resolution required for the different optical components such as the employed SLM. Based on the dynamical evolution of the IM, we will discuss strategies to further improve the problem-solving capacity and speed of these optical IMs.
Abstract Quantum computers have strict requirements for the problems that they can efficiently solve. One of the principal limiting factor for the performances of noisy intermediate-scale quantum (NISQ) devices is the number of qubits required by the running algorithm. Several combinatorial optimization problems can be solved with NISQ devices once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived. Numerous techniques have been proposed to achieve such reformulations and, depending on the method chosen, the number of binary variables required, and therefore of qubits, can vary considerably. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with NISQ devices. This goal is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts, called the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement . We follow by submitting several instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios. Moreover, this study allows to appreciate several performance differences between the D-wave Advantage and next-generation Advantage2 quantum annealers. We show that the adoption of our techniques in this context allows to obtain QUBO formulations with significantly fewer slack variables, i.e. around 90% less, and D-wave annealers provide considerably higher correct solution rates, which moreover do not decrease with the input size as fast as when adopting standard techniques.
Quantum and quantum-inspired optimisation algorithms are designed to solve problems represented in binary, quadratic and unconstrained form. Combinatorial optimisation problems are therefore often formulated as Quadratic Unconstrained Binary Optimisation Problems (QUBO) to solve them with these algorithms. Moreover, these QUBO solvers are often implemented using specialised hardware to achieve enormous speedups, e.g. Fujitsu's Digital Annealer (DA) and D-Wave's Quantum Annealer. However, these are single-objective solvers, while many real-world problems feature multiple conflicting objectives. Thus, a common practice when using these QUBO solvers is to scalarise such multi-objective problems into a sequence of single-objective problems. Due to design trade-offs of these solvers, formulating each scalarisation may require more time than finding a local optimum. We present the first attempt to extend the algorithm supporting a commercial QUBO solver as a multi-objective solver that is not based on scalarisation. The proposed multi-objective DA algorithm is validated on the bi-objective Quadratic Assignment Problem. We observe that algorithm performance significantly depends on the archiving strategy adopted, and that combining DA with non-scalarisation methods to optimise multiple objectives outperforms the current scalarised version of the DA in terms of final solution quality.
As a quantum-inspired, non-traditional analog solver architecture, the analog Ising machine (AIM) has emerged as a distinctive computational paradigm to address the rapidly growing demand for computational power. However, the mathematical understanding of its principles, as well as the optimization of its solution speed and accuracy, remain unclear. In this work, we for the first time systematically discuss multiple implementations of AIM and establish a unified mathematical formulation. On this basis, by treating the binarization constraint of AIM (such as injection locking) as a Lagrange multiplier in optimization theory and combining it with a Lyapunov analysis from dynamical systems theory, an analytical framework for evaluating solution speed and accuracy is constructed, and further demonstrate that conventional AIMs possess a theoretical performance upper bound. Subsequently, by elevating the binarization constraint to a control variable, we propose the controllable analog Ising machine (CAIM), which integrates control Lyapunov functions and momentum-based optimization algorithms to realize adaptive sampling-feedback control, thereby surpassing the performance limits of conventional AIMs. In a proof-of-concept CAIM demonstration implemented using an FPGA-controlled LC-oscillator Ising machine, CAIM achieves a twofold speedup and a 7\% improvement in accuracy over AIM on a 50-node all-to-all weighted MaxCut problem, validating both the effectiveness and interpretability of the proposed theoretical framework.
Abstract Solving large-scale Quadratic Unconstrained Binary Optimization (QUBO) problems is critical in various fields, including finance, physics, biology and engineering. However, these problems remain intractable on conventional computing architectures. As a result, alternative solvers—such as Ising Machines (IMs) based on networks of coupled electronic, mechanical or photonic parametric oscillators (POs)—have recently been developed. PO-based Ising Machines (IMs) aim to find the ground state of an Ising Hamiltonian, which encodes the solution to a QUBO problem. However, they rely on an energy minimization process based on gradient descent, making them inherently susceptible to getting trapped in local minima and, as a result, to identifying inaccurate solutions. In this work, we introduce and validate a QUBO solver—the Analog Floquet Solver (AFS)—which enhances the dynamics of PO-based Ising machines (IMs) by leveraging Floquet states that emerge spontaneously in POs coupled to high quality-factor resonances. These states enable the AFS to embed periodic time modulation into its energy minimization process, allowing it to escape local minima during the search for QUBO problems’ solutions. As a result, the AFS significantly increases the likelihood of identifying accurate solutions compared to conventional PO-based IMs. More generally, this work establishes a new paradigm in analog computing that can be physically implemented using existing technologies across a variety of physical domains.