Limitations of Local Quantum Algorithms for Random Optimization

In a body of growing work, it is becoming increasingly clear that local quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) do not provide any computational advantage over classical algorithms for a large family of optimization problems. The results in the literature often come in two flavors:

1) An efficient classical algorithm that solves typical instances of the problem under a certain solution geometry (known as full-Replica Symmetry Breaking).

2) Obstructions to large families of algorithms (now including local quantum algorithms) in the absence of this solution geometry (known as a Branching Overlap-Gap Property).

We present two recent results that contribute to this line of research and show the following:

1) Every local quantum algorithm (including the QAOA up to ~log(n) depth) is obstructed from computing arbitrarily good solutions to typical instances of random constraint satisfaction problems (random CSPs) when the problem exhibits a Branching Overlap-Gap Property. Furthermore, the exact quality of the computed solution is established by a variational principle, and is matched by a classical algorithm called Approximate-Message Passing (AMP) - This is proved by establishing strong concentration properties of local quantum algorithms on a large family of problems.

2) A large class of random CSPs possess a Branching Overlap-Gap Property - This is proved by generalizing the Guerra-Tonnineli interpolations from spin glass theory using techcniques from discrete Fourier analysis.

The two results above in conjunction with prior results in the literature immediately rule out, for example, the possibillity for quantum advantage on the canonical problem of approximating the maximum-cut of random d-regular graphs (where the degree d is a large constant)