  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.
