On the power of quantum fingerprinting

ABSTRACT

In the simultaneous message model, two parties holding n-bit integers x,y send messages to a third party, the referee, enabling him to compute a boolean function f(x,y). Buhrman et al [3] proved the remarkable result that, when f is the equality function, the referee can solve this problem by comparing short "quantum fingerprints" sent by the two parties, i.e., there exists a quantum protocol using only O(log n) bits. This is in contrast to the well-known classical case for which Ω(n^1/2) bits are provably necessary for the same problem even with randomization. In this paper we show that short quantum fingerprints can be used to solve the problem for a much larger class of functions. Let R^{<??par line>,pub}(f) denote the number of bits needed in the classical case, assuming in addition a common sequence of random bits is known to all parties (the public coin model). We prove that, if R^{<??par line>,pub}(f)=O(1), then there exists a quantum protocol for f using only O(log n) bits. As an application we show that O(log n) quantum bits suffice for the bounded Hamming distance function, defined by f(x,y)=1 if and only if x and y have a constant Hamming distance d or less.

REFERENCES

• 1: A. Ambainis. Communication complexity in a 3-computer model. Algorithmica, 16:298--301, 1996.
• 2: L. Babai , P. G. Kimmel, Randomized Simultaneous Messages: Solution Of A Problem Of Yao In Communication Complexity, Proceedings of the 12th Annual IEEE Conference on Computational Complexity, p.239, June 24-27, 1997
• 3: H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf. Quantum fingerprinting. Physical Review Letters, 87(16):167902, 2001.
• 4: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 5: Ilan Newman, Private vs. common random bits in communication complexity, Information Processing Letters, v.39 n.2, p.67-71, July 31, 1991 [doi>10.1016/0020-0190(91)90157-D]
• 6: Ilan Newman , Mario Szegedy, Public vs. private coin flips in one round communication games (extended abstract), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.561-570, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238004]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Theory

Keywords:
communication complexity, computational complexity, public coin, quantum protocol, simultaneous message model