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
 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.
 H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf. Quantum fingerprinting. Physical Review Letters, 87(16):167902, 2001.
 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.
 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.
 J. Justesen. A class of constructive asymptotically good algebraic codes. IEEE Trans. Information Theory, IT-18:652-656, 1972.
 E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, Cambridge, 1997.
 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.
 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.
 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.
 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.