Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-172 | 5th November 2024 19:54

Quantum Communication Advantage in TFNP

RSS-Feed




TR24-172
Authors: Mika Göös, Tom Gur, Siddhartha Jain, Jiawei Li
Publication: 7th November 2024 15:40
Downloads: 82
Keywords: 


Abstract:

We exhibit a total search problem whose communication complexity in the quantum SMP (simultaneous message passing) model is exponentially smaller than in the classical two-way randomized model. Moreover, the quantum protocol is computationally efficient and its solutions are classically verifiable, that is, the problem lies in the communication analogue of the class TFNP. Our problem is a bipartite version of a query complexity problem recently introduced by Yamakawa and Zhandry (JACM 2024). We prove the classical lower bound using the structure-vs-randomness paradigm for analyzing communication
protocols.



ISSN 1433-8092 | Imprint