Design and FPGA Realization of QUBO hardware accelerator for MAX-CUT problem

Maciej Lewandowski; Piotr Dudek

doi:10.1109/ISCAS56072.2025.11044179

Design and FPGA Realization of QUBO hardware accelerator for MAX-CUT problem

Maciej Lewandowski, Piotr Dudek

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

5 Downloads (Pure)

Abstract

Combinatorial optimization problems are fundamental to many industrial and scientific applications, but are often NP-hard, requiring heuristic and probabilistic approaches to find good solutions fast. This paper presents the first hardware implementation of the neuromorphic-inspired NeuroSA algorithm, for accelerating Quadratic Unconstrained Binary Optimization (QUBO) problems. We show that it is possible to run a standard QUBO benchmark problem with 800 variables on a low-cost FPGA with a clock speed of approximately 144 MHz, which converges to the same solution value found by the numerical solver.

Original language	English
Title of host publication	2025 IEEE International Symposium on Circuits and Systems (ISCAS)
Publisher	IEEE
ISBN (Electronic)	979-8-3503-5683-0
DOIs	https://doi.org/10.1109/ISCAS56072.2025.11044179
Publication status	Published - 27 Jun 2025

Access to Document

10.1109/ISCAS56072.2025.11044179

ISCAS_2025___Digital_Fowler_Nordheim_AnnealerAccepted author manuscript, 577 KBLicence: CC BY

Cite this

@inproceedings{4581bd69527e4a43a327c079e69faa5e,

title = "Design and FPGA Realization of QUBO hardware accelerator for MAX-CUT problem",

abstract = "Combinatorial optimization problems are fundamental to many industrial and scientific applications, but are often NP-hard, requiring heuristic and probabilistic approaches to find good solutions fast. This paper presents the first hardware implementation of the neuromorphic-inspired NeuroSA algorithm, for accelerating Quadratic Unconstrained Binary Optimization (QUBO) problems. We show that it is possible to run a standard QUBO benchmark problem with 800 variables on a low-cost FPGA with a clock speed of approximately 144 MHz, which converges to the same solution value found by the numerical solver.",

author = "Maciej Lewandowski and Piotr Dudek",

year = "2025",

month = jun,

day = "27",

doi = "10.1109/ISCAS56072.2025.11044179",

language = "English",

booktitle = "2025 IEEE International Symposium on Circuits and Systems (ISCAS)",

publisher = "IEEE",

address = "United States",

}

TY - GEN

T1 - Design and FPGA Realization of QUBO hardware accelerator for MAX-CUT problem

AU - Lewandowski, Maciej

AU - Dudek, Piotr

PY - 2025/6/27

Y1 - 2025/6/27

N2 - Combinatorial optimization problems are fundamental to many industrial and scientific applications, but are often NP-hard, requiring heuristic and probabilistic approaches to find good solutions fast. This paper presents the first hardware implementation of the neuromorphic-inspired NeuroSA algorithm, for accelerating Quadratic Unconstrained Binary Optimization (QUBO) problems. We show that it is possible to run a standard QUBO benchmark problem with 800 variables on a low-cost FPGA with a clock speed of approximately 144 MHz, which converges to the same solution value found by the numerical solver.

AB - Combinatorial optimization problems are fundamental to many industrial and scientific applications, but are often NP-hard, requiring heuristic and probabilistic approaches to find good solutions fast. This paper presents the first hardware implementation of the neuromorphic-inspired NeuroSA algorithm, for accelerating Quadratic Unconstrained Binary Optimization (QUBO) problems. We show that it is possible to run a standard QUBO benchmark problem with 800 variables on a low-cost FPGA with a clock speed of approximately 144 MHz, which converges to the same solution value found by the numerical solver.

UR - https://www.scopus.com/pages/publications/105010619879

U2 - 10.1109/ISCAS56072.2025.11044179

DO - 10.1109/ISCAS56072.2025.11044179

M3 - Conference contribution

BT - 2025 IEEE International Symposium on Circuits and Systems (ISCAS)

PB - IEEE

ER -

Design and FPGA Realization of QUBO hardware accelerator for MAX-CUT problem

Abstract

Access to Document

Other files and links

Fingerprint

Cite this