Quantum Communication Protocols with Public Coins

概要

論文の詳細を見る
This paper studies the model of quantum protocols with classical public coins, and shows its application to quantum communication complexity of some functions. The paper first proves, by carefully combining quantum Grover search with the concept of quantum protocols with classical public coins, that the quantum communication complexity for LNE(l, k) is O(√l log l + log k), where LNE(l, k) is an lk-bit total Boolean function called the list-nonequality function. The function is a generalization of the equality function and the disjoint function. The above bound gives some separation between quantum and classical communication complexity for a total function, since the classical randomized communication complexity for the same function is Θ(l + log k). As a multi-party version of the list-nonequality function, the distinctness problem is considered. The goal of this problem is to decide whether or not there are two parties that have the same inputs. The sub-optimal bound of the communication complexity of the problem is given via the model of quantum protocols with classical public coins.
一般社団法人情報処理学会の論文
2009-09-08