Multi-Party Quantum Communication Complexity with Routed Messages

• TANI Seiichiro

  NTT Communication Science Laboratories, NTT Corporation

• NAKANISHI Masaki

  Graduate School of Information Science, Nara Institute of Science and Technology

• YAMASHITA Shigeru

  Graduate School of Information Science, Nara Institute of Science and Technology

Abstract

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.

Journal

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E92-D (2), 191-199, 2009

  The Institute of Electronics, Information and Communication Engineers

Keywords

• quantum communication complexity
• network topology
• distributed computing

Details

• CRID: 1390001204377764224
• NII Article ID: 10026807413
• NII Book ID: AA10826272
• DOI: 10.1587/transinf.e92.d.191
• ISSN: 17451361
• ISSN: 09168532
• Web Site: http://www.jstage.jst.go.jp/article/transinf/E92.D/2/E92.D_2_191/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
• Abstract License Flag: Disallowed