GPU Brute Force Reaches 60-Spin Ground States, Giving Quantum Solvers a Truth Standard

Every optimization algorithm needs an honest referee. For combinatorial problems written as Ising spin glasses or quadratic unconstrained binary optimization (QUBO) models, the only unquestionable answer comes from brute force: evaluate all 2^N configurations and pick the lowest energy. A team of Polish researchers has now matured exactly such a referee into a released, numerically stabilized, multi-GPU software backend called omnisolver-bruteforce, an update to the Omnisolver framework published in the journal SoftwareX. The new version certifies true global optima for instances of up to 60 binary variables, extends the previous reach by three orders of magnitude in enumerated configurations, and exposes, for the first time at this scale, precisely where state-of-the-art classical heuristics begin to fail.

Omnisolver itself is a plugin-based framework that provides a uniform Python and command-line interface to QUBO and Ising solvers, integrated with the widely used dimod ecosystem. Each solver arrives as an independent package that registers itself through an entry point and a small specification file, from which the framework automatically derives the command-line interface and input-output handling. Solvers can therefore be swapped without touching the surrounding workflow. The exhaustive-search plugin discussed in the update exposes two sampler classes: a single-node, single-GPU sampler and a distributed multi-GPU sampler built on the Ray framework, which fixes a small number of variables, enumerates all assignments of those frozen spins, and dispatches each resulting subproblem as an independent Ray task to a GPU worker. The performance-critical kernels are written in CUDA and C++ and exposed to Python through Cython.

The benchmark hardware was a cluster of eight NVIDIA H100 GPUs with 96 gigabytes of memory each, spread across two nodes connected by standard Ethernet. On dense random Ising instances with couplings drawn uniformly from the interval [-1, 1], the single-GPU sampler certified ground states up to N=54 spins, with measured runtimes growing by a factor of almost exactly two per added variable, the expected signature of the O(2^N) enumeration. The distributed sampler, using three fixed variables so that eight subproblems map one-to-one onto the eight GPUs, pushed the certified frontier to N=60, a run that took roughly 3.15 days and landed within 0.3 percent of the doubling-rule extrapolation. Projected to the same size, the single-GPU path would have needed about 25 days, confirming nearly ideal linear scaling.

That scaling was quantified explicitly. Below a crossover between N=40 and N=42, splitting the work across eight GPUs is actually slower than using one, because kernel-launch and Ray-scheduling overheads dominate the tiny subproblems. Efficiency then climbs steeply, from 43 percent at N=44 through 75 percent at N=46 and 93 percent at N=48, and saturates at the ideal eightfold speedup from N=52 onward. A complementary experiment held the problem fixed and varied the machine: strong scaling at N=50 reached 2.00 times on two GPUs, 3.99 on four and 7.86 on eight, while weak scaling kept wall-clock time flat to within 0.2 percent as the instance grew from 50 to 53 spins alongside the device count. Notably, crossing the node boundary between the two hosts produced no measurable slowdown at all, consistent with the search phase involving no inter-worker communication whatsoever.

The most delicate engineering problem was numerical. The fast ground-state path operates in single-precision float32 arithmetic, which halves the size of the energy buffers resident on the GPU and effectively buys working-set size rather than raw speed, since the enumeration turns out to be limited by memory traffic and integer bookkeeping rather than floating-point throughput. But single precision accumulates roundoff drift over long incremental updates. The update counters this with compensated incremental updates, periodic re-anchoring of the energy from scratch, and a final refresh of the best-state buffer, all activated automatically whenever the kernel sees at least 40 variables. After these fixes, the deviation between the reported energies and independent float64 recomputation stayed below 10^-5 across all twenty measured runs, corresponding to about eight significant digits. Interestingly, repeating the search in full double precision showed it to be only about 2 percent slower, and both precisions returned identical configurations at every tested size.

Verification is layered and deliberately paranoid. Every returned configuration is re-evaluated from scratch in float64 on the host. On the eight sizes where both samplers are feasible, the single-GPU and distributed routes, which sweep the configuration space in genuinely different patterns, returned bit-identical ground states with energies agreeing to within 8.2 times 10^-6. Small instances were cross-checked against dimod’s exact CPU solver, and the QUBO and Ising code paths, which coincide up to a host-side transformation, produced runtimes matching to within 0.2 percent. The authors are careful about terminology: because the fast path uses floating-point arithmetic, their minima are described as empirically cross-validated rather than formal certificates for arbitrary real-valued coefficients.

The real payoff comes when the certified optima are turned against the heuristics they are meant to judge. The team distributed a discrete simulated-bifurcation solver, a relative of the Simulated Bifurcation Machine that has served as the classical benchmark in recent studies of quantum runtime advantage, and ran it against every stored brute-force result from N=38 to N=60. On the dense random family it matched the certified optimum on all twenty instances, with bit-identical configurations and energies agreeing to 6 times 10^-14 after independent recomputation. A second comparison using simulated annealing across twenty instances drawn from four algorithmically distinct coupling families, uniform, bimodal, Gaussian and sparse, likewise reached the certified optimum on every one, with the rare disagreements traced to genuine ground-state degeneracy rather than optimization error.

The story changes dramatically on a harsher landscape. On the Wishart ensemble, a fully connected zero-field family with a tunable ruggedness parameter, the simulated-bifurcation heuristic underwent a sharp collapse. It recovered the certified optimum on every instance at ruggedness values of 0.45 and above, but on only 3 of 20 instances at 0.3, 1 of 20 at 0.25, and none at all at 0.2, terminating at configurations up to 0.6 percent above optima that were known only because brute force had found them. These are wrong, near-optimal answers that nothing short of exhaustive certification can expose. The cost asymmetry is striking: certification took about 2 seconds per instance on a single H100, less than one heuristic run, and time-to-solution analysis showed that relying on the heuristic was between roughly 600 and 1800 times slower than simply certifying the answer directly on the hardest instances.

The authors are candid about limits. Exhaustive enumeration remains exponential no matter how many GPUs are thrown at it: a back-of-the-envelope projection to 16,384 GPUs, a partition within reach of leadership-class supercomputers, would cut the N=60 certification from about 3.15 days to roughly 2.2 minutes and place the practical ceiling for a one-month budget near N=74, with the 64-bit configuration word imposing a hard bound at N=64 plus the number of fixed variables. A hypothetical fourfold increase to 65,536 GPUs would buy only two additional spins, a stark illustration of the tyranny of exponential complexity. The controller-side merge cost was measured directly up to 65,536 subproblems, showing that the merge arithmetic itself is not the bottleneck, and a hierarchical tree merge is available and automatically engaged beyond 64 subproblems.

The intended role of the software is therefore not to solve application-scale problems but to serve as a certification backend for research pipelines: a source of ground-truth optima against which heuristics, annealers and NISQ-era quantum algorithms can be calibrated, particularly for metrics such as the optimality gap that depend explicitly on the true ground-state energy. The entire reproduction package, including instances, raw results, benchmark drivers and even the heuristic solver, ships with the article, and much of the verification can be re-run on a laptop without any GPU. In a field where claims of quantum advantage increasingly rest on the quality of classical reference answers, a dependable, open, GPU-accelerated arbiter of global optima is a quietly essential piece of infrastructure, and this update makes it one that anyone can install, inspect and trust.

Subject of Research: A distributed GPU exhaustive-search backend for certifying ground states of Ising spin-glass and QUBO optimization problems

Article Title: Omnisolver: An extensible interface to Ising spin–glass and QUBO solvers – a numerically stabilized, distributed GPU exhaustive-search plugin

Article References: Jałowiecki, K., Pawłowski, J., Gardas, B., & Pawela, Ł. (2026). Omnisolver: An extensible interface to Ising spin–glass and QUBO solvers – a numerically stabilized, distributed GPU exhaustive-search plugin. SoftwareX, 36, Article 103031. https://doi.org/10.1016/j.softx.2026.103031

Image Credits: AI Generated

DOI: 10.1016/j.softx.2026.103031

Keywords: Ising spin glass, QUBO, combinatorial optimization, GPU computing, CUDA, exhaustive search, simulated bifurcation, quantum advantage benchmarking, Ray distributed computing, ground-state certification, H100 GPUs, Omnisolver