Quantum Weakly Nondeterministic Communication Complexity
<|reference_start|>Quantum Weakly Nondeterministic Communication Complexity: 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.<|reference_end|>
@article{gall2005quantum,
    title={Quantum Weakly Nondeterministic Communication Complexity},
    author={Francois Le Gall},
    journal={Theoretical Computer Science, Vol. 486, pp. 43-49, 2013},
    year={2005},
    doi={10.1016/j.tcs.2012.12.015},
    archivePrefix={arXiv},
    eprint={quant-ph/0511025},
    primaryClass={quant-ph cs.CC}
}