Closing in on Practical Quantum Advantage for Combinatorial Optimization with Quantum Generative Models (Part 1)

Practical quantum advantage, the demonstration of a quantum or quantum-assisted model solving a valuable academic or industry interest problem faster, better, or more cost-efficient than any classical algorithm, is the most sought-after milestone after the recent results on quantum computational advantage with random quantum circuits. 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 part 1 of this talk, we will focus on combinatorial optimization as an application domain to achieve a practical quantum advantage in the near term. We will discuss the challenges ahead and how quantum ML can help achieve this goal.

In part 2, we will present results benchmarking our quantum-enhanced optimizer (QEO) strategy head-to-head against state-of-the-art meta-heuristic techniques commonly used to solve hard instances from a specific financial application. We show recent results comparing the performance of our quantum-inspired algorithms, which leverages generative models based on matrix product states.