{
  "id": "quant-ph/0311038",
  "version": "v2",
  "published": "2003-11-06T20:54:06.000Z",
  "updated": "2003-12-01T20:11:52.000Z",
  "title": "Quantum algorithms for subset finding",
  "authors": [
    "Andrew M. Childs",
    "Jason M. Eisenberg"
  ],
  "comment": "7 pages; note added on related results in quant-ph/0310134",
  "journal": "Quantum Information and Computation 5, 593 (2005)",
  "categories": [
    "quant-ph"
  ],
  "abstract": "Recently, Ambainis gave an O(N^(2/3))-query quantum walk algorithm for element distinctness, and more generally, an O(N^(L/(L+1)))-query algorithm for finding L equal numbers. We point out that this algorithm actually solves a much more general problem, the problem of finding a subset of size L that satisfies any given property. We review the algorithm and give a considerably simplified analysis of its query complexity. We present several applications, including two algorithms for the problem of finding an L-clique in an N-vertex graph. One of these algorithms uses O(N^(2L/(L+1))) edge queries, and the other uses \\tilde{O}(N^((5L-2)/(2L+4))), which is an improvement for L <= 5. The latter algorithm generalizes a recent result of Magniez, Santha, and Szegedy, who considered the case L=3 (finding a triangle). We also pose two open problems regarding continuous time quantum walk and lower bounds.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2003-12-01T20:11:52.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "quantum algorithms",
      "subset finding",
      "problems regarding continuous time quantum",
      "open problems regarding continuous time",
      "regarding continuous time quantum walk"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 7,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2003quant.ph.11038C"
    }
  }
}