Distributed construction of quantum fingerprints

Preprint English OPEN
Ambainis, Andris; Shi, Yaoyun;
  • Subject: Quantum Physics

Quantum fingerprints are useful quantum encodings introduced by Buhrman, Cleve, Watrous, and de Wolf (Physical Review Letters, Volume 87, Number 16, Article 167902, 2001; quant-ph/0102001) in obtaining an efficient quantum communication protocol. We design a protocol fo... View more
  • References (10)

    [4] R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials. Journal of the ACM, 48(4):778-797, July 2001.

    [5] H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf. Quantum fingerprinting. Physical Review Letters, 87(16):167902, 2001.

    [6] H. Buhrman, R. Cleve, and A. Wigderson. Quantum vs. classical communication and computation. In ACM, editor, Proceedings of the thirtieth annual ACM Symposium on Theory of Computing: Dallas, Texas, May 23-26, 1998, pages 63-68, New York, NY, USA, 1998. ACM Press.

    [7] L. K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the TwentyEighth Annual ACM Symposium on the Theory of Computing, pages 212-219, Philadelphia, Pennsylvania, May 1996.

    [8] J. Justesen. A class of constructive asymptotically good algebraic codes. IEEE Trans. Information Theory, IT-18:652-656, 1972.

    [9] E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, Cambridge, 1997.

    [10] I. Newman and M. Szegedy. Public vs. private coin flips in one round communication games (extended abstract). In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 561-570, Philadelphia, Pennsylvania, 22-24 May 1996.

    [11] A. A. Razborov. Quantum communication complexity of symmetric predicates (russian). Izvestiya of the Russian Academy of Science, Mathematics, 6, 2002. To appear, English translation avaialbe at URL: http://genesis.mi.ras.ru∼razborov/qcc eng.ps.

    [12] A. C. Yao. Some complexity questions related to distributive computing. In Eleventh Annual ACM Symposium on Theory of Computing (STOC '79), pages 209-213, New York, Apr. 1979. ACM.

    [13] A. C.-C. Yao. Quantum circuit complexity. In 34th Annual Symposium on Foundations of Computer Science: November 3-5, 1993, Palo Alto, California: proceedings [papers], pages 352-361. IEEE Computer Society Press, 1993.

  • Metrics
Share - Bookmark