Niel de Beaudrap, IQC
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.