{
  "annotation_id": "fcc91db0-bcc8-4fa6-a298-e5852d6d93d9",
  "date_created": "2026-03-02T18:02:34.113000Z",
  "date_modified": "2026-03-02T18:02:34.113000Z",
  "file_hash": "ae59287e63b350a5febe084e1a0bf0993c9b919efe774723a3274350465b3c41",
  "private": false,
  "record": {
    "abstract": "For every NAND formula of size N, there is a bounded-error N^{1/2+o(1)}-time\nquantum algorithm, based on a coined quantum walk, that evaluates this formula\non a black-box input. Balanced, or ``approximately balanced,\u0027\u0027 NAND formulas\ncan be evaluated in O(sqrt{N}) queries, which is optimal. It follows that the\n(2-o(1))-th power of the quantum query complexity is a lower bound on the\nformula size, almost solving in the positive an open problem posed by Laplante,\nLee and Szegedy.",
    "arxiv_id": "quant-ph/0703015",
    "authors": [
      "Andrew M. Childs",
      "Ben W. Reichardt",
      "Robert Spalek",
      "Shengyu Zhang"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Every NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a   quantum computer",
    "url": "https://arxiv.org/abs/quant-ph/0703015"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "018d11ce-14bf-4442-b94b-be890b9fb719",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}