|
| related topics |
| {algorithm, log, probability} |
| {information, entropy, channel} |
| {let, theorem, proof} |
|
Entropy lower bounds of quantum decision tree complexity
Yaoyun Shi
abstract: 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.
- oai_identifier:
- oai:arXiv.org:quant-ph/0008095
- categories:
- quant-ph
- comments:
- 7 pages Latex
- arxiv_id:
- quant-ph/0008095
- created:
- 2000-08-23
- updated:
- 2000-10-09
Full article ▸
|
|
| related documents |
| 0010057v1 |
| 9901068v1 |
| 0306042v1 |
| 0609220v1 |
| 0210141v2 |
| 0609166v1 |
| 0303074v1 |
| 0609160v1 |
| 0207108v1 |
| 0508156v3 |
| 0403071v1 |
| 0208112v1 |
| 0308016v1 |
| 0011052v2 |
| 0106121v2 |
| 0206066v1 |
| 0612052v2 |
| 0209148v1 |
| 0010081v1 |
| 0009086v1 |
| 0608156v1 |
| 0012088v1 |
| 0606077v1 |
| 0406104v1 |
| 0109038v1 |
|