𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Entropy lower bounds for quantum decision tree complexity

✍ Scribed by Yaoyun Shi

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
70 KB
Volume
81
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

We prove a general lower bound of quantum decision tree complexity in terms of some entropy notion. We regard decision tree 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 taken uniformly random in f 's domain. Our main result is that it takes (E(f )) queries to compute any total function f . It is interesting to contrast this bound with the (E(f )/ log n) bound, which is tight for some partial functions.

πŸ“œ SIMILAR VOLUMES

Complexity Lower Bounds for Approximatio
Complexity Lower Bounds for Approximation Algebraic Computation Trees
✍ Felipe Cucker; Dima Grigoriev πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 159 KB

We prove lower bounds for approximate computations of piecewise polynomial functions which, in particular, apply for round-off computations of such functions.

Universal Lower Bounds for Quantum Diffu
Universal Lower Bounds for Quantum Diffusion
✍ J.M. Barbaroux; S. Tcheremchantsev πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 220 KB

We study the connections between dynamical properties of Schro dinger operators H on separable Hilbert space H and the properties of corresponding spectral measures. Our main result establishes a relation for the moment of order p of the form H dt L , pΓ‚d (T ). (1) Here L , pΓ‚d (T ) is a function