Nondeterministic Quantum Query and Quantum Communication Complexities
<|reference_start|>Nondeterministic Quantum Query and Quantum Communication Complexities: We study nondeterministic quantum algorithms for Boolean functions f. Such algorithms have positive acceptance probability on input x iff f(x)=1. In the setting of query complexity, we show that the nondeterministic quantum complexity of a Boolean function is equal to its ``nondeterministic polynomial'' degree. We also prove a quantum-vs-classical gap of 1 vs n for nondeterministic query complexity for a total function. In the setting of communication complexity, we show that the nondeterministic quantum complexity of a two-party function is equal to the logarithm of the rank of a nondeterministic version of the communication matrix. This implies that the quantum communication complexities of the equality and disjointness functions are n+1 if we do not allow any error probability. We also exhibit a total function in which the nondeterministic quantum communication complexity is exponentially smaller than its classical counterpart.<|reference_end|>
@article{de wolf2000nondeterministic,
    title={Nondeterministic Quantum Query and Quantum Communication Complexities},
    author={Ronald de Wolf (CWI Amsterdam)},
    journal={SIAM Journal on Computing, 32(3):681-699, 2003},
    year={2000},
    archivePrefix={arXiv},
    eprint={cs/0001014},
    primaryClass={cs.CC quant-ph}
}