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.
We present several new examples of speed-ups obtainable by quantum algorithms in the context of property testing. First, motivated by sampling algorithms, we consider probability distributions given in the form of an oracle f:[n]→[m]. Here the probability $\PP_f(j)$ of an outcome j∈[m] is the fraction of its domain that f maps to j. We give quantum algorithms for testing whether two such distributions are identical or ε-far in L1-norm. Recently, Bravyi, Hassidim, and Harrow \cite{BHH10} showed that if $\PP_f$ and $\PP_g$ are both unknown (i.e., given by oracles f and g), then this testing can be done in roughly m quantum queries to the functions. We consider the case where the second distribution is known, and show that testing can be done with roughly m1/3 quantum queries, which we prove to be essentially optimal. In contrast, it is known that classical testing algorithms need about m2/3 queries in the unknown-unknown case and about m queries in the known-unknown case. Based on this result, we also reduce the query complexity of graph isomorphism testers with quantum oracle access. While those examples provide polynomial quantum speed-ups, our third example gives a much larger improvement (constant quantum queries vs polynomial classical queries) for the problem of testing periodicity, based on Shor's algorithm and a modification of a classical lower bound by Lachish and Newman \cite{lachish&newman:periodicity}. This provides an alternative to a recent constant-vs-polynomial speed-up due to Aaronson \cite{aaronson:bqpph}.