Broken Promises and Quantum Algorithms

Physics – Quantum Physics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

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.

Rate now

     

Profile ID: LFWR-SCP-O-125689

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.