Sharp Quantum vs. Classical Query Complexity Separations

Details Sharp Quantum vs. Classical Query Complexity Separations Sharp Quantum vs. Classical Query Complexity Separations

2000-11-15

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

Physics

Quantum Physics

13 pages, change in title, improvements in presentation, and minor corrections. To appear in Algorithmica

Scientific paper

We obtain the strongest separation between quantum and classical query complexity known to date -- specifically, we define a black-box problem that requires exponentially many queries in the classical bounded-error case, but can be solved exactly in the quantum case with a single query (and a polynomial number of auxiliary operations). The problem is simple to define and the quantum algorithm solving it is also simple when described in terms of certain quantum Fourier transforms (QFTs) that have natural properties with respect to the algebraic structures of finite fields. These QFTs may be of independent interest, and we also investigate generalizations of them to noncommutative finite rings.

Affiliated with

Also associated with

No associations

Rating

Sharp Quantum vs. Classical Query Complexity Separations 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 Sharp Quantum vs. Classical Query Complexity Separations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sharp Quantum vs. Classical Query Complexity Separations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-251525