Enhancing Combinatorial Optimization with Quantum Generative Models

Combinatorial optimization is one of the key candidates in the race for practical quantum advantage. In this work we introduce a new family of quantum-enhanced optimizers and demonstrate how quantum machine learning models, knows as quantum generative models, can enhance the performance over results based only on state-of-the-art classical solvers. We present two new quantum-enhanced optimization strategies. The first scheme works as a stand-alone solver and we show here its superior performance when the goal is to find the best minimum within the least number of cost function evaluations. We compare our results with Bayesian optimizers which are known to be one of the best competing solvers in such tasks. The second optimization strategy corresponds to a quantum-classical scheme which leverages on data points evaluated during the optimization search from any quantum or classical optimizer. We show how our quantum-assisted generative model boosts the performance of a classical solver in hard-to-solve instances where the classical solver is not capable of making progress as a stand-alone solution. To illustrate our findings, we benchmark our quantum-enhanced optimization strategies in portfolio optimization problems by constructing instances from the S&P 500 stock market index.