A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem

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 (1/2 + 1101 D1/2\, l n\, D) times the number of equations. A recent classical algorithm achieved (1/2 + constantD1/2). We also show that in the typical case the quantum computer will output a string that satisfies (1/2+ 12√3e\, D1/2) times the number of equations.