Quantum Weakly Nondeterministic Communication Complexity
arXiv:quant-ph/0511025 · doi:10.1016/j.tcs.2012.12.015
Abstract
We study the weakest model of quantum nondeterminism in which a classical proof has to be checked with probability one by a quantum protocol. We show the first separation between classical nondeterministic communication complexity and this model of quantum nondeterministic communication complexity for a total function. This separation is quadratic.
12 pages. v3: minor corrections