Uselessness for an Oracle Model with Internal Randomness

Details Uselessness for an Oracle Model with Internal Randomness Uselessness for an Oracle Model with Internal Randomness

2011-11-07

arxiv.org/abs/1111.1462v1

Physics

Quantum Physics

Scientific paper

We consider a generalization of the standard oracle model in which the oracle acts on the target with a permutation which is selected according to internal random coins. We show new exponential quantum speedups which may be obtained over classical algorithms in this oracle model. Even stronger, we describe several problems which are impossible to solve classically but can be solved by a quantum algorithm using a single query; we show that such infinity-vs-one separations between classical and quantum query complexities can be constructed from any separation between classical and quantum query complexities (in the unbounded-error regime). We also give conditions to determine when oracle problems---either in the standard model, or in any of the generalizations we consider---cannot be solved with success probability better than random guessing would achieve. In the oracle model with internal randomness where the goal is to gain any nonzero advantage over guessing, we prove (roughly speaking) that (k) quantum queries are equivalent in power to (2k) classical queries, thus extending results of Meyer and Pommersheim, and Montanaro, Nishimura and Raymond.

Affiliated with

Also associated with

No associations

Rating

Uselessness for an Oracle Model with Internal Randomness 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 Uselessness for an Oracle Model with Internal Randomness, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Uselessness for an Oracle Model with Internal Randomness will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-689188