  We apply our recent Quantum Approximate Optimization Algorithm to the
combinatorial problem of bounded occurrence Max E3LIN2. The input is a set of
linear equations each of which contains exactly three boolean variables and
each equation says that the sum of the variables mod 2 is 0 or is 1. Every
variable is in no more than D equations. A random string will satisfy 1/2 of
the equations. We show that the level one QAOA will efficiently produce a
string that satisfies $\left(\frac{1}{2} + \frac{1}{101 D^{1/2}\, l n\,
D}\right)$ times the number of equations. A recent classical algorithm achieved
$\left(\frac{1}{2} + \frac{constant}{D^{1/2}}\right)$. We also show that in the
typical case the quantum computer will output a string that satisfies
$\left(\frac{1}{2}+ \frac{1}{2\sqrt{3e}\, D^{1/2}}\right)$ times the number of
equations.
