A super-polynomial quantum advantage for combinatorial optimization problems

Combinatorial optimization - a field of research addressing problems that feature strongly in a wealth of scientific and industrial contexts - has been identified as one of the core potential fields of applicability of quantum computers. It is still unclear, however, to what extent quantum algorithms can actually outperform classical algorithms for this type of problems. In this work, by resorting to computational learning theory and cryptographic notions, we prove that quantum computers feature a super-polynomial advantage over classical computers in approximating solutions to combinatorial optimization problems. Specifically, building on seminal work by Kearns and Valiant, we have identified special types of problems that are hard for classical computers to approximate. Despite this, we give a quantum algorithm such that an optimal solution can be efficiently approximated by quantum computers. The advantage for special instances of the so-called integer programming problem is shown to be super-polynomial. This result shows that quantum devices have the power to approximate combinatorial optimization solutions beyond the reach of classical efficient algorithms. Our results also give clear guidance on how to construct such advantage-bearing problem instances.