Entanglement-assisted heuristic for variational solutions of discrete optimization problems

From fundamental sciences to economics and industry, discrete optimization problems are ubiquitous across all fields. Yet, their complexity often renders exact solutions computationally intractable, necessitating the use of approximate methods. Among these, heuristic algorithms inspired by classical, and more recently quantum physics are widely employed. Quantum annealing holds promise over classical approaches by framing the problem as finding the ground state of a many-body spin system via adiabatic state preparation. Although still debated, it is believed that entanglement formation during the annealing process may lead to a speedup over classical methods.

We present a novel classical heuristic that efficiently simulates quantum annealing using a parameterized Ansatz of Generalized Coherent States. This framework allows for computation of energy and gradients with O(N³) complexity, permitting efficient gradient descent optimization of large problems with over 2000 spins. At the same time, these states capture non-trivial entanglement structures, which are crucial for the effectiveness of quantum annealing.

We perform a thorough analysis of our method, comparing solution quality and runtime to those achieved by other popular heuristics. Our findings suggest that our method offers a scalable path forward in leveraging quantum effects for complex optimization problems, potentially surpassing conventional heuristics in large-scale applications.