On computing with 'probabilities' modulo k

Add to your list(s) Download to your calendar using vCal

• Niel de Beaudrap (University of Oxford)
• Thursday 28 May 2015, 14:00-15:00
• MR14, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.

If you have a question about this talk, please contact William Matthews.

Note unusual time

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.

This talk is part of the CQIF Seminar series.

This talk is included in these lists:

• All CMS events
• CMS Events
• CQIF Seminar
• DAMTP info aggregator
• Hanchen DaDaDash
• Interested Talks
• MR14, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
• bld31

Note that ex-directory lists are not shown.