The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Cet article décrit une technique générale de limite inférieure quantique pour la complexité de communication d'une fonction qui dépend des entrées données à deux parties connectées via des chemins, qui peuvent être partagés avec d'autres parties, sur un réseau de n'importe quelle topologie. La technique peut également être utilisée pour obtenir une limite inférieure de la complexité de communication quantique de certaines fonctions qui dépendent des entrées réparties sur toutes les parties du réseau. En tant qu'application typique, nous appliquons notre technique au distinction problème de décider s’il existe une paire de parties avec des entrées identiques, sur un k-bague de fête ; des limites supérieures presque correspondantes sont également données.
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.
Copier
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
Copier
@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},}
Copier
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 -