{
  "id": "1807.08970",
  "version": "v1",
  "published": "2018-07-24T09:01:50.000Z",
  "updated": "2018-07-24T09:01:50.000Z",
  "title": "Computational speedups using small quantum devices",
  "authors": [
    "Vedran Dunjko",
    "Yimin Ge",
    "J. Ignacio Cirac"
  ],
  "comment": "5+12 pages",
  "categories": [
    "quant-ph",
    "cs.AI",
    "cs.CC"
  ],
  "abstract": "Suppose we have a small quantum computer with only M qubits. Can such a device genuinely speed up certain algorithms, even when the problem size is much larger than M? Here we answer this question to the affirmative. We present a hybrid quantum-classical algorithm to solve 3SAT problems involving n<<M variables that significantly speeds up its fully classical counterpart. This question may be relevant in view of the current quest to build small quantum computers.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-07-24T09:01:50.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "small quantum devices",
      "computational speedups",
      "build small quantum computers",
      "hybrid quantum-classical algorithm",
      "3sat problems"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}