Multi-Party Quantum Communication Complexity with Routed Messages

Seiichiro TANI  Masaki NAKANISHI  Shigeru YAMASHITA 

Publication
IEICE TRANSACTIONS on Information and Systems  Vol.E92-D  No.2  pp.191-199
Publication Date: 2009/02/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
Category: 
Keyword: 
quantum communication complexity,  network topology,  distributed computing, 

Full Text: PDF(435.1KB)

Summary: 
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 lower-bound 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 a pair of parties with identical inputs, on a k-party ring; almost matching upper bounds are also given.