Entropy lower bounds of quantum decision tree complexity

Details Entropy lower bounds of quantum decision tree complexity Entropy lower bounds of quantum decision tree complexity

2000-08-23

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

Physics

Quantum Physics

7 pages Latex

Scientific paper

We prove a general lower bound of quantum decision tree complexity in terms of some entropy notion. We regard the computation as a communication process in which the oracle and the computer exchange several rounds of messages, each round consisting of O(log(n)) bits. Let E(f) be the Shannon entropy of the random variable f(X), where X is uniformly random in f's domain. Our main result is that it takes \Omega(E(f)) queries to compute any \emph{total} function f. It is interesting to contrast this bound with the \Omega(E(f)/log(n)) bound, which is tight for \emph{partial} functions. Our approach is the polynomial method.

Affiliated with

Also associated with

No associations

Rating

Entropy lower bounds of quantum decision tree 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 Entropy lower bounds of quantum decision tree complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Entropy lower bounds of quantum decision tree complexity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-355897