{
  "id": "1307.6538",
  "version": "v3",
  "published": "2013-07-24T19:31:17.000Z",
  "updated": "2014-05-08T21:28:54.000Z",
  "title": "Period Finding with Adiabatic Quantum Computation",
  "authors": [
    "Itay Hen"
  ],
  "comment": "6 pages",
  "journal": "EPL (Europhysics Letters), Volume 105, Number 5, 50005 (2014)",
  "doi": "10.1209/0295-5075/105/50005",
  "categories": [
    "quant-ph"
  ],
  "abstract": "We outline an efficient quantum-adiabatic algorithm that solves Simon's problem, in which one has to determine the `period', or xor-mask, of a given black-box function. We show that the proposed algorithm is exponentially faster than its classical counterpart and has the same complexity as the corresponding circuit-based algorithm. Together with other related studies, this result supports a conjecture that the complexity of adiabatic quantum computation is equivalent to the circuit-based computational model in a stronger sense than the well-known, proven polynomial equivalence between the two paradigms. We also discuss the importance of the algorithm and its theoretical and experimental implications for the existence of an adiabatic version of Shor's integer factorization algorithm that would have the same complexity as the original algorithm.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2014-05-08T21:28:54.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "adiabatic quantum computation",
      "period finding",
      "shors integer factorization algorithm",
      "efficient quantum-adiabatic algorithm",
      "proven polynomial equivalence"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "journal": "EPL (Europhysics Letters)",
      "year": 2014,
      "month": "Mar",
      "volume": 105,
      "number": 5,
      "pages": 50005
    },
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014EL....10550005H"
    }
  }
}