Abstract

Probability distributions and quantum states are examples of abstract “distributions” over information such as bit-strings, in which more than one bit-string may be a possible outcome. Probability distributions are vectors of non-negative reals; quantum states are vectors of complex-valued amplitudes, which may interfere destructively. To investigate the importance of destructive interference of “possibilities” independently of quantum mechanics, we consider the power of computational models where the states are vectors over some other rings, such as finite fields or the integers modulo k, as in Schumacher and Westmoreland’s “modal quantum theory”. We find that, whether one allows invertible transformations or restricts to transformations which are “convex” or “unitary”, the boolean functions which such models can efficiently compute form powerful classes which are well-known from traditional counting complexity (e.g. Parity-P). We close by considering how these results might inform the theory of exact quantum computation.