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 Ω(n1/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.
- A. Ambainis. Communication complexity in a 3-computer model. Algorithmica, 16:298--301, 1996.Google ScholarCross Ref
- L. Babai and P. Kimmel. Randomized simultaneous messages. In Proc. 12th IEEE Symp. on Computational Complexity, pages 239--246. IEEE, 1997. Google ScholarDigital Library
- H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf. Quantum fingerprinting. Physical Review Letters, 87(16):167902, 2001.Google ScholarCross Ref
- E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, Cambridge, UK, 1997. Google ScholarDigital Library
- I. Newman. Private vs. common random bits in communication complexity. Information Processing Letters, 39:67--71, 1991. Google ScholarDigital Library
- 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. Google ScholarDigital Library
Index Terms
- On the power of quantum fingerprinting
Recommendations
Unbounded-Error Classical and Quantum Communication Complexity
Algorithms and ComputationAbstractSince the seminal work of Paturi and Simon [26,FOCS’84 & JCSS’86], the unbounded-error classical communication complexity of a Boolean function has been studied based on the arrangement of points and hyperplanes. Recently, [14, ICALP’07] found ...
Demonstration of multiparty quantum clock synchronization
Quantum clock synchronization (QCS) is a kind of method to measure the time difference among spatially separated clocks with the principle of quantum mechanics. The first QCS algorithm proposed by Chuang and Jozsa is merely based on two parties, which ...
Noisy Interactive Quantum Communication
We study the problem of simulating protocols in a quantum communication setting over noisy channels. This problem falls at the intersection of quantum information theory and quantum communication complexity, and it will be of importance for eventual real-...
Comments