WEKO3
アイテム
多人数の量子通信複雑性にける新しい手法
https://ipsj.ixsq.nii.ac.jp/records/218778
https://ipsj.ixsq.nii.ac.jp/records/2187780b9d8b25-030d-4337-9f75-eb496f338e4c
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-QS22006019.pdf (728.9 kB)
|
Copyright (c) 2022 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2022-06-30 | |||||||||
| タイトル | ||||||||||
| タイトル | 多人数の量子通信複雑性にける新しい手法 | |||||||||
| タイトル | ||||||||||
| 言語 | en | |||||||||
| タイトル | Bounds on oblivious multiparty quantum communication complexity | |||||||||
| 言語 | ||||||||||
| 言語 | eng | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||
| 資源タイプ | technical report | |||||||||
| 著者所属 | ||||||||||
| Nagoya University | ||||||||||
| 著者所属 | ||||||||||
| Nagoya University | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Nagoya University | ||||||||||
| 著者所属(英) | ||||||||||
| en | ||||||||||
| Nagoya University | ||||||||||
| 著者名 |
ルガル, フランソワ
× ルガル, フランソワ
× 駿河, 大樹
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | The main conceptual contribution of this technical report is investigating quantum multiparty communication complexity in the setting where communication is oblivious. This requirement, which to our knowledge is satisfied by all quantum multiparty protocols in the literature, means that the communication pattern, and in particular the amount of communication exchanged between each pair of players at each round is fixed independently of the input before the execution of the protocol. We show, for a wide class of functions, how to prove strong lower bounds on their oblivious quantum k-party communication complexity using lower bounds on their two-party communication complexity. We apply this technique to prove tight lower bounds for all symmetric functions, and in particular obtain an optimal Ω(k√n) lower bound on the oblivious quantum k-party communication complexity of the n-bit Set-Disjointness function. We also obtain (nearly) matching upper bounds by examining the optimal protocols for each function. In this technical report, we overview these results and do not give most of the technical proofs. | |||||||||
| 論文抄録(英) | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | The main conceptual contribution of this technical report is investigating quantum multiparty communication complexity in the setting where communication is oblivious. This requirement, which to our knowledge is satisfied by all quantum multiparty protocols in the literature, means that the communication pattern, and in particular the amount of communication exchanged between each pair of players at each round is fixed independently of the input before the execution of the protocol. We show, for a wide class of functions, how to prove strong lower bounds on their oblivious quantum k-party communication complexity using lower bounds on their two-party communication complexity. We apply this technique to prove tight lower bounds for all symmetric functions, and in particular obtain an optimal Ω(k√n) lower bound on the oblivious quantum k-party communication complexity of the n-bit Set-Disjointness function. We also obtain (nearly) matching upper bounds by examining the optimal protocols for each function. In this technical report, we overview these results and do not give most of the technical proofs. | |||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AA12894105 | |||||||||
| 書誌情報 |
量子ソフトウェア（QS） 巻 2022-QS-6, 号 19, p. 1-7, 発行日 2022-06-30 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 2435-6492 | |||||||||
| Notice | ||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
