{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T22:10:49Z","timestamp":1648937449006},"reference-count":0,"publisher":"Rinton Press","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["QIC"],"published-print":{"date-parts":[[2005,5]]},"abstract":"<jats:p>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 unstrucred 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.<\/jats:p>","DOI":"10.26421\/qic5.2-4","type":"journal-article","created":{"date-parts":[[2021,3,15]],"date-time":"2021-03-15T01:48:37Z","timestamp":1615772917000},"page":"131-145","source":"Crossref","is-referenced-by-count":0,"title":["Broken promises and quantum algorithms"],"prefix":"10.26421","volume":"5","author":[{"given":"A.","family":"Brazier","sequence":"first","affiliation":[]},{"given":"M.B.","family":"Plenio","sequence":"additional","affiliation":[]}],"member":"10955","published-online":{"date-parts":[[2005,5]]},"container-title":["Quantum Information and Computation"],"original-title":[],"deposited":{"date-parts":[[2021,3,15]],"date-time":"2021-03-15T01:48:41Z","timestamp":1615772921000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rintonpress.com\/journals\/doi\/QIC5.2-4.html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,5]]},"references-count":0,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2005,5]]},"published-print":{"date-parts":[[2005,5]]}},"URL":"https:\/\/doi.org\/10.26421\/qic5.2-4","relation":{},"ISSN":["1533-7146","1533-7146"],"issn-type":[{"value":"1533-7146","type":"print"},{"value":"1533-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,5]]}}}