MaxCut as a QUBO
MaxCut has a direct QUBO formulation. For an unweighted graph with adjacency matrix A, the QUBO matrix is Q = -(A - diag(A·1)) / 4 (up to a constant). This makes MaxCut the canonical benchmark for QUBO solvers and QAOA research — no penalty method required.
python
import nerox
import numpy as np
client = nerox.Client()
# Random 3-regular graph (64 nodes)
n = 64
A = np.zeros((n, n))
for i in range(n):
neighbors = np.random.choice([j for j in range(n) if j != i], 3, replace=False)
for nb in neighbors:
A[i, nb] = A[nb, i] = 1
# Solve MaxCut
job = client.optimize.maxcut(
adjacency_matrix=A,
solver="gpu", # or "qaoa" for quantum-inspired
)
result = job.wait()
partition = result.solution # binary: 0 or 1 per node
cut_weight = result.objective
print(f"Cut weight: {cut_weight}")QAOA for MaxCut research
MaxCut is the canonical benchmark for QAOA. Use solver="qaoa" to run simulated QAOA circuits on small-to-medium instances and compare approximation ratios against GPU Annealing and the Goemans-Williamson SDP bound.
python
# Compare GPU annealing vs QAOA on the same instance
for solver, depth in [("gpu", None), ("qaoa", 4), ("qaoa", 8)]:
kwargs = {"adjacency_matrix": A, "solver": solver}
if depth:
kwargs["depth"] = depth
job = client.optimize.maxcut(**kwargs)
r = job.wait()
label = solver if not depth else f"qaoa-p{depth}"
print(f"{label:12s}: cut={r.objective:.0f} time={r.runtime_s:.1f}s")Weighted MaxCut
Supply edge weights for the general weighted MaxCut variant. Common in image segmentation (pixel similarity as edge weight) and community detection in social networks.
python
# Weighted adjacency matrix (any non-negative values)
W = np.random.rand(n, n)
W = (W + W.T) / 2 # symmetrize
np.fill_diagonal(W, 0)
job = client.optimize.maxcut(adjacency_matrix=W, solver="gpu")
result = job.wait()
print(f"Weighted cut: {result.objective:.3f}")Applications
Circuit layout — minimize cross-layer wire connections
Community detection — partition social networks by maximum inter-community edges
Image segmentation — pixel graph with similarity weights
Statistical physics — ground state of Ising spin glasses
VLSI design — optimize chip partitioning for minimizing bus congestion