Entropy lower bounds of quantum decision tree complexity

Preprint English OPEN
Shi, Yaoyun;
  • Subject: Quantum Physics
    acm: TheoryofComputation_GENERAL

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
  • References (6)

    [1] 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.

    [2] 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.

    [3] H. Buhrman and R. de Wolf. Complexity measures and decision tree complexity: A survey. Unpublished manuscript, 1999.

    [4] 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.

    [5] 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.

    [6] 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.

  • Related Organizations (4)
  • Metrics
Share - Bookmark