{
  "annotation_id": "13045fc7-dceb-4fac-92ce-5565fc05b591",
  "date_created": "2026-03-02T18:01:58.871000Z",
  "date_modified": "2026-03-02T18:01:58.871000Z",
  "file_hash": "fa24e4bb076dc9c9c22e0169275eda58b064ffb412d382a453b941e6284352c8",
  "private": false,
  "record": {
    "abstract": "In the black-box model, problems constrained by a `promise\u0027 are the only ones\nthat admit a quantum exponential speedup over the best classical algorithm in\nterms of query complexity. The most prominent example of this is the\nDeutsch-Jozsa algorithm. More recently, Wim van Dam put forward an algorithm\nfor unstructured problems (i.e., those without a promise). We consider the\nDeutsch-Jozsa algorithm with a less restrictive (or `broken\u0027) promise and study\nthe transition to an unstructured problem. We compare this to the success of\nvan Dam\u0027s algorithm. These are both compared with a standard classical sampling\nalgorithm. The Deutsch-Jozsa algorithm remains good as the problem initially\nbecomes less structured, but the van Dam algorithm can be adapted so as to\nbecome superior to the Deutsch-Jozsa algorithm as the promise is weakened.",
    "arxiv_id": "quant-ph/0304017",
    "authors": [
      "Adam Brazier",
      "Martin B. Plenio"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "Broken Promises and Quantum Algorithms",
    "url": "https://arxiv.org/abs/quant-ph/0304017"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "3998493d-4ffc-4310-a51f-bb161c2eb2e5",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}