Quantum / CONCEPT

Tight penalty coefficients for the QUBO reformulations of max k-cut

For max k-cut with real edge weights, every optimal solution of the one-hot QUBO reformulation is an optimal k-cut as soon as each penalty c_v exceeds max(d+_v / k, -d-_v / 2), and every optimal solution of the reduced R-QUBO reformulation is one as soon as c_v exceeds d+_v - d-_v, where d+_v and d-_v are the sums of the positive and of the negative weights at v. These are Conjectures 1 and 2 of A. Harkness et al. (arXiv:2511.01108), who proved the bounds with -(3/2) d-_v and -2 d-_v.