Quantum Simultaneous Protocols without Public Coins using Modified Equality Queries

Autor:	Gall, François Le, Nadler, Oran, Nishimura, Harumichi, Oshman, Rotem
Rok vydání:	2024
Předmět:	Quantum Physics Computer Science - Distributed Parallel and Cluster Computing
Druh dokumentu:	Working Paper
Popis:	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. Comment: 20 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2412.08091 Zobrazit plný text záznamu View this record from Arxiv