BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:On computing with 'probabilities' modulo k - Niel de Beaudrap (Uni
 versity of Oxford)
DTSTART:20150528T130000Z
DTEND:20150528T140000Z
UID:TALK59639@talks.cam.ac.uk
CONTACT:William Matthews
DESCRIPTION:Probability distributions and quantum states are examples of a
 bstract "distributions" over information such as bit-strings\, in which mo
 re than one bit-string may be a possible outcome. Probability distribution
 s are vectors of non-negative reals\; quantum states are vectors of comple
 x-valued amplitudes\, which may interfere destructively. To investigate th
 e 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 t
 he integers modulo k\, as in Schumacher and Westmoreland's "modal quantum 
 theory". We find that\, whether one allows invertible transformations or r
 estricts 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 exac
 t quantum computation.
LOCATION:MR14\,  Centre for Mathematical Sciences\, Wilberforce Road\, Cam
 bridge
END:VEVENT
END:VCALENDAR