High-parallel FPGA Enables Discrete Simulated Bifurcation for Large-Scale Optimization of Ising Problems

Combinatorial optimisation problems, which underpin many real-world challenges, often present an insurmountable computational hurdle due to their inherent complexity. Fabrizio Orlando, Deborah Volpe, Giacomo Orlandi, and colleagues from Politecnico di Torino and Istituto Nazionale di Geofisica e Vulcanologia now demonstrate a significant advance in tackling these problems through a novel hardware implementation of discrete simulated bifurcation. Their work leverages the principles of adiabatic quantum computation, emulating the behaviour of complex physical systems to efficiently explore potential solutions. By designing a highly parallelisable architecture for Field-Programmable Gate Arrays, the team achieves a substantial speed-up in solving large-scale optimisation problems, successfully demonstrating a 256-variable solution on a readily available FPGA platform and paving the way for tackling even more complex challenges in fields ranging from logistics to machine learning.

This approach models problems as a network of Kerr-nonlinear parametric oscillators, where each oscillator represents a variable and the system’s lowest energy state corresponds to the problem’s solution. The team meticulously analyzed different variations of this method, ballistic, discrete, and heated, to identify the most promising path towards a practical system. To enhance performance and reduce errors, the researchers pioneered the discrete Simulated Adiabatic Bifurcation (dSB) method.

This technique intentionally neglects energy conservation at boundaries within the oscillator network, allowing the system to escape local minima and find more optimal solutions. The dSB builds upon the ballistic method, which introduces constraints to oscillator positions, effectively removing analogue errors. Both methods maintain the inherent parallelizability of the original technique, crucial for accelerating computation. The team engineered a fully functional hardware implementation of the dSB algorithm on an AMD Kria KV260 FPGA. This design allows users to adjust the degree of parallelization, tailoring the system to specific problem requirements. A proof-of-concept implementation successfully solved 256-variable problems, validated using well-known max-cut and knapsack problems. This work delivers a versatile, open-source architecture, complete with software models and hardware description, enabling broader evaluation and application of these powerful optimization techniques.

Ising Model Solved on FPGA Hardware

Scientists have achieved a significant breakthrough in solving complex optimization problems by developing a hardware implementation of the Simulated Adiabatic Bifurcation (aSB) algorithm. This work addresses the challenge of combinatorial optimization, where problems exhibit exponential complexity. The team successfully demonstrated a functioning system capable of solving problems with 256 variables using a low-tier AMD Kria KV260 Field-Programmable Gate Array (FPGA). The research centers on mimicking the behavior of a network of Kerr-nonlinear parametric oscillators (KPOs) to find approximate solutions to problems formulated in the Ising model.

Each oscillator represents a variable within the problem, and the system evolves to a state where the lowest energy corresponds to the optimal solution. The team explored different variations of the aSB algorithm, ballistic, discrete, and thermal, and focused on implementing the discrete version for the FPGA. This implementation allows for a high degree of parallelization, enabling faster computation. Experiments confirmed the functionality of the hardware implementation using well-known max-cut and knapsack problems as benchmarks. The system’s performance demonstrates the feasibility of using fixed-point representation for hardware implementation of aSB. By successfully solving a 256-variable problem on a relatively modest FPGA, the team has shown a promising path toward scalable hardware solutions for complex optimization challenges.

Adiabatic Computing Prototype Solves 256-Variable Problems

This work presents a novel hardware architecture for solving complex combinatorial optimization problems using the discrete Simulated Bifurcation algorithm. Researchers successfully demonstrated a functioning prototype implemented on a low-tier Field-Programmable Gate Array, capable of tackling problems with 256 variables, and validated its performance using established benchmarks like the max-cut and knapsack problems. The achievement lies in translating the principles of adiabatic computation, inspired by physical systems, into a practical digital circuit. The team’s design prioritizes parallel processing, allowing multiple variables to be updated simultaneously, which is crucial for accelerating the search for optimal or near-optimal solutions.

By employing a fixed-point representation, the architecture is well-suited for implementation in hardware. While the current demonstration focuses on a relatively small problem size, the modular design allows for scalability, suggesting the potential to address larger and more complex challenges in the future. Future research directions include exploring different parallelization strategies and investigating the use of more advanced optimization techniques to improve solution quality and convergence speed.