{
  "annotation_id": "c8dd7c41-3c14-4a3f-a807-3d3206db0031",
  "date_created": "2026-03-02T18:02:27.173000Z",
  "date_modified": "2026-03-02T18:02:27.173000Z",
  "file_hash": "0dd506c55524c3abb92c6b2962c953834a7925dabfc0095ac2616ad56229d072",
  "private": false,
  "record": {
    "abstract": "In this paper we study the complexity of quantum query algorithms computing\nthe value of Boolean function and its relation to the degree of algebraic\npolynomial representing this function. We pay special attention to Boolean\nfunctions with quantum query algorithm complexity lower than the deterministic\none. Relation between the degree of representing polynomial and potentially\npossible quantum algorithm complexity has been already described;\nunfortunately, there are few examples of quantum algorithms to illustrate\ntheoretical evaluation of the complexity. Work in this direction was aimed (1)\nto construct effective quantum query algorithms for computing Boolean\nfunctions, (2) to design methods for Boolean function construction with a large\ngap between deterministic complexity and degree of representing polynomial. In\nthis paper we present our results in both directions.",
    "arxiv_id": "quant-ph/0607022",
    "authors": [
      "Alina Dubrovska Vasilieva",
      "Taisija Mischenko-Slatenkova"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Computing Boolean Functions: Exact Quantum Query Algorithms and Low   Degree Polynomials",
    "url": "https://arxiv.org/abs/quant-ph/0607022"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "88c31f02-b0f3-477c-b727-5acf56a43274",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}