Quantum Simultaneous Protocols without Public Coins using Modified Equality Queries
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913607524024320 |
|---|---|
| author | Gall, François Le Nadler, Oran Nishimura, Harumichi Oshman, Rotem |
| author_facet | Gall, François Le Nadler, Oran Nishimura, Harumichi Oshman, Rotem |
| contents | In this paper we study a quantum version of the multiparty simultaneous message-passing (SMP) model, and we show that in some cases, quantum communication can replace public randomness, even with no entanglement between the parties. This was already known for two players, but not for more than two players, and indeed, so far all that was known was a negative result. Our main technical contribution is a compiler that takes any classical public-coin simultaneous protocol based on "modified equality queries," and converts it into a quantum simultaneous protocol without public coins with roughly the same communication complexity. We then use our compiler to derive protocols for several problems, including frequency moments, neighborhood diversity, enumeration of isolated cliques, and more. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_08091 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum Simultaneous Protocols without Public Coins using Modified Equality Queries Gall, François Le Nadler, Oran Nishimura, Harumichi Oshman, Rotem Quantum Physics Distributed, Parallel, and Cluster Computing In this paper we study a quantum version of the multiparty simultaneous message-passing (SMP) model, and we show that in some cases, quantum communication can replace public randomness, even with no entanglement between the parties. This was already known for two players, but not for more than two players, and indeed, so far all that was known was a negative result. Our main technical contribution is a compiler that takes any classical public-coin simultaneous protocol based on "modified equality queries," and converts it into a quantum simultaneous protocol without public coins with roughly the same communication complexity. We then use our compiler to derive protocols for several problems, including frequency moments, neighborhood diversity, enumeration of isolated cliques, and more. |
| title | Quantum Simultaneous Protocols without Public Coins using Modified Equality Queries |
| topic | Quantum Physics Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2412.08091 |