{
  "id": "quant-ph/0304017",
  "version": "v2",
  "published": "2003-04-02T16:57:18.000Z",
  "updated": "2004-12-27T22:44:06.000Z",
  "title": "Broken Promises and Quantum Algorithms",
  "authors": [
    "Adam Brazier",
    "Martin B. Plenio"
  ],
  "comment": "18 pages, 1 figure. Replaced with version to appear in QIC",
  "categories": [
    "quant-ph"
  ],
  "abstract": "In the black-box model, problems constrained by a `promise' are the only ones that admit a quantum exponential speedup over the best classical algorithm in terms of query complexity. The most prominent example of this is the Deutsch-Jozsa algorithm. More recently, Wim van Dam put forward an algorithm for unstructured problems (i.e., those without a promise). We consider the Deutsch-Jozsa algorithm with a less restrictive (or `broken') promise and study the transition to an unstructured problem. We compare this to the success of van Dam's algorithm. These are both compared with a standard classical sampling algorithm. The Deutsch-Jozsa algorithm remains good as the problem initially becomes less structured, but the van Dam algorithm can be adapted so as to become superior to the Deutsch-Jozsa algorithm as the promise is weakened.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2004-12-27T22:44:06.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "quantum algorithms",
      "broken promises",
      "quantum exponential speedup",
      "van dam algorithm",
      "deutsch-jozsa algorithm remains"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 18,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2003quant.ph..4017B"
    }
  }
}