Generalized quantum optimization algorithms for near-term quantum computing architectures

In a distant future, large-scale, ideal quantum computers will speed up many interesting computational tasks by leveraging a restricted number of fundamental quantum algorithms. However, the rst generation of quantum computers |those that exist now or that we may see in a few years| will be error-prone, hence merely capable of running a restricted set of quantum programmes. In this context, it is pressing to find valuable applications for these machines. Obtaining good solutions to hard optimization problems could be such an application.

The Quantum Approximate Optimization Algorithm (QAOA) is the best-established quantum optimization algorithm for near-term hardware to date. However, as of today, the advantage of QAOA over classical algorithms has remained elusive. More specifically, a series of recent results established significant limitations on the most naive versions of QAOA - though the relevance of these results to the intermediate-scale problems addressable by near-term quantum computers may be questioned.

Starting from the present understanding of the limitations of QAOA, the project will aim at designing generalized versions of the algorithm and assess their performance. Potential applications of these building blocks as shallow approximations of common quantum algorithms will then be explored. Several applications of these approximate algorithms will subsequently be considered, possibly including the enhancement of classical optimization heuristics or algorithms from the variational quantum eigensolver family |which are central to quantum chemistry or material science simulations on a quantum computer.