Nondeterministic quantum query and . . .

We study nondeterministic quantum algorithms for Boolean functions f. Such algorithms have positive acceptance probability on input x i f(x) = 1. In the setting of query omplexity, we show that the nondeterministic quantum complexity of a Boolean function is equal to its \nondeterministi\ud polynomial " degree. We also prove a quantum-vs.-\ud lassi\ud al gap of 1 vs. n for nondeterministi query \ud omplexity for a total fun\ud tion. In the setting of \ud ommuni\ud ation \ud omplexity, we show that the nondeterministi\ud quantum \ud omplexity of a two-party fun\ud tion is equal to the logarithm of the rank of a nondeterministi\ud version of the \ud ommuni\ud ation matrix. This implies that the quantum \ud ommuni\ud ation \ud omplexities of the equality and disjointness fun\ud tions 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