Within a fraction of a percent of the best-known cuts, in seconds.

System setup

Quicopt v0.2 on a single NVIDIA A100 80GB GPU; on 22 of the 71 instances a short CPU post-solve (AMD EPYC) refines the GPU solution. Most graphs finish in well under a second; the largest take about thirty.

The problem, in depth

Maximum Cut asks for a partition of a graph’s vertices into two sets that maximizes the number (or weight) of edges crossing between them. It is NP-hard and a canonical testbed for combinatorial and quantum-inspired solvers, because its QUBO/Ising form is the same energy minimization that quantum annealers target.

The Gset suite spans dense and sparse graphs with +1 and ±1 edge weights and sizes from 800 to 20,000 nodes, so it probes both solution quality and scaling on a single hardware budget.

How the benchmark is run

For each graph Quicopt minimizes the corresponding Ising energy and the resulting cut is recorded. Where a confident best-known value exists in the literature, the cut is reported as a percentage of it (100% = matched); 52 of the 71 instances are graded this way, with a median of 99.98% and a range of 98.9–100.0%; 23 of them match the best-known cut exactly.

Every number (per-instance cuts, wall-times, hardware and reference values) is published in the open Quicopt/Benchmarks repository and regenerated from the raw data, so it can be checked and reproduced.