Quantum Communication Advantage in TFNP

Mika Göös; Tom Gur; Siddhartha Jain; Jiawei Li

doi:10.1145/3717823.3718155

STOC2025顶会

Quantum Communication Advantage in TFNP

Mika Göös, Tom Gur, Siddhartha Jain, Jiawei Li

arXiv DOI 出版方

2025年份

3顶会引用

摘要

We exhibit a total search problem with classically verifiable solutions whose communication complexity in the quantum SMP model is exponentially smaller than in the classical two-way randomized model. 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.