Quadratic Unconstrained Binary Optimization (QUBO) problems are ubiquitous across computer science, operations research, and statistical physics, but are NP-hard in general to solve. This has motivated a flurry of heuristic and rigorous algorithms to (approximately) solve them, even with special chips dedicated to them. The seminal work of Goemans and Williamson introduced a semidefinite programming (SDP) relaxation for such problems, solvable in polynomial time that upper bounds the optimal value. Their approach also enables randomized rounding techniques to obtain feasible solutions with provable performance guarantees.
In this work, EQUALITY partners identify instances of QUBO problems where matrix multiplicative weight methods lead to quantum and quantum-inspired algorithms that approximate the Goemans-Williamson SDP exponentially faster than existing methods, achieving polylogarithmic time complexity relative to the problem dimension. This speedup is attainable under the assumption that the QUBO cost matrix is sparse when expressed as a linear combination of Pauli strings satisfying certain algebraic constraints, and leverages efficient quantum and classical simulation results for quantum Gibbs states.
The authors demonstrate how to verify these conditions efficiently given the decomposition. Additionally, they explore heuristic methods for randomized rounding procedures and extract the energy of a feasible point of the QUBO in polylogarithmic time. While the practical relevance of instances where these methods excel remains to be fully established, the group propose heuristic algorithms with broader applicability and identify Kronecker graphs as a promising class for applying their techniques.
Read the paper: https://doi.org/10.48550/arXiv.2510.08292
