Quantum Communication Advantage in TFNP

Mika Göös, Tom Gur, Siddhartha Jain +1

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-w…