期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2002
卷号：2002
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In the simultaneous message model, two parties holding n -bit integers x y send messages to a third party, the {\it referee}, enabling him to compute a boolean function f ( x y ) . Buhrman et al [BCWW01] proved the remarkable result that, when f is the equality function, the referee can solve this problem by comparing short \lq\lq 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 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 {\it public coin} model). We prove that, if R 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.
关键词：Communication complexity , public coin , quantum protocol , simultaneous message model
y send messages to a third party, the {\it referee}, enabling him to compute a boolean function f ( x 
