Optimal and Verifiable Quantum Advantages in Communication Complexity

Ryan Anselm, Michelle Ding, Dar Gilboa, Sabee Grewal

arXivarxiv/2610.05585Oct 4, 2026quant-phscore 0

We establish optimal quantum-classical separations in communication complexity for search problems. We introduce a total search problem called Pelagic Fourier Fishing and show that it admits an $n$-qubit quantum one-way protocol, whereas every randomized two-way protocol requires $Ω(2^n)$ bits of communication. We then introduce a variant of this problem whose solutions can be verified in polynomial time. This variant also admits an $n$-qubit quantum one-way protocol, while every randomized one-way protocol requires $Ω(2^n)$ bits of communication. We also construct a family of efficiently…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2610.05585
curl -X POST /api/v1/records/arxiv/2610.05585/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.05585/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'