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.
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.
The discussion of different principles of additivity (finite vs. countable vs. complete additivity) for probability functions has been largely focused on the personalist interpretation of probability. Very little attention has been given to additivity principles for physical probabilities. The form of additivity for quantum probabilities is determined by the algebra of observables that characterize a physical system and the type of quantum state that is realizable and preparable for that system. We assess arguments designed to show that only normal quantum states are realizable and preparable and, therefore, quantum probabilities satisfy the principle of complete additivity. We underscore the little remarked fact that unless the dimension of the Hilbert space is incredibly large, complete additivity in ordinary non-relativistic quantum mechanics (but not in relativistic quantum field theory) reduces to countable additivity. We then turn to ways in which knowledge of quantum probabilities may constrain rational credence about quantum events and, thereby, constrain the additivity principle satisfied by rational credence functions.