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

Edward Farhi, Jeffrey Goldstone, Sam Gutmann

Published 2014-12-18Version 1

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 mod2 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}{22 D^{3/4}}\right)$ times the number of equations. This beats the best known classical algorithm for this problem which has an approximation ratio of $\left(\frac{1}{2} + \frac{constant}{D}\right)$. We also show that if the hypergraph that describes the instance has no small loops then 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.