{
  "annotation_id": "a5587d7d-ae46-41ee-ac5e-232ea39f0fe8",
  "date_created": "2026-03-02T18:01:42.366000Z",
  "date_modified": "2026-03-02T18:01:42.366000Z",
  "file_hash": "da6026cc19eecb61601ca2321161885c008158717c8da1b956a4fdd762d99c25",
  "private": false,
  "record": {
    "abstract": "We show that Nechiporuk\u0027s method for proving lower bounds for Boolean\nformulas can be extended to the quantum case. This leads to an $\\Omega(n^2 /\n\\log^2 n)$ lower bound for quantum formulas computing an explicit function. The\nonly known previous explicit lower bound for quantum formulas states that the\nmajority function does not have a linear-size quantum formula. We also show\nthat quantum formulas can be simulated by Boolean circuits of almost the same\nsize.",
    "arxiv_id": "quant-ph/0104053",
    "authors": [
      "Vwani P. Roychowdhury",
      "Farrokh Vatan"
    ],
    "categories": [
      "quant-ph",
      "cs.CC"
    ],
    "title": "Quantum Formulas: a Lower Bound and Simulation",
    "url": "https://arxiv.org/abs/quant-ph/0104053"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "d07a9e10-3d01-48dc-b068-8fd6cc67d6b0",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}