Reproduce “Optimal and Verifiable Quantum Advantages in Communication Complexity” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Ryan Anselm, Michelle Ding, Dar Gilboa, Sabee Grewal
The authors establish exponential quantum–classical communication separations for total search tasks, where each answer can be checked on its input. Pelagic Fourier Fishing achieves quantum success of at least 3/4 and requires Ω(2ⁿ) classical bits even with two-way communication, but lacks efficient verification. Its affine variant is efficiently verifiable and requires Ω(2ⁿ) bits only for randomized one-way classical communication, on average over uniform inputs.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.