Entanglement-assisted variational algorithm for discrete optimization problems

From fundamental sciences to economics and industry, discrete optimization problems are ubiquitous. Yet, their complexity often renders exact solutions intractable, necessitating the use of approximate methods. Heuristics inspired by classical physics have long played a central role in this domain. More recently, quantum annealing has emerged as a promising alternative, with hardware implementations realized on both analog and digital quantum devices. Here, we develop a heuristic inspired by quantum annealing, using Generalized Coherent States as a parameterized variational Ansatz to represent the quantum state. This framework allows for the analytical computation of energy and gradients with low-degree polynomial complexity, enabling the study of large problems with thousands of spins. Concurrently, these states capture non-trivial entanglement, crucial for the effectiveness of quantum annealing. We benchmark the heuristic on the three-dimensional Edwards-Anderson model and compare the solution quality and runtime of our method to other popular heuristics. Our findings suggest that it offers a scalable way to leverage quantum effects for complex optimization problems, with the potential to complement or improve upon conventional alternatives in large-scale applications.