{
  "id": "1001.3116",
  "version": "v2",
  "published": "2010-01-18T18:09:22.000Z",
  "updated": "2010-01-19T01:11:33.000Z",
  "title": "Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design",
  "authors": [
    "Vicky Choi"
  ],
  "comment": "10 pages, 5 figures",
  "journal": "Quantum Information Processing: Volume 10, Issue 3 (2011), Page 343",
  "doi": "10.1007/s11128-010-0200-3",
  "categories": [
    "quant-ph",
    "cs.CC"
  ],
  "abstract": "In [Choi08], we introduced the notion of minor-embedding in adiabatic quantum optimization. A minor-embedding of a graph G in a quantum hardware graph U is a subgraph of U such that G can be obtained from it by contracting edges. In this paper, we describe the intertwined adiabatic quantum architecture design problem, which is to construct a hardware graph U that satisfies all known physical constraints and, at the same time, permits an efficient minor-embedding algorithm. We illustrate an optimal complete-graph-minor hardware graph. Given a family F of graphs, a (host) graph U is called F-minor-universal if for each graph G in F, U contains a minor-embedding of G. The problem for designing a F-minor-universal hardware graph U_{sparse} in which F consists of a family of sparse graphs (e.g., bounded degree graphs) is open.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2010-01-19T01:11:33.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "adiabatic quantum computation",
      "minor-universal graph design",
      "hardware graph",
      "minor-embedding",
      "adiabatic quantum architecture design problem"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}