Terastate-Per-Second QUBO Brute-Force on a Single GPU Matrix Prefix-Suffix Decomposition

Jul 16, 2026

Upload by Noah

This paper introduces a parallel exhaustive QUBO search algorithm for dense matrices using a prefix-suffix decomposition combined with Gray code ordering. The approach provides O(1) per-state arithmetic cost for evaluating the QUBO objective function. An adjustable cache for energy components places repeated computations in the fastest memory tier, minimizing memory-bandwidth pressure and shifting the workload from memory-bound to compute-bound. A CUDA implementation reaches 7.5×10^12 states per second on one GPU, establishing a new benchmark for fullspace-search exact solvers.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages17

Reading Time43 min

Introduction

Exact Solution Methods

Branch and Bound approaches

SDP-based Branch-and-Cut and solver limits

Heuristic Methods

Terastate-per-second QUBO Brute-Force on a Single GPU: A Matrix Prefix-Suffix Decomposition Aleksandr Maltsev, Mikhail Remnev, Alexey Kapranov and Ekaterina Krivtsova Correspondence to: A. Maltsev, Email: [pulkin@gmail.com](pulkin@gmail.com). arXiv :2607 .04857v 1 [ cs .DS] 6 Jul 2026 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 × 1012 states per second on a single GPU, setting a new performance benchmark for the fullspace-search subclass of exact solvers. Index Terms—Quantum computing, Ising model, Ising spin–glass, QUBO, Combinatorial optimization, GPU, CUDA, Exhaustive search, Bruteforce, Quantum annealers, HPC I. Introduction The QUBO (Quadratic Unconstrained Binary Optimization) problem involves minimizing the function E (x) =X Qij xixj , i,j where x ∈ {0 , 1}n , and is one of the central problems in combinatorial optimization [1–3] . This problem is equivalent to finding the ground state of the Ising model [1, 4], described by the Hamiltonian H (s) =X Jij si sj +Xhisi. i,j i A wide range of combinatorial optimization problems can be reduced to the QUBO formulation, which underlies its practical importance. These include graph-theoretic problems (MaxCut, graph coloring, maximum independent set, community detection in networks), logistic problems such as the traveling salesman problem (TSP) with N 2 variables for solving an N-city problem, and financial applications (portfolio optimization) [3, 5–7] . Machine learning tasks (inference in graphical models, restricted Boltzmann machines), industrial applications (optimization of metal heat treatment schedules), as well as physical simulations (molecular modeling and ground state search in spin glasses) are also worth mentioning [1, 2, 4, 8–10] . Furthermore, a systematic transformation from general 0/1 linear programming models to QUBO formulations is available [5] . The practical significance of these formulations is further strengthened by the fact that the Ising Hamiltonian is naturally expressible in the language of quantum computation, where binary spin variables are directly associated with qubit degrees of freedom and pairwise couplingscan be encoded as quantum interactions. As a result, QUBO and Ising representations provide a broadly applicable route for translating realworld optimization tasks into forms amenable to quantum algorithms and quantum hardware, including adiabatic and gate-based approaches [7] . The main reason for the difficulty of QUBO problems lies in their NP-hardness [1–4] . Even with just one additional bit in problem size, the state space doubles, reaching 2n possible configurations [2] . Without special graph structure, finding an exact solution in polynomial time is impossible [1] . This complexity is worsened by the presence of numerous local minima in the energy landscape [11, 12] . Fully-connected problems have non-zero Qij elements for all variable pairs, creating maximum computational complexity [13] . For example, a fully-connected problem on 100,000 spins contains about 5 billion edges [11] . Sparse problems contain connections only between nearest neighbors or on specific topologies, such as the D-Wave Chimera graph, where each node connects to 5–6 others [1, 4] . A. Exact Solution Methods Branch and Bound is one of the most powerful classical tools for exactly solving NP-hard problems [4, 14, 15] . The algorithm recursively partitions the s

FAQs

What is the core idea of the proposed QUBO brute-force algorithm?

It uses a prefix-suffix decomposition together with Gray code ordering to enable parallel exhaustive search over dense-matrix QUBOs while keeping the per-state computation at O(1).

How does the algorithm reduce memory bandwidth requirements?

It employs an adjustable cache for energy components so computations are placed in the fastest available memory tier, effectively reducing memory-bandwidth pressure.

What performance does the CUDA implementation achieve on a single GPU?

The CUDA implementation reaches a state evaluation rate of 7.5×10^12 states per second on one GPU, setting a benchmark for fullspace-search exact solvers.

Jul 16, 2026

Upload by Noah