Performance of QAOA on Typical Instances of Constraint Satisfaction Problems with Bounded Degree

Understand

We consider constraint satisfaction problems of bounded degree, with a good notion of "typicality", e.g.

• the negation of the variables in each constraint is taken independently at random.
• Using the quantum approximate optimization algorithm (QAOA), we show that $ \mu+\Omega(1/\sqrt{D}) $ fraction of the constraints can be satisfied for typical instances, with the assignment efficiently produced by QAOA.
• We do so by showing that the averaged fraction of constraints being satisfied is $ \mu+\Omega(1/\sqrt{D}) $, with small variance.