Terastate-per-second QUBO Brute-Force on a Single GPU: A Matrix Prefix-Suffix Decomposition
2026-07-06 • Data Structures and Algorithms
Data Structures and AlgorithmsDistributed, Parallel, and Cluster Computing
AI summaryⓘ
The authors developed a fast algorithm that looks through all possible solutions to a problem called QUBO, which involves dense matrices. They use a smart trick with prefixes and suffixes along with a special ordering (Gray code) to only do one calculation for each possible solution, making the process very efficient. Their method stores some data in the fastest memory to avoid slowing down due to data transfer. Running this on a single GPU, their implementation evaluates over seven trillion states per second, setting a new record for exact, full-space QUBO solvers.
QUBOdense matricesprefix-suffix decompositionGray codeCUDAGPU computingcompute-boundmemory bandwidthexact solversfull-space search
Authors
Aleksandr Maltsev, Mikhail Remnev, Alexey Kapranov, Ekaterina Krivtsova
Abstract
This paper presents a parallel QUBO exhaustive search algorithm for dense matrices, based on a prefix-suffix decomposition and Gray code ordering. The algorithm achieves O(1) per-state complexity: for the QUBO objective function computation only one arithmetic operation per state is performed. An adjustable energy components cache size enables placement in the fastest available memory tier. This reduces memory bandwidth requirements to a negligible level and transforms the problem from memory-bound to compute-bound. Our CUDA-based implementation achieves a state-of-the-art evaluation rate of $7.5\times10^{12}$ states per second on a single GPU, setting a new performance benchmark for the full-space-search subclass of exact solvers.