{
  "annotation_id": "b946d29c-0f7c-4890-9b03-c7ab2f544241",
  "date_created": "2026-03-02T18:02:03.410000Z",
  "date_modified": "2026-03-02T18:02:03.410000Z",
  "file_hash": "d8b49202aeece6998398b0d14741f9b412726ba80df18c8f5387fa0d38789ae3",
  "private": false,
  "record": {
    "abstract": "Query complexity measures the amount of information an algorithm needs about\na problem to compute a solution. On a quantum computer there are different\nrealizations of a query and we will show that these are not always equivalent.\nOur definition of equivalence is based on the ability to simulate (or\napproximate) one query type by another. We show that a bit query can always\napproximate a phase query with just two queries, while there exist problems for\nwhich the number of phase queries which are necessary to approximate a bit\nquery must grow exponentially with the precision of the bit query. This result\nfollows from the query complexity bounds for the evaluation problem, for which\nwe establish a strong lower bound for the number of phase queries by exploiting\na relation between quantum algorithms and trigonometric polynomials.",
    "arxiv_id": "quant-ph/0308140",
    "authors": [
      "Arvid J. Bessen"
    ],
    "categories": [
      "quant-ph"
    ],
    "doi": "10.1016/j.jco.2003.07.001",
    "journal_ref": "Journal of Complexity, Volume 20, Issue 5 (October 2004), Pages:\n  699 - 712",
    "title": "Approximation of Various Quantum Query Types",
    "url": "https://arxiv.org/abs/quant-ph/0308140"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "63d102a4-5b1d-4c1b-ad50-81e1a015efe8",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}