On some features of Quadratic Unconstrained Binary Optimization with random coefficients

Quadratic Unconstrained Binary Optimization (QUBO or UBQP) is concerned with maximizing/minimizing the quadratic form H(J, η) = W ∑i,j Ji,j ηᵢ ηⱼ with J a matrix of coefficients, η ∈ \0, 1 and W a normalizing constant. In the statistical mechanics literature, QUBO is a lattice gas counterpart to the Sherrington--Kirkpatrick spin glass model. Finding the optima of H is an NP-hard problem. Several problems in combinatorial optimization and data analysis can be mapped to QUBO in a straightforward manner. In the combinatorial optimization literature, random instances of QUBO are often used to test the effectiveness of heuristic algorithms. Here we consider QUBO with random coefficients and show that if the Ji,j's have zero mean, then, after proper normalization, the minimum and maximum per particle of H do not depend on the details of the distribution of the couplings and are concentrated around their expected values. Further, with the help of numerical simulations, we give estimates of the minimum and maximum of the objective function and provide some insight into the structure of the minimizer and the maximizer of H. We argue that also this structure is rather robust. Our findings hold in the diluted case where each of the Ji,j's is allowed to be zero with probability going to $1$ as N → ∞ in a suitable way.