Physics – Quantum Physics
Scientific paper
2003-04-02
Physics
Quantum Physics
18 pages, 1 figure. Replaced with version to appear in QIC
Scientific paper
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.
Brazier Adam
Plenio Martin . B.
No associations
LandOfFree
Broken Promises and Quantum Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Broken Promises and Quantum Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Broken Promises and Quantum Algorithms will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-125689