Entropy lower bounds of quantum decision tree complexity
Subject: Quantum Physics
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. Le... View more
 A. Ambainis. Quantum lower bounds by quantum arguments. In Proceedings of the Thirty-second Annual ACM Symposium on the Theory of Computing, pages 636-643, Portland, Oregon, May 2000.
 R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials. In 39th Annual Symposium on Foundations of Computer Science, pages 352-361, Los Alamitos, CA, November 1998. IEEE.
 H. Buhrman and R. de Wolf. Complexity measures and decision tree complexity: A survey. Unpublished manuscript, 1999.
 Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 212-219, Philadelphia, Pennsylvania, May 1996.
 A. S. Holevo. Some estimates for the amount of information transmittable by a quantum communications channel. Problemy Peredaˇci Informacii, 9(3):3-11, 1973. English translation: Problems of Information Transmission, 9(3):177-183, 1973.
 Y. Shi. Lower bounds of quantum black-box complexity and degree of approximating polynomials by influence of boolean variables. Information Processing Letters, 75(1- 2):79-83, 31 July 2000.