Multi-Party Quantum Communication Complexity with Routed Messages
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E92-D No.2 pp.191-199
- Publication Date
- 2009/02/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E92.D.191
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Seiichiro TANI, Masaki NAKANISHI, Shigeru YAMASHITA, "Multi-Party Quantum Communication Complexity with Routed Messages" in IEICE TRANSACTIONS on Information,
vol. E92-D, no. 2, pp. 191-199, February 2009, doi: 10.1587/transinf.E92.D.191.
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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E92.D.191/_p
Copy
@ARTICLE{e92-d_2_191,
author={Seiichiro TANI, Masaki NAKANISHI, Shigeru YAMASHITA, },
journal={IEICE TRANSACTIONS on Information},
title={Multi-Party Quantum Communication Complexity with Routed Messages},
year={2009},
volume={E92-D},
number={2},
pages={191-199},
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.},
keywords={},
doi={10.1587/transinf.E92.D.191},
ISSN={1745-1361},
month={February},}
Copy
TY - JOUR
TI - Multi-Party Quantum Communication Complexity with Routed Messages
T2 - IEICE TRANSACTIONS on Information
SP - 191
EP - 199
AU - Seiichiro TANI
AU - Masaki NAKANISHI
AU - Shigeru YAMASHITA
PY - 2009
DO - 10.1587/transinf.E92.D.191
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E92-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2009
AB - 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.
ER -
English
