{
  "annotation_id": "0bf14bd7-a6ba-4cf6-8fd8-c57b3376b10a",
  "date_created": "2026-03-02T18:01:52.613000Z",
  "date_modified": "2026-03-02T18:01:52.613000Z",
  "file_hash": "0f273f1ae2620f3ed20c45bae9ad7758e99852108c3a05e66e6cd95e48d2cd51",
  "private": false,
  "record": {
    "abstract": "Given a Boolean function f, we study two natural generalizations of the\ncertificate complexity C(f): the randomized certificate complexity RC(f) and\nthe quantum certificate complexity QC(f). Using Ambainis\u0027 adversary method, we\nexactly characterize QC(f) as the square root of RC(f). We then use this result\nto prove the new relation R0(f) = O(Q2(f)^2 Q0(f) log n) for total f, where R0,\nQ2, and Q0 are zero-error randomized, bounded-error quantum, and zero-error\nquantum query complexities respectively. Finally we give asymptotic gaps\nbetween the measures, including a total f for which C(f) is superquadratic in\nQC(f), and a symmetric partial f for which QC(f) = O(1) yet Q2(f) = Omega(n/log\nn).",
    "arxiv_id": "quant-ph/0210020",
    "authors": [
      "Scott Aaronson"
    ],
    "categories": [
      "quant-ph",
      "cs.CC"
    ],
    "title": "Quantum Certificate Complexity",
    "url": "https://arxiv.org/abs/quant-ph/0210020"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "7198fde7-fa5a-468a-9780-0a6f012edde5",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}