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
DOI: 10.1587/transinf.E92.D.191
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>>
Buy this Article


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.