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

System setup

Quicopt v0.1 on a single NVIDIA A100 80GB GPU; for some sparse instances a short CPU post-solve (AMD EPYC) refines the GPU solution. Per-instance wall-times range from well under a second to about twenty seconds on the largest graphs.

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.4% and a range of 97.1–100.0%.

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