Broken Promises and Quantum Algorithms
| dc.creator | Brazier, Adam | |
| dc.creator | Plenio, Martin B. | |
| dc.date | 2003-04-02 | |
| dc.date | 2004-12-27 | |
| dc.date.accessioned | 2026-07-07T06:06:29Z | |
| dc.date.available | 2026-07-07T06:06:29Z | |
| dc.description | 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. | |
| dc.description | 18 pages, 1 figure. Replaced with version to appear in QIC | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0304017 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0304017 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/90993 | |
| dc.subject | Quantum Physics | |
| dc.title | Broken Promises and Quantum Algorithms | |
| dc.type | text |