Reproduce “BQP^cc is not contained in MA^cc” 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
Dmytro Gavinsky
The authors show that the complement of Cheat-Shape has polylogarithmic quantum communication but remains hard for public-coin Merlin–Arthur communication. Each party holds N_n input bits, and the classical cost counts both Merlin’s proof and verifier communication. For worst-case error at most 1/3, a rectangle-based argument gives an Ω(N_n^{1/12}/log^{1/6}N_n) lower bound, versus O(log^3 N_n) quantum communication, for this family.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.