  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.
Here $ \mu $ is the fraction that would be satisfied by a uniformly random
assignment, and $ D $ is the number of constraints that each variable can
appear. CSPs with typicality include Max-$ k $XOR and Max-$ k $SAT. We point
out how it can be applied to determine the typical ground-state energy of some
local Hamiltonians. We also give a similar result for instances with "no
overlapping constraints", using the quantum algorithm. We sketch how the
classical algorithm might achieve some partial result.
