{
  "id": "quant-ph/0401083",
  "version": "v1",
  "published": "2004-01-14T21:26:38.000Z",
  "updated": "2004-01-14T21:26:38.000Z",
  "title": "The quantum query complexity of the hidden subgroup problem is polynomial",
  "authors": [
    "Mark Ettinger",
    "Peter Hoyer",
    "Emanuel Knill"
  ],
  "comment": "To appear in Information Processing Letters (IPL)",
  "categories": [
    "quant-ph"
  ],
  "abstract": "We present a quantum algorithm which identifies with certainty a hidden subgroup of an arbitrary finite group G in only a polynomial (in log |G|) number of calls to the oracle. This is exponentially better than the best classical algorithm. However our quantum algorithm requires exponential time, as in the classical case. Our algorithm utilizes a new technique for constructing error-free algorithms for non-decision problems on quantum computers.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2004-01-14T21:26:38.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "quantum query complexity",
      "hidden subgroup problem",
      "polynomial",
      "quantum algorithm",
      "arbitrary finite group"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2004quant.ph..1083E"
    }
  }
}