After the recent results on quantum computational advantage with random quantum circuits, practical quantum advantage is the next most sought-after milestone. We define practical quantum advantage as a demonstration where a quantum or quantum-assisted model is able to solve a valuable academic or industry-relevant problem faster, better, or more cost-efficiently than any classical algorithm. Besides quantum chemistry, where a more explicit path is laid out for achieving quantum advantage, machine learning (ML) and combinatorial optimization problems (COP) stand out as key candidates. Despite all the efforts, there is still no demonstration of quantum advantage for practical and industrial applications in ML and COP.

In this talk, we will discuss how quantum generative models can be leveraged to achieve a practical quantum advantage in combinatorial optimization in the near term. We will focus on recent results benchmarking our quantum-inspired Generator-Enhanced Optimization strategy (TN-GEO) head-to-head against state-of-the-art meta-heuristic techniques commonly used to solve hard instances from a real-world application. Here, the quantum-inspired generative models are based on tensor networks (e.g., matrix product states) and we will discuss the challenges ahead on how and when to take advantage of fully quantum generative models. We will present recently developed metrics that allow us to define a concrete path and milestones towards reaching practical quantum advantage with near-term quantum hardware.