{
  "id": "1004.5409",
  "version": "v1",
  "published": "2010-04-29T21:43:46.000Z",
  "updated": "2010-04-29T21:43:46.000Z",
  "title": "Adiabatic quantum computation: Enthusiast and Sceptic's perspectives",
  "authors": [
    "Zhenwei Cao",
    "Alexander Elgart"
  ],
  "comment": "4 pages, 2 figures",
  "categories": [
    "quant-ph",
    "cs.CC"
  ],
  "abstract": "Enthusiast's perspective: We analyze the effectiveness of AQC for a small rank problem Hamiltonian $H_F$ with the arbitrary initial Hamiltonian $H_I$. We prove that for the generic $H_I$ the running time cannot be smaller than $O(\\sqrt N)$, where $N$ is a dimension of the Hilbert space. We also construct an explicit $H_I$ for which the running time is indeed $O(\\sqrt N)$. Our algorithm can be used to solve the unstructured search problem with the unknown number of marked items. Sceptic's perspective: We show that for a robust device, the running time for such $H_F$ cannot be much smaller than $O(N/\\ln N)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2010-04-29T21:43:46.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "adiabatic quantum computation",
      "sceptics perspective",
      "enthusiast",
      "running time",
      "small rank problem hamiltonian"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 4,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1004.5409C"
    }
  }
}