{
  "id": "1412.6062",
  "version": "v1",
  "published": "2014-12-18T20:38:18.000Z",
  "updated": "2014-12-18T20:38:18.000Z",
  "title": "A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem",
  "authors": [
    "Edward Farhi",
    "Jeffrey Goldstone",
    "Sam Gutmann"
  ],
  "categories": [
    "quant-ph"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-12-18T20:38:18.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "quantum approximate optimization algorithm",
      "bounded occurrence constraint problem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1412.6062F"
    }
  }
}