Average-Case Quantum Query Complexity

Details Average-Case Quantum Query Complexity Average-Case Quantum Query Complexity

1999-04-23

arxiv.org/abs/quant-ph/9904079v3

Physics

Quantum Physics

14 pages, LaTeX. Some parts rewritten. This version to appear in the Journal of Physics A

Scientific paper

We compare classical and quantum query complexities of total Boolean functions. It is known that for worst-case complexity, the gap between quantum and classical can be at most polynomial. We show that for average-case complexity under the uniform distribution, quantum algorithms can be exponentially faster than classical algorithms. Under non-uniform distributions the gap can even be super-exponential. We also prove some general bounds for average-case complexity and show that the average-case quantum complexity of MAJORITY under the uniform distribution is nearly quadratically better than the classical complexity.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-627008