Multi-party Quantum Communication Complezity with Routed Messages
This paper describes a general quantum lower bounding technique for the communication complexity of a function that depends on the inputs given to two parties connected via paths, which may be shared with other parties, on a network of any topology. The technique can also be employed to obtain a lowerbound of the quantum communication complexity of some functions that depend on the inputs distributed over all parties on the network. As a typical application, we apply our technique to the distinctness problem of deciding whether there are at least two parties with identical inputs, on a k-party ring; almost matching upper bounds are also given.
Seiichiro Tani Masaki Nakanishi Shigeru Yamashita
NTT Communication Science Laboratories, NTT Corporation Graduate School of Information Science, Nara Institute of Science and Technology
国际会议
The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)
大连
英文
180-190
2008-06-01（万方平台首次上网日期，不代表论文的发表时间）