Abstract

Quantum algorithms with shallow circuit depth, specifically the so-called Quantum Approximation Optimization Algorithms (QAOA), is a highly promising class of algorithms for solving a variety of optimization problems, widely studied in the literature, and already implemented on some quantum devices. We will survey a recent progress in power and limits of this algorithm to solve various optimization problem in random structures, such as optimization on random graphs and finding ground state of spin glasses. Specifically, we will show that QAOA at shallow depth cannot overcome an Overlap Gap Property barrier and, and as a result, is suboptimal by a certain multiplicative factor. Standard techniques such as concentration inequalities and distributional universality are not applicable in the quantum world, and we will discuss technical approaches to overcome these technical hurdles. Joint work with Ed Farhi, Sam Gutmann, Joao Basso, Song Mei and Leo Zhou.