{
  "id": "0907.1623",
  "version": "v1",
  "published": "2009-07-09T18:03:08.000Z",
  "updated": "2009-07-09T18:03:08.000Z",
  "title": "Faster quantum algorithm for evaluating game trees",
  "authors": [
    "Ben W. Reichardt"
  ],
  "comment": "25 pages, 4 figures",
  "journal": "Proc. 22nd ACM-SIAM Symp. on Discrete Algorithms (SODA), 2011, pages 546-559",
  "categories": [
    "quant-ph"
  ],
  "abstract": "We give an O(sqrt n log n)-query quantum algorithm for evaluating size-n AND-OR formulas. Its running time is poly-logarithmically greater after efficient preprocessing. Unlike previous approaches, the algorithm is based on a quantum walk on a graph that is not a tree. Instead, the algorithm is based on a hybrid of direct-sum span program composition, which generates tree-like graphs, and a novel tensor-product span program composition method, which generates graphs with vertices corresponding to minimal zero-certificates. For comparison, by the general adversary bound, the quantum query complexity for evaluating a size-n read-once AND-OR formula is at least Omega(sqrt n), and at most O(sqrt{n} log n / log log n). However, this algorithm is not necessarily time efficient; the number of elementary quantum gates applied between input queries could be much larger. Ambainis et al. have given a quantum algorithm that uses sqrt{n} 2^{O(sqrt{log n})} queries, with a poly-logarithmically greater running time.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-07-09T18:03:08.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "faster quantum algorithm",
      "evaluating game trees",
      "novel tensor-product span program composition",
      "tensor-product span program composition method",
      "size-n read-once and-or formula"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 25,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0907.1623R"
    }
  }
}