{
  "id": "2010.07852",
  "version": "v1",
  "published": "2020-10-15T16:14:26.000Z",
  "updated": "2020-10-15T16:14:26.000Z",
  "title": "On Quantum Computing for Mixed-Integer Programming",
  "authors": [
    "Chin-Yao Chang",
    "Eric Jones",
    "Peter Graf"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "Quantum computing (QC) is emerging as a new computing resource that could be superior to conventional computing (CC) for certain classes of optimization problems. However, in principle QC can only solve unconstrained binary programming problems, while mixed-integer linear programming (MIP) is of most interest in practice. We attempt to bridge the gap between the capability of QC and real-world applications by developing a new approach for MIP. The idea is decomposing the MIP into binary programming and linear programming (LP) problems, which are respectively solved by QC and conventional computing. We formalize a decomposition approach that ensures that with a sufficient number of back and forth iterations, the algorithm can reach the optimal solution of the original MIP problem. The algorithm is tested on a 2000Q D-Wave quantum processing units (QPU) and is shown to be effective for small-scaled test cases.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-10-15T16:14:26.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "quantum computing",
      "mixed-integer programming",
      "2000q d-wave quantum processing units",
      "original mip problem",
      "test cases"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}