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 and P. Kimmel. Randomized simultaneous messages. In Proc. 12th IEEE Symp. on Computational Complexity, pages 239--246. IEEE, 1997.
3. H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf. Quantum fingerprinting. Physical Review Letters, 87(16):167902, 2001.
4. E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, Cambridge, UK, 1997.
5. I. Newman. Private vs. common random bits in communication complexity. Information Processing Letters, 39:67--71, 1991.
6. I. Newman and M. Szegedy. Public vs. private coin flips in one round communication games. In Proc. 28th ACM Symp. on Theory of Computing, pages 561--570. ACM, 1996.

Index Terms

• Theory of computation

  • Models of computation

    • Abstract machines