A quantum algorithm for examining oracles

Details A quantum algorithm for examining oracles A quantum algorithm for examining oracles

2004-08-03

arxiv.org/abs/quant-ph/0408013v2

Physics

Quantum Physics

19 pages, 3 figures, Latex2e; v2: minor corrections

Scientific paper

In this paper, we consider a quantum algorithm for solving the following problem: ``Suppose $f$ is a function given as a black box (that is also called an oracle) and $f$ is invariant under some AND-mask. Examine a property of $f$ by querying the oracle.'' We compare the efficiency of our quantum algorithm with that of classical algorithms by evaluating the expected number of queries for each algorithm. We show that our quantum algorithm is more efficient than any classical algorithm in some cases. However, our quantum algorithm does not exhibit an exponential speedup in the size of an input, compared with the best classical algorithm. Our algorithm extracts a global property of $f$ (that is, invariance of $f$) while it neglects local properties of $f$ (that is, outputs of $f$). We can regard our algorithm as an application of Simon's algorithm.

Affiliated with

Also associated with

No associations

Rating

A quantum algorithm for examining oracles 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 A quantum algorithm for examining oracles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A quantum algorithm for examining oracles will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-307684