🔬 physics

Omnisolver: An extensible interface to Ising spin-glass and QUBO solvers: adding a distributed GPU brute-force plugin

This paper introduces \texttt{omnisolver-bruteforce}, a new plugin for the Omnisolver framework that enables exact exhaustive search of QUBO and Ising instances on distributed CUDA GPUs through a unified interface, a Ray-based task-splitting architecture, and numerical stabilization techniques, achieving ground-truth solutions for up to 60 variables in close agreement with theoretical scaling laws.

Original authors: Konrad Jałowiecki, Jakub Pawłowski, Bartłomiej Gardas, Łukasz Pawela

Published 2026-10-09

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Konrad Jałowiecki, Jakub Pawłowski, Bartłomiej Gardas, Łukasz Pawela

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of modern computing, there exists a class of problems so complex that finding the single best solution feels like searching for a specific grain of sand in a desert that doubles in size with every step you take. These are optimization challenges, often modeled as networks of interacting parts where the goal is to arrange the pieces to reach the lowest possible state of energy or cost. Scientists and engineers use these models to understand everything from how materials behave at the atomic level to how to schedule traffic or manage financial portfolios. For decades, the most reliable way to solve these puzzles has been to check every single possible arrangement, a method known as exhaustive search. However, as the number of pieces grows, the number of possible arrangements explodes so rapidly that even the world's most powerful supercomputers cannot finish the job in a human lifetime. This creates a critical gap: without a way to find the absolute best answer, researchers cannot be certain if the clever shortcuts they use to find "good enough" answers are actually close to the truth.

A team of researchers from Poland has now built a new tool designed to bridge this gap for a specific range of difficult problems. They have created a software update that turns a standard graphics card, the kind found in high-end computers for gaming and video, into a machine capable of checking every possible arrangement for problems with up to sixty pieces. By combining this raw checking power with a system that splits the work across multiple computers, they have managed to find the perfect solution for problems that were previously too large to solve completely. This achievement provides a "gold standard" answer that other, faster computer programs can be tested against, allowing scientists to verify if their shortcuts are truly working or if they are missing the best solution entirely.

The core of this work is a software plugin called Omnisolver-bruteforce, which acts as a universal translator for different types of computer solvers. Think of it as a master key that lets researchers plug in various tools to tackle the same problem. The researchers took an existing tool that could check every possibility on a single graphics card and upgraded it to work across a network of eight powerful cards simultaneously. They achieved this by breaking the massive search space into smaller, independent chunks. Imagine a library where you need to find a specific book; instead of one person checking every shelf, the task is divided so that eight people check different sections at the same time, reporting back only when they find the target. In this case, the "library" is the set of all possible arrangements of the problem, and the "searchers" are the graphics cards working in parallel.

The researchers tested this new system on a cluster of eight high-performance graphics cards, each with a large amount of memory. They set the system to solve random versions of these optimization problems, gradually increasing the size of the problem from forty pieces up to sixty. The results were striking. For problems with sixty pieces, the system took approximately three days to check every single possibility and confirm the best answer. This might sound like a long time, but without this new method, the task would have been impossible to complete in a reasonable timeframe. The team observed that for every additional piece added to the problem, the time required to solve it roughly doubled, a pattern that held true across all their tests. This predictable behavior confirmed that their system was working exactly as the laws of physics and mathematics dictate for this type of exhaustive search.

A significant part of the innovation involved ensuring the computer did not make small mistakes while doing such a massive amount of work. Graphics cards are designed to be fast, often at the expense of extreme precision, which can lead to tiny errors that add up over time. The researchers developed a method to automatically correct these tiny errors as they happened, ensuring that the final answer was mathematically exact. They verified this by comparing their results against a known perfect solution for smaller problems and found that the answers matched down to the last digit. This level of reliability is crucial because the tool is not intended to solve everyday problems for businesses, but rather to serve as a reference point. It allows scientists to test new, faster algorithms—such as those inspired by quantum physics or biological systems—to see if they can truly find the best solution or if they are just guessing.

The study also looked ahead to what might be possible with even larger computer clusters. The researchers calculated that if they could connect two hundred and sixteen graphics cards, they could solve a problem with sixty pieces in just thirty-three seconds. They further estimated that with such a massive network, they could theoretically solve problems with up to seventy-six pieces within a month. However, they were careful to note that these are projections based on their current data, and real-world factors like communication delays between computers might change the exact numbers. The current system is limited to problems with sixty-four pieces due to the way the software handles the counting of arrangements, but within that limit, it provides a definitive answer.

This work does not claim to have solved all optimization problems, nor does it suggest that exhaustive search will replace faster, approximate methods for daily use. Instead, it offers a way to certify the quality of those faster methods. By providing a guaranteed correct answer for problems of a certain size, the researchers have given the scientific community a ruler to measure the accuracy of new technologies. As the field of computing moves toward more complex challenges, having a tool that can definitively say "this is the best possible answer" becomes an essential benchmark. The researchers have made their software available to others, inviting the community to use this new capability to verify their own discoveries and push the boundaries of what is computationally possible.

Technical Summary: Omnisolver-Bruteforce Plugin

Problem Statement
The paper addresses the need for certified, ground-truth solutions for Quadratic Unconstrained Binary Optimization (QUBO) and Ising spin-glass instances. While heuristic methods (such as the Simulated Bifurcation Machine) and quantum annealers are widely used, their performance must be benchmarked against exact optima. Previous exhaustive solvers were often standalone tools lacking integration with modern solver frameworks. Furthermore, existing GPU-based exhaustive solvers faced two specific limitations: they were restricted to single-device execution, and their "fast path" (utilizing float32 arithmetic for throughput) suffered from numerical drift (roundoff errors) for problem sizes $N \ge 40$ , compromising the accuracy of the reported ground-state energies.

Methodology
The authors introduce omnisolver-bruteforce, a plugin for the existing Omnisolver framework. The methodology integrates three core technical components:

Unified Interface: The single-GPU brute-force kernel from prior work [2] is repackaged as a first-class plugin. It exposes a uniform Python and Command-Line Interface (CLI) compatible with dimod, returning dimod.SampleSet objects with runtime metadata.
Distributed Execution: To overcome single-GPU memory and time limits, the authors implemented a distributed framework using Ray. The search space is decomposed by fixing $k$ variables, creating $2^k$ independent subproblems with $N-k$ unfixed variables. These subproblems are dispatched across multiple GPUs and hosts. A controller node aggregates partial results.
Numerical Stabilization: To maintain the high throughput of float32 arithmetic while ensuring accuracy, the plugin employs:
- Compensated incremental updates.
- Periodic exact energy re-anchoring (re-evaluating energy in float64).
- Best-buffer refresh mechanisms.
  These stabilization techniques activate automatically for $N \ge 40$ .

The performance-critical kernels are written in CUDA/C++ and exposed to Python via Cython. The implementation supports 64-bit safe bit operations to handle problem sizes beyond the original single-GPU regime.

Key Contributions

First-Class Plugin: Integration of an exhaustive GPU solver into the Omnisolver ecosystem with a consistent API.
Scalable Distributed Search: A Ray-based architecture that enables exhaustive search on problem sizes infeasible for a single device, achieving near-linear strong scaling.
Stabilized Fast Path: Elimination of float32 drift for large $N$ without sacrificing the throughput benefits of single-precision arithmetic.
Validation: Comprehensive testing against dimod.ExactSolver and re-computation in float64 to verify energy accuracy.

Results
The authors evaluated the plugin on a local cluster of 8× NVIDIA H100 GPUs (96 GB each).

Performance Scaling: The distributed sampler crosses the single-GPU performance break-even point between $N=40$ and $N=42$ . From $N \gtrsim 44$ onwards, it achieves the full $\approx 8\times$ speedup expected from the 8-GPU pool.
Exhaustive Limits: The system successfully solved all-to-all random Ising instances up to $N=60$ in the distributed mode, taking approximately 3.15 days. This aligns with the empirical doubling rule ( $t_{N+1} \approx 2t_N$ ).
Accuracy: For the largest tested instances ( $N=56, 58, 60$ ), the absolute deviation between the reported float32 energies and float64 recomputed energies remained below $4 \times 10^{-6}$ .
Benchmarking Utility: The plugin successfully certified the exact ground state for instances where the Simulated Bifurcation Machine (SBM) was also tested. The SBM solutions were bit-identical (Hamming distance 0) to the brute-force results, with energy differences attributable solely to single-precision roundoff.

Significance and Scope
The paper positions omnisolver-bruteforce not as a routine optimizer for application-scale problems, but as a verification and certification backend. Its primary significance lies in providing ground-truth optima necessary for:

Benchmarking approximate and heuristic methods (e.g., SBM).
Verifying NISQ-oriented workflows.
Assessing claims of quantum runtime advantage.

The authors explicitly note that the $O(2^N)$ complexity remains unchanged; the update reduces constant factors and removes numerical pitfalls but does not alter the fundamental computational complexity. The current implementation has hard limits: $N \le 64$ due to 64-bit spin indexing, and subproblem sizes are bounded by GPU L2 cache budgets. Future work suggested by the authors includes exposing stabilization parameters to users, implementing hierarchical reductions for better scaling to massive worker counts, and publishing reproducibility capsules.

Technical Summary: Omnisolver-Bruteforce Plugin

More like this