Search papers, labs, and topics across Lattice.
This paper introduces a parallel exhaustive search algorithm for Quadratic Unconstrained Binary Optimization (QUBO) problems that leverages a prefix-suffix decomposition and Gray code ordering to achieve O(1) per-state complexity. By optimizing memory usage through an adjustable energy components cache, the method significantly reduces memory bandwidth demands, shifting the problem from being memory-bound to compute-bound. The CUDA implementation reaches a groundbreaking evaluation rate of $7.5 \times 10^{12}$ states per second on a single GPU, establishing a new benchmark for exact solvers in full-space search scenarios.
Achieving an unprecedented evaluation rate of $7.5 \times 10^{12}$ states per second on a single GPU could redefine the limits of QUBO problem-solving efficiency.
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.
